c++ - セグメントが線と交差しているかどうかを確認するにはどうすればよいですか？

Question

私はstd::list行があります。各線は2つのCPointオブジェクトのリストであり、線の始点と終点を示します。

std::list<std::list<CPoint>> edges;

次に、別の線（2つのCPointのリスト）があり、メインリストの線のいずれかとの交差をテストします。これどうやってするの？おそらく、反復のためのループ内の交差テスト。

Answer 1

あなたが示唆するように、基本的なアプローチは、すべての線を反復処理してから、線交差アルゴリズムを適用することです。漸近的にはこれが最善かもしれません。結局、新しい行は他のすべての行と交差する可能性があります。

多くの線交差アルゴリズムでは、最初にバウンディング ボックス テストを適用します。非常に大まかに、比較される 2 つの行を含む四角形が重なるようにします。それらが重なっていない場合、線は交差できませんが、重なっている場合は、より包括的なテストを適用する必要があります。

境界ボックス テストは、2 つのボックスの x 間隔が重なり、2 つのボックスの y 間隔が重なり合っているかどうかを確認しています。効率的な区間交差チェックのために特別に設計されたデータ構造があります。インターバル ツリーに関する情報を参照してください。このような構造は、多くの場合、より少ない行で境界ボックス テストを実行することを意味します。テストを適用する必要がある前に、データ構造が（間隔を介して）いくつかの行を破棄します。