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

Question

У меня есть 1 красный многоугольник скажи и 50 случайно расположенных синих многоугольников - они расположены в географическом 2D пространство.Какой самый быстрый/самый быстрый алгоритм поиска кратчайшего расстояния между красным многоугольником и ближайшим к нему синим многоугольником?

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

Итак, в итоге ответ должен вернуть ближайший синий многоугольник к единственному красному.

Это сложнее, чем кажется!

Answer 1

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

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

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

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

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

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

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

Ориентированные ограничивающие рамки — КЭШ

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

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

Ограничительная рамка с выравниванием по осям — AABB

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

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

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

Answer 2

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

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

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

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

Answer 3

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

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

Видеть http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline3d/ (это легко просто для 2d случая)

Answer 4

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

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

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

Answer 5

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

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

Answer 6

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

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

Итак, если у вас есть количество вершин, которое превращает это число в квадрат, И «хорошее/очень хорошее» решение вам подходит, выберите эвристическое решение или аппроксимацию.

Answer 7

Возможно, вам захочется взглянуть на Вороного Каллинга.Бумага и видео здесь:

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

Answer 8

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

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

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

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

Answer 9

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

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

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

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

Answer 10

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

Answer 11

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

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

Answer 12

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

Answer 13

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

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

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