Алгоритм, определяющий, находится ли точка внутри простого многоугольника (такого, который не пересекается сам с собой), можно объяснить так: пусть из точки исходит луч в горизонтальном направлении. Если луч пересекает сторону многоугольника один раз, значит, точка расположена внутри многоугольника. Если луч не пересекает сторон многоугольника или пересекает две стороны, значит, точка расположена вне многоугольника. Случай, когда точка лежит на горизонтальной стороне, обрабатывается отдельно. Функция PointInPoly1 реализует этот алгоритм.
typedef struct {int x, y;} CPoint;
/* Функция PointInPoly2, определяет, принадлежит ли точка простому многоугольнику.
p - точка, poly - набор вершин многоугольника, n - число вершин.
Возвращает 1, если точка расположена внутри многоугольника, 0 - в противном случае. */
int PointInPoly1( CPoint p, CPoint* poly, int n )
{
int cn = 0;
for (int i=0; i p.y)) || ((poly[i].y > p.y) && (poly[i+1].y <= p.y))) {
float vt = (float)(p.y - poly[i].y) / (poly[i+1].y - poly[i].y);
if (p.x < poly[i].x + vt * (poly[i+1].x - poly[i].x))
++cn;
}
}
return (cn&1);
}
Как определить, находится ли точка внутри многоугольника, который пересекается сам с собой? Первый алгоритм в этом случае сработает для точки A, но не для точки B, так как для B любой горизонтальный луч пересечет границу многоугольника 2 раза. Для этого воспользуемся алгоритмом, показанным ниже. Этот алгоритм можно объяснить так: пусть точка принадлежит многоугольнику (и не лежит на горизонтальном ребре). Если обход многоугольника выполняется в определенном порядке, луч, исходящий из этой точки, пересечет n сторон многоугольника, при этом число пересеченных сторон, которые при обходе проходятся сверху вниз, будет неравно числу сторон, которые проходятся снизу вверх. Если же точка не принадлежит многоугольнику, то луч либо вообще не пересечет стороны многоугольника, либо число сторон, которые при обходе проходятся сверху вниз, будет равно числу сторон, которые проходятся снизу вверх.
int isLeft( CPoint p0, CPoint p1, CPoint p2 )
{
return ( (p1.x - p0.x) * (p2.y - p0.y)
- (p2.x - p0.x) * (p1.y - p0.y) );
}
/* Функция PointInPoly2, определяет, принадлежит ли точка многоугольнику.
p - точка, poly - набор вершин многоугольника, n - число вершин.
Возвращает n > 0, если точка расположена внутри многоугольника, 0 - в противном случае. */
int PointInPoly2( CPoint p, CPoint* poly, int n )
{
int wn = 0;
for (int i=0; i p.y)
if (isLeft( poly[i], poly[i+1], p) > 0)
++wn;
}
else {
if (poly[i+1].y <= p.y)
if (isLeft( poly[i], poly[i+1], p) < 0)
--wn;
}
}
return wn;
}