Определение, существует ли координата в полигоне
Я работаю над отслеживанием с открытым исходным кодом и приложением геозабора и испытываю немного затруднений при выяснении математики для геозонирования.
Я должен определить, существует ли координата в полигоне. Однако хитрая часть - то, что полигон не имеет никакого определенного номера сторон. Я должен смочь вычислить для пятидесяти сторон или для пяти сторон.
Мое исследование говорит, что самый легкий путь состоит в том, чтобы взять мою точку (который я назову x), и точка вне полигона (назовите это y), и определите, пересекается ли строка ((xx, xy), (yx, yy)) с границами полигона. Если это пересекает нечетное количество раз, точка x должна быть в полигоне.
Зная это, однако, я не могу выяснить, как выразить это в алгоритме.. Я, очевидно, должен буду циклично выполниться через различные строки, создающие полигон, но проверка, которую я делаю, ускользает от меня. Кто-либо может быть полезным? Знайте, что я не прошу решение обязательно. Что-либо, что поможет мне изобразить его ответ, является огромной справкой.
Очень ценивший.
5 ответов
См. здесь
в основном есть Подход (я думаю, что его теорема кривой Джордана), которая подсчитывает количество раз, что Рэй пересекает сегменты линии, составляющие многоугольник. Если результат даже тогда точка находится за пределами многоугольника, в противном случае точка лежит внутри полигона.
HTH
Редактировать Есть еще один настолько вопрос, касающийся этого вопроса, который можно найти здесь
Я предположу, что вы находитесь в (2D) плоскости.
- Вычисляют наклоны каждой стороны (в некоторой системе координат) и наклон строки от пункта X до пункта Y (строка XY).
- Для всех сторон, где наклон не равняется наклону XY, вычислите точку пересечения.
- Для каждой точки, определите, является ли точкой пересечения на линейном сегменте XY и линейный сегмент, определяющий сторону. Если это, вы пересекли ту сторону. (Проверьте координаты перекрестка и посмотрите, включены ли оба компоненты X и Y в диапазон значений для каждого линейного сегмента.)
- подсчитывают количество пересечений, и у вас есть свой ответ.
Один ключ вот понять, что вы можете выбрать любую точку Y, которое вам нравится. Действительно хороший выбор - это точка (xx, -infinity). Другими словами, точка прямо с точки зрения точки и бесконечно далеко. Теперь возникает вопрос: сколько краев многоугольника пересекают вашу X-координату под точкой под вопросом. Поэтому только линейные сегменты, которые должны быть рассмотрены координаты X координата.
Если ваша точка P = (x, y), и конечные точки сегмента представляют собой P1 = (x1, y1) и p2 = (x2, y2) координата y сегмента, когда он пересекает x, дается SY = (x-x1) * (y2-y1) / (x2-y1) + y1
Проверьте, если SY Существуют тонкие проблемы с этим, когда одна из вершин многоугольника находится в том же положении y, что и рассматриваемая точка. Вы должны быть осторожны по этому делу.
Джастин,
Вам может также понадобиться лучше определить «вне полигона», чтобы построить сегмент.
Возьмите MIN & MAX всех координат X & Y и построить прямоугольник (xmin, ymin), (xmax, ymin), (xmax, ymax), (xmin, ymax). Любая точка за пределами прямоугольника, безусловно, будет за пределами многоугольника, затем продолжайте, поскольку другие показали выше. Каждый сегмент многоугольника и построенная линия определяется уравнением y = ax + b и для каждого сегмента, диапазон XLO и XHI. Ваша построенная линия либо пересекает сегмент в диапазоне или нет. То есть решение двух одновременных уравнений в диапазоне сегмента либо существует, либо нет. Просто подсчитайте количество решений, которые существуют, чтобы получить количество пересечений.