Точка внутри многоугольника

#cpp #c #алгоритм

Допустим есть многоугольник из N (и это главное) вершин. И есть точка в произвольном
месте. Необходимо определить принадлежит она ему или нет. Точки представлены в виде
структуры:

struct point{ unsigned int x; unsigned int y;};


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

Я остановился на идеи подсчитать сколько сторон луч выпущенный из точки пройдет.
если четное число - не в многоугольнике. если не четное - в многоугольнике. То есть
нам надо указывать вершины по часовой стрелке. Сделать структуру сторон. Но как проверять?
Как расчитать эти стороны и сделать пересечение?
    

Ответы

Ответ 1

Плохо ищете.

bool result = false;
int j = size - 1;
for (int i = 0; i < size; i++) {
    if ( (p[i].Y < point.Y && p[j].Y >= point.Y || p[j].Y < point.Y && p[i].Y >=
point.Y) &&
         (p[i].X + (point.Y - p[i].Y) / (p[j].Y - p[i].Y) * (p[j].X - p[i].X) < point.X) )
        result = !result;
    j = i;
}



p - список точек
size - количество точек
result - входит ли точка в многоугольник


Первая строка условия проверяет попадание point.Y между значениями p[i].Y и p[j].Y,
контролирует направление прохода вершины и обеспечивает ненулевой знаменатель основной
формулы.

Вторая строка проверяет нахождение стороны p[i]p[j] слева от точки point.

Третья строка формирует отрицательный ответ при чётном количестве сторон слева и
положительный — при нечётном.


Ответ 2

Пусть луч направлен горизонтально вправо.

Для каждой пары смежных точек:


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


Нужно учитывать специальный случай, когда луч проходит через вершину многоугольника:


Если вторые точки обоих отрезков, которым принадлежит данная вершина находятся по
одну сторону от луча, то считать это двумя пересечениями (или отсутствием пресечения
- четность будет та же)
Если вторые точки по разные стороны луча - считать одним пересечением.


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