拓扑、缩放
假设有一个 2D 平面（正方形），其中有一些点。
如何移动所有点，使其尽可能均匀地填充平面，但每个点都保持其邻居？
换句话说，我希望这些点彼此尽可能远离，但应保留它们的局部性（拓扑）并且它们应位于正方形中。
换句话说，我想放大丰富点密集的区域并缩小空白区域。
PS：高维空间有通用的解决方案吗？有直接的解决方案还是只有迭代的解决方案？
Say there is a 2D plane (square) with some points inside it.
How to move all the points in such a way that they fill the plane as evenly as possible but every point maintains its neighbors?
In other words, I want the points to be as far from each other as possible but their locality (topology) should be preserved and they should lay in the square.
In other words, I want to kind of zoom-in in the rich-point-populated area and zoom out in the empty areas.
PS: is there a general solution for higher-dimension spaces? Is there a direct solution or only iterative one?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
一个很好的建议是Lloyd 算法。然而，您所要求的“邻居保护”财产并不清楚。
但是，如果您要问的是以下内容：
那么劳埃德算法就可以了。
旁白：
概括不是指空间点所在的位置，而是您要求的点的密度（例如，您可能需要 R^n 上的高斯度量）。
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:
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).
这是一个可能的策略的草图。
向原始点集 P 中添加一些来自正方形边界的点（至少是正方形的顶点）。点应从边界均匀采样，如果原来有n个点，则至少应从边界额外采样√n个点。将此增广集称为 Q。
然后对 Q 进行 Delaunay 三角剖分。我们将使用在下一步中进行三角测量。
现在进行最小二乘最小化来找到P中点的位置（将点保留在QP中）固定），最小化边长平方和。
您可以通过求解矩阵表达式来解决这个最小化问题，因此这是一个“直接解”。
最小二乘问题的解决方案将趋向于使边的长度相等。所以小边会变大，大边会变小。这将具有更均匀地分布点的效果，同时保留其拓扑。
这很容易推广到更高的维度。
Here's a sketch of a possible strategy.
To your original set P of points, add some points from the boundary of the square (at a minimum, the vertices of the square). The points should be evenly sampled from the boundary, and if there are originally n points, there should be at least √n additional points sampled from the boundary. Call this augmented set Q.
Then do a Delaunay Triangulation of Q. We'll use the edges from this triangulation in the next step.
Now do a least squares minimization to find the position of the points in P (keeping the points in Q-P fixed) that minimizes the sum of squares of edge lengths.
You can solve this minimization problem by solving a matrix expression, so this is a 'direct solution'.
The solution of the least squares problem will tend to equalize the lengths of the edges. So small edges will become larger and large edges will become smaller. This will have the effect of more uniformly distributing your points while preserving their topology.
This generalizes easily to higher dimensions.