In or Out?

Is a point in two dimensions inside or outside a polygon?

Theoretically this question is dead simple. Start at the point and draw a line parallel to the x-axis and continue until you reach infinity ( or as near to infinity as makes any sense ). As you go, count the occasions when your line crosses an edge of the polygon. If the line crosses a polygon edge an odd number of times then the point was inside but if it crosses an even number of times then it must have been outside.

To get a feeling for how this works, imagine a simple square. From a point inside, any line towards infinity must cross an edge once as it leaves the box. From a point outside the line may never touch the box ( 0 is considered to be an even number ) or it may enter the box and then leave it, for two crossings.

Implementing this simple algorithm in computer code is quite a challenge, especially if you care about performance. When you have some code that seems to work, testing all the special cases could consume days. What if the point is on an edge? On a corner? What if the polygon is not simple, but has holes and several seperate components?

“I have seen farther by standing on the shoulders of giants.” _ Isaac Newton

Many years ago an elegant little piece of code to determine if a point was inside a polygon was published by W. Randolph Franklin. You can find it here with a discussion of how to use it properly, but here is the code itself, all 7 lines of it:

int pnpoly(int nvert, float *vertx, float *verty, float testx, float testy)
{
  int i, j, c = 0;
  for (i = 0, j = nvert-1; i testy) != (verty[j] > testy)) 
       if ( ((verty[i]>testy) != (verty[j]>testy)) &&
            (testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]) )
       c = !c;
  }
  return c;
}

Isn’t this quite wonderful? Well, if you have ever tried to code the point inside a polygon problem, you would think it was just outstanding.

The snag is that it uses an ancient dialect of the C programming language, specifically arrays. Arrays are horrible things, which generate endless bugs, off-by-one bugs and out-of-bounds bugs in particular.

Modern code avoids all these bugs ever occurring by using standard template library vectors. So I have taken the liberty of translating Franklin’s code into modern C++

/**

  Is a point inside the boundary

  @param[in] point  the point being tested

  @return 1 if the point is inside, 0 otherwise

  This code is modified James Bremner, to use the STL vector, from that of W. Randolph Franklin
  given here  http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html

  */
int cBoundary::IsInside( c2d point ) const
{
	int c = 0;
	vector<c2d>::const_iterator j = myBoundary.end()-1;
	for ( vector<c2d>::const_iterator i= myBoundary.begin();
		i != myBoundary.end(); j = i++ )
	{
		if( (( i->y > point.y ) != ( j->y > point.y )) &&
			(point.x < ( j->x - i->x ) * ( point.y - i->y ) / ( j->y - i->y ) + i->x ) )
			c  = ! c;
	}
	return c;

}
Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s