拓扑，缩放

Question

假设有一个2D平面（正方形），里面有一些点。

如何以尽可能均匀地填满飞机的方式移动所有点，但每个点都保持其邻居？

换句话说，我希望点尽量远离彼此，但它们的位置（拓扑）应该保留下来，并且应该放在方块中。

换句话说，我想放大富点人口区域，并缩小空白区域。

PS：是否有更高维空间的通用解决方案？有直接的解决方案还是只有迭代的解决方案？

Answer 1

好的建议是Lloyd's algorithm。然而，你所要求的“邻居保护”属性并不清楚。

但是，如果你要问的是以下几点：

给定图（V，E），其中V中的点由 [0,1]^2和E 段，没有两段 内部相交（即我们有一个 平面图）尽可能均匀地移动点，保留 平面属性

然后劳氏算法会做。

除此之外： 泛化不是根据空间点的位置，而是你要求点的密度（例如，你可能想要R^n上的高斯度量）。

Answer 2

下面是一个可能的策略草图。

对于您的原始P点集合，从平方的边界（最小值，正方形的顶点）添加一些点。这些点应该从边界均匀采样，如果最初有n个点，那么至少应该从边界采样n个附加点。调用此扩充集Q.

然后做Q的Delaunay Triangulation我们将在接下来的步骤中使用边缘从这个三角。

现在做一个least squares minimization来找到P中点的位置（保持Q-P中的点固定），使边长的平方和最小。

您可以通过求解矩阵式解决这个最小化问题，所以这是一个“直接的解决方案”。

最小二乘问题的解决方案将倾向于均衡边的长度。所以小边缘会变大，而大边缘会变小。这将有更均匀的分布点，同时保留其拓扑的效果。

这容易推广到更高维度。