Physics - Game Programming Algorithms and Techniques - page 168

malize the result of and dot it with the normal, if it's positive, then P is

on the interior of .
This algorithm can then be applied to all the other sides of the triangle. It turns out
that this works not only for triangles, but for any convex polygon that lies on a
single plane. The pseudocode for this is provided in Listing 7.4 .

Listing 7.4 Determining Whether a Point Is Inside a Convex Polygon

Click here to view code image

// This function only works if the vertices are
provided in a
// clockwise winding order and are coplanar.
function PointInPolygon( Vector3 [] verts , int
numSides ,

Vector3 point )
// Calculate the normal of the polygon
Vector3 normal = CrossProduct( Vector3 ( verts [1] -
verts [0]),

Vector3 ( verts [2] -

verts [1])
normal .Normalize()

// Temporary variables
Vector3 side , to , cross

for int i = 1, i < numSides , i ++
// FROM previous vertex TO current vertex
side = verts [ i ] - verts [ i - 1]
// FROM previous vertex TO point
to = point - verts [ i - 1]

cross = CrossProduct( side , to )
cross .Normalize()

// This means it's outside the polygon
if DotProduct( cross , normal ) < 0