平行四辺形内のランダムポイント

StackOverflow https://stackoverflow.com/questions/240778

質問

2Dの4点で定義された4辺の凸多角形があり、その中にランダムな点を生成できるようにしたい。

実際に問題を単純化する場合、ポリゴンを平行四辺形に制限できますが、より一般的な答えが望ましいです。

ポリゴン内にランダムポイントを生成することは、時間がかかることが予測できないため、機能しません。

役に立ちましたか？

解決

A。入力を平行四辺形に制限できる場合、これは本当に簡単です：

  1. 0と1の間の2つの乱数を取得します。次にuとvを呼び出します。

  2. 平行四辺形がABCDによって定義され、AB、BC、CD、およびDAが側面である場合、次のように点を取ります。

     p = A + (u * AB) + (v * AD)

ABはAからBへのベクトル、AD AからDへのベクトルです。

B。これで、できない場合でも、重心座標を使用できます。クワッドの重心座標は、(a,b,c,d)のような4つの座標a+b+c+d=1に対応します。次に、クワッド内の任意のポイントPは、次のような4つのアップルで記述できます。

P = a A + b B + c C + d D

あなたの場合、4つの乱数を描画し、それらを合計して1になるように正規化することができます。その場合、ポイントの分布は均一ではないことに注意してください。

C。他で提案されているように、クワッドを2つの三角形に分解し、半平行四辺形法（つまり、平行四辺形として条件u+v=1を追加）または三角形の重心座標を使用することもできます。ただし、均一な分布が必要な場合、三角形の1つに点がある確率は、三角形の面積を四角形の面積で割ったものと等しくなければなりません。

他のヒント

OPによる質問は少し曖昧なので、答える質問は次のとおりです。任意の四辺形内の均一な分布からポイントを生成する方法。これは実際にはの一般化です。任意の（凸）ポリゴン内の均一な分布からポイントを生成する方法。答えは、三角形内の均一な分布からサンプルを生成する場合に基づいています（ http：// mathworldを参照してください.wolfram.com / TrianglePointPicking.html 、非常に良い説明があります）。

これを達成するために：

  1. 多角形を三角形化します（つまり、多角形をカバーする重複しない三角形領域のコレクションを生成します）。四辺形の場合、エッジ全体を作成します 任意の2つの非隣接頂点。他のポリゴンについては、 http://en.wikipedia.org/wiki/Polygon_triangulation を参照してください。ポイント、またはライブラリが必要な場合は http://www.cgal.org/ を参照してください。

    ここに画像の説明を入力

  2. 三角形の1つをランダムに選択するには、各三角形にインデックスを割り当てます（つまり、0,1,2、...）。四辺形の場合、それらは0.1になります。各三角形に対して、次のように等しい重みを割り当てます。

    重量計算

  3. 次に、重みが与えられたインデックスの有限分布からランダムインデックスiを生成します。四辺形の場合、これはベルヌーイ分布です。

    ここに画像の説明を入力

  4. v0、v1、v2を三角形の頂点（点の位置で表されるため、v0 =（x0、y0）など）とします。次に、両方から一様に描かれた2つの乱数a0およびa1を生成します。間隔[0,1]。次に、ランダムポイントxをx = a0（v1-v0）+ a1（v2-v0）で計算します。

    ここに画像の説明を入力

  5. 確率0.5では、xは三角形の外側にありますが、三角形の場合は、（v1の中点を中心としたpiの回転後の三角形と画像の結合で構成される平行四辺形の内側にあります、v2）（画像内の破線）。その場合、新しいポイントx '= v0 + R（pi）（x-v3）を生成できます。ここで、R（pi）はpi（180度）の回転です。点x 'は三角形の内側になります。

  6. さらに、四辺形がすでに平行四辺形であった場合、三角形をランダムに選択する必要はありません。決定的に三角形を選択し、その中にあることをテストせずに点xを選択できますソースの三角形。

均一な分布が必要な場合：ポリゴンから2つの三角形を形成します。面積比に応じてポイントを生成する三角形を選択します。

