Допустим есть многоугольник из 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
Третья строка формирует отрицательный ответ при чётном количестве сторон слева и положительный — при нечётном.
Комментариев нет:
Отправить комментарий