Как быстрее всего найти кратчайшее декартово расстояние между двумя многоугольниками

Я сомневаюсь, что есть лучшее решение, чем вычисление расстояния между красным и каждым синим и сортировка их по длине.

Что касается сортировки, обычно QuickSort трудно превзойти по производительности (оптимизированный, который отключает рекурсию, если размер становится меньше 7 элементов, и переключается на что-то вроде InsertionSort, возможно, ShellSort).

Таким образом, я предполагаю, что вопрос в том, как быстро вычислить расстояние между двумя полигонами, ведь вам нужно сделать это вычисление 50 раз.

Следующий подход будет работать и для 3D, но, вероятно, не самый быстрый:

Минимальное расстояние до многоугольника в 2D-пространстве

Вопрос в том, готовы ли вы променять точность на скорость? Например. вы можете упаковать все полигоны в ограничивающие прямоугольники, где стороны прямоугольников параллельны осям системы координат. В 3D-играх этот подход используется довольно часто. Поэтому вам нужно найти максимальное и минимальное значения для каждой координаты (x, y, z), чтобы построить виртуальную ограничивающую рамку. В таком случае вычисление расстояний до этих ограничивающих рамок является довольно тривиальной задачей.

Вот пример изображения более продвинутых ограничивающих рамок, которые не параллельны осям системы координат:

Ориентированные ограничивающие рамки - OBB

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

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

Ограничивающая рамка с выравниванием осей - AABB

OOB более точны, AABB быстрее. Может быть, вы хотите прочитать эту статью:

Расширенные методы обнаружения столкновений

Это всегда предполагает, что вы готовы торговать точностью на скорость. Если точность важнее скорости, вам может понадобиться более продвинутая техника.

Возможно, вы сможете уменьшить проблему, а затем провести интенсивный поиск на небольшом множестве.

Сначала обработайте каждый многоугольник, найдя:

• Центр многоугольника
• Максимальный радиус многоугольника (т.е. точка на краю / поверхности / вершине многоугольника, наиболее удаленная от заданного центра)

Теперь вы можете собрать, скажем, 5-10 полигонов, ближайших к красному (найти расстояние от центра до центра, вычесть радиус, отсортировать список и взять 5 первых), а затем выполнить гораздо более исчерпывающую процедуру.

Для многоугольников с разумным количеством граничных точек, например, в ГИС или игровом приложении, может быть проще провести серию тестов.

Для каждой вершины в красном многоугольнике вычислите расстояние до каждой вершины в синих многоугольниках и найдите ближайшую (подсказку, сравните расстояние ^ 2, чтобы вам не понадобился sqrt ()) Найдите ближайшую, затем проверьте вершины с каждой стороны найденной красной и синей вершины, чтобы решить, какие линейные сегменты являются ближайшими, а затем найти самый близкий подход между двумя линейными сегментами.

См. http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline3d/ (это просто для 2-го случая)

Этот метод скрининга предназначен для уменьшения количества вычислений расстояний, которые вам необходимо выполнить в среднем случае, без ущерба для точности результата. Работает с выпуклыми и вогнутыми многоугольниками.

Найдите минимальное расстояние между каждой парой вершин, чтобы одна была красной вершиной, а другая - синей. Назовите это r. Расстояние между многоугольниками не превышает r. Постройте новую область из красного многоугольника, где каждый линейный сегмент перемещается наружу на r и соединяется со своими соседями дугой радиуса r с центром в вершине. Найдите расстояние от каждой вершины внутри этой области до каждого отрезка линии противоположного цвета, пересекающего эту область.

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

Может быть, расстояние Фреше - это то, что вы ищете?

Расчет Фреше расстояние между двумя многоугольными кривыми
Вычисление расстояния Фреше между простыми многоугольниками

Я знаю, что вы сказали «кратчайшее расстояние», но на самом деле вы имели в виду оптимальное решение или «хорошее / очень хорошее» решение подходит для вашей проблемы?

Потому что, если вам нужно найти оптимальное решение, вы должны вычислить расстояние между всеми границами вашего исходного и целевого полигонов (а не только вершинами). Если вы находитесь в трехмерном пространстве, то каждая граница - это плоскость. Это может быть большой проблемой (O (n ^ 2)) в зависимости от того, сколько у вас вершин.

Так что, если у вас есть количество вершин, которое приводит к квадрату страшного числа, И вам подходит «хорошее / очень хорошее» решение, используйте эвристическое решение или приближение.

