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

Question

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

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

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

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

Answer 1

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

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

Answer 2

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

Answer 3

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

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

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