ポリゴン内の線分のリストを探すには

Question

私は線とポリゴンを持っています。線は部分的にポリゴンの内側と部分的に外側にあります。線はポリゴンを一点または複数の点で交差することができます。例線画像を参照してください

以下のように示されています。水平の赤い色の線については、線分のリストを取得したいと思います。所望の出力は（A-B）（C-D）（E-F）であり、垂直線については線分1-2を得たい。

私はhow to detemine if a line segment is inside of a polygon?やその他のスタックオーバーフローの問題を経験しました。

しかし、ポリゴン内の線分のリストを取得するのに最も最適化されたアルゴリズムを得ることができませんでした。

https://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm私は多角形内の線分を見つけるアルゴリズムがより最適化されていますか？

Answer 1

前処理が許可されていない場合、つまり、指定されたポリゴンに対して1行のセグメント（または一部）を処理する必要がある場合に答えることができます。ポリゴンは一般的です（穴がある場合もあります）。

ラインを回転させて水平にし、同時にポリゴンの頂点を回転させます。

次に、端点に異なる符号の縦座標がある場合は、ポリゴンの一辺がセグメントの補助線と交差します。この場合、交差点の位置を計算することができます。

ポリゴン内のサブセグメントは、セグメントの端点間にある順序付き交点から作成されます。