Point in polygon or “hit test”

The problem is to decide whether point p(x, y) is inside polygon polygon [(x1,y1), (x2,y2), …]

First check the bounding box (for perf optimization). If x,y are even bigger than xmax or ymax, it’s outside

When it’s convex polygon, you can check whether point is on same side of all edges, by checking the angle PAB, PBC, PCD… They must all be < 180 degrees.

More general approach is the ray casting method. Take a point from outiside polygon Q, count how many edges QP crosses. It should be odd if inside, even if outside.

Then, how to check whether QP crosses all the edges? Check edges one by one, find the linear formula of the edges, substitute Q and P coordinates. If same sign, on same side

Written on September 18, 2017