c++ - 点に重なるすべての間隔を見つける

Question

1次元の浮動小数点間隔の大きなセットを考えてみましょう。

 [1.0, 2.5],                1.0 |---------------|2.5

 [1.5, 3.6],                      1.5|---------------------|3.6

 .....

与えられた点を含むすべての間隔を見つけることが望まれます。たとえば、ポイント = 1.2 を指定すると、アルゴリズムは最初の間隔を返す必要があり、ポイント = 2.0 を指定すると、上記の例の最初の 2 つの間隔を返す必要があります。

私が扱っている問題では、この操作を多数の間隔で何度も繰り返す必要があります。したがって、ブルート フォース検索は望ましくなく、パフォーマンスは重要な要素です。

それについて調べた後、計算幾何学のコンテキストでインターバルスキップリストを使用してこの問題が解決されていることがわかりました。シンプルで効率的な C++ 実装が利用できるかどうか疑問に思っていました。

---

編集:問題についてより正確に言うと、N 個の間隔があり、M ポイントの場合、どの間隔に各ポイントが含まれているかを判断する必要があります。N と M は大きな数で、M は N よりも大きくなります。

Answer 1

CGAL レンジ ツリーの使用を提案します。

ウィキペディアによると、インターバル ツリー(1 次元の範囲ツリー) は、「任意のインターバルまたはポイントと重なるすべてのインターバルを効率的に見つける」ことができます。

Answer 2

間隔の分布が許す場合は、グリッド化アプローチを検討する価値があるかもしれません: グリッド サイズを選択sし、リストの配列を作成します。番目のリストごとkに、「セル」と重複する間隔が列挙されます[k.s, (k+1).s[。

次に、クエリは、クエリ ポイントを含むセルを検索し ( O(1))、それを実際に含むリスト内のすべての間隔をレポートする ( O(K)) ことになります。

前処理時間とストレージの両方O(I.L+G)が、グリッド サイズとグリッド セルの総数Iに関する間隔の数とL平均間隔の長さです。慎重に選択する必要があります。Gs