1

角度を形成する 3 つの点がある場合、4 番目の点が前の 3 点によって形成された角度内にあるかどうかを判断する最良の方法は何でしょうか?

現在、原点から3点すべてへの線の角度を決定し、テスト角度が他の2つの角度の間にあるかどうかを確認しますが、それを行うためのより良い方法があるかどうかを把握しようとしています. この関数は更新ごとに何万回も実行され、私がやろうとしていることを達成するためのより良い方法があることを願っています.

4

4 に答える 4

2

角度があるとしましょうDEF（Eは「とがった」部分です）、EDは左の光線で、EFは右の光線です。

      * D (Dx, Dy)
     /
    /          * P (Px, Py)
   /
  /
 *---------------*
E (Ex, Ey)       F (Fx, Fy)

ステップ1。ED古典的なAl * x + Bl * y + Cl = 0 形式の線の方程式を作成します。つまり、単純に計算します。

    Al = Dy - Ey                    // l - for "left"
    Bl = -(Dx - Ex)
    Cl = -(Al * Ex + Bl * Ey)

(引き算の順番に注意してください。)

ステップ 2。従来のAr * x + Br * y + Cr = 0 形式の線FE(逆方向) の線方程式を作成します。つまり、単純に計算します。

    Ar = Ey - Fy                    // r - for "right"
    Br = -(Ex - Fx)
    Cr = -(Ar * Ex + Br * Ey)

(引き算の順番に注意してください。)

ステップ 3。テストポイントPの式を計算します

    Sl = Al * Px + Bl * Py + Cl
    Sr = Ar * Px + Br * Py + Cr

あなたのポイントは、との両方が正の場合にのみSlSr、角度の内側にあります。そのうちの 1 つが正で、もう 1 つがゼロの場合、ポイントは対応するサイド レイ上にあります。

それでおしまい。

注 1:この方法が正しく機能するためには、角度の左右の光線が実際に左右の光線であることを確認することが重要です。つまり、 とを時計の針と考えると、 からへの方向は時計回りになります。入力に当てはまることが保証されていない場合は、いくつかの調整が必要です。たとえば、ステップ 2 と 3 の間に挿入された、アルゴリズムの追加ステップとして実行できます。EDEFDF

ステップ 2.5。の値を計算しますAl * Fx + Bl * Fy + Cl。この値が負の場合、すべての ABC 係数の符号を反転します。

Al = -Al, Bl = -Bl, Cl = -Cl
Ar = -Ar, Br = -Br, Cr = -Cr

注 2:上記の計算は、X 軸が右を指し、Y 軸が上を指す座標系で作業していると仮定して行われます。座標軸の 1 つが反転している場合は、6 つの ABC 係数すべての符号を反転する必要があります。ところで、上記のステップ 2.5 で説明したテストを実行すると、すべてが自動的に処理されることに注意してください。ステップ 2.5 を実行していない場合は、最初から軸方向を考慮する必要があります。

ご覧のとおり、これは正確な整数メソッドです (浮動小数点計算も除算もありません)。その代償はオーバーフローの危険です。乗算には適切なサイズの型を使用してください。

この方法には、線の向きや実際の非反射角の値に関して特別なケースはありません。鋭角、鈍角、ゼロ、および直線の角度に対してすぐに機能します。反射角で簡単に使用できます (補完的なテストを実行するだけです)。

PSおよびの+/-符号の 4 つの可能な組み合わせは、平面が線およびによって分割される 4 つのセクターに対応します。 SlSrEDEF

            * D
           / 
   (-,+)  /    (+,+)
         /
 -------*------------* F
       / E
(-,-) /     (+,-)
     /

この方法を使用すると、「ポイントがどのセクターに属するか」の完全なテストを実行できます。角度が 180 より小さい場合は、たまたまこれらのセクターの 1 つだけに関心があります(+, +)。ある時点でこの方法を反射角 (180 より大きい角度) にも適用する必要がある場合は、1 つではなく 3 つのセクターをテストする必要が(+,+)あり(-,+)ます(+,-)。

于 2012-07-14T02:52:44.833 に答える
1

原点Oと他の2点AとBを記述してください。そうすると、角度はAOBとして与えられます。次に、テストポイントを検討し、図のようにそのCを呼び出します。

ここに画像の説明を入力してください

ここで、ベクトルOAの倍数とOBの倍数を取ることにより、Cのベクトル方程式を取得できると考えてください。明示的に

  C = K1 x OA + K2 OB

計算する必要のあるK1、K2について。他のすべての点から（ベクトル的に）減算して、Oを原点に設定します。Aの座標が（a1、a2）、B =（b1、b2）、C =（c1、c2）の場合、行列の項で次のようになります。

 [ a1 b1 ] [ K1 ] = [ c1 ]
 [ a2 b2 ] [ K2 ] = [ c2 ]

したがって、行列の逆行列を使用してK1とK2を解くと、次のようになります。

  1 / (a1b2 - b1a2)  [ b2 -b1 ] [ c1 ] = [ K1 ]
                     [ -a2 a1 ] [ c2 ] = [ K2 ]

これはに減少します

 K1 = (b2c1 - b1c2)/(a1b2 - b1a2)
 K2 = (-a2c1 + a1c2)/(a1b2 - b1a2)

ここで、点Cが角度内にある場合、ベクトルOAとOBの倍数は両方とも正になります。CがOBの下にある場合、他の方向でも同様に到達するには、負の量のOAが必要です。したがって、K1とK2の両方がゼロより大きい（または等しい）場合、条件は満たされます。a1b2 = b1a2これが特異行列とゼロ除算に対応する場合は注意が必要です。幾何学的には、OAとOBが並列であるため、解決策がないことを意味します。上記の代数は、おそらくわずかなタイプミスを検証する必要がありますが、方法論は正しいです。長い間巻き込まれているかもしれませんが、ポイント座標からすべてを簡単に取得でき、角度を取得するための逆三角関数を計算する手間が省けます。

上記は180度未満の角度に適用されるため、角度が180度より大きい場合は、代わりに次のことを確認する必要があります。

 !(K1 >= 0 && K2 >= 0)

これは、180度未満のセグメントの外部にあるためです。0度と180度の場合、ゼロ除算エラーが発生することを覚えておいてください。これをチェックする必要があります（確認a1b2 - b1a2 != 0）

于 2012-07-14T01:19:14.240 に答える
0

はい、上記のコメントで最小の角度を意味しました。2つのベクトル間の角度の測度を見つけるための安価な方法に関する広範な議論については、このスレッドを参照してください。私は多くの場合、ルックアップテーブルアプローチを使用して大成功を収めてきました。

于 2012-07-12T17:17:31.557 に答える
0

三角形 OBC は正の方向を向いている必要があり、三角形 OC A も正方向でなければなりません。両方の値が正でなければなりません。

于 2012-07-14T16:19:30.197 に答える