多数の不規則な長方形を含むインタラクティブな SVG ダイアグラムを作成しています。ユーザーが SVG の領域内をクリックすると、それに基づいて、そのオブジェクトに関する詳細情報が提供されます。(少し単純化しています。これは産業用アプリケーションであり、領域は実際には四角形ではありません。ただし、各形状の境界四角形を使用できると仮定します。)
残念ながら、一部の長方形には他の長方形が「完全に含まれています」。たとえば、R2 は、別の長方形 R1 内に「完全に含まれる」小さな長方形である可能性があります。R1 の後にR2が SVG ファイルに追加されている場合、小さな長方形 R2 はインタラクティブです。残念ながら、オブジェクトの入力ストリームはこれを保証しません。R1 の後に R2 を取得する場合があります。その後、R1 が印刷されるため、R2 は R1 によって完全に覆われているため、クリックできません。(オブジェクトは半透明なので、R1 は表示されたままです – クリックできないだけです – 最も面倒です!)
したがって、「Ri」が「Rj」に含まれていないことを保証できる「j」未満のすべての「i」となるように、四角形配列をソートしたいと考えています。しかし、これとは別に、元のシーケンスの z オーダーへの乱れを最小限に抑えたいと考えています。何千もの四角形をソートする必要があるため、どのアルゴリズムを選択しても、n 乗の動作を行わない方がよいでしょう。
私は当初、これはグラフィックス システムではかなり一般的な問題だと思っていました。しかし、文献をスキャンしても、そうであるとは思えません。私はこれに取り組むためのいくつかのアイデアを持っています - スペースを領域に分割する (KD ツリー) および/または領域ごとに四角形を並べ替える (小さな四角形に大きな四角形を含めることはできません!)。この問題の解決策はすでに出ています。おそらく、私は正しい検索用語を使用していないだけです。
何か案は ？