Вы можете посмотреть на Вороного Каллинга. Бумага и видео здесь:

http://www.cs.unc.edu/~geom/DVD/

Я бы начал с ограничения всех полигонов ограничивающим кругом, а затем нашел бы верхнюю границу минимального расстояния. Затем я бы просто проверил края всех синих многоугольников, нижняя граница расстояния которых ниже, чем верхняя граница минимального расстояния, по всем краям красного многоугольника.

upper bound of min distance = min {distance(red's center, current blue's center) + current blue's radius}

for every blue polygon where distance(red's center, current blue's center) - current blue's radius < upper bound of min distance
    check distance of edges and vertices

Но все зависит от ваших данных. Если синие многоугольники относительно малы по сравнению с расстояниями между ними и красным многоугольником, тогда этот подход должен работать хорошо, но если они находятся очень близко, вы ничего не сохраните (многие из них будут достаточно близко). И еще одно: если у этих многоугольников не так много вершин (например, если бы большинство из них были треугольниками), то было бы почти так же быстро просто сверять каждое красное ребро с каждым синим ребром.

Надеюсь, это поможет

Как уже упоминалось, использование ограничивающих областей (прямоугольников, кружков) может позволить вам отказаться от некоторых взаимодействий многоугольника с многоугольником. Для этого есть несколько стратегий, например

1. Выберите любой синий многоугольник и найдите расстояние от красного. Теперь выберите любой другой многоугольник. Если минимальное расстояние между ограничивающими областями больше, чем уже найденное расстояние, вы можете игнорировать этот многоугольник. Продолжайте для всех полигонов.
2. Найдите минимальное расстояние / центроидное расстояние между красным многоугольником и всеми синими многоугольниками. Отсортируйте расстояния и сначала рассмотрите наименьшее расстояние. Вычислите фактическое минимальное расстояние и продолжайте просмотр отсортированного списка до тех пор, пока максимальное расстояние между полигонами не станет больше, чем минимальное расстояние, найденное на данный момент.

Ваш выбор окружностей / прямоугольников, выровненных по оси, или ориентированных прямоугольников, может сильно повлиять на производительность алгоритма, в зависимости от фактического расположения входных многоугольников.

Для расчета фактического минимального расстояния вы можете использовать Новый пост Янга и др. алгоритм вычисления расстояния между двумя непересекающимися выпуклыми многоугольниками на основе диаграммы Вороного ', который равен O (log n + log m).

Надо бежать на похороны через секунду, но если вы разбиваете полигоны на выпуклые субполиции, вы можете сделать некоторые оптимизации. Вы можете выполнить двоичный поиск на каждом полигоне, чтобы найти ближайшую вершину, а затем я верю, что ближайшей точкой должна быть либо эта вершина, либо смежное ребро. Это означает, что вы сможете сделать это за log(log m * n), где m - среднее количество вершин на поли, а n - количество полигонов. Это своего рода поспешность, поэтому это может быть неправильно. При желании я предоставлю более подробную информацию позже.

Вы можете начать со сравнения расстояния между ограничивающими рамками. Тестировать расстояние между прямоугольниками проще, чем тестировать расстояние между полигонами, и вы можете немедленно удалить любые полигоны, которые находятся на расстоянии больше, чем near_rect + its_diagonal (возможно, вы можете уточнить это еще больше). Затем вы можете протестировать оставшиеся многоугольники, чтобы найти ближайший многоугольник.

Существуют алгоритмы определения близости полигонов - я уверен, что в Википедии есть их хороший обзор. Если я правильно помню, те, которые допускают только выпуклые многоугольники, значительно быстрее.

Я считаю, что вы ищете алгоритм A *, который используется при поиске пути.

Наивный подход состоит в том, чтобы найти расстояние между красными и 50 синими объектами - так что вы смотрите на 50 трехмерных вычислений Пифагора + сортировку, чтобы найти ответ. Однако это действительно сработает только для определения расстояния между центральными точками.

Если вам нужны произвольные многоугольники, возможно, лучше всего вам подходит решение для трассировки лучей, которое испускает лучи с поверхности красного многоугольника относительно нормали и сообщает о попадании в другой многоугольник.

Гибрид может работать - мы могли бы найти расстояние от центральных точек, предполагая, что у нас есть некоторое представление об относительном размере синих многоугольников, мы могли бы отбраковать результирующий набор до ближайшего из них, а затем использовать трассировку лучей, чтобы сузить истинный размер. ближайший многоугольник.