Flutterby™! : Basic geometric operations in Perl 2010-08-27 16:00:49.859226+00

Basic geometric operations in Perl

2010-08-27 16:00:49.859226+00 by Dan Lyke 4 comments

I've been carrying a Wintec G-Rays 2+ GPS tracker in my pocket recently. Sometimes I'll remember to mash the "start new track" button, sometimes I won't, so I whipped together a little Perl that grabs the bounding rects of polygons saved in "My Places" in Google Earth, and runs through the tracks that come off that thing and splits 'em up. So I can run my tracks through it and see "Oh, look, there's a "005-Home-HelenPutnamPark.kml", and a 006-HelenPutnamPark-HelenPutnamPark.kml", so I drove to the park, ran in the park, and...

There are a few limitations with what I've got so far.

I can take Perl and convert from WGS84 (ie: "latitude and longitude" for you folks who don't want to know about datums) to UTM (meters, for those of you who don't wish to dig further) so that I can say "how far did I jog?" using Proj.4 or Geo::Coordinates::UTM.

However, I'm just using axis aligned bounding boxes around the regions I've drawn in Google Earth because I don't have a convenient library for basic 2d vector operations in Perl.

What I'd like is to not have to:

Rewrite line-to-line intersection code in Perl from C++.
Rewrite "in polygon" intersection code in Perl from C++.

When I go looking for basic geometric operations code in Perl, I find examples that were written by professors as examples for CS classes that have clear degeneracies. I could fix them, but that's a few hours, and in that time I could write my own that'd also have some edge cases I undoubtedly missed, and that use data structures that look nothing like what other people might use.

There has to be a library of basic 2d vector operations for Perl, no? I'm installing Math::Intersection::StraightLine and Math::Polygon::Tree, but the CPAN entries don't give me great hope that these are any better than the other sample code I've stumbled across. Someone has to have done this right?

C++ even more recently got GEOS (which includes several functions I was banging my head against several years ago). You could probably go a long ways by making a Perl module that wraps GEOS.

There are actually a whole libary's worth of functions like yours for interacting with GPS tracks that needs to be written. I think, initially, the language wouldn't matter much because it's so universally desireable. Perl's as good a place to start as any.

The Perl code is embarassingly ad-hoc, but Math::Polygon::Tree installed with some coaxing and I just used that. I'm parsing the KML with regular expressions. If anyone cares I suppose I could make a git repo and work on this collaboratively, but probably nobody does...

The problem is Perl people seem to address specific problem subsets where this topic is concerned; it doesn't seem to be the sort of thing that inspires Perl developers to say, "Hmm, maybe I should generalize this into an all-purpose library." Dunno why; they're perfectly willing to make that leap with other topics.

That said, if the Math:: sublibraries don't do it for you (try poking around Math::Geometry as well as Math::Polygon), you could also dig in the sublibraries under Geo::, some of which seem to have at least given some thought to these problems. How well they solved them, I could not say.

There's a lot of good stuff in Geo:: (I'm (ab)using some of it), but a good portion of the stuff there seems to degenerate into "I've got code that reads into this opaque data structure and writes it back out, you figure it out!"

Then again, most stuff that deals with XML ends up being pretty horrendous; Perl modules are no exception...