Archive for July 28th, 2009

Efficient closest point calculation; how to?

Tuesday, July 28th, 2009

Randall Lawrence Waterhouse

Current meatspace coordinates, hot from the GPS receiver card in my laptp:

27 degrees, 14.95 minutes N lattitude 143 degrees, 17.44 minutes E longitude

Nearest geographical feature: the Bonin Islands

—Neal Stephenson, Cryptonomicon

One of the projects that I’ve had cooking in the back of my mind is to implement something like Waterhouse’s signature block in Cryptonomicon. After all, I’ve reached a point in my life where I actually have GPS equipment and a computer that are small enough to use on an airplane. (Unlike Waterhouse, I tend to fly coach.)

There’s a couple of different parts to this project as I see it.

  • You need an interface to the GPS reciever to get the current position data. That should be easy; both Perl and Python have GPSD interfaces.
  • You need a database of geographic points. It looks like that shouldn’t be a hard problem to solve; there’s some online databases that I think can be made to work, or converted, for this purpose.
  • You need an interface between your programming language and the database to look up points. Again, that should be easy; I’m assuming the database of geographic points is stored in some sort of standard SQL databse, and both Perl and Python have SQL database interfaces. (One possible problem is that I want to be able to run this on a Nokia N800, and the SQL database choices for that machine are kind of limited.)
  • You need to be able to calculate distance between two points. That’s easy: see http://www.movable-type.co.uk/scripts/latlong.html  for an example.
  • But here’s the problem. Let’s say you have a database of two million geographic points. How do you efficiently find the closest point to your current geographic location?

I’m stumped by the last part. Doing two million Haversine calculations seems like a time consuming operation; I suspect on a N800, the closest point would have changed substantially by the time the calculations finish.

Anyone have any good ideas? If I ever do write the script, I promise public acknowledgment (and public posting of the code).

Welcome to Whipped Cream Difficulties.

Tuesday, July 28th, 2009

Whipped Cream Difficulties is an occassional web log about things I find interesting. Some of those things might be:

  • Food (especially around Austin, TX).
  • Guns (especially Smith and Wesson revolvers).
  • Interesting items I find around the net (but I’ll try not to duplicate FARK).
  • People who died (died).
  • Popular culture.
  • Computer security.
  • Art, damn it, art!

This isn’t intended to be all-inclusive.

I work for a large four-letter computer company, but I am not an official representative of same, and will not comment on non-public information.

I welcome comments. Spam will be vigorously deleted.