определите, находится ли данная точка внутри полигона

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

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

3 6
computational-geometry

3 ответа:

Единственное известное мне решение этой задачи требует O(n) полигональнойпредварительной обработки времени. После этого каждая точка запроса по отношению к предварительно обработанному полигону обрабатывается за O(lg n) Время.

Просто возьмите точку P внутри многоугольника (назовем ее "полюсом") и для каждой вершины нарисуйте луч, выходящий из P и проходящий через вершину. Рассмотрим это как полярную систему координат с началом координат в точке P, где вся Полярная плоскость разделена этими лучами на сектора. Сейчас, учитывая вашу точку запроса, вам просто нужно преобразовать ее в полярные координаты с началом координат на нашем полюсе P. Затем просто выполните двоичный поиск, чтобы определить конкретный сектор, содержащий точку запроса. Окончательная внутренняя / внешняя проверка внутри сектора (Точка против ребра бокового теста) является тривиальной операцией O(1). Каждый запрос обрабатывается за O(lg n) Время, необходимое для бинарного поиска. Этот подход фактически будет работать с большим классом многоугольников, чем просто выпуклые. Она охватывает классу так называютсязвездообразными многоугольниками, то есть многоугольниками, имеющими точку, из которой вся внутренняя часть многоугольника может быть "видна" или "наблюдаема".

Время предварительной обработки исходит из необходимости заранее определить местоположение полюса.

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

12

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

Http://alienryderflex.com/polygon/

1

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

0