我不知道有哪个服务器端库可以为您完成这项工作。不过,我可以为您提供一些有关如何自行实施的指导。
聚类的基本方法就是计算标记之间的距离以及其中两个标记之间的距离。足够接近您可以将它们替换为位于两者之间的中点的单个标记。
您不仅可以限制彼此标记的距离,还可以(或相反)选择限制您想要的簇/标记的数量。
为了实现这一点,您可以计算所有标记对之间的距离,对它们进行排序,然后从顶部合并,直到您想要的标记/簇数量为止。
为了在形成簇时细化中点定位,您可以考虑要合并的两个中的每一个所代表的实际标记的数量。将该数字视为重量,将两个标记之间的线视为秤。然后,不要总是选择中点,而是选择可以平衡天平.
我猜想,如果标记数量有限,这种简单的聚类形式就足够了。如果您的数据集(标记数量及其位置)大致是静态的,您可以偶尔在服务器上计算聚类,对其进行缓存,然后直接从缓存中为客户端提供服务。
但是,如果您需要支持可能具有世界各地标记的大规模场景,您将需要更复杂的方法。
上述集群算法无法扩展。事实上,其计算成本通常会随着标记数量呈指数增长。
为了解决这个问题,您可以将世界分成多个分区并计算集群并为每个分区的客户端提供服务。这确实支持扩展,因为工作负载可以由多个(大致)独立的服务器分割和执行。
接下来的问题是如何找到一个好的分区方案。您可能还需要考虑在不同的缩放级别提供不同的标记聚类,并且您的分区方案也应该包含这一点以允许缩放。
Google 将地图划分为具有 x、y 和 z 坐标的图块,其中x and y是从地图西北角开始的图块的水平和垂直位置,其中z是缩放级别。
在最小缩放级别(零)时,整个地图由单个图块组成。 (所有图块均为 256x256 像素)。在下一个缩放级别,该图块被分为四个子图块。这样继续下去,因此在缩放级别 2 中,这四个图块中的每个图块都被分为四个子图块,这总共为我们提供了 16 个图块。缩放级别 3 有 64 个图块,级别 4 有 256 个图块,依此类推。 (任何缩放级别上的图块数量可以表示为4^z
.)
使用此分区方案,您可以从最低缩放级别(最高 z 坐标)开始计算每个图块的聚类,一直向上冒泡,直到到达顶部。
对于单个图块要聚类的标记集是其四个子图块的所有标记(其中一些可以代表聚类)的并集。
这为您提供了有限的计算成本,并且还为您提供了一种将数据分块发送到客户端的好方法。而不是请求给定缩放级别的所有标记(这将not比例)客户端可以在将标记加载到地图中时逐个图块地请求标记。
然而,这种方法有一个缺陷:考虑两个相邻的图块,一个在左边,一个在右边。如果左侧图块在其最右侧包含一个标记/簇,而右侧图块在其最左侧包含一个标记/簇,则这两个标记/簇应该合并,但不会合并,因为我们正在执行聚类每个图块单独的机制。
为了解决这个问题,您可以在对图块进行聚类后对其进行后处理,以便合并位于四个边缘中的每一个上的标记/簇,同时考虑给定图块的八个相邻图块中的每一个。只有当我们假设没有单个集群存在时,这种合并后机制才会起作用。足够大影响不在同一子图块中的周围标记。然而,这是一个合理的假设。
最后一点:通过横向扩展的方法,您将让客户提出几个小请求。这些请求将具有局部性(即,瓦片不是随机请求的,而是地理上彼此接近的瓦片通常也被一起访问)。
为了提高查找/查询性能,您将受益于使用也具有此局部性属性的搜索键(代表切片)(因为这会将相邻切片的数据存储在磁盘上的相邻数据块中 - 提高读取时间和缓存利用率)。
您可以使用平铺/子平铺分区方案来形成这样的密钥。让顶部图块(跨越整个地图的单个图块)将空字符串作为键。接下来,让每个子图块都有键 A、B、C 和 D。下一个级别将有键 AA、AB、AC、AD、BA、BC、...、DC、DD。
递归地应用此方法,您最终将得到一个分区键,该分区键可识别您的图块,允许快速转换为 x、y、z 坐标并具有位置属性。这种密钥命名方案有时称为Quad Key由于分区方案形成了一个事实四叉树。局部性属性与使用 Z 顺序曲线将 2D 值映射到 1D 值时获得的属性相同。
如果您需要更多详细信息,请告诉我。