三角形A、B、Cの角、サイドベクトルAB、BC、ACを呼び出し、uおよびvと呼ばれる[0,1]の2つの乱数を生成します。p= u * AB + v * ACとします。

A + pが三角形の内側にある場合、A + pを返します

A + pが三角形の外側にある場合、A + AB + AC-pを返します

（これは基本的にPierreBdRの公式です。ただし、前処理と、ポイントを三角形に折り返す最後のステップを除いて、平行四辺形以外の形状を処理できます。）

多角形は2つの三角形なので、そのうちの1つをランダムに選択して、三角形内のランダムなポイントを見つけてください。

おそらく最善の解決策ではありませんが、うまくいくでしょう。

やや少ない<！> quot; na <！>＃239; ve <！> quot;アプローチは、ポリゴンフィルアルゴリズムを使用し、フィルラインからランダムにポイントを選択することです。

Cコードサンプル

//  public-domain code by Darel Rex Finley, 2007

int  nodes, nodeX[MAX_POLY_CORNERS], pixelX, pixelY, i, j, swap ;

//  Loop through the rows of the image.
for (pixelY=IMAGE_TOP; pixelY<IMAGE_BOT; pixelY++) {

  //  Build a list of nodes.
  nodes=0; j=polyCorners-1;
  for (i=0; i<polyCorners; i++) {
    if (polyY[i]<(double) pixelY && polyY[j]>=(double) pixelY
    ||  polyY[j]<(double) pixelY && polyY[i]>=(double) pixelY) {
      nodeX[nodes++]=(int) (polyX[i]+(pixelY-polyY[i])/(polyY[j]-polyY[i])
      *(polyX[j]-polyX[i])); }
    j=i; }

  //  Sort the nodes, via a simple “Bubble” sort.
  i=0;
  while (i<nodes-1) {
    if (nodeX[i]>nodeX[i+1]) {
      swap=nodeX[i]; nodeX[i]=nodeX[i+1]; nodeX[i+1]=swap; if (i) i--; }
    else {
      i++; }}

  //  Fill the pixels between node pairs.
  //  Code modified by SoloBold 27 Oct 2008
  //  The flagPixel method below will flag a pixel as a possible choice.
  for (i=0; i<nodes; i+=2) {
    if   (nodeX[i  ]>=IMAGE_RIGHT) break;
    if   (nodeX[i+1]> IMAGE_LEFT ) {
      if (nodeX[i  ]< IMAGE_LEFT ) nodeX[i  ]=IMAGE_LEFT ;
      if (nodeX[i+1]> IMAGE_RIGHT) nodeX[i+1]=IMAGE_RIGHT;
      for (j=nodeX[i]; j<nodeX[i+1]; j++) flagPixel(j,pixelY); }}}

   // TODO pick a flagged pixel randomly and fill it, then remove it from the list.
   // Repeat until no flagged pixels remain.

<！> quot; general <！> quot;一般的なすべての非平行四辺形の4辺ポリゴンまたはすべての可能なポリゴンを意味しますか？

4辺をつなぐランダムな線を描くのはどうですか？これがある場合：

.BBBB.
A    C
A    C
.DDDD.

次に、単位正方形上にランダムなポイントを生成し、X軸上の距離の割合でラインBおよびD上のポイントをマークします。 Y軸の値を使用して、ラインAとCで同じことを行います。

次に、ラインAのポイントをラインCに接続し、ラインBをラインDに接続すると、交点がランダムポイントとして使用されます。

丸め誤差は特定のポイントを支援するため、均一ではありませんが、浮動小数点値を操作している場合は近いはずです。

すでにポリゴンを使用しているため、実装もかなり簡単です。これらの簡単なタスクを実行するコードが既にあるはずです。

簡単な擬似コードを次に示します。

void GetRandomPoint(Polygon p, ref float x, ref float y) {

    float xrand = random();
    float yrand = random();

    float h0 = p.Vertices[0] + xrand * p.Vertices[1];
    float h1 = p.Vertices[2] + yrand * p.Vertices[3];

    float v0 = p.Vertices[0] + xrand * p.Vertices[2];
    float v1 = p.Vertices[1] + yrand * p.Vertices[3];

    GetLineIntersection(h0, h1, v0, v1, x, y);

}

