I’ve been learning Common Lisp lately, so I’ve been writing a lot of small projects in it.
A few days ago I started a project to parse GPX files and print out some information about them. I’ve written similar utilities before in Perl and Python, and rewriting in Lisp seemed like a good way to learn the language.
Parsing the XML file was easy enough, but one problem I ran into was using the latitude and longitude readings in the GPX file to calculate distances. The problem is that latitude and longitude don’t have a physical meaning – they’re essentially just angles used to locate positions on sphere-like objects. There’s no easy way to take two points and calculate a distance between them, because the angles themselves can just as easily locate a point on a tennis ball as they can the entire earth.
The solution is to convert the coordinates to the Universal Traansverse Mercator (UTM) projection, which was specifically created for locating points on Earth in more usable units (meters). A UTM coordinate consists of a zone number saying approximately where the location is around the planet, and then “easting” and “northing” coordinates, measured in meters, specifying the distance to the point from the origin of the zone.
The calculations to convert latitude and longitude to UTM are pretty ugly, in part because the model takes into account the true shape of the earth, which isn’t a sphere, but more of an ellipsoid. There are also various measurements for the ellipsoid, both because of uncertainty measuring the exact size, and because the Earth isn’t a perfect ellipsoid – different measurements can work better at different locations on Earth.
When I wrote a similar script in Perl, I used the Geo::Coordinates::UTM CPAN module to avoid doing the calculations myself. For the new version in Common Lisp, I was hoping to avoid the work again, so I looked through the libraries available in QuickLisp and on Cliki. The only one that did what I wanted was cl-proj, a Common Lisp binding for Proj.4. I investigated a bit, but the library seemed hard to use, and would have added a large dependency on Proj.4.
I decided to write a library myself. The math for the conversion is super ugly, as can be seen on Wikipedia. Fortunately for me, Steve Dutch at the University of Wisconsin has a couple of very helpful pages on the topic. The first covers the formulas in a bit more detail, and he makes it more clear what’s going on. The second provides a thorough higher level explanation of UTM, covering zones and many other topics.
The biggest problem I had was converting the formula into Lisp’s prefix notation, where “4 * sin(3*u + 4*v)” becomes “(* 4 (sin (+ (* 3 u) (* 4 v))))”. The code is on GitHub, and you can see the formulas are pretty ugly. Once I got the hang of it, though, it wasn’t very hard, and by the end I was able to convert them from “normal” infix notation into prefix notation quite easily.
At first I only supported the most common ellipsoid, WGS-84, which is the only one I’ve seen used anywhere, and is the most accurate one for North America. Before adding the project to GitHub, though, I realized it wouldn’t be hard to store the constants for a few other ellipsoids, so I went ahead an added them.
After finishing up the conversion from latitude and longitude, I realized it might be useful for other people, so I decided to make it a real library. Before doing so, though, I wanted to add the reverse conversion from UTM to latitude and longitude. I don’t really need that ability, but I know if I were looking for a library, I would expect it to convert both ways. The reverse conversion isn’t as complicated, and didn’t take as long, but the math is still pretty ugly in CL.
Once all of the functionality was in place, I had a little bit of work to do packaging it up in a way other people could use. Fortunately I used QuickProject, so most of the boilerplate was already created for me, I just needed to fill in some info like the version number, the author name, a license file, and a project description.
Once everything was done, I threw the project on GitHub, and added a page on Cliki for it. The final step was to open a GitHub issue on the QuickLisp project, asking them to include the project in QuickLisp.
I haven’t heard back yet, but hopefully it will be accepted and start getting used by other people.