algorithm - 一連の線が輪郭で閉じたオブジェクトを作成するかどうかを確認する

Question

ユーザーがフォームに線を引くことができる割り当てがあります。ユーザーが行を作成するとすぐに、その行は、ユーザーが以前に入力したすべての行を含むリストにプッシュされます。次に、ユーザーがフレームを黄色で見ることができるように、線がフレームに描画されます。私の仕事は、ユーザーが線を使用して接続されたオブジェクトを作成しようとするたびに、そのオブジェクトが黄色ではなく緑色に変わる必要があるということです。だから私はすべての線分の2つの座標を持っています.閉じたオブジェクトが線のセットによって形成されていることをどのように判断できますか. 私が従うことができるアルゴリズムはありますか？

Answer 1

セグメントごとに、他のセグメント（存在する場合）との交点を見つけます。交点を見つけたら、それを2つの関連するセグメントにリンクします。

これで、交点を頂点、セグメントをエッジとする「無向グラフ」ができました。

あとは、グラフでサイクルを見つけるだけです。各サイクルは閉じたオブジェクトです。