# A Point About Polygons

Several algorithms exist in the public domain for web servers to determine whether a point is inside a polygon. They are used in the implementation of “image maps”, both of the traditional server-side variety as well as those of the more modern client-side. So who needs one more? Well, the bone this author wishes to respectfully pick is that most of the point-in-polygon code he could find is woefully over-complicated. Being a lover of simplicity and simplification, he just could not leave well enough alone.

The resulting C-language routine has just three
**if** statements and no divides. Contrast that with
three divides and ten **if** statements in the
corresponding routine that's part of the popular Apache web server.
Get the Apache distribution and search for
**pointinpoly** to see the whole works. The routine
from CERN/W3C's httpd is even worse, weighing in at 19
**if** statements! Search for
**inside_poly** in their HTImage.c. (The URLs are
shown in Table 2.)

Table 1 contrasts five different routines in the public domain for finding out if a point is in a polygon. In all cases, the polygon is specified as an array of X,Y coordinates of the corner points.

Table 1. Comparison of Point-in-Polygon Algorithms

This is a pretty casual analysis of the algorithms. I
certainly didn't shy away from showing my
**inpoly()** in a good light. For example,
**&&** and **||** operators
in C are often statements in disguise. I used one of these
operators (as did most of the other folks), but that doesn't show
up in the table at all. Also, some line counts are inflated
slightly by comments and blank lines. But you get a rough
idea.

Table 2. Sources of Public Domain Point-in-Polygon Algorithms

All judgments have a context, and I should explain mine. The primary prerogative in this article is algorithmic simplicity. This, I confess, has very little to do with the practical needs of the Web. In case I've gotten ahead of myself, a web image map is a way of carving up an image so that clicking in one particular region does one thing, and clicking somewhere else does something else. Web image maps are such a tiny fraction of the work of web servers and browsers that all of the above routines are just fine as they are. Changing from one to another is not going to make any noticeable difference in web performance. And once we're sure it works, who's going to look at the code again for 100 years? Thus I don't have any practical considerations of performance or readability to justify my cause. I'm simply championing the aesthetics of simplicity.

The point I wish to make is that problems are not always what
they seem. Sometimes a simple solution exists, but you've got to
take a hard look to find it. My buddy Craig had started out by
porting **inside_poly()** from W3C, I think it was,
for use on our web server. When I saw all the floating point math
and **if** statement special cases, I thought there
had to be a better way. So Craig and I started from scratch,
wrestled the problem to the ground, and came up with a solution
containing no floating point math, which is silly for screen
pixels, and no math more tedious than multiplication. We also got
rid of all the pesky special cases, except for one: polygons with
fewer than three sides are excluded. What could be inside a
two-sided polygon? Apache's pointinpoly() doesn't even check, and
probably makes a big mess with a one-point polygon.

Now, the stated goal is simplicity, not performance, but I
did stray from that course on one issue: avoiding divides. Again,
performance hardly matters for image map applications, but one day
someone might use this algorithm for some kind of 3D hidden surface
algorithm or something. Getting rid of the divide may have, in
effect, required me to use an additional **if**
statement. Anyhow, what all this is leading up to is that Kevin
Kenny's algorithm (see Table 1) at 29 lines and two
**if** statements is by far the shortest and
simplest. But mine is still better in some sense, because mine
doesn't need a divide and his does.

Now let's discuss the more popular algorithm for determining whether a point is inside a polygon.

Imagine you could detect whether a point was in a polygon or not by placing a friendly trained snail at the point and telling him to head for the North Pole. (We're only concerned with image maps, so we exclude polygons that extend to the North Pole, and we ignore Coriolis forces.) You'd equip our intrepid friend in Figure 1 with a snail-sized clipboard and instruct him to tick off each time he crossed an edge of the polygon. He'd call you from the North Pole and report the number of crossings. An even number (including zero) means he started outside the polygon, odd means inside.

This reduces the problem to detecting whether or not line segments intersect. It's even a little better than that, because one of the line segments is simply the positive Y axis. To make that leap, just declare the snail's starting point to be the origin, (0,0), and translate all of the polygon corners so they're relative to that point.

We'll go into the algorithm a little later, but take a look at the finished code in Listing 1. The very picture of simplicity, right? If you haven't checked out the other versions, you really ought to.

## Comments

## 17 Years later...

I've implemented this algorithm in javascript as an extension to google maps http://dawsdesign.com/drupal/google_maps_point_in_polygon