Postgresql earth_box algorithm

postgresql

Solution

If you mean the earth_box, the idea is to come up with a data type that can be useful with a GIST index (inverted search tree):

http://www.postgresql.org/docs/current/static/gist-intro.html

See in particular the links at the bottom of the maintainers' page:

http://www.sai.msu.su/~megera/postgres/gist/

One leads to:

The GiST is a balanced tree structure like a B-tree, containing pairs. But keys in the GiST are not integers like the keys in a B-tree. Instead, a GiST key is a member of a user-defined class, and represents some property that is true of all data items reachable from the pointer associated with the key. For example, keys in a B+-tree-like GiST are ranges of numbers ("all data items below this pointer are between 4 and 6"); keys in an R-tree-like GiST are bounding boxes, ("all data items below this pointer are in Calfornia"); keys in an RD-tree-like GiST are sets ("all data items below this pointer are subsets of {1,6,7,9,11,12,13,72}"); etc. To make a GiST work, you just have to figure out what to represent in the keys, and then write 4 methods for the key class that help the tree do insertion, deletion, and search.

http://gist.cs.berkeley.edu/gist1.html

If you mean the earth distance itself, the meaty part of source is:

/* compute difference in longitudes - want < 180 degrees */
longdiff = fabs(long1 - long2);
if (longdiff > M_PI)
    longdiff = TWO_PI - longdiff;

sino = sqrt(sin(fabs(lat1 - lat2) / 2.) * sin(fabs(lat1 - lat2) / 2.) +
                cos(lat1) * cos(lat2) * sin(longdiff / 2.) * sin(longdiff / 2.));
if (sino > 1.)
        sino = 1.;

return 2. * EARTH_RADIUS * asin(sino);

https://github.com/postgres/postgres/blob/master/contrib/earthdistance/earthdistance.c#L50

My math is too rusty to be affirmative on what the above does exactly, but my guess would be that it's computing the distance between two points on the surface of a sphere (without considering the height of the two points). In other words, nautical miles.

Problem

Original source