用于保存矩形列表的数据结构？
Mic*_*ael 7 sorting algorithm data-structures
我想知道是否有一个良好的数据结构来保存轴对齐的非重叠离散空间矩形的列表.因此,每个矩形可以存储为整数x,y,宽度和高度.只存储这样的列表会很容易,但我也希望能够查询给定的x,y坐标是否在任何其他矩形内.
一个简单的解决方案是创建一个哈希并用每个矩形开头的散列左下坐标填充它.这不允许我测试给定的x,y坐标,因为它会击中中间的空白区域.另一个答案是在哈希表中创建一堆边,用单位正方形覆盖整个矩形.这会为100×100的矩形创建太多不必要的条目.
