問題タブ [range-tree]

私が見つけた唯一の妥当なスライド セットはこれで、15 ページには次のように書かれています。

• すべてのポイントを x 座標値で並べ替え、バランスの取れたバイナリ ツリー (つまり、範囲ツリー) のリーフ ノードに格納します。
• 
  ルートから始まる各ノードには、ツリーの浅い深さに格納されていない y 座標の最大値を持つサブツリー内のポイントが含まれます。そのようなノードが存在しない場合、ノード
  は空です

の直前に範囲ツリーを実装したので、そこで使用した例に基づいて、(優先検索ツリーの場合):

ここで、すべての内部ノードは次の形式です。

私が提起している範囲クエリは (-inf, 1) x (-0.5, 5)、つまり (x_low, x_high) x (y_low, y_high) です。

1. それでは、ルートから始めましょう。x (=0) が (-inf, 1) にあるかどうか、および 7 > (-0.5, 5) であるかどうかを確認します。したがって、両方の子で進めますが、簡単にするために、左側の子に従います (すべての場合で今から)。
2. -3 が x 範囲であるかどうか、および 6 がクエリの y 範囲の上限 (つまり 5) 以上であるかどうかを確認します。ですので、続けます。
3. 次のレベルでも同じなので、次のレベルに進み、この内側のノードに注目してください。これは、サブツリーの最大 y が 0 であることを示します (左の子は (-5, 6)) ^*です。

構築/検索プロセスで何が欠けていますか?

言い換えると：

ツリーの一番左の枝を確認してください。値としてmax_y(引用符の 2 番目の箇条書き)、7、6、4、0 があります。

しかし、その値は、内部ノードの下のサブツリーに格納されている最大の y 値を示すものではありませんか? もしそうなら、これは0and ポイントには当てはまりません(-5, 6)(6 は第 2 レベルで使用されるため、使用されません)。

*_{私が提起している特定のクエリは、それによって破損しないかもしれませんが、別のクエリは破損する可能性があります。}

定義された領域の 2 次元空間で任意の長方形が占めるすべてのグリッド セルを計算できるアルゴリズムを探しています。長方形は、その 4 つのコーナーの座標によって定義されます。下の図では、そのうちの 2 つを赤でマークしました。グリッド セルの座標は黒です。位置合わせされていないグリッド (グリッドの中心!= 基になる座標系の中心) もカバーする一般的なケースを探していますが、セル座標間の変換 <=> 座標系は簡単で、既に実装されています。すべてのセルは正方形です。

計算は非常に短い時間で数千回行われるため、できるだけ速く実行する必要があります。

私が今していること：

現在、長方形のエッジ (AB、BC、CD、DA) を計算し、sampleRate = cellWidth / 4間隔を置いてサンプリングしています。AB + sampleRate * x中央のセルを見つけるために、 からから新しい行を作成しCD + sampleRate * x、 でそれらの行を再度サンプリングしsampleRateます。サンプリングされた各ポイントで見つけたすべてのセルを HashSet に入れて、重複を削除します。しかし、これは非常に非効率的だと感じています。

また、関連する領域のすべてのセルをバッファーに取り込み、範囲ツリーまたはインデックス ツリーを生成することも考えました。次に、長方形の境界をキューに入れ、含まれているすべてのセルを O(log n+m) で取得できますが、それを実装する方法がわからず、C# レンジ ツリーの実装も見つかりません。

コンピュータ グラフィックスに関する私の知識は非常にさびしいものですが、サンプリングせずに機能する簡単な幾何学的アプローチがあるはずではありませんか?

インデックスを構築するために使用しているクラスがRangeTreeIndexありRangeTreeNode、2500 レコードを挿入した後、RangeTreeIndex受信しているファイルにオブジェクトを保存しようとしています。StackOverflowError以下はコード全体です。

以下は私が受け取っている例外です:

シリアライズ可能なオブジェクトのみを渡してApache commons-langライブラリ クラスを使用している場合でも、同じエラーがスローされます。SerializationUtils.serialize

プリミティブな値でこのような問題に直面した人はいますか?