MathOnWeb.com

The Inside / Outside Problem

A calculation that must be performed billions of times in every movie that uses computer graphics is to find what parts of one object are hidden by another object that is 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.

The problem is that in the computer, points are stored as ordered pairs or (x, y) coordinates:

A=(22, 15)   B=(40,17)   C=(8, 16)

The polygon is stored as a pline – a list of points. These points represent the vertices of the polygon. By letting the last vertex equal the first vertex we are indicating that the pline ends where it starts and that it represents a closed polygon (rather than just a line). Each vertex is connected to the next vertex by an edge. Here are the five vertices and the five edges for the polygon shown above.

The basic idea of our algorithm is to count the number of times that a 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 we see that the rays from A and C cross the boundary once so A and C are inside the polygon. The ray from B crosses twice so B is outside.

The picture to the right shows a more complicated object. This time the ray from C crosses the boundary 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

We want to count the number of times that the ray crosses the boundary of the polygon. To do that we need two variables: Edge, the index for the edge presently being tested and Count, the number of crossings found so far.

(For the picture to the right Edge will run from 1 to 5 and Count will start at 0 and end up equaling 1.)

Here is the algorithm expressed in point form and as a flowchart.

• Set Count to an initial value of zero and set Edge to the first edge.
• Do the tests (described in detail below) to determine if the ray crosses this Edge. If it does cross then Count is incremented by 1. If it does not cross then Count is not changed.
• Go to the next edge and repeat the tests. Cycle through all the edges.
• Once you have tested all the edges, examine the value of Count, the total number of crossings found. If it is even then test point A is outside the polygon. If it is odd then A is inside.

Tests to Determine if the Ray crosses an Edge

This is the minimum
bounding box for edge E

There are four simple checks that are done first, followed by one "harder" test (harder only because it requires a bit of math, whereas the simple checks only require comparisons of coordinates).

It is easier to visualize the tests if we put a

minimum bounding box In geometry the minimum bounding box for an object is the smallest rectangle that contains the object, subject to the constraint that the rectangle's edges are parallel to the (Cartesian) coordinate axes.

around the edge being tested, as shown here.

The Four Simple Checks

1. If the bounding box is completely to the left of the test point (like edge E₁ in the picture) then the ray can't cross the edge. Count does not change.
2. If the bounding box is to the right of the test point (like edge E₂) then again, the ray can't cross the edge so Count does not change.
3. If the bounding box is below the test point (like edge E₃) then again, Count does not change.
4. If the bounding box is above the test point and straddling the ray (like edge E₄) then the ray definitely crosses the edge. Increment Count by 1.

The Harder Test

After the four simple checks the only remaining possibility is that the test point A is inside the bounding box, as shown to the right, either above the edge or below the edge.

To decide which it is, we use the

point-slope form The equation of a straight line can be expressed as y = y_L + m · (x − x_L), where (x_L , y_L ) is any point on the line and m is the slope.

for the edge's line and calculate y_C , the y coordinate of the point where the edge and a vertical line through A would cross (the blue dot inside the bounding box).

If y_C > y_A , like in the picture to the right, then the ray does cross this edge so increment Count by 1. If y_C < y_A, like in the previous picture on the left, then there is no crossing so leave Count unchanged.