polygon - 耳かきで困っている

Question

私が抱えている問題は、実際に切り落とされるべきである耳と三角形に陥没したものを特定できないためです。

凸三角形と凹三角形の見分け方は？

Answer 1

三角形を凹面にすることはできません。メッシュが凹んでいるということですか？

---

あなたが特定のテクニックについて話しているとは知りませんでした。少し調査を行った後、回答を試みるのに十分な問題を理解していると思います。

反時計回りの順序でポリゴンの頂点をトラバースしているとします。この順序でトラバースすると、ポリゴンのボディは常に左側になります。A、B、Cの3 つの頂点を考えています。AからBを介して光線を放つと想像してください。Cがその光線の左側にある場合、これは多角形の一部である整形式の三角形です。Cがその光線の右側にある場合、それはネガティブ スペースを表します。

では、ベクトルv ( A → B ) とw ( B → C ) を作成しましょう。また、 v'を作成しましょう。これはvですが、反時計回りに 90 度回転しています。v' = < -v[y], v[x] >

Cがvの左にあるか右にあるかを調べるには、単にv'とwの間の角度を測定する必要があります。(0, 90) または (270, 360) 内にある場合は、左にあります。(90, 270) 以内にある場合は、右側にあります。これは、それぞれ cos(Θ) > 0 と cos(Θ) < 0 に正確に対応するため、便利です。したがって、cos(Θ) > 0 の場合、C は左側にあり、cos(Θ) < 0 の場合、C は右側にあります。

内積を使用して cos(Θ) を決定できます。cos(Θ) = ( v' • w ) / (mag( v' ) ⋅ mag( w )) であることを思い出してください。ただし、実際には cos(Θ) は必要ありません。必要なのは sign(cos(Θ)) だけです。mag( v' ) と mag( w ) は両方とも正でなければならないので、無視できます。したがって、v' • w > 0 の場合、C は左側にあり、3 つの点は多角形の一部である三角形に対応します。一方、v' • w < 0 の場合、C は右側にあり、3 つの点は多角形の外側の負のスペースに対応します。

簡単なテスト以外で実際に試したことはありませんが、それ (またはそれに近いもの) が機能すると信じています。

ああ、(私のように) このテクニックについて聞いたことがない人は、ここでそれについて読むことができます。