如何在平面图上有效地分配点

Question

我有一个平面（屏幕），它的宽度和高度（显示器分辨率，不是正方形）。我想在这个平面上分布点，使它们之间的距离（大约）相同。

例如：

• 1个点将位于中心位置，
• 2个点将位于y轴中心，而x轴将被分为3部分，
• 3个点可能像三角形一样排列，但如果屏幕足够宽，它们可以对齐在同一y轴上，
• 4个点类似于上面的第二部分，或者作为矩形排列，
• 等等，最多8个点。

是否有算法可以实现这个目标？

谢谢您的时间！

编辑：与平面边界之间的距离也相同

编辑2：我计算了我在平面上模拟行为的对象组的质心。

- Kamil

---

@DoSparKot 刚刚编辑了问题。所以，从两个方面来看：将平面分成矩形并在矩形中找到任意随机点？这将是粗略的近似，但如果我使用这些矩形的中心呢？你觉得呢？ - Kamil

彼此之间和平面边界的距离相同，然后它们就成为每个矩形的中心。这样做会更容易、更快捷。 - जलजनक

对于点数为偶数或边长为偶数的矩形，你无法在正中心放置一个点。然而，等距性质会将它们漂亮地分散在屏幕上。 - जलजनक

@DoSparKot 我计算物体组的质心，模拟它们在平面上的行为。现在我找到了一些有趣的文章，所以当我实现它时，我会发布答案。 - Kamil

请将该信息添加到问题中。这是方法的重要信息。 - जलजनक

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 cell 的质心。这也可以非常高效地完成，可以通过使用牛顿法而不是 Lloyd 迭代来加速。 最终，如果您的域是一个正方形，则应该获得一个六边形网格（它最小化上述功能）。

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

- nbonneel

---

我正在使用您的第二个建议。请看下面我的答案。 - Kamil

Answer 2

如果你有很多点，结果看起来会像一个六边形网格：

http://people.sc.fsu.edu/~jburkardt/m_src/hex_grid/hex_grid.html

否则它会变得更加复杂。一个非常好用的算法（但可能过度复杂）是进行物理模拟，其中点是相互排斥的粒子。查看this video，该视频提供了在球体上执行此操作的示例。

- static_rtti

Answer 3

首先，感谢大家的建议，这些建议帮助我更好地定义了我的问题，并找到了最佳解决方案。

现在我正在使用“重心沃罗诺伊剖分”，根据维基百科的定义：“在几何学中，重心沃罗诺伊剖分（CVT）是一种特殊类型的沃罗诺伊剖分或沃罗诺伊图。当每个沃罗诺伊单元的生成点也是其平均值（质心）时，称为重心沃罗诺伊剖分。它可以被视为对应于发生器的最佳分区，即最佳分布。”

它非常快速，并且在我使用的javascript D3js库中有实现。

- Kamil

Answer 4

编辑：与物理排斥仿真无关。

将平面划分为矩形更易处理。对于边长为偶数的矩形，中心点不能完全重合。但等距性质可以将它们漂亮地分散在屏幕上。

以下是用PHP编写的简单程序来说明这一点：

<?php 
$x_min = 1; $x_max = 1366;

$y_min = 1; $y_max = 768;

$x_div_count = 5;
$y_div_count = 5;

$x_div_len = (integer)round(($x_min + $x_max) / $x_div_count);
$y_div_len = (integer)round(($y_min + $y_max) / $y_div_count);

$x_mid_offset = (integer)round($x_div_len /2);
$y_mid_offset = (integer)round($y_div_len /2); 

$x_offset = $x_mid_offset;
for ($idx =0; $idx < $x_div_count; $idx ++) {

    $y_offset = $y_mid_offset;
    for ($jdx =0; $jdx < $y_div_count; $jdx ++) {

        $points_dist[] = array ('x' => $x_offset, 'y' => $y_offset);

        $y_offset += $y_div_len;
    }
    $x_offset += $x_div_len;
}

var_dump(get_defined_vars());
?>

附注：如果您能够处理子像素渲染，则使用浮点值。这些点通常会模糊，但整体效果很好。

- जलजनक