高效计算不规则间距点的密度的方法
14 浏览
高效计算不规则间距点的密度的方法
我正在尝试生成地图覆盖图像，以帮助识别热点，即地图上密度较高的区域。我尝试过的方法都不够快满足我的需求。
注意：我忘记提到算法应该在低缩放和高缩放场景（或低和高数据点密度）下都能很好地工作。
我查看了numpy、pyplot和scipy库，找到的最接近的是numpy.histogram2d。如下图所示，histogram2d的输出相当粗糙。（每个图像中包含叠加在热图上的点，以便更好地理解）
我的第二次尝试是遍历所有数据点，然后根据距离计算热点值。这样产生的图像看起来更好，但在我的应用程序中速度太慢。由于是O(n)复杂度，使用100个点时效果还可以，但当我使用实际的30000个点的数据集时，速度就非常慢了。
我的最后一次尝试是将数据存储在KDTree中，并使用最近的5个点计算热点值。这个算法是O(1)复杂度，所以对于大型数据集来说速度更快。但仍然不够快，生成一个256x256位图需要大约20秒时间，我希望能在大约1秒内完成这个过程。
编辑
6502提供的boxsum平滑解决方案在所有缩放级别上效果都很好，并且比我的原始方法快得多。
Luke和Neil G建议的高斯滤波解决方案是最快的。
你可以在下面看到这四种方法的效果，使用了总共1000个数据点，在3倍缩放时可见约60个点。
完整的代码生成了我最初的3个尝试、6502提供的boxsum平滑解决方案和Luke建议的高斯滤波（改进以更好地处理边缘和允许放大）：
重点：这段代码包含了一些特定的库和函数，无法直接翻译。