0

サーバーから位置情報を取得したデータを使用して、javascript を使用してページに追加する必要がある要素がいくつかあります。重ならないように並べたい。たとえばelement 5、薄い緑色のボックスがある場所に移動して、重ならないようにしelement 3ます。

2 つのボックスが重なるかどうかを判断する関数の作成に成功しました。たとえば、実行overlaps($('#element5')[0],$('#element3')[0])すると、 が返されtrueます。

ただし、この関数を使用すると、各要素をループして、他のすべての要素と比較する必要があります。したがって、50 要素の場合、関数を 1275 回実行する必要があり、overlaysロードに時間がかかります。

最初に要素を整理するための rtree を作成するのが最善であると判断しました。これにより、オーバーレイ関数を実行する必要がある 2 つの要素を簡単に見つけ出すことができ、オーバーレイ関数の実行回数を大幅に減らすことができます。ただし、これがどのように機能するかについては非常に混乱しています。少数でのみ関数を実行する必要があるように、それらをどのように整理しますか? rtree のバウンディング ボックスの 2 つが重なって、この手法が冗長になるのではないでしょうか? これを行う最良の方法は何ですか？

ここに画像の説明を入力

4

1 に答える 1

0

R ツリーでは、長方形のページが重なることがあります。

オーバーラップを検索するときは、両方のグループを調査する必要があります。

ただし、r ツリー内のオーバーラップするページの数は (ツリーが非常に不適切に構築されていない限り) 大きくなりすぎないようにする必要があるため、これでも十分な速度向上が得られます。それぞれ 10 要素の 5 ページに 50 要素があると仮定すると、最初に 5 つのトップ レベル ページをテストする必要があります。次に、これらのページの 0 ～ 2 ページで 10 要素をテストする必要があります。もちろん、正確な数は大きく異なります。

ただし、HTML ソリューションの場合は、代わりにグリッド ベースの近似を検討します。表面を 10x10 セルに分割します。各セルには、このグリッド セルと重なる四角形の参照が含まれています。

オーバーラップをテストするときは、クエリの四角形が接触するグリッド セルを調べ、参照されている既存の四角形をすべて収集してから、それらのみをオーバーラップ テストします。各セルに 2 つのリスト (「部分的に重複」と「完全に重複」) を格納する場合、重複テストの多くをスキップすることもできます: 一方が接触しているグリッド セルがもう一方と完全に重複している場合、それらはどこかで重複します。

さらに別のアプローチは、四角形を X 軸で並べ替えて、二分探索で実際にオーバーラップできる四角形の数をすばやく絞り込むことです。これにより、交差呼び出しの数も大幅に削減されます。

ああ、最後になりましたが、1275 のオーバーラップ テストにはそれほど時間はかかりません。これは、あなたが話している小さなデータセットです。R ツリーおよび同様のアプローチは、何百万ものアイテムを含むデータ セットを対象としています。

于 2013-07-17T13:16:55.810 に答える