Postgresql earth_box 算法

Question

我找到了 this教程如何找到指定半径内的东西。我的问题是使用什么算法来实现它？

Answer 1

如果您指的是 earth_box，则想法是提出一种可用于 GIST 索引(倒置搜索树)的数据类型:

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

请特别查看维护者页面底部的链接:

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

一个导致:

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

如果您指的是地球距离本身，源代码的重要部分是:

/* 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

我的数学太生疏了，无法肯定上面的内容，但我的猜测是它正在计算球体表面两点之间的距离(不考虑两点的高度)。换句话说，海里。