3

幅と高さ（正方形ではなくモニターの解像度）の平面（画面）があります。そして、その平面上のポイントを（ほぼ）互いに同じ距離で分散させたいと思います。

例えば：

  • 1点が真ん中になり、
  • 2 点が Y 軸の中央になり、X 軸が 3 で分割されます。
  • 3 点は三角形のように見えるかもしれませんが、画面が十分に広い場合は、同じ y に揃えることができます。
  • 4 上記の 2 番目の部分のように、または長方形として..
  • など 最大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

  • ポイントの位置を実際に最適化できます。これは、ロイド アルゴリズムと同様の最適化手順につながります。点の初期セットのボロノイ図を計算し、これらの点をボロノイ セルの重心に移動します。これも非常に効率的に行うことができ、ロイド反復法ではなくニュートン法を使用することで高速化できます。最終的に、ドメインが正方形の場合、六角形のグリッドを取得する必要があります (上記の関数を最小化します)。

おおよその結果のみが必要な場合は、はるかに高速な最初のアプローチをお勧めします。

于 2013-03-04T19:40:41.033 に答える
2

ポイントがたくさんある場合、結果は六角形のグリッドのようになります。

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

それ以外の場合は、より複雑になります。非常にうまく機能するアルゴリズムの 1 つ (ただし、おそらくやり過ぎです) は、ポイントが互いに反発する粒子である物理シミュレーションを実行することです。例として、球体で同じことを行うこのビデオをチェックしてください。

于 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

まず第一に、私の問題をよりよく定義し、私の問題に対する最善の解決策を見つけるのに役立つ提案をしてくれた皆さんに感謝します.

ウィキペディアによると、「ジオメトリでは、重心ボロノイテッセレーション(CVT) は特殊なタイプのボロノイ テッセレーションまたはボロノイ ダイアグラムです。ボロノイ テッセレーションは、各ボロノイ セルの母点も重心である場合、重心と呼ばれます。その平均 (質量の中心)。これは、生成元の最適な分布に対応する最適な分割と見なすことができます。」

その非常に高速で、私が使用している JavaScript の D3js ライブラリに実装があります。

于 2013-03-06T23:08:49.083 に答える