10

フライトシムのウェイポイントにランダムな場所を設定できる必要があります。数学の課題は簡単です。

「四角形内の単一のランダムな場所を見つけること。ポイントが任意の場所にある可能性が同じです。」

視覚的にこのように：

代替テキスト

ABCD四角形の例は次のとおりです。A：[21417.78 37105.97] B：[38197.32 24009.74] C：[1364.19 2455.54] D：[1227.77 37378.81]

あなたが提供できるどんな助けにも前もって感謝します。:-)

編集お返事ありがとうございます。私は週末にこれを見て、その時に受け入れられた答えを授与します。ところで、四角形は凸面または凹面にすることができることを述べておかなければなりません。Sry'試合データ。

4

9 に答える 9

9

四角形を2つの三角形に分割し、この優れたSO回答を使用して、そのうちの1つでランダムな点をすばやく見つけます。

アップデート：

三角形の中のランダムな点を選ぶ際に、Akuseteからこの素晴らしいリンクを借ります。

メインフィギュア
（MathWorldから-Wolfram Webリソース：wolfram.com）

原点に1つの頂点があり、位置v1とv2に他の頂点 がある三角形 がある 場合、A1 とA2が 間隔[ 0,1 ]、四辺形に均一に分布した点を与えます（左図）。三角形の内部にないポイントは、破棄するか、三角形の内部の対応するポイントに変換することができます（右図）。バツ

于 2010-06-17T01:03:42.323 に答える
4

この問題を解決するには、2 つの適切な方法があると思います。

他のポスターが最初に言及したのは、長方形を囲む最小の境界ボックスを見つけて、長方形の内側にあるポイントが見つかるまでそのボックスにポイントを生成することです。

  Find Bounding box (x,y,width, height)
  Pick Random Point x1,y1 with ranges [x to x+width] and [y to y+height]
  while (x1 or y1 is no inside the quadrangle){
       Select new x1,y1
  }

四角形の領域が Q で、境界ボックスが A であると仮定すると、N 個の点のペアを生成する必要がある確率は 1-(Q/A)^N であり、逆指数関数的に 0 に近づきます。

特に二次元では、上記のアプローチをお勧めします。ポイントの生成とテストは非常に高速です。

終了の保証が必要な場合は、四角形内のポイントのみを生成するアルゴリズムを作成できますが (簡単です)、ポイントの確率分布が四角形外であることを確認する必要があります。

http://mathworld.wolfram.com/TrianglePointPicking.html

とても良い説明をしてくれます

于 2010-06-17T01:09:03.887 に答える
3

「強引な」アプローチは、有効な座標が得られるまで単純にループすることです。擬似コード:

left   = min(pa.x, pb.x, pc.x, pd.x)
right  = max(pa.x, pb.x, pc.x, pd.x)
bottom = min(pa.y, pb.y, pc.y, pd.y)
top    = max(pa.y, pb.y, pc.y, pd.y)
do {
    x = left   + fmod(rand, right-left)
    y = bottom + fmod(rand, top-bottom)
} while (!isin(x, y, pa, pb, pc, pd));

「isin」はネットから引っ張ってきたストック機能が使えます。これが世界で最も速く実行できるものではないことはわかっていますが、うまくいくと思います。

于 2010-06-17T00:43:56.037 に答える
2

したがって、今回は、ポイントがクワッド内にあるかどうかを判断する方法に取り組みます。

y = mx + b4つのエッジは、フォームの線として表すことができます。ポイントが4本の線のそれぞれの上にあるか下にあるかを確認し、まとめると、ポイントが内側か外側かを判断できます。

于 2010-06-17T01:02:50.673 に答える
1

ポリゴン内にあるポイントを見つけた後にのみ停止する、バウンドインボックス内のポイントをランダムに作成できます。

それで：

  1. ポリゴンのすべてのポイントを含むボックスを見つけます。
  2. 以前に見つかったボックスの境界内にランダムなポイントを作成します。ランダム関数を使用して、x値とy値を生成します。
  3. そのポイントがポリゴンの内側にあるかどうかを確認します（ここまたはここで方法を参照してください）
  4. そのポイントがポリゴンストップの内側にある場合は完了です。そうでない場合は手順2に進みます。
于 2010-06-17T01:06:44.180 に答える
1

四角形を複数の図形に分割します。各図形は、1つの辺（または両側）が軸の1つに平行な正多角形です。たとえば、上の図の場合、最初に四角形の内側に収まる最大の長方形を見つけます。長方形はX/Y軸に平行である必要があります。次に、残りの領域に三角形を合わせます。このような三角形は、長方形の各辺に隣接します。

次に、関数を作成するのは簡単です。

1）ランダムに数字を取得します。2）図からランダムな点を見つけます。

＃1で選択した図形が長方形の場合、その中のランダムな点を見つけるのは非常に簡単です。トリッキーな部分は、三角形の内側のランダムな点を見つけることができるルーチンを書くことです

于 2010-06-17T01:07:46.863 に答える
1

クワッド内に何かが得られるまで、四角形の境界となる長方形内のどこかで繰り返し試行することはできますか？クワッド内で何かを確実に選択するために、これはいくつかの派手なアルゴリズムよりもさらに高速でしょうか？

ちなみに、その問題文では、「見つける」という言葉の使用は混乱を招くと思います。条件を満たすランダムな値を実際に見つけることはできません。ランダマイザーはあなたにそれを与えるだけです。あなたがやろうとしているのは、特定の基準に一致する値を与えるためにランダマイザーにパラメーターを設定することです。

于 2010-06-17T00:47:45.017 に答える
0

だから、それはあなたがあなたの配布をどのように望むかに依存します。

2Dビュー空間でポイントをランダムにサンプリングしたい場合は、Jacobの答えが最適です。ポイントをパースビューのようなものにしたい場合（例の画像では、左下よりも右上の密度が高い）、双一次内挿を使用できます。

バイリニア補間は非常に簡単です。[0..1]の範囲で2つの乱数sとtを生成します。次に、入力ポイントがp0、p1、p2、p3の場合、双一次内挿は次のようになります。

bilerp(s,t) = t*(s*p3+(1-s)*p2) + (1-t)*(s*p1+(1-s)*p0)

主な違いは、分布を2次元空間で均一にするか（Jacobの方法）、パラメーター空間で均一にするかです。

于 2010-06-17T05:29:59.390 に答える
0

これは興味深い問題であり、おそらく本当に興味深い答えがありますが、それを機能させたいだけの場合は、簡単なものを提供させてください。

アルゴリズムは次のとおりです。

  1. 四角形の境界となる長方形内にあるランダムな点を選択します。
  2. 四角形（または任意の形状）内にない場合は、繰り返します。
  3. 利益！

編集

Bart K.の提案に従って、最初のステップを更新してバウンディングボックスについて言及しました。

于 2010-06-17T00:45:52.387 に答える