A Point About Polygons

An essay on the aesthetics of polygons and algorithms that one might see in a web image map.
Life on the Edge

By the way, who cares whether the points in an image map along the edge of a polygon are technically inside or outside? As you can see in the close-up, some of the originally white pixels (representing the polygon edge) turned to red, others to blue. If a browsing user clicks on the edge of a region, he may get in, he may not. But being one pixel off is usually not an issue if your screen resolution is greater than 100 x 100. In the inpoly() routine, some edges are in, some are out. (I don't mind admitting to a crime after convincing everyone it deserves no punishment.)

Angling for Adders

I haven't discussed the angle-sum method used by Woods Hole Oceanographic Institution for their algorithm written in Matlab. The algorithm needs to compute arc-tangents, so it's mostly just a laboratory curiosity. The idea is that you add up the angles subtended by lines drawn from the target point to each of the corners of the polygon. If the sum is an even multiple of 360 degrees, you're out; odd, you're in. Vaguely familiar? Here's the analogy: You're in a pitch-black room with a very, very long snake all over the floor. This is a particularly rare variety of deep sea snake (Woods Hole knows all about them) with glow-in-the-dark dots every foot or so. Oh, and he reacts to light by instantly constricting in an iron grip of death. Your question is whether you're standing inside the maze of coils at your feet or outside. You'd like to know before you turn on the light because he gets very annoyed if you step on him.

Face the head of the snake and visually trace his entire body, somehow noting as you do how your feet turn (it's a stretch I know). When you're done, face the head again. Now, if you didn't have to turn around at all, you're safely outside the snake. If you turned around twice in either direction things are fine too. Four times, and you're still OK. If you turned around an odd number of times in either direction, you're meat—no wonder folks tend to use the crossing-count algorithm.

Bob Stein has been a writer/developer at Galacticomm for nine years. He developed the web server that's part of Galacticomm's Worldgroup software which, of course, uses his inpoly.c for image map polygons.



Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

17 Years later...

Matt Williamson's picture

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

White Paper
Linux Management with Red Hat Satellite: Measuring Business Impact and ROI

Linux has become a key foundation for supporting today's rapidly growing IT environments. Linux is being used to deploy business applications and databases, trading on its reputation as a low-cost operating environment. For many IT organizations, Linux is a mainstay for deploying Web servers and has evolved from handling basic file, print, and utility workloads to running mission-critical applications and databases, physically, virtually, and in the cloud. As Linux grows in importance in terms of value to the business, managing Linux environments to high standards of service quality — availability, security, and performance — becomes an essential requirement for business success.

Learn More

Sponsored by Red Hat

White Paper
Private PaaS for the Agile Enterprise

If you already use virtualized infrastructure, you are well on your way to leveraging the power of the cloud. Virtualization offers the promise of limitless resources, but how do you manage that scalability when your DevOps team doesn’t scale? In today’s hypercompetitive markets, fast results can make a difference between leading the pack vs. obsolescence. Organizations need more benefits from cloud computing than just raw resources. They need agility, flexibility, convenience, ROI, and control.

Stackato private Platform-as-a-Service technology from ActiveState extends your private cloud infrastructure by creating a private PaaS to provide on-demand availability, flexibility, control, and ultimately, faster time-to-market for your enterprise.

Learn More

Sponsored by ActiveState