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

Я реализовал алгоритм "точка в многоугольнике" на основе http://alienryderflex.com/polygon/.

Работает нормально, но как написано в статье:

Если контрольная точка находится на границе полигона, этот алгоритм даст непредсказуемые результаты.

Оказывается, мне нужно, чтобы алгоритм возвращал true, когда контрольная точка находится на границе/ребре (и вершинах) многоугольника.

Есть ли:

  • Альтернативный алгоритм, который мне поможет; или
  • Способ изменить этот алгоритм, чтобы получить то, что я хочу (например, немного расширив полигон перед запуском алгоритма)

algorithm polygon point-in-polygon
person James Bateson    schedule 04.03.2016    source источник
comment
Алгоритм работает с числами с плавающей запятой, поэтому в целом понятие «на краю» сложнее, чем может показаться. См., например, Что каждый программист должен знать об арифметике с плавающей запятой и Примеры решения задач устойчивости в геометрических вычислениях в классе.   -  person Vincent van der Weele    schedule 04.03.2016
comment
В любом случае вы можете реализовать предварительную проверку для интересующей вас ситуации. т.е. вернуть true, если точка находится в пределах эпсилон края многоугольника. Если ваши координаты являются целыми числами, вы можете сделать это даже с эпсилон = 0. Но алгоритм может вернуть true даже для точек, которые находятся за пределами многоугольника с расстоянием эпсилон, потому что он, вероятно, работает с числами с плавающей запятой.   -  person Niklas B.    schedule 04.03.2016

Ответы (1)


arrow_upward
2
arrow_downward

Можно немного расширить полигон, но это может быть сложно с вогнутыми полигонами.

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

Другой вариант — позволить линии, на которой подсчитываются пересечения, проходить в разных направлениях, а не только по горизонтали.

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

person Frank Puffer    schedule 04.03.2016