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

Question

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

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

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

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

Answer 1

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

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

Answer 2

Если точки могут падать только на ребра, то вы можете найти многоугольники в O (n), просто исследовав ребра.

Если бы это было иначе, вам пришлось бы триангулировать многоугольники в O (n log n) для проверки на треугольники в O (n).

Вы также можете разделить пространство на линию, проходящую от каждого сегмента, отметив, какая сторона находится внутри / снаружи соответствующего многоугольника. Точка находится внутри многоугольника, если она падает на ребро или если она находится на внутренней части каждого ребра многоугольника. Это O (n) для числа ребер в худшем случае, но стремится к O (m) для числа многоугольников в среднем случае.

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

Answer 3

Я думаю, что вы сталкиваетесь с интуицией о проблеме (которая является квазианалоговым восприятием) по сравнению с вычислительным подходом, который необходим O (n).

При заданной плоскости вырожденный многоугольник (линия) и произвольный набор точек на плоскости, точки пересекают линию или падают «выше» или «ниже» ее?Я не могу думать о подходе, который меньше, чем O (n), даже для этого вырожденного случая.

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

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