algorithm - 如何在平面上有效分配点

Question

我有一个平面(屏幕)及其宽度和高度(显示器分辨率，而不是正方形)。我想在该平面上以彼此之间(大约)相同的距离分布点。

例如:

• 1分在中间，
• 2个点在y轴中间，x轴除以3
• 3个点可能像三角形，但如果场景足够宽，可以在同一个y轴上对齐
• 4 就像上面的第二部分，或者是矩形..
• 等等，最多 8 分

有什么算法吗？

感谢您的宝贵时间!

编辑:彼此和平面边界的距离相同

EDIT2: 我计算我在平面上模拟行为的对象组的质心。

Answer 1

取决于你想要的精度:

• 您可以通过泊松圆盘采样获得随机正确答案。具体来说，泊松圆盘采样是一种随机采样，使得没有点比指定半径更近。这样的事情可以在高维中有效地(线性时间)实现——例如: 来自 Robert Bridson 的 C++ 代码:http://www.cs.ubc.ca/~rbridson/download/curlnoise.tar.gz实现他的论文 http://www.cs.ubc.ca/~rbridson/docs/bridson-siggraph07-poissondisk.pdf

• 你真的可以针对点的位置进行优化。这导致 Lloyd 算法和类似的优化程序:计算一组初始点的 Voronoi 图，并将这些点移动到其 Voronoi 单元的质心。这也可以非常有效地完成，并且可以通过使用牛顿法而不是劳埃德迭代法来加速。最终，如果您的区域是正方形，您应该获得一个六边形网格(它最小化了上面的函数)。

如果您只需要近似结果，我建议使用第一种方法，它应该更快。