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

Настройка

Функция должна обеспечить расстояние от точки до ближайшего края многоугольника
Известно, что точка внутри многоугольника
Многоугольник может быть выпуклым или вогнутым
Необходимо проверить многие моменты (миллионы).
Множество отдельных многоугольников (десятков) должно выполняться через функцию на точку
Предварительно рассчитанные и постоянно сохраняемые структуры данных являются опцией.
Последняя функция поиска будет в С++

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

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

Я нашел ссылку для хранения сегментов линии в квадранте, что обеспечило бы очень быстрый поиск, и я думаю, что его можно было использовать для моей цели, чтобы быстро сузить, какой сегмент смотреть как самый близкий сегмент, а затем нужно только вычислить расстояние до одного сегмента линии. https://people.cs.vt.edu/~shaffer/Papers/SametCVPR85.pdf

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

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

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

http://www.codeproject.com/Articles/30535/A-Simple-QuadTree-Implementation-in-C

https://github.com/Esri/geometry-api-java/blob/master/src/main/java/com/esri/core/geometry/QuadTree.java

Мой реальный вопрос был бы, похоже ли это, как звуковой подход для быстрой функции поиска времени?

Есть ли что-то, что будет работать быстрее?

EDIT: Я искал вокруг и нашел некоторые проблемы с использованием quadtree. Способ работы квадрантов хорош для обнаружения конфликтов, но не настроен для эффективного поиска ближайших соседей. https://gamedev.stackexchange.com/info/14373/in-2d-how-do-i-efficiently-find-the-nearest-object-to-a-point

R-деревья выглядят лучше. https://en.wikipedia.org/wiki/R-tree

эффективный способ обработки сегментов 2-й линии

На основе этих сообщений R-деревья выглядят как победитель. Также удобно видеть, что С++ Boost уже реализовал их. Это выглядит достаточно близко к тому, что я планировал сделать, и я продолжу его реализацию и проведу результаты.

Ответ 1

EDIT: Поскольку я реализовал квадрант PMR, теперь я вижу, что поиск ближайшего соседа немного сложнее, чем я описывал. Если результат поиска в четырех точках поиска будет пустым, тогда он станет более сложным. Я помню описание где-то в Hannan Sammets: Многомерная структура поиска. Давая ответ ниже, я имел в виду поиск всех объектов с заданным расстоянием. Это легко для квадрантов PMR, но просто найти ближайший является более сложным. Изменить конец

Я бы не использовал R-Tree.
Слабой точкой (и сильной точкой!) На R-деревьях является разделение пространства на прямоугольники. Существует три алгоритма, которые делают это разделение, но ни один из них не подходит для всех ситуаций. R-деревья действительно сложны для реализации. Зачем же тогда? Просто потому, что R-деревья могут быть в два раза быстрее, чем квадровое дерево, когда они прекрасно реализованы. Разница в скорости между квадрантом и R-деревом не имеет значения. Денежная разница. (Если у вас есть рабочий код для обоих, я бы использовал квадрант PMR, если у вас есть только код для R-Tree, тогда используйте его, если вы не используете PMR Quadtree)

Квадратные деревья (PMR) всегда работают, и их просто реализовать.

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

Люди, которые рассказывают о квадроциклах, не подходят или соседний поиск, не знаю, что есть сотни различных квадратов. Непригодность верна только для дерева с четырьмя точками, а не для PMR, которое хранит ограничивающие прямоугольники.

Я однажды вспомнил compelx описание нахождения соседних точек в POINT-Quadtree. Для PMR-quadtree мне нечего было делать (для поиска в указанном прямоугольном интервале), без изменения кода, просто повторите результат и найдите ближайший.

Я думаю, что есть даже лучшие решения, чем Quad tree или R-Tree для ваших специальных вопросов, но дело в том, что PMR всегда работает. Просто реализуйте его один раз и используйте, если для всех пространственных запросов.

Ответ 2

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

Рассмотрим такой подход (предполагается, что многоугольники не имеют отверстий):

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

Эта диаграмма должна иллюстрировать концепцию. Синие линии определяют полигон, а красные линии - эквидистантные линии.

Обратите внимание, что необходимость поддержки вогнутых многоугольников значительно увеличивает сложность, как показано в области 6-7-8. Вогнутые области означают, что сегменты линии, которые простираются до бесконечности, могут быть определены вершинами, которые сколь угодно далеко друг от друга.

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

Ответ 3

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

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