Новая количественная мера разделения и проникновения между выпуклыми примитивами и облаком точек или треугольной сетью

В статье предложен новый эффективный метод количественной оценки разделения и проникновения между набором выпуклых примитивов (включая эллипсоиды, капсулы, цилиндры, выпуклые многогранники и треугольники) и облаком точек или треугольной сетью. Во-первых, вводится минимальный коэффициент масштабирования выпуклого примитива относительно его центра масс до касания точки или треугольника в качестве новой метрики расстояния; этот коэффициент может быть больше, равен или меньше единицы, что указывает на то, что точка или треугольник отделены от примитива, только касаются его или проникают в него. Его можно вычислять в основном в закрытой форме или иногда с помощью одномерного градиентного спуска, что гораздо быстрее, чем вычисление эвклидова расстояния. Более того, предложен эффективный алгоритм для вычисления наименьшего такого минимального коэффициента масштабирования для примитивов в наборе относительно облака точек или треугольной сети. Алгоритм основывается на наблюдении, что вычисление минимального коэффициента масштабирования для примитива относительно точки или треугольника порождает плоскость, отделяющую больше точек или треугольников от этого или других выпуклых примитивов. Следовательно, общий наименьший коэффициент масштабирования можно найти, проверяя лишь несколько пар примитивов и точек или треугольников, что делает метод значительно быстрее исчерпывающего поиска. В различных численных примерах и при сравнении с существующими алгоритмами предложенная метрика и алгоритм демонстрируют превосходную или сопоставимую эффективность.