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

Question

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

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

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

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

Answer 1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Answer 2

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

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

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

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

Answer 3

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

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

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

Answer 4

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

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

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

Answer 5

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

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

Answer 6

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

Answer 7

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

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

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

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

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

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

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

Answer 10

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

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

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