Ask HN: Getting started with geospatial data?

[rufugee]

I have a startup idea I really want to pursue. Without going into great depth, it would require guessing based on submitted GPS data a user's proximity to certain landmarks. Say, for example, if the data indicates they're within a mile radius of the Whitehouse, my software should be able to determine that...assuming I'd loaded the Whitehouse's latitude and longitude ahead of time.

I'd like to use Rails for the application, and possibly PostGIS, since PostgreSQL is already my database of choice.

Problem is, I'm a geospatial noob, and haven't done any significant math in a decade. In fact, even then, my math background was weak at best compared to most software engineers...I followed a non-traditional path.

So, what's the best way to get started on learning how to implement a system like this? I'm less interested in theory (though welcome it as well) and more interested in practical, make-it-work advice.

Thank you so much!

[RiderOfGiraffes]

Close enough is good enough.

Given a (lat,lng) of (A,B) and another of (X,Y), each in degrees, the distance between them is (roughly)

  sqrt( (A-X)^2 + (B-Y)^2 )

in degrees, and to convert to miles you use 360 degrees is 25000 miles.

OK, now that's not quite right, because as your latitude increases the distance between the lines of longitudes decreases. You need to multiply by cos(lat). So your answer in miles is:

  sqrt( (cos(A)*(A-X))^2 + (B-Y)^2 )/360*25000

Again, close enough is good enough because if you're more than a mile or three then the errors are really small.

There is a more exact formula using dot products of 3-space vectors, and then another that takes the non-spherical nature of the Earth into consideration, but the above is good enough to start with.

EDIT ...

To get the more accurate version, for a (lat/lng) you convert to a unit vector:

    X = cos(lat)*cos(lng)
    Y = cos(lat)*sin(lng)
    Z = sin(lat)

Given two lat/lngs, convert to (a,b,c) and (x,y,z). Now you can take the dot product:

    dot = (a,b,c).(x,y,z) = a*x+b*y+c*z

Compute the angle between the vectors:

    angle_in_radians = arccos(dot)

Finally, the distance is

    distance = radius * angle_in_radians
             = 25000 * angle_in_radians (miles)
             = 40000 * angle_in_radians (kilometers)

As a comment about accuracy and appropriate formulae,

... if the points really are close together then the arccos comes out as highly error-prone because of limited accuracy. The dot product is very, very close to one, so the arccos is unreliable. This is because when theta is really, really small then the value of cos(theta) is very, very close to 1. If you subtract it from 1, you get very small rubbish. Multiply by a large number and you get big rubbish.

[gruseom]

If you want an overview, the bible right now is Samet's Foundations of Multidimensional and Metric Data Structures:

http://www.amazon.com/Foundations-Multidimensional-Structure...

[iterationx]

I've found this site useful, http://www.movable-type.co.uk/scripts/latlong.html

[rufugee]

Thanks to you both for your pointers. I will explore both.