Sir*_*get 4 mapping algorithm map geolocation data-structures
假设我有一张地理地图,其中各点由纬度\经度表示.我在这张地图上有很多点,可以随时添加\删除\移动点.
我需要的是获得"最热点" - 包括最大点数除以面积的区域 - 或者换言之,具有最高点密度的区域.
我需要一个有效的数据结构,以及一个重新计算任何变化的最热点的算法.计算复杂度和内存复杂度必须最小,因为点数可能会非常高.
我希望知道并保持一份最热门地点的降序排列 - 首先是最拥挤的地区,然后是不那么拥挤的地区.有一个有限大小的列表是可以的 - 例如,100个最热点.
当然,为了防止一个孤立点上的100%密度,存在最小区域(定义为常数).
这里"区域"的定义是地图上包含点的任何可感知区域.它可能是整个地图,但算法不应该将其视为当然的热点=)
谢谢!如果需要任何澄清,请说出来......
你在做什么在统计上被称为'二维密度估计'(所以你知道在哪里看).
一种常见的方法是"内核平滑".想象一下,您的每个数据点上都有一张光盘.在该区域上平滑的内核是在每个点处重叠的盘的数量.这是使用固定半径的统一内核进行内核平滑.
您不必使用统一内核,也不必在所有点都使用相同的大小 - 现在这是"自适应带宽内核平滑".
这给了你一个可以很容易更新的网格,特别是如果你有一个有限的内核(你可以使用一个无限的高斯(又名正常)内核,但会剪切到你的研究区域).每次添加或删除一个点时,都会添加或删除其内核对密度的贡献.
这就是问题的一半 - 你现在有一个密度网格.然后,您可以使用聚类算法对其进行分区,并根据任何标准找到单独的峰值a)定义"峰值",b)将其定义为与相邻峰值分开.其他人已经建议了聚类算法.我(十年前)使用统计软件包"R"中的聚类函数完成了这项工作.虽然速度不是它的强项......
您可能希望将其转到http://stats.stackexchange.com