by Ostsol » Sat Jan 17, 2009 6:31 pm
Assume you have a rectangle defined in a clockwise manner with points a, b, c, and d. Point a is at the upper left. This gives you four edges, which we will lable ab, bc, cd, and da. If we drew this on a sheet of paper and and looked at the top edge, ab, anything above the edge is obviously outside the rectangle and a point below might be inside the rectangle. Rotate the paper such that edge bc is horizontal, with point b being to the left of point c. Once again, anything above that edge is always outside the rectangle and a point below the edge might be inside. Rotate the paper again such that cd is horizontal, with point c left of d. The same above/below rules will apply. Thus, a point can only be inside the rectangle if it is "below" all edges.
Here's some pseudo-code to tell you if a point is "above" or "below" a line:
e1 = p2 - p1
e2 = point - p2
e = e1.x * e2.y - e1.y * e2.x
if e > 0 then above
if e < 0 then below
if e == 0 then on_line
"p1" and "p2" are the two points (as 2d vectors) of the edge being tested. "point" is the point being tested.
This works on any convex polygon as long as the points are arranged in a clockwise manner. A polygon that is not fully convex must be divided into convex polygons.