処理スケッチに選択アルゴリズムを実装するときは、シーン内の各オブジェクトを循環し、マウスがクリックした場所から数ピクセルの範囲内にあるかどうかを確認します。たくさんのオブジェクトがあり、それらは非常に小さいです。
ご想像のとおり、シーンがオブジェクトでいっぱいになると、これは非常に負担になります。この検索を高速化する簡単な方法はありますか? この検索バイナリを簡単に作成できますか? シーン内のオブジェクトはポイントであるため、ポリゴン ヒット テスト アルゴリズムは適切なソリューションとは思えません。
シーンを N x-buckets と M y-buckets、または N*M x*y バケットのいずれかに分割します。前者の場合、バケットは 2 つの配列 (x 配列と y 配列) に格納されます。後者の場合、バケットは配列の配列に格納されます (外側の配列は x 座標にインデックスを付け、内側の配列は y 座標にインデックスを付けます)。いずれの場合も、バケットは、バケットによってインデックス付けされた領域内のすべてのポイントへの参照を格納します。たとえば、点 (8, 12) は x バケット [5, 10] と y バケット [10, 15] にあるか、そうでなければ x*y バケット ([5, 10]) にあります。 、[10、15])。
ポイントを検索するときは、適切な x バケットと y バケットを検索するか、適切な x*y バケットを検索します。前者の場合、 を取るintersection(union(x-buckets), union(y-buckets))。ヒット半径に応じて複数のバケットを検索する必要がある場合があります。たとえば、半径 2 の x 座標 9 を検索する場合、[5, 10] バケットと [10, 15] バケットの両方が必要になります。
x バケットと y バケットを別々に使用すると、使用するスペースが少なくなり (N*M バケットの代わりに N + M バケット)、インデックス作成が容易になります (2 つの別々の配列と 1 つのネストされた配列)。設定された交差点を通過する必要はありません。
バケットが小さいほど、データ構造が占めるスペースは大きくなりますが、取得する誤検知は少なくなります。理想的には、十分なメモリがある場合、バケットはヒット半径と同じ間隔をカバーします。