拓撲，縮放

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中的點固定），使邊長的平方和最小。

您可以通過求解矩陣式解決這個最小化問題，所以這是一個「直接的解決方案」。

最小二乘問題的解決方案將傾向於均衡邊的長度。所以小邊緣會變大，而大邊緣會變小。這將有更均勻的分佈點，同時保留其拓撲的效果。

這容易推廣到更高維度。