<分区>
如果在二维空间中有一组点，是否有一种算法可以将这些点分成 N 个“区域”，每个区域包含 K 个相邻点？
例如，假设要将这 20 个点聚类为 4 组，每组 5 个点。一个令人满意的解决方案可能如下所示:
动机:我正在尝试优化 visualization that loads lots of images into the browser .我计划在页面加载时加载非常低分辨率的图像，然后在用户放大该区域时提高该区域图像的分辨率。当然，我需要量化空间，所以如果用户直接滚动到上面示例的中间，我必须为 4 组中的每一组获取高分辨率图像。
console.log('stackoverflow wants code for posts with codepen links')
最佳答案
一个算法可以是这样的:
- get a triangulation of the points (for example: Delaunay Triangulation): D
- get a planar graph from D: G
- Then partition G into connected subgraphs with equal size k
对于最后一步 this solution简短易懂(来自 Theoretical Computer Science 网站):
Compute a constant degree spanning tree T of your graph, root it, and now greedily find subtrees of roughly size r, extract them, and repeat. Naturally, if there is no constant degree spanning tree, then the star example shown above demonstrates that this algorithm can fail.
关于algorithm - 将 2D 点划分为 N 个区域，每个区域有 K 个相邻点，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/47458593/