The Inside or Outside Problem
A calculation that must be performed billions of times in every movie that uses computer graphics
is to check if one object is hidden by another object in front of it. This calculation in turn
is based on another calculation that checks whether or not a test point lies inside or outside
the boundary of an object.
For example, can you tell which of these points:
A=(22, 15), B=(40,17) or C=(8, 16) ?
lies inside the polygon whose vertices (given in counter-clockwise order) are at (x, y) coordinates:
Unfortunately this is the form in which polygons are represented in the computer's memory and it
isn't easy to tell.
The picture to the right shows the points and the polygon. Now it is obvious: C and A are inside,
B is outside.
The standard method of checking whether a test point is inside or outside the boundary of an object is this:
- Draw a ray (line) from the test point out to infinity in any direction. (In the picture we
have drawn the lines straight up.)
- Count the number of times the ray crosses the boundary of the object.
- If it crosses an odd number of times (1, 3, 5, etc.) then the test point is inside the object.
If it crosses an even number of times (0, 2, 4, etc.) then the test point is outside.
In the picture above, the rays from A and C cross once and the ray from B crosses twice so A and C
are inside and B is outside the polygon.
The picture to the right shows a more complicated object. This time the ray from C crosses 3 times
and the ray from B crosses twice, so C is inside and B is outside the object. (If point B was
behind the object it still would not be hidden. It would show through the hole.)
Algorithm to test whether a point A is inside or outside a polygon:
- Set the number of crossings found to zero.
- Look at each of the edges of the polygon in turn and do the following tests in turn.
(The picture below shows five edges (blue) of a polygon in various relationships with the
test point A and the ray from A to infinity (red) to illustrate.):
- If both endpoints of the edge are to the left of the test point (edge 1) then do nothing;
go to the next edge.
- If both endpoints of the edge are to the right of the test point (edge 2) then do nothing.
- If both endpoints of the edge are below the test point (edge 3) then do nothing.
- If both endpoints of the edge are above the test point, then if one endpoint is to the left
of the test point and the other is to the right (edge 4), then add 1 to the number of crossings found;
proceed to the next edge.
- If a "bounding box" for the edge encloses the test point (edge 5 above and the magnified
picture to the right)) then do the following calculation:
- Calculate yC, the y coordinate of the point where the polygon's edge and the
vertical ray cross, from this formula:
- If yC > yA then the ray to infinity does cross this edge of the polygon
so add 1 to the number of crossings found and go on to the next edge.
If yC < yA then there is no crossing so do nothing; go to the next edge.
- You have now tested all the edges around the entire polygon. If the total number of
crossings found is even then test point A is outside the polygon. If the total number
of crossings found is odd then A is inside.
Click here to return to the Math Entertainment page.