クイックタイムインターバルのためのデータ構造

Question

私は時間間隔のセットを持っています。In =（an、bn）。私は、時間にトンを与え、すぐにトン、例えば、それらの間隔は、このような億< = T < =それが含まれている区間を返す必要がよルックアップの多くを実行する必要があります。

このための良いデータ構造またはアルゴリズムは何ですか？

私の場合、とbnは整数です。

Answer 1

Interval Tree（タイプはRange Tree）です。

これらは他のツリー構造（RBツリーなど）と同様に対数ルックアップ時間があるため、Java TreeMapやSTLマップなどと似たパフォーマンスが必要です。

• Code for Red-black trees and interval trees MIT
• からCGAL LibraryでC++ implementationがあります。
• ここであなたは、まさにこの問題を解決するためC# implementation I've posted on CodePlex for IntervalTreeをチェックアウトして歓迎されているC# Implementation

Answer 2

これは基本的にスペースを区切る質問です。あなたはコンテナを持つ大きなスペースと、そのスペースの特定のポイントを持っています。どのコンテナに触れますか？多くのゲームがこの問題を解決しなければならないので、そこで始めるのは悪い考えではありません。 「広域位相衝突検出」に関する記事を探します。

これを行う最も簡単な方法は、数字スペースを一定数に分割することです。各セットは、どのセットがそれと交差するかを知っています。新しいセットが追加されるたびに計算されるものです。ポイントがあるときにすべてのセットをテストするのではなく、そのポイントが含まれるピースに含まれるセットをチェックするだけです。

もう1つの一般的で効率的なアルゴリズムは、バイナリスペースパーティショニングです。このアルゴリズムは、あなたのスペースを2つの側面に細分します。各側は、どのセットがそれと交差するかを知るだろう。このプロセスを反復して希望の精度で繰り返すことができます（最小の集合の範囲より小さい細分を作成することは意味がありません）。

Answer 3

問題は1次元に過ぎないので、ほとんどのゲームで見られる領域分割の問題よりも少し簡単です。 あなたは単純なBSTを持つことができ、各葉には葉を左から左への間隔のリストを覚えています。

間隔A（0,10）とB（5,15）がある場合、ツリーの葉は（空のリストで0）、（5でA）、（10でA、B）と（15とB）。

Answer 4

です。

Ido。