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

Ответ 1

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

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

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

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

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

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

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

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

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

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

Осевые выровненные рамки - AABB

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

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

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

Ответ 2

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

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

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

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

Ответ 3

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

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

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

Ответ 4

Может быть, Frechet Distance - это то, что вы ищете?

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

Ответ 5

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

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

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

Ответ 6

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

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

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

Ответ 7

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

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

Ответ 8

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

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

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

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

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

Ответ 9

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

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

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

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

Ответ 10

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

Ответ 11

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

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

Ответ 12

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

Ответ 13

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

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

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