画像があり、マウスが特定の長方形の領域に移動したときにツールチップを表示したいと考えています。長方形の領域は最大 1000 まで可能です。ただし、点がその中にある場合、各長方形をチェックするだけで、O(N) であり、マウスを動かしたときにインターフェイスが応答しなくなります。
O(N)未満でそれを行う方法はありますか? 事前に四角形を並べ替えることができます（必要になると思います）。四角形は (ごくまれに) 重なっている場合がありますが、同じ領域に重なる四角形は 4 ～ 5 個までです。その場合、すべての長方形のリストを取得する必要があるかもしれませんが、それらのどれかだけでも十分です。
しかし、この問題はウィンドウマネージャーなどによってすでに解決されていると思います。
R ツリー内に四角形を格納し、それを照会したいようです。いくつかの実装が利用可能です:
彼らの STRtree クラスをチェックしてください。
画像 (およびかなり小さい画像にレンダリングできる Web ページ) のツリーよりも高速で単純な (メモリ効率は劣りますが) 方法は、ステンシルを使用することです。つまり、x x y ピクセルの画像がある場合は、x x y のサイズの 2 次元配列を作成し、ツール ヒント ID を入力します。これは、ピクセル位置から O(1) の ID までの検索速度を持っています (私のお気に入りの O)
四角形が軸に沿って配置されている場合は、特殊なデータ構造を避けることができます。
最初に空間を 1 次元で分割します。たとえば、画面を水平方向に分割して垂直ストリップに分割します。各長方形は、複数のストリップに含まれる場合があります。次に、そのストリップに重なる長方形に応じて、各ストリップを細分化します。次に、検索には 2 つの O(log n) バイナリ検索またはバイナリ ツリーが含まれます。1 つはストリップを識別し、もう 1 つはどの長方形を識別するかです。
これは認識された空間データ構造ですが、私には実際にはカウントされません。通常のバイナリ ツリーを使用しているだけです。.でそれを行うこともできますstd::map<int, std::map<int, int>>。
しかし、実際には、「ピクセル ピッキング」と呼ばれる O(1) 検索をサポートするオプションがあります。基本的に、四角形をオフスクリーン ビットマップで描画し、各四角形を異なる色で描画し、最前面の四角形は通常の描画 (ペインター アルゴリズム) と同じように最後に描きます。そのピクセルを読み取るだけで、任意の時点でどの長方形が最前面にあるかを識別できます。
追加のボーナス - グラフィックカードは長方形の描画を高速化することさえできるので、長方形のセットが変更されたときの再描画についてあまり心配する必要はありません (明らかにその O(1) には含まれていません)。メモリは少し高価ですが、最新のマシンでは気にしないかもしれません。
quad-treeなどの空間検索データ構造を使用します。
事前に長方形をツリーに追加する必要がありますが、平均的な検索は高速です。最悪の場合、まだ O(N) があるかもしれません。