頂点を持つ凸多角形があるとします
(v0,v1,....vn)
私の目的は、特定のポイントp(x,y)について、このポイントとポリゴンの頂点を結ぶ線分がポリゴンの内側にあるか、特定の2つのポイントにあるかどうかを判断することです
p(x0,y0) `p(x1,y1)`
この2点を結ぶ線分は多角形の中にありますか? これについて多くのサイトを検索しましたが、まだ混乱しています。通常、頂点の座標を比較する必要があり、どの点の座標が別の点の座標よりも小さいか大きいかを決定することで、任意の線分の位置を決定できますが、これがどれだけ正しいかわかりません、助けてください
(n > 2)の頂点を持つ点Pと凸多角形を想定します。nV_1V_n
多角形の頂点を、選択した頂点に対する角度で並べ替え、時計回りまたは反時計回りの順序になるようにします。ポリゴンのエッジはV_1 -> V_2, V_2 -> V_3, ..., V_(n-1) -> V_n, V_n -> V_1です。
ここで、すべてのエッジについて、外積 の値を確認します(V_(i+1) - V_i) x (P - V_i)。すべての値が >= 0 またはすべての値が <= 0 の場合、現在Pはポリゴン i の内側にあります。
ポリゴンが凸面である必要がないというより一般的な問題については、TopCoderに関する優れたチュートリアルがあります。彼らがしていることは、テスト ポイントからレイを送信し、それが交差するエッジの数を確認することです。
注:ここで使用される外積は、次のように定義されます。(u1, u2) x (v1, v2) := u1*v2 - u2*v1