Принадлежность точки любому многоугольнику

#алгоритм #cpp

Не подскажите нормальный алгоритм определения принадлежности точки многоугольнику
на С++    

Ответы

Ответ 1

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


Ответ 2

В случае выпуклого многоугольника без "дырок" внутри алгоритм будет такой:

Подсчитать площадь многоугольника - допустим SM
Соединить точку со всеми вершинами многоугольника - в итоге получится N треугольников
с основаниями сторон многоугольника и вершиной в нашей точке
Подсчитать сумму площадей полученных треугольников - допустим SN
Если SN > SM - значит точка лежит за пределами многоугольника, иначе внутри.


Ответ 3

Все необходимые инструменты (классы) для решения этой задачи находятся тут http://algolist.manual.ru/maths/geom/belong/poly2d.php 
Именно функция pointInPolygon проверять находиться ли точка в пределах многоугольники,
но в качестве аргумента она должна получить объекты класса Point и Polygon, которые
тебе надо взять отсюда http://algolist.manual.ru/maths/geom/datastruct.php