47

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

それが本当に問題を単純化するのであれば、ポリゴンを平行四辺形に制限することができますが、より一般的な答えが好まれます。

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

4

11 に答える 11

44

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 = a0 (v1-v0) + a1 (v2-v0) によってランダムポイント x を計算します。

    ここに画像の説明を入力

  5. 確率 0.5 の場合、x は三角形の外側にあることに注意してください。ただし、そうである場合は、(v1,v2) の中点を中心に pi を回転させた後の三角形とそのイメージの結合で構成される平行四辺形の内側にあることに注意してください (破線)。画像で）。その場合、新しい点 x' = v0 + R(pi)(x - v3) を生成できます。ここで、R(pi) は pi (180 度) の回転です。点 x' は三角形の内側になります。

  6. さらに、四角形がすでに平行四辺形である場合、三角形をランダムに選択する必要はなく、決定論的にいずれかを選択し、ソース三角形の内側にあるかどうかをテストせずに点 x を選択できることに注意してください。

于 2011-12-07T18:18:38.323 に答える
29

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.これで、できない場合でも、重心座標を使用できます。重心座標は、クワッドの場合、次のような4つの座標に対応(a,b,c,d)しa+b+c+d=1ます。次に、クワッド内の任意のポイントPは、次のように4つのupleで記述できます。

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

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

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

于 2008-10-27T17:43:46.870 に答える
18

均一な分布が必要であると仮定すると、ポリゴンから 2 つの三角形を形成します。面積比に従って、ポイントを生成する三角形を選択します。

三角形 A、B、C の角を辺ベクトル AB、BC、AC と呼び、[0,1] に u と v という 2 つの乱数を生成します。p = u * AB + v * AC とします。

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

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

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

于 2008-10-27T18:09:42.170 に答える
4

ポリゴンは2つの三角形なので、そのうちの1つをランダムに選択してから、三角形の中でランダムな点を見つけてください。

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

于 2008-10-27T17:46:16.397 に答える
2

やや「ナイーブ」なアプローチは、ポリゴン塗りつぶしアルゴリズムを使用してから、塗りつぶし線からランダムにポイントを選択することです。

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.
于 2008-10-27T17:44:40.830 に答える
2

「一般的」とは、一般的なすべての非平行四辺形の 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);

}
于 2008-10-27T18:09:37.427 に答える
2

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

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

基本的なレシピ:

  1. 適切な乱数発生器を選択して、正方形の 2D ドメインで適切に分散された点を生成します
  2. [-1, 1] の範囲でランダムな UV ペアを生成します
  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)

唯一の問題は、UV 空間に均一に分散されたポイントがクワッドに均一に分散されたポイントを生成しないことです (ユークリッドの意味で)。それが重要な場合は、クワッドのバウンディング ボックス内で 2D で直接作業し、クワッド内のポイント テストを作成して (問題を 3 つのポイントに分割することによって)、外側にあるランダムなポイントをカリングすることができます。

于 2011-01-14T03:20:46.327 に答える
1

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

ポリゴンは凹面にすることができますか、それとも凸面にすることが保証されていますか？

上記の両方の答えが「いいえ」の場合は、頂点のいずれか2つを選択し、それらの間の線分上のランダムな点を選択します。これは、頂点を接続するラインセグメントに限定されます（つまり、非常に不均一です）。3番目の頂点を選択してから、その頂点と最初の点の間の点を選択することで、もう少しうまくいくことができます。それでも不均一ですが、少なくともポリゴン内の任意の点が可能です。

2つのポイント間の線上のランダムなポイントを選択するのは簡単です。A+p（BA）です。ここで、AとBはポイントであり、pは0.0から1.0の間の乱数です。

于 2008-10-27T17:54:19.283 に答える
1

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

于 2008-10-27T18:08:34.043 に答える
1

MATLAB 関数cprndは、一般凸多面体の一様分布から点を生成します。あなたの質問では、四角形を三角形に分解することに基づくより特殊なアルゴリズムがより効率的です。

于 2012-01-07T15:50:37.103 に答える
0

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;
于 2011-04-13T12:13:14.313 に答える