セグメントがポリゴン内にあるかどうかを確認

Question

凹状のポリゴンを指定すると、2つの頂点をつなぐセグメント（エッジ）がポリゴン内にあるかどうかをどのように判断できますか？下の図には、元のポリゴンに接続されていない2つの同じ頂点を接続するエッジ（赤色）があります。私は内部と外部をどのように決定するか分かりません。何か助けてくれてありがとう。

Example of polygons

Answer 1

追加のセグメントは、多角形の他のセグメントと交差する場合、それは、部分的に内側と部分的外です。

そうでなければ、例えば追加のセグメント、その中点上の点を取ると、それは内部または外部であるかどうかを確認。点が内側にあるかどうかを調べるには、点がそこから伸びていて、ポリゴンの端点を持つ交差点の数を数えます。交差点の数が奇数であれば、それは内側です。

は簡単に聞こえるが、頂点における共線や交差点などの特別な場合を扱うために調製すること。それが実装を困難にするものです。