2d - 拓扑、缩放

Question

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

如何移动所有点以使它们尽可能均匀地填充平面但每个点都保持其邻居？

换句话说，我希望这些点尽可能地彼此远离，但它们的位置（拓扑）应该被保留并且它们应该位于正方形中。

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

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

Answer 1

A good suggestion is Lloyd's algorithm. However, the "neighbor preserving" property you're asking for is not clear.

However, if what you're asking is the following:

Given a graph (V, E) where V consists in points of [0,1]^2 and E are segments, and no two segments' interior intersect (ie. we have a planar graph) move the points as evenly as possible, preserving the planar property

then Lloyd's algorithm will do.

Aside: Generalizations are not in term of what space points lie in, but what density you request for the points (you may want Gaussian measures on R^n for instance).

Answer 2

这是一个可能的策略的草图。

在您的原始点集 P 中，从正方形的边界添加一些点（至少是正方形的顶点）。点应该从边界均匀采样，如果原来有n个点，应该至少有√n个额外的点从边界采样。称此增广集 Q。

然后对 Q 进行Delaunay 三角剖分。我们将在下一步中使用该三角剖分的边。

现在进行最小二乘最小化以找到 P 中的点的位置（保持 QP 中的点固定），使边长的平方和最小化。

您可以通过求解矩阵表达式来解决此最小化问题，因此这是“直接解决方案”。

最小二乘问题的解决方案将倾向于使边缘的长度相等。所以小边会变大，大边会变小。这将具有更均匀地分布您的点的效果，同时保留它们的拓扑。

这很容易推广到更高的维度。