geometry - 拡散2Dポイント分布のアルゴリズム

Question

2Dピクセル配列では、最も広がっているピクセルのp％を選択する効率的なアルゴリズムが必要です。

これは、ポイントを選択し、互いに近すぎるポイントの位置を繰り返し調整することで、適応的に行うことができます。しかし、これは多くの反復と距離計算を必要とするため、効率的ではありません。

完璧である必要はありません。効率的に実行できる限り、ポイントクラスターを回避する必要があります。

score 1 · Accepted Answer

答えてくれたみんなに感謝します！

最善の解決策は、「事前に構築されたビルディングブロック」を使用することであると思われます。すでに選択されたセルを持つnxn配列であり、ピクセル配列をこれらでカバーします。

たとえば、カバレッジが12.5％の4x4アレイは次のようになります。

カバレッジが6.3％の場合：

これらの間の％カバレッジを取得するには、これまでの全体的な実際の％カバレッジの実行中の集計に従って、これらのブロックを交互に切り替えます。4の倍数ではない幅をカバーするには、3x3ブロックを使用します。より広い領域をより効率的にカバーするには、より大きなブロックを使用するだけです。

これは、距離計算や浮動小数点演算なしで、アレイ全体を効率的にカバーします。

score 1 · Accepted Answer

「最も広がった」ピクセルの選択は、ドロネー三角形分割が正三角形で構成されるセットです。この三角形分割につながるポイントのセットは、ピクセル配列をボックスのセットに分割することによって検出されます。各ボックスは、幅よりも sqrt(3) 長くなっています。各ボックスは、最終的なピクセルセットに 5 ピクセルを提供します (各コーナーに 1 つと、ボックスの中心にある中央ノード)。秘訣は、この 1:sqrt(3) の比率が得られるボックスの行と列の数を見つけることです。派生を経由せずに、これを取得する方法は次のとおりです。

std::vector<PixelIndices> PickPixels(int width, int height, float percent)
{
  int total_pixels = width*height;
  int desired_pixel_count = (int)total_pixels*percent;

  // split the region up into "boxes" with 4 corner nodes and a center node.
  // each box is sqrt(3) times taller than it is wide.

  // calculate how many columns of boxes
  float a = 1.155*height/(float)width;
  float b = .577*height/(float)width + 1;
  float c = 1 - desired_pixel_count;
  int num_columns = (int)((-b + sqrt(b*b -4*a*c))/(2*a));

  // Now calculate how many rows
  int num_rows = .577*height*num_columns/(float)width;

  // total number of pixels
  int actual_pixel_count = 2*num_rows*num_columns + num_rows + num_columns + 1;

  std::cout << "  Total pixels: " << total_pixels << std::endl;
  std::cout << "       Percent: " << percent << std::endl;
  std::cout << "Desired pixels: " << desired_pixel_count << std::endl;
  std::cout << " Actual pixels: " << actual_pixel_count << std::endl;
  std::cout << "   Number Rows: " << num_rows << std::endl;
  std::cout << "Number Columns: " << num_columns << std::endl;

  // Pre-allocate space for the pixels
  std::vector<PixelIndices> results;
  results.reserve(actual_pixel_count);

  // Now get the pixels, my integer math is probably wrong here, didn't test
  //  (didn't even finish, ran out of time)
  for (int row = 0; row <= num_rows; row++)
  {
    int row_index = row*height/num_rows;

    // Top of box
    for (int col = 0; col <= num_columns; col++)
    {
      int col_index = col*width/num_columns;
      results.push_back(PixelIndices(row_index, col_index));
    }

    // Middle of box
    if (row != num_columns)
    {
      for (int col = 0; col < num_columns; col++)
      {
         // I'll leave it to you to get this, I gotta go!
      }
    }
  }

  return results;
}

整数除算を使用してインデックスを見つける代わりに、行/列の各ポイント間の距離を見つけてオフセットを追加するだけで、これを高速化できます。

score 1 · Accepted Answer

ポアソンディスク分布が必要ですが、それは難しいです。検索を行うと、それを効率的に行う方法に関する多くの学術論文が見つかります: http://people.csail.mit.edu/thouis/JonesPoissonPreprint.pdf

score 1 · Accepted Answer

かなり古いですが、掘り下げる価値があります。回答は重要な方法を見逃しており、興味のない最適なソリューションに焦点を当てているためです。しかし、私が提案する方法は、ニーズに合う場合と合わない場合があります。

このような問題用に設計された準乱数列を使用できます。最も広く普及しているのはSobol シーケンスで、事実上すべての言語の缶詰パッケージを見つけることができます。それらは非常に高速です。ビット演算のみです。

ほとんどの場合、いくつかのクラスターが生成されますが、これは、x 次元と y 次元に使用する「シード」を事前に選択し、肉眼で確認することで回避できます。

ポイントで何をしたいかによって異なります。「視覚的な広がり」が重要な場合、これはあなたが望むものではないかもしれません. ほぼ均等に「平面を埋める」ポイントが必要な場合、それらは完全に機能します。「通常の」ランダム生成よりも必要なポイントが少ないため、画像上の何かをすばやく平均化するのに特に役立ちます。さまざまな次元を試してみてください。

実験例と写真については、このリンクも参照してください。

score 1 · Accepted Answer

