このトピックについて少しグーグルで調べたところ、http://www.geeksforgeeks.org/でこれを見つけました。
インターバル ツリーは主に幾何学的データ構造であり、ウィンドウ クエリによく使用されます。たとえば、長方形のビューポート内のコンピューター化された地図上のすべての道路を検索したり、3 次元シーン内のすべての可視要素を検索したりします。
今、私の質問は実際には2つの部分に分かれています:
PS: インターバル ツリーに関するより多くの読み物を参照した簡単な説明は大歓迎です。
ウィンドウ クエリでは、一連の線分と軸に沿った四角形が与えられた場合、線分と四角形との交点を見つける必要があります。これは、インターバル ツリーをレンジ ツリーと組み合わせて使用することで解決できます。
範囲ツリーは、範囲/長方形内に存在する点のセットを見つけるための効率的なデータ構造です。したがって、これらを使用して、各線分の終点の 1 つがクエリ Rectangle に存在するように、すべての線分を見つけることができます。これらは、下図の青い線分に対応しています。
インターバル ツリーを使用して、ウィンドウとオーバーラップしているが端点がウィンドウの外側にあるセグメントを見つけることができます。これらは、図の赤いセグメントです。
この問題を解決する前に、すべての線分が水平または垂直である、より制限されたバージョンの問題を想像してください。この場合、長方形と交差する水平セグメントは、長方形の左 (および右) 垂直エッジと交差する必要があります。水平線分を間隔、長方形の垂直エッジを点と考えると、問題は点を含むすべての間隔を見つけることです。したがって、区間木を使用してこの問題を解決できます。同様に、交差するすべての垂直線分を見つけることができます。
線分が軸に平行でない問題の一般的なバージョンは、間隔ツリーを使用して完全に解決することはできません。ただし、インターバル ツリーを使用して、クエリの四角形と重ならない圧倒的多数の線分を削除できます。入力の各線分に対して、対角線が線分である軸平行な長方形を作成します。次に、長方形の辺を使用して (水平および垂直) インターバル ツリーを構築します。クエリ四角形 R が与えられると、最初に、以前と同様に R と交差するすべての四角形を見つけることができます。対応する線分は R と交差する可能性が高く、実際の交差を個別に確認できます。
あなたの質問に直接答えないかもしれませんが、役に立つと思います：
囲み区間探索問題: n 区間の集合 S とクエリ点 q が与えられた場合、q を含むすべての区間を報告します。
重複間隔検索問題: n 間隔のセット S とクエリ間隔 Q が与えられた場合、S の重複 Q 内のすべての間隔を報告します。
参照 (セグメント ツリーのような他の同様のデータ構造とも比較してください): http://www.iis.sinica.edu.tw/~dtlee/dtlee/CRCbook_chapter18.pdf