BorderPatrol: KML border checking in Ruby
Presenting a gem to import KML files and detect whether or not points are contained within defined regions.
Written by Zach Brock.
BorderPatrol allows you to easily check if a point exists within a region defined by a KML file. Thanks to Google Map’s KML export and shape drawing, this makes it really easy to define regions of interest and quickly check if points are inside of them. BorderPatrol supports regions made of simple polygons as well as more complex regions of multiple unlinked many-sided polygons. We’ve used it for everything from single cities to entire continents to collections of countries.
For example, let’s consider the case where we have a set of points and want to know if they are inside of the state of Colorado. We’ve defined a shape on google maps and can use the kml output option to export it.
require 'open-uri'
require 'lib/border_patrol'
kml_file = open("http://maps.google.com/maps/ms?ie=UTF8&hl=en&msa=0&ll=38.814031,-103.743896&spn=9.600749,16.248779&z=7&msid=110523771099674876521.00049301d20252132a92c&output=kml")
region = BorderPatrol.parse_kml(kml_file)
denver = BorderPatrol::Point.new(-105, 39.75)
region.contains_point?(denver) # true
region.contains_point?(-105, 39.75) # also true!
san_francisco = BorderPatrol::Point.new(-122.5, 37.75)
region.contains_point?(san_francisco) # false
region.contains_point?(-122.5, 37.75) # also false!
BorderPatrol implements the Point in polygon ray-casting algorithm. The algorithm itself is very elegant: For a given point, draw a ray in a random direction. If the ray passes through a side of the polygon an even number of times, the point is outside the polygon. If you go through an odd number of sides, your point is inside. The graphic below from wikipedia demonstrates the concept in reverse. When the ray has passed through an odd number of sides it is inside the polygon and vice versa.
BorderPatrol also includes a few performance optimizations, including checking the polygon bounding box first (i.e. “is this point even anywhere near the given region?”), adding equality checking for polygons to prevent repeated work, and a quick hash function for polygons. We’ve found it to be sufficiently fast for our purposes. There’s a benchmarking script included with the code if you want to test the performance yourself. Anecdotally, an early 2011 macbook pro can check region inclusion of more than 10,000 points a second given a relatively simple KML file.
We’ve been using BorderPatrol in production as a part of several critical paths since October 2010. It’s proven extremely helpful both for making real time assessments of geo data and for offline evaluation of large collections of points. You can find the code on github and the gem on rubygems. We wrote it because we couldn’t find anything comparable, and we hope other people will find it useful. If you do, be sure to let us know! Zach Brock - Profile *Oklahoma was not one of the states who signed onto the brief in support of the North Carolina board. The reasons why…*medium.com
Authored By
