Страницы

Поиск по вопросам

среда, 31 октября 2018 г.

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

Допустим есть многоугольник из N (и это главное) вершин. И есть точка в произвольном месте. Необходимо определить принадлежит она ему или нет. Точки представлены в виде структуры:
struct point{ unsigned int x; unsigned int y;};
Все решения и алгоритмы которые я находил были написаны для четырехугольников и для треугольников. Главное уточнение многоугольник может быть выпуклый и не выпуклый.
Я остановился на идеи подсчитать сколько сторон луч выпущенный из точки пройдет. если четное число - не в многоугольнике. если не четное - в многоугольнике. То есть нам надо указывать вершины по часовой стрелке. Сделать структуру сторон. Но как проверять? Как расчитать эти стороны и сделать пересечение?


Ответ

Плохо ищете.
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
Третья строка формирует отрицательный ответ при чётном количестве сторон слева и положительный — при нечётном.

Комментариев нет:

Отправить комментарий