3

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

例如：

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

有什么算法可以解决这个问题吗？

感谢您的时间！

编辑：彼此之间和与平面边界的距离相同

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

4

4 回答 4

4

根据您想要的精度：

  • 您可以通过泊松圆盘采样获得随机正确的答案。具体来说，泊松盘采样是随机采样，使得没有点比指定半径更近。这样的事情可以在高维度上有效地（线性时间）实现 - 例如：来自 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 单元的质心。这也可以非常有效地完成，并且可以通过使用牛顿法而不是劳埃德迭代来加快速度。最终，如果你的域是正方形，你应该得到一个六边形网格（它最小化了上面的函数）。

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

于 2013-03-04T19:40:41.033 回答
2

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

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

否则会变得更复杂。一种效果很好（但可能有点过分）的算法是进行物理模拟，其中点是相互排斥的粒子。看看这个在球体上做同样的视频的例子。

于 2013-03-04T11:03:14.113 回答
1

编辑：不适用于物理排斥模拟。

将平面划分为矩形更容易处理。对于边长均匀的矩形，你不能在中心有一个点。然而，等距属性将它们很好地分散在屏幕上。

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());
?>

PS：如果您可以处理亚像素渲染，那么请使用浮点值。这样的点往往是模糊的，但整体效果很好。

于 2013-03-04T10:53:20.360 回答
0

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

现在我正在使用根据维基百科的Centroidal Voronoi tessellation ： “在几何学中，Centroidal Voronoi tessellation (CVT) 是一种特殊类型的 Voronoi tessellation 或 Voronoi 图。当每个 Voronoi 单元的生成点也是时，Voronoi tessellation 称为质心它的平均值（质心）。它可以被视为对应于发电机的最佳分布的最佳分区。

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

于 2013-03-06T23:08:49.083 回答