html5 キャンバスに描画される長方形の大きなセットがあります。
マウス トラッキングを使用してこの画像を操作できるようにしたいと考えています (10 ～ 100k の四角形にスケーリングされないため、SVG は使用できません)。マウスのx、y座標が与えられた場合、マウスがどのボックスの上にあったかを(長方形の計算された位置を使用して)知ることができるデータ構造/アルゴリズムはありますか? kd ツリーのようなものを考えていましたが、確信が持てませんでした。
3 に答える
6
データが常に示されている形式である場合、空間ツリーのデータ構造よりもうまくいくはずです。
データは構造化されているため、時間yのオフセットに基づいて、ポイントがどの長方形の「ストリップ」にあるかを計算できるはずですO(1)。
各「ストリップ」内に個々の長方形を ( xmaxsay を使用して) ソートされた順序で格納すると、バイナリ検索を使用してストリップ内の特定の長方形を見つけることができるはずです ( をO(log(n))参照)。
お役に立てれば。
于 2012-10-18T15:39:13.827 に答える
0
素朴な解決策は、すべての長方形を反復処理して、その中にいるかどうかを確認することです。単一の長方形をチェックするのは簡単です（必要に応じて、明示的に書き留めておきます）。
長方形が多く、パフォーマンスに関心がある場合は、長方形をデータ構造に配置することで簡単にスピードアップできます。データ構造を使用すると、より高速に表示できます。送信した画像を見ると、データの明らかな特性の1つは、制限があることです。垂直位置（「行」）の量。つまり、現在の行を確認する場合は、その行内の長方形のみを確認する必要があります。最後に、現在の行または行内の行を選択するには、並べ替えられたデータ構造（検索ツリーなど）を保持して、どの長方形を選択します。
したがって、データ構造は、行の検索ツリーのようなものであり、各ノードは行に沿って長方形の検索ツリーを保持します。
于 2012-10-18T15:40:41.413 に答える
0
R ツリーは、この種の空間アクセスを提供するのに適しています
しかし、いくつかの質問:
長方形は静的または動的に設定されていますか?
長方形セットに対していくつのポイント クエリが予想されますか?
編集：
長方形セットは静的であるため: ビットマップを使用した従来のグラフィックスで使用されるメソッドがあります (html5 キャンバスに適用できるかどうかはわかりません):
メイン画像と同じサイズの追加ビットマップを作成します。すべての四角形を同じ座標で描画しますが、一意の色で塗りつぶします (たとえば、色 = 四角形のインデックス)。次に、マウスポイントの下の色を確認します=> O(1)で長方形のインデックスを取得します
于 2012-10-18T15:50:21.350 に答える