これは、一般的な凸四角形に対して機能します：

有限要素法から、特に四辺形（4面）要素（ セクション16.5を参照 ）。基本的に、uv空間の正方形（この場合u、v \ in [-1、1]）を点p_i（i = 1,2,3,4で構成される）にマッピングする双一次パラメーター化があります。 ）。提供されたリファレンスでは、パラメーターは\ etaおよび\ xiと呼ばれます。

基本的なレシピ：

  1. 適切な乱数ジェネレーターを選択して、正方形の2Dドメインで十分に分散したポイントを生成します
  2. 範囲[-1、1]でランダムなu-vペアを生成します
  3. 各UVペアについて、クワッドの対応するランダムポイント= 1/4 *（（1-u）（1-v）* p_1 +（1 + u）（1-v）* p_2 +（1+ u）（1 + v）* p_3 +（1-u）（1 + v）* p_4）

唯一の問題は、u-v空間で均一に分布する点が、クワッドで均一に分布する点を生成しないことです（ユークリッドの意味で）。それが重要な場合は、クワッドの境界ボックス内で2Dで直接作業し、ポイントインクワッド（問題をトリスで2つのポイントに分割することにより）テストを書いて、外側にあるランダムなポイントをカリングできます。

ポイントは均一に分布する必要がありますか、それとも分布は大丈夫ですか？

多角形を凹面にすることはできますか、それとも凸面になることを保証しますか？

上記の両方の答えが「いいえ」の場合、頂点の任意の2つを選択し、それらの間の線分上でランダムな点を選択します。これは、頂点を結ぶ線分に限定されます（つまり、非常に不均一です）。 3つ目の頂点を選択し、その点と最初の点の間の点を選択することで、少し改善できます-まだ不均一ですが、少なくともポリゴン内の任意の点が可能です

2つのポイント間の線でランダムポイントを選択するのは簡単です。A+ p（B-A）で、AとBはポイントで、pは0.0〜1.0の乱数です

ポイントにどのような分布を持たせたいですか？気にしない場合は、上記の方法で問題なく動作します。均一な分布が必要な場合、次の手順を実行します。ポリゴンを2つの三角形、aとbに分割します。 A（a）とA（b）をそれぞれのエリアとします。 0とA（a）+ A（b）の間の間隔で均一分布から点pをサンプリングします。 p <！> lt; A（a）、三角形aを選択します。それ以外の場合は、三角形bを選択します。選択した三角形の頂点vを選択し、三角形の辺に対応するベクトルをcとdにします。単位平均の指数分布から2つの数値xとyをサンプリングします。次に、ポイント（xc + yd）/（x + y）は、ポリゴン上の均一な分布からのサンプルです。

MATLAB関数 cprnd は、上の均一分布からポイントを生成します。一般的な凸ポリトープ。四角を三角形に分解することに基づいた、より専門的なアルゴリズムの方が効率的です。

PostGISの場合、これは私が使用しているものです（無限ループが発生する可能性がある場合は、病棟が必要な場合があります）。アルゴリズムをプログラミング言語にエクスポートできます：

CREATE or replace FUNCTION random_point(geometry)
RETURNS geometry
AS $$
DECLARE 
    env geometry;
    corner1 geometry;
    corner2 geometry;
    minx real;
    miny real;
    maxx real;
    maxy real;
    x real;
    y real;
    ret geometry;
begin

select ST_Envelope($1) into env;
select ST_PointN(ST_ExteriorRing(env),1) into corner1;
select ST_PointN(ST_ExteriorRing(env),3) into corner2;
select st_x(corner1) into minx;
select st_x(corner2) into maxx;
select st_y(corner1) into miny;
select st_y(corner2) into maxy;
loop
    select minx+random()*(maxx-minx) into x;
    select miny+random()*(maxy-miny) into y;
    select ST_SetSRID(st_point(x,y), st_srid($1)) into ret;
    if ST_Contains($1,ret) then
        return ret ;
    end if;
end loop;
end;
$$
LANGUAGE plpgsql
volatile
RETURNS NULL ON NULL INPUT;
ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top