問題タブ [interval-tree]

整数値を持つ間隔のリストがあります[例. [1、4]、[10、19]など]。これらの間隔をいくつかのJavaコレクションのコンテナに入れる方法はありますか[例. コンテナで「ユニオン」関数を呼び出せるように設定します。「ユニオン」関数は、挿入された2つの間隔が重なっている場合、それらが出力にマージされるように、間隔のリストを提供する必要があります。Guava で Range クラスを使用してみましたが、マージする前にすべての間隔を互いに比較することになりました。これに対するエレガントなアプローチは本当にありがたいです! 以下の回答に基づいて私が試したことは次のとおりです。出力は [[1, 15], [17, 20]] で、正しいです。このようなものを実装する既存の API があるかどうかを知りたかったのです。

ありがとう

間隔を処理するために Guava の Range クラスを使用しています。Guava のコレクション コンテナーのいくつかを使用して、一連の間隔から特定のポイント/間隔までの最も近い間隔を見つけることができるかどうかを知りたいですか?

Javaでインターバルツリーを検索してみましたが、これが見つかりました。可能であれば、Guava クラスの 1 つを使用してそれを行うことをお勧めします。

http://picard.sourceforge.net/javadoc/net/sf/picard/util/IntervalTree.html http://tribble.googlecode.com/svn/trunk/src/org/broad/tribble/index/interval/IntervalTree .java

ありがとう

Python でセグメント ツリー クラスを実装しようとしています。セグメント ツリーを使用すると、対数時間の範囲でクエリを実行できます (セグメント ツリーの詳細については、 を参照してください)。私の実装では、範囲内の要素の合計に答えるために必要な情報を保持しています(i, j)。以下に私のコードがあります。私はPythonが初めてなので、各行の最後にセミコロンを使用しています(C++から継承)。

build 関数は、入力配列からセグメント ツリーを構築することになっていますa。プログラムを実行すると、次の出力が得られます。

シーケンスのすべての値が関数の終了24後にある理由がわかりません。build関数の実行中はデバッグ情報に他の多くの値が表示されますが、build関数が終了すると、すべての値が魔法のように に変わります24。なぜこうなった？前もって感謝します。

CLRSアルゴリズムの本で概説されているように、Javaでインターバルツリーを実装しました（基本的な構造として赤黒ツリーを使用します）。この本では (そして私がオンラインで見た限りでは)、間隔にクエリ対象の番号が含まれるノードを見つける方法について説明しています。

私の場合、照会された数値がどの間隔にも当てはまらない場合、「最も近い」ノード、つまり間隔がクエリの直前と直後にあるノードを知りたいと考えています。次の関数を使用してこれを達成しました。各ノードには、間隔 (int low、int high) と、それ自体とそのサブツリーの最小値と最大値が含まれています。

もちろん問題は、関数 findPrev() と findNext() の両方がツリー全体をトラバースし、ツリーの構造を利用していないことです。このクエリを O(lgn) 時間で実行する方法はありますか?

また、すべてのインターバル ギャップを含む 2 つ目のインターバル ツリーを作成し、そこでクエリを実行する可能性も検討しました。ノードには、そのギャップの前後にある要素に関する情報が含まれます（私は試みましたが、これを実装することにまだ成功していません）。

編集:関数 findPrevNext() は、クエリの検索に失敗した後に呼び出されます。そのため、クエリは事前に特定の間隔に収まらないことがわかっています。

いくつかの間隔 (実際にはこれらはアドレスの間隔です) をオブジェクト ID にマップする必要があります。

ブーストの interval_map を使用しようとしました。例は非常にきれいに見えます。次のようにすべての間隔を簡単に列挙します。

どの出力:

しかし、次のようなことはできません:

それは出力します: error: no match for 'operator[]' in 'party[when]' map の主な機能が operator[] にあるので、奇妙に見えます

そのため、「特定の時間に誰がパーティーにいたか」という情報を取得できません

この問題に対してすぐに使用できるソリューションはありますか?

これは、重なり合う間隔を見つけることに関連しています。間隔のリスト（間隔ツリー）が与えられた場合、その方法を知っています。私が持っているのは、間隔のリストのリストです。例えば、

この結果は次のようになります。

[2,3]、[7,8]

私がしなければならないことは、すべてのリストに共通する間隔のリストを見つけることです。

この問題は、リストのマージに似ていると思いnます。問題は、リストのペアごとのマージを適用できないことです。この方法を適用すると、重複する間隔が失われる可能性があります。したがって、すべてのリストを一度に (ペアごとではなく) 考慮して、すべてのリストをマージする必要があります。

インターバルツリーを使用できます。各リストの最初の間隔を間隔ツリーに挿入し、オーバーラップを見つけます。ツリーから最も弱い間隔を削除し、リストの 1 つから次の間隔を挿入します。この方法をどのように使用できるかはまだ完全にはわかりませんが、コストがかかりすぎるようです。

間隔のリストのリストから重複する間隔を見つけるための効率的なアルゴリズムはありますか?

追加情報: リスト内の間隔はソートされます。それらは重複せず、シーケンスを形成します。

したがって、最初にどのように実装したいかを説明する必要があります。私のアイデアはかなり単純です。各チャンクを作成し、各チャンクにローカルな浮動小数点グリッドを利用して各頂点の位置を決定し、ボクセルを大きな 64 ビット整数グリッドに配置します (各チャンクの位置は、それが持つ整数値、0,0,0 は中央、20,20,20 は x、y、z 軸上で 20 チャンク離れた場所になります) さらに大規模な世界を作成するには、いくつかのチェックを実行して、チャンクは、整数グリッド内の位置から推測されて生成されますが、これはまだわかりません。（実行することほど重要ではありません）

私が問題を抱えていること：

1. libnoise を使用して 3D パーリン ノイズを生成する方法を考え出しましたが、このドキュメントでは、私が知る限り、この問題には触れておらず、Google に問い合わせてもまともな結果は得られません。
2. どういうわけかチャンクを整数グリッドに配置する
3. 次に、チャンクがグリッド内の位置から推測される固さをどのように決定するかを正確に把握する (これは、周囲のチャンクが何であるか、グリッド内のどこにいるかを確認し、そのデータに基づいて決定することで簡単になると思います)
4. 整数グリッドから推測される位置に基づいて、希少性のあるさまざまな鉱石を周囲に散らします。これはかなり簡単ですが、他のものが解決されるまで実行できません。
5. インターバルツリーを理解する。

それで、何かアイデアはありますか？これまでの関連コード (ライト、オクルージョン、UV、通常の計算コードは質問に関係ないため削除)

私が知る限りでは、このコードが C と python で書かれた特定のデモに非常に似ていることに気付くかもしれません。これは、多くのコードがそれを読んだ後に書かれたものであり、私に少しこすりつけられたからです。

問題は、それが私の問題をカバーしていないように見えることです.ボクセルがどのように機能するかについての理解がいくらか深まりました.

それで、私のこのプロジェクトを解決するためにどのように進むべきかについての指針はありますか?

PS、これはバトルフィールド 3 が DOOM のクローンであるのと同じくらいマインクラフトのクローンです。それをどのように解釈するかはあなたに任せると思います。

ああ、私は調査を行って、次のことを発見しました: 0fps に関する投稿。あなたのほとんどは、ブログ https://sites.google.com/site/letsmakeavoxelengine と、GPU gems 3 を含むいくつかの他のブログに精通していると確信しています。マーチング キューブやその他のいくつかの機能がありますが、どれも私の問題を解決するものではありません。

以下を達成するための適切な方法を決定しようとしています。

範囲が必要です->特定の範囲内でルックアップを設定します（[0x0 - 0xffffffff]など）。値は範囲の範囲に挿入されます (したがって、T = 一意の文字列を使用している場合)、insert("beef3490", [0x1234, 0xFFFF]); また、1 つの ID に複数の挿入が含まれる場合があり、それらは重複する場合と重複しない場合があります。さらに、重複する他の値が挿入される可能性があり、それらが重複する場所では、結果として一意の文字列のセットを受け取る必要があります。最後に、値を範囲から削除することもできます (必ずしも一致する必要はありませんが、通常は最初の挿入範囲内に含まれます)。

簡単な使用例を次に示します。

これは私にとって多くの質問につながります：

1. この種の問題の一般化された名前、または洞察を見つけることができる同様のタイプの問題はありますか?

2. 次の制約を考えると、理想的な実装は何ですか:

   • 高速/非常に高速なルックアップ時間
   • メモリ使用量が膨れ上がることはありません (つまり、次の操作は同等のフットプリントを持ちます)。
   • • [10,20] を挿入、[20,30] を挿入、[14,24] を削除
   • • [10,15] を挿入、[25,30] を挿入
   • 最後と同様に、データ構造は長時間稼働するシステムで安定している必要があります
   • 挿入/削除時間は絶対にひどいわけではありません (ルックアップほど速くする必要はありません)。

3. 理想的な実装が与えられた場合、それを C++ で使用するためのアドバイスはありますか

すべての応答とヘルプに感謝します。