6

ポイントが平行四辺形/菱形の内側にあるかどうかを判断する最も速い方法は何ですか？

4

9 に答える 9

16

こんにちは。すべての回答に感謝します。その間に、私自身、かなり速いと思うものを思いついた。

PQとPRにまたがる平行四辺形があるとします。ここで、PQとPRはベクトルです（P、Q、Rはコーナーです）。さらに、Aと呼ばれるチェックしたいポイントがあります。

ベクトルPAは、PQとPRに平行な2つのベクトルに分割できることがわかっています。

PA=n*PQ+m*PR

これで、nとmは区間[0; 1]、nとmを解きます：

n = -det(PA, PQ)/det(PQ, PR)
m = det(PA, PR)/det(PQ, PR)

ここで、det（PA、PQ）は、ベクトルPAおよびPQの行列式です。

det(PA, PQ) = PA.x*PQ.y-PQ.x*PA.y

点Aが平行四辺形の内側にある場合、0 <= n<=1および0<=m <= 1の場合、これにより擬似コードが得られます。

var d:Number = det(PQ, PR);
if (0 <= -det(PA, PQ)/d <= 1 && 0 <= det(PA, PR)/d <= 1)
{
    //inside
}
else
{
    //outside
}
于 2009-08-02T09:42:49.467 に答える
5

あなたのポイントから一方向に放射する光線を想像してみてください。その光線がシェイプの線と奇数回交差する場合、それはシェイプの内側にあります。偶数回交差する場合は、形状の外側にあります。

したがって、プログラムでは、目に見えない線を作成し、それが交差する頻度を確認します。Actionscriptには、おそらくこれを行うための組み込み関数があると思います。

これで、大量のオブジェクトがあり、ポイントを1つにしかできない場合は、バイナリスペースパーティションを使用してオブジェクトの場所を保存することで、処理を高速化できます。そうすれば、ポイントをすべてのオブジェクトと比較する必要はなく、近くにあるオブジェクトだけを比較できます。

于 2009-08-01T22:03:54.417 に答える
2

この質問に対する私の回答を参照してください。これは非常によく似ています。そこでは、説明が見やすくなるため、平行四辺形の角の 1 つが にある場合の非常に簡単なテストだと思いますが、(0,0)一般的に機能するように変更することはそれほど難しくありません。

編集:質問の所有者はベクトルに精通しているため、基本的にその言語で回答を書き直します。平行四辺形がベクトルPQおよびPRで張られているとします。ここでP、 、Q、およびRはコーナーです。記号*は内積を表します。(つまり) と(たとえば、90 度回転して取得できます)に垂直なq点を選択します。また、とのような点を選びます。次に、の場合に限り、ポイントは内部にあります。PQPqPq*PQ=0PR*Pq>0qQPrPR*Pr=0PQ*Pr>0A(0 < Pr*PA < Pr*PQ) && (0 < Pq*PA < Pq*PR)

于 2009-08-01T22:31:46.327 に答える
1

この論文では、光線と四角形が交差する場所を決定する方法について説明します。四角形が平行四辺形の場合、さらに単純化できます。

ベクトルABとACで表される隣接する辺を持つ平行四辺形があるとします。平行四辺形の平面内の任意の点は、次のベクトルで表すことができます

T(a, b) = A + a * AB + b * AC

任意の光線は、原点Oと方向Dとして記述できます。

R(t) = O + t * D

2の交差点はいつですT(a, b) == R(t)

O + t * D = A + a * AB + b * AC

これをaとについて解きb、両方が 0 と 1 の間にあることを確認します。これを実装する方法については、ペーパーの最後にある疑似コードを参照してください。

于 2009-08-03T11:55:26.530 に答える
0

線の標準方程式は ax+bx+c=0 として与えられます..しかし興味深いことに、その式 ax+bx+c を使用して、特定の線の a,b,c を指定して点 x,y を評価すると、式が平面を 2 つの半分に分割することがわかります。一方の半分は式が 0 よりも大きく、他方の半分は式がゼロよりも小さい部分です。

