如何为定义区域计算地图上点的平均密度？

Question

假设我有经纬度坐标的2万余个数据点。所有这些点都落在地图上的定义区域内。我想计算四分之一英里半径内这些点的平均密度。

我在解释它时遇到了麻烦，但是用例是可以输入一些任意坐标，查看该点四分之一英里半径内有多少个点，并确定该点是高于还是低于数据平均值。

我不是在寻找任何特定语言的解决方案，而是在寻找一种通用的（伪代码）解决方案或解决此问题的方法。

Answer 1

假设您有一堆纬度，经度的地理坐标。

如果要计算适合您的地理坐标的边界框的密度，则使一个O（N）穿过数据集并确定角的地理坐标。

找到它们后，使用Haversine公式（此处为Java实现）来计算两个角之间的边长。确保始终选择距离单位为英里或公里。计算边缘距离后，可以以km ^ 2或miles ^ 2为单位计算盒子的面积。在此处，将密度计算为点数除以面积。

如果要对单个目标点周围的密度进行临时查询，请选择以英里或公里为单位的半径R。使一个O（N）通过数据集，然后计算目标点与其他所有点之间的Haversine距离。如果另一点在距目标的距离R之内，则将其添加到结果列表中。然后，将密度计算为半径所定义的圆内的点数。

如果您进行大量此类查询，请预先计算空间索引数据结构。流行的索引是R-Trees，R * -Trees和kd Trees。下面是Wikipedia中的R树的图片。树将空间分解为矩形区域，因此您可以快速查询点。

如果您的观点适合内存，请使用实现这些数据结构之一的开源库。这是我找到的一个名为rtree的库的链接，它使您可以找到某个半径范围内的所有点。我没有亲自使用过那个图书馆。

如果您的观点不适合记忆，则可以使用SQL数据库。例如，Oracle Spatial实现了这些类型的数据结构。