### 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

*and we will give an*

**inside / outside problem****algorithm**An algorithm is an exact list of instructions to be followed by a computer to solve a problem.

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

**ray**In geometry a ray is part of a line. It has one endpoint and extends infinitely far in some direction.

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.

#### The Four Simple Checks

- If the bounding box is
of the test point (like edge**completely to the left***E*_{1}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*E*_{2}) 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*E*_{3}) then again,*Count*does not change. - If the bounding box is
(like edge**above the test point and straddling the ray***E*_{4}) 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*), where (

_{L}*x*,

_{L}*y*) is any point on the line and

_{L}*m*is the slope.

*y*, the

_{C}*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*, like in the picture to the right, then the ray

_{A}*does cross*this edge so increment

*Count*by 1. If

*y*<

_{C}*y*, like in the previous picture on the left, then there is no crossing so leave

_{A}*Count*unchanged.

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