ここで、平行四辺形の 4 つの点を取り、平行四辺形の辺を構成する各線の a、b、c 係数を計算すると、問題の x、y の各式を評価して、どの辺を見つけることができます。ポイントがオンになっている各行の。平行四辺形の内側は、特定の辺の論理積になります。

つまり、4 行それぞれの a、b、c を取得したら、次のようなテストを作成できます 。 

if ( ((a1*x+b1*y+c1)>0) && ((a2*x+b2*y+c2)<0) && 
        ((a3*x+b3*y+c3)<0) && ((a4*x+b4*y+c4)>0) {
    // it's in!
}

.. 残っている唯一のトリックは、各符号テストの「極性」、つまりゼロより大きいか小さいかを判断する必要があることです。これを行う簡単な方法は、0,0 を評価し、それが希望する側にあるかどうかを確認することです。これは、'c' の符号がどちらの方法をテストするかを示すことになります。

確かに、これは一種の強引な方法ですが、任意の凸多角形で機能するように拡張できます..または、ポイントを削除して三角形でも機能します.

于 2009-08-02T01:12:27.670 に答える
0

この問題について私が最初に観察したのは、(軸に沿って配置された) 長方形は単純な縮退ケースであるということです。その長方形の 2 つの角が (x1,y1) と (x2,y2) の場合、点 (x3,y3) が与えられた場合に、min(x1,x2) < x3 < max(x1,x2) と最小 (y1、y2) < y3 < 最大 (y1、y3)。

これも最適化に役立つ可能性があります。平行四辺形の軸に沿った外接する四角形が見つかった場合は、それに対する任意の点の簡単なテストを開始できます。

緯線の勾配がゼロでない場合、境界線の軸交点と、それらの勾配で問題の点を通過する線の交点を計算します。ポイントの交点 (両方の勾配によって定義される) の両方が、境界線の交点の間にある場合は、範囲内です。どちらかがこれらの範囲外にある場合は、そうではありません。

例をコード化する時間はありませんが、これらの勾配と交点を計算するのは 1 年目の代数です。

【追記】

最初の投稿（テスト対象のポイントからの光線に関して、任意の勾配に沿って伸びる）は、閉じた平面ポリゴンのこの問題に対する一般的な解決策への参照であることがわかりました...または、実際には、閉じた平面曲線。また、閉じたサーフェスの 3 次元に拡張することもできます。

ただし、平行四辺形にも菱形にも当てはまる注意点が 1 つあります。凹面多角形 (またはその他の曲線) の場合、光線が頂点 (角) に当たると、テストが偶数の「線」交差を返す可能性があります。言い換えれば、多角形の複数の「辺」に同時に含まれる「曲線」の部分は、偽陽性を返す可能性があります。

これに対する 2 つの解決策は、線分の境界 (コーナー/頂点) での交点を明示的にテストするか、各線分を (点 + イプシロン) によって一方の端が囲まれているものとして処理することです (計算で共通点が見つからないようにします)。任意の 2 つの側面)。

境界の四角形を見つけるという私の考えは、依然として有用なクイック テストであり、一般的にすべてのポリゴンに適用されます。min() と max() x を見つけて左右の境界辺を見つけ、min() と max() y を見つけて上下の境界を見つけます。これは 3 次元に拡張することもできます...友人は、標準的なグラフィックス ライブラリがほとんどの仮想現実や MMORPG などで衝突検出にこれを広く使用していると教えてくれました。そこに含まれるポリゴンについて。

于 2009-08-01T22:51:31.090 に答える
-1

y座標が最も単純なので、それから始めます。ポイントのy座標がシェイプの上部と下部の間にある場合は、x座標に進みます。ポイントのy座標で形状の左側と右側のx座標を計算し、ポイントのx座標がそれらの間にあるかどうかを確認します。

編集：

左上隅、右上隅、右下隅、左下隅の4つの座標が与えられます。

if (y >= y1 && y <= y3) {
   var k = (x4 - x1) / (y4 - y1);
   var m = x1 - k * y1;
   if (x >= k * y + m) {
     k = (x3 - x2) / (y3 - y2);
     m = x2 - k * y2;
     if (x <= k * y + m) {
       // inside
     }
   }
}
于 2009-08-01T22:10:13.063 に答える