math - 三角形が左向きかどうかを判断する

Question

(x1, y1)、(x2, y2)、(x3, y3) に 3 つの頂点のセットがある場合、これらの 3 つの頂点によって定義される三角形が左向きか右向きかをどのように判断しますか?

現在、クロス積をとって頂点が時計回りかどうかを判断しています。その知識があれば、y 座標を並べ替えているときに、三角形が左向きか右向きかを判断できます。

これは問題なく機能しますが、外積には 5 つの減算と 2 つの乗算が必要です。

私が見逃している三角形が左向きであるかどうかを判断するための、より簡単で高速な方法はおそらくありますか?

score 2 · Accepted Answer

これは、浮動小数点演算のコストと条件文のコストに依存します (命令パイプラインを半分の時間クリアするコストが追加されます)。

私の直感では、あなたの現在のソリューションはおそらくかなり良いものです。

score 0 · Accepted Answer

私はそれを次のように見ています：

最小および最大 Y 座標で 2 点を見つける
- 任意の 2 点が同じ Y 座標を持つ場合
- 次に、X座標が他のY最小/最大ポイントに近いものを選択する必要があります
3番目のポイントx座標をテストします
- それが他の点よりも小さい場合、それは左向きです
- 他のポイントよりも大きい場合は、左向きです

三角形の向き

[ノート]

あなたの三角形が定義された巻線を持っている場合（常にCWまたはCCW）

次のような行の正と負の dy の数を計算します。

int p=0,n=0;
if (B.y-A.y>=0) p++; else n++;
if (C.y-B.y>=0) p++; else n++;
if (A.y-C.y>=0) p++; else n++;

2 に答える 2