|
Находится ли точка в многоугольнике?
Дан многоугольник и точка.
Необходимо проверить, располагается ли наша точка внутри многоугольника.
Если провести горизонтальную прямую проходящую через заданную точку, то могут возникнуть пересечения прямой с многоугольником. Рассмотрим все точки пересечения, у которых абсцисса меньше, чем у заданной точки. Если этих точек нечётное число, то исходная точка лежит внутри многоугольника, иначе нет.
Асимптотика O(n).
Листинг C++
bool point_in_polygon (point t, vector < point > p)
{
int i, j;
int count = 0;
for (i = 0; i < p.size(); ++ i)
{
j = (i + 1) % p.size();
if (min (p[i].y, p[j].y) < t.y && t.y <= max (p[i].y, p[j].y) &&
ccw (min_py (p[i], p[j]), max_py (p[i], p[j]), t))
{
// если проекция точки лежит на отрезке и точка находится справа от отрезка
// то увеличиваем количество "вхождений" точки в многоугольник
++ count;
}
}
return count % 2;
}
25.06.2007, 17:20
По всем вопросам обращаться: rumterg@gmail.com