c# - 点簇算法

Question

是否有任何 C# 库可用于计算点集群（云？）？

我得到了一张包含 5-50k 点的地图，需要根据缩放级别对点进行聚类——但我还需要一种方法来过滤掉在计算聚类之前不可见的点。

我的想法是计算 N 缩放级别/地图比例的所有集群并将它们拆分为网格。然后地图发送一个 ajax 请求，说“我在坐标，这个范围和地图比例尺” - 服务器查询缓存中与客户端请求匹配的所有网格项目并发送响应。

这是一个可行的想法，矫枉过正，还是只是“远离正常做法”的那些想法之一？

Answer 1

It seems what you are trying to do here is two things: (1) find the relevant points from a given point given a zoom level, and (2) not include points that are too close together given a zoom level.

If this is the case, then (1) is trivial: you compute the distance to each point from the observation point. Only points under the threshold distance are included. The threshold distance is a function of the zoom level.

To do (2) you want to avoid computing the distance of each point to each other point because that is computationally intensive. What you do is a Delaunay triangulation of the points discovered in step (1). Then, compute the area of each triangle. Then, for each point add up the areas of the triangles for which it is a vertex. Sort the points by this value (the total triangular area--TTA). Remove all points which have a TTA below a zoom-level-dependent threshold. You can discover the best thresholds to use by experimentation.