如何确定一组矩形是否包含两个有重叠区域的人？

Question

struct Rect
{
double left, right, top, bottom;
};

std::vector<Rect> vec;

现在我们有N(N> 1000)个矩形,什么是一个有效的算法来确定它们中的任何两个是否重叠？

更新: 所有这些矩形与坐标系平行.

Answer 1

您可以通过两个段表示一个矩形:开放段(x1,y1)到(x1,y2)和关闭段(x2,y1)到(x2,y2),x1 <x2和y1 <y2.

首先,我们可以通过其x坐标在O(nlogn)时间内对所有这些段进行排序.

其次,我们逐个处理每个段,如果遇到一个开放段,我们将该段的间隔(y1,y2)添加到一个区间树中,如果遇到一个关闭段,则从树中删除它.对于我们添加的每个段,我们可以查询树以查看树中有多少段与此段重叠,这也是与此矩形的开放段重叠的矩形数.每个查询的时间复杂度O(logn).

所以,我们将有一个O(nlogn)算法.