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.
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.
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.
|HPC Cluster Grant Accepting Applications!||Jan 28, 2015|
|Sharing Admin Privileges for Many Hosts Securely||Jan 28, 2015|
|Red Hat Enterprise Linux 7.1 beta available on IBM Power Platform||Jan 23, 2015|
|Designing with Linux||Jan 22, 2015|
|Wondershaper—QOS in a Pinch||Jan 21, 2015|
|Ideal Backups with zbackup||Jan 19, 2015|
- HPC Cluster Grant Accepting Applications!
- Sharing Admin Privileges for Many Hosts Securely
- Designing with Linux
- Red Hat Enterprise Linux 7.1 beta available on IBM Power Platform
- Wondershaper—QOS in a Pinch
- Internet of Things Blows Away CES, and it May Be Hunting for YOU Next
- Ideal Backups with zbackup
- Slow System? iotop Is Your Friend
- Hats Off to Mozilla
- diff -u: What's New in Kernel Development
Editorial Advisory Panel
Thank you to our 2014 Editorial Advisors!
- Jeff Parent
- Brad Baillio
- Nick Baronian
- Steve Case
- Chadalavada Kalyana
- Caleb Cullen
- Keir Davis
- Michael Eager
- Nick Faltys
- Dennis Frey
- Philip Jacob
- Jay Kruizenga
- Steve Marquez
- Dave McAllister
- Craig Oda
- Mike Roberts
- Chris Stark
- Patrick Swartz
- David Lynch
- Alicia Gibb
- Thomas Quinlan
- Carson McDonald
- Kristen Shoemaker
- Charnell Luchich
- James Walker
- Victor Gregorio
- Hari Boukis
- Brian Conner
- David Lane