9

ポリゴン内に均等に分散されたポイントを生成するアルゴリズムを探しています。

シナリオは次のとおりです。

各ポイントのコーナー (x、y) のポイントの座標で指定されたポリゴンがあります。そして、ポリゴン内に生成するポイントの数があります。

たとえば、5 つのポイント (1, 1) を含むポリゴンがあるとします。(1, 2) ; (2, 3) ; (3, 2) ; と (3, 1)

そして、そのポリゴン内に 20 個の等間隔のポイントを生成する必要があります。

注: 一部のポリゴンは、均等に分散されたポイントをサポートしていない場合がありますが、ポリゴンのすべての領域を可能な限り一貫してカバーする方法でポイントを分散しようとしています。(私が言いたいのは、他のパーツよりも多くのポイントを持つパーツが欲しくないということです)

そうするアルゴリズムはありますか？または多分図書館

私は C# アプリケーションに取り組んでいますが、アルゴリズムだけが必要で、翻訳できるので、どの言語でも構いません。

助けてくれてありがとう

4

7 に答える 7

14

私が使用する簡単なアプローチは次のとおりです。

  1. ポリゴンを三角形化します。耳のクリッピングは完全に適切です。必要なのは、ポリゴンを重複しない一連の三角形に分割することだけだからです。

  2. 各三角形の面積を計算します。全体に対するその三角形の面積に比例して、各三角形からサンプリングします。これには、サンプルごとに 1 つの一様乱数しかかかりません。

  3. ポイントが特定の三角形に由来すると判断されたら、三角形全体を均一にサンプリングします。これ自体は、思ったより簡単です。

つまり、すべては三角形内でどのようにサンプリングするかにかかっています。これは簡単に実行できます。三角形は 3 つの頂点によって定義されます。それらを P1、P2、P3 と呼びます。

  1. 三角形の任意のエッジを選択します。そのエッジに沿って一様にある点 (P4) を生成します。したがって、P1 と P2 が対応する端点の座標である場合、r が区間 [0,1] で均一に分布している場合、P はそのエッジに沿って均一にサンプリングされた点になります。

    P4 = (1-r)*P1 + r*P2

  2. 次に、P3 と P4 の間の線分に沿ってサンプリングしますが、不均一に行います。s が区間 [0,1] の一様乱数の場合、

    P5 = (1-sqrt(s))*P3 + sqrt(s)*P4

もちろん、r と s は独立した疑似乱数です。次に、P5 がランダムにサンプリングされ、三角形全体で均一になります。

良いことは、実装に拒否スキームが必要ないことです。そのため、長くて薄いポリゴンは問題になりません。また、各サンプルのコストは、イベントごとに 3 つの乱数を生成する必要がある場合のみです。耳のクリッピングはかなり単純で効率的なタスクであるため、見栄えの悪いポリゴンや非凸ポリゴンの場合でも、サンプリングは効率的です。

于 2012-06-24T16:04:04.750 に答える
4

これを行う簡単な方法は次のとおりです。

  1. 境界ボックスを計算する
  2. そのボックスでポイントを生成します
  3. 関心のあるポリゴンにないすべてのポイントを破棄します

このアプローチでは、一定量の無駄なポイントが生成されます。三角形の場合、50% を超えることはありません。任意のポリゴンの場合、これは任意に高くなる可能性があるため、それが機能するかどうかを確認する必要があります.

任意のポリゴンの場合、最初にポリゴンを三角形に分解して、無駄なポイントの上限を保証することができます: 50%。

等距離のポイントの場合、空間充填曲線からポイントを生成します (そして、ポリゴンにないすべてのポイントを破棄します)。

于 2012-06-24T15:27:08.543 に答える
0

簡単な答えは、より簡単な質問から得られます。指定されたポリゴン内にすべて収まる一様分布から、指定された数のランダムに分散されたポイントを生成する方法は?

簡単な答えは次のとおりです。ポリゴンの境界ボックスを見つけて ([a,b] x [c,d] としましょう)、実数のペアを生成し続けます。1 つは U(a,b) から、もう 1 つはポリゴン内に収まる n 個の座標ペアが得られるまで、U(b,c)。これはプログラムするのは簡単ですが、多角形が非常にぎざぎざしていたり​​、細くて歪んでいたりすると、非常に無駄が多く遅くなります。

より良い答えを得るには、最小の回転した長方形の境界ボックスを見つけ、変換された座標で上記を実行します。

于 2012-06-24T17:57:04.337 に答える
-2

  1. 遺伝的アルゴリズムはそれをかなり迅速に行うことができます
    GENETIC ALGORITHMS FOR GRAPH LAYOUTS WITH GEOMETRIC CONSTRAINTSを参照してください

  2. そのためにForce-Directed Graphを使用できます... http://en.wikipedia.org/wiki/Force-based_algorithms_(graph_drawing)
    を見てください 。

試したことはありません
が、グラフのいくつかの頂点に修正を設定する可能性があることを覚えています

あなたのアルゴリズムは最終的に次のようになります

  1. グラフを作成する G = V の頂点の閉じたパス
  2. 頂点を所定の位置に固定します
  3. グラフに N 個の頂点を追加し、それらを等しい張力値 1.0 のエッジで完全に接続します。
  4. Run_force_graph(G)

グラフを境界のあるボックスにスケーリング

いくつかの凸形状がより複雑な結果を生成する可能性があるため、絶対ではありませんが（星を取る）

最後に: は読みませんでしたが、タイトルとアブストラクトから関連性が
あるよう です。加重グラフの一貫したグラフ レイアウトをご覧ください

お役に立てれば...

于 2012-06-24T16:00:16.593 に答える
-4

より良い答えは、より良い質問から生まれます。多角形をカバーするために n 個の監視塔のセットを配置するとします。これを最適化問題と見なすことができます。目標に適合するコスト関数を最小化する (または値関数を最大化する) n 点の 2n 座標を見つけます。考えられるコスト関数の 1 つは、各ポイントについて、最も近い隣接点またはポリゴンの境界のいずれか小さい方までの距離を計算し、このシーケンスの分散を「不均一性」の尺度として計算することができます。上記のように取得した n 個の点のランダムなセットを初期解として使用できます。

ある本でそのような「ものみの塔問題」を見たことがあります。アルゴリズム、微積分、または最適化。

@Youssef: 遅れて申し訳ありません。友人が来て、ネットワークがしゃっくりしました。

@others: 辛抱強く待ってください。トリガーに満足しないでください。

于 2012-06-24T18:10:06.470 に答える