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.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
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.
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
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
The Four Simple Checks
- 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.
- 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.
- If the bounding box is below the test point (like edge E3) then again, Count does not change.
- 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.
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
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!