Jeffrey Bosboom's Blog

[blog] [projects] [about]

Polygon adjacency project

While an undergraduate at the University of California, Irvine, I worked under Professor Michael Goodrich to develop an algorithm for accurate computation of polygon adjacency, with a proof-of-concept implementation targeting the United States Census Bureau’s Zip Code Tabulation Area data.

Naive approaches using the distance between center points of the polygons must make false positive/negative tradeoffs; setting too low a threshold leads to missed adjacencies, while setting too high a threshold allows polygons separated by thin polygons to be considered adjacent. Instead, my algorithm breaks the polygons into their segments, then compares only segments adjacent (or overlapping) on a sweep line. Using a sweep line naturally incorporates polygons “blocking” other polygons from being adjacent, reducing false positives, while supporting efficient computation of adjacency between unblocked polygons. (In the ZCTA data, unblocked polygons might not be adjacent if they’re separated by a large gap, such as a body of water.)

The resulting adjacency graph might be useful for studying the spread of a disease based on case reports geocoded by zip code. While humans can use visualizations to get a sense of the direction of spread (say, a map on which cases appear as dots, color-coded by date), algorithms can provide constant monitoring of all case reports, impractical for human analysis, to produce warnings of impending outbreaks.

An archive containing a partial draft of a paper and code for an implementation is available for download. Code is GPLv3+; other text is CC-BY-SA 4.0. (Sorry, I hadn’t discovered version control yet, so you’ll have to decide which implementation is most complete.)

This work was not published. I started the project during my first quarter at UCI; after completing all the assignments in my introductory programming course, I asked Professor Goodrich if he had anything useful for me to work on. By the time I completed it, I decided computational geometry wasn’t the field for me, though it was a valuable experience. If you find it a useful starting point for your work, I’m still interested in hearing from you.