Graphics Reference
In-Depth Information
V
4
D
V
3
V
5
A
V
2
V
6
P
C
B
V
1
V
7
V
0
Figure 5.28
A binary search over the vertices of the convex polygon allows the containment
test for
P
to be performed in
O
(log
n
) time (here using four sidedness tests,
A
through
D
).
// Test if point p lies inside ccw-specified convex n-gon given by vertices v[]
int PointInConvexPolygon(Point p, int n, Point v[])
{
// Do binary search over polygon vertices to find the fan triangle
// (v[0], v[low], v[high]) the point p lies within the near sides of
int low = 0, high = n;
do {
int mid = (low + high) / 2;
if (TriangleIsCCW(v[0], v[mid], p))
low = mid;
else
high = mid;
} while (low+1<high);
// If point outside last (or first) edge, then it is not inside the n-gon
if (low == 0 || high == n) return 0;
// p is inside the polygon if it is left of
// the directed edge from v[low] to v[high]
return TriangleIsCCW(v[low], v[high], p);
}
