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.

poly and 3 points Somehow the human brain can easily tell that points C and A are inside the polygon and point B is outside. But how can we program a computer to do it? This is called the inside / outside problem and we will give an
algorithm An algorithm is an exact list of instructions to be followed by a computer to solve a problem.
to solve it.

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.

eqn list of vertices and edges

5-poly with vertical rays Our algorithm will have only these numbers to work with. The picture to the right shows the test points, A, B, C and the polygon with edges 1, 2, 3, 4, 5. It also shows a
ray In geometry a ray is part of a line. It has one endpoint and extends infinitely far in some direction.
originating at each test point and going vertically up to infinity.

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.

dragon with hole and vertical rays

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

pt A and 5 vertices

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.

Tests to Determine if the Ray crosses an Edge

bounding box

This is the minimum
bounding box for edge E

bounding box

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.

easy tests

The Four Simple Checks

  1. If the bounding box is completely to the left of the test point (like edge E1 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 E2) 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 E3) then again, Count does not change.
  4. If the bounding box is above the test point and straddling the ray (like edge E4) then the ray definitely crosses the edge. Increment Count by 1.

hard tests

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.

yc for hard test To decide which it is, we use the
point-slope form The equation of a straight line can be expressed as y = yL + m · (xxL), where (xL , yL ) is any point on the line and m is the slope.
for the edge's line and calculate yC , the y coordinate of the point where the edge and a vertical line through A would cross (the blue dot inside the bounding box).

formula for intersection

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

If you would like to leave a comment or ask a question please send me an email!