我们正在创建包含大量不规则矩形的交互式 SVG 图表。我们的用户在 SVG 的某个区域内单击，并基于此提供有关该对象的更多信息。（我稍微简化了一点——这是一个工业应用程序，这些区域实际上不是矩形——但我假设我们可以使用每个形状的边界矩形。）
不幸的是，一些矩形“完全包含”了其他一些矩形。例如，R2 可以是一个“完全包含”在另一个矩形 R1 中的小矩形。如果在 R1之后将R2 添加到 SVG 文件，那么小矩形 R2 是交互式的。不幸的是，对象的输入流并不能保证这一点。我可能会在 R1 之后得到 R2。然后 R1 被打印出来，因此 R2 不能被点击，因为它完全被 R1 覆盖。（对象是半透明的，所以 R1 仍然可见 - 只是不可点击 - 最烦人的！）
因此，我们想要对矩形数组进行排序，使得所有“i”都小于“j”，我们可以保证“Ri”不包含在“Rj”中。但除此之外，我们希望对原始序列的 z 顺序产生最小的干扰。我们将有数千个矩形要排序——所以无论我们选择什么算法，最好不要有 n 平方行为。
我最初认为这将是图形系统中相当普遍的问题。但对文献的扫描似乎并不表明它是。我自己对此有一些想法 - 包括将空间分成区域（KD树）和/或按区域对矩形进行排序（小矩形不能包含大矩形！）但是，找到一个好的这个问题的解决方案已经存在。也许我只是没有使用正确的搜索词。
有任何想法吗 ？