Wang タイルを試すことができます:
http://en.wikipedia.org/wiki/Wang_tile
(Cohen の論文と Kopf の論文にリンクされているページを参照してください。私は新しいユーザーなので、すべてのリンクを投稿することはできません)。

これらは、事前に構築されたタイルのアイデアと、通常はポアソンディスクパターンで解決される均等に分散された要件の両方を結び付けます。Wang タイルは、構築済みタイルを直接使用することでほぼ確実に問題となる周期性の影響を回避できます。

score 0 · Accepted Answer

これはどう：

各ポイントから他のポイントまでの距離の合計を見つけます。したがって、点Aの合計距離はdist（A、B）+ dist（A、C）+ dist（A、D）+..です。
これらの合計距離を並べ替えます。
目的のパーセンテージに達するまで、距離の合計が最小のポイントを削除します。

これは十分に正確かもしれませんが、そうでない場合は、いつでも手順3を次のように置き換えることができます。

「合計が最小のポイントを削除します。目的のパーセンテージに到達するためにさらにポイントを削除する必要がある場合は、手順1に戻ります。」

待って。今、私は疑問に思っています。特定のポイントのセットから最も広がっているポイントを見つけようとしていますか...または、特定の配列から、最も広がっているポイントを見つけようとしていますか？それは完全に異なります...そしてそれでも本当に難しいです。

score 0 · Accepted Answer

他のすべてのピクセルへの近接度に基づいて、最初に各ピクセルの「密度」値を計算するのはどうですか。次に、リストに残っているp％を下回るまで、最も「密度の高い」ピクセルを繰り返し削除します。

任意の2点間の密度を最大2回決定するには、距離の計算を行う必要があります。最初は、元のリストを作成するときです。各ピクセルを他のピクセルと比較する必要があります。2つ目は、リストからピクセルを削除する場合です。リストに残っている各ピクセルに対して、削除されたピクセルを計算する必要があります。これは、各ピクセルが削除されるときに変化する密度値を説明するためです。たとえば、隣接する2つのピクセルの値は非常に高くなりますが、1つを削除すると、残りのピクセルの値は非常に低くなる可能性があります。

いくつかの簡単な擬似コード（この例では、密度の高い領域の数が少ないことに注意してください）

For I = 0 to MaxPixel
    For J = I to MaxPixel
        PixelDensity[I], PixelDensity[J] += DistanceBetween(Pixels[I], Pixels[J])

While PixelDensity.Count > TargetCount
    RemovePixel = IndexOfSmallest(PixelDensity)
    ForEach I in PixelDensity
        PixelDensity[I] -= DistanceBetween(Pixels[I], Pixels[RemovePixel])
    PixelDensity.Remove(RemovePixel)

メモリが計算時間よりも問題にならない場合は、任意の2点間の距離を単純な2次元配列に格納することもできます。また、単純な距離の代わりに、距離の計算を指数関数的にすることが役立つ場合があります。これにより、2つのポイントがほぼ重なり合っているが、他のすべてから遠く離れていて、両方が通過するようなことは避けられます。

score 0 · Accepted Answer

反復的な掃海艇によるフラッドフィルアプローチは、簡単に視覚化できます。

各セルについて、最も近い 2 つの点を見つけ、それら 2 つの距離の積を記録します。
最高の製品を持つセルは、最も遠い点に接続されているセルです。

score 0 · Accepted Answer

凸包アルゴリズムを使用して、このアルゴリズムが計算するポイントを除外し、p% 基準に達する限り繰り返すことができます。

凸包アルゴリズムのステップを実行し、100% - p% の条件を満たしているかどうか、包内とその内部に含まれるポイントをチェックします。

凸包のいくつかのデモはこちら http://www.cs.unc.edu/~snoeyink/demos/

そして、ここにいくつかの詳細情報があります http://softsurfer.com/Archive/algorithm_0109/algorithm_0109.htm

score 0 · Accepted Answer

おお！これはどう！

（あなたの行列が正方形か何かわからないので、非常に手の込んだ方法で...私はそれを仮定します。）

47 ポイントを配置したい 1000x1000 配列があるとします (47 を選んでいるのは、「うまく」適合しない異常な数になるためです)。

ceil(sqrt(47))... を取得すると、値 (7) が得られます。そこで、7x7 の正方形を作成し、47 ピクセル (一部は空白) で塗りつぶし、それを配列の隅に配置することを想像してください。

ここで、小さい (7x7) 配列から大きい配列 (1000x1000) にある場所に基づいて、これらの各ピクセルを新しい場所に変換します。簡単な方程式でこれを行う必要があります... X 座標については、たとえば、次のようになります。

xBigArrayIndex = xSmallArrayIndex * 1000 / 7;

次に、ピクセルが非常に広がります！しかも速くてうまい。

唯一の欠点は、正方形が最初から理想的な間隔で配置されている場合にのみ完全に機能することです...素朴に（左上から始めて、横に移動するなど）埋めると、わずかに理想以下になります。スプレッド...変換されたピクセルが大きな配列の右下に完全に到達しないためです。でもこれでいいのかな。そうでない場合は、対処しやすい問題のサブセットの方が小さいのではないでしょうか?

geometry - 拡散2Dポイント分布のアルゴリズム

10 に答える 10

Related

Reference