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

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。

首先，我们可以在 O(nlogn) 时间内根据其 x 坐标对所有这些段进行排序。

其次，我们逐个处理每个段，如果我们遇到一个开放段，我们将该段的interval (y1, y2) 添加到interval tree 中，如果我们遇到一个接近的段，将其从树中移除。对于我们添加的每个线段，我们可以查询树以查看树中有多少线段与该线段重叠，这也是与该矩形的开放线段重叠的矩形数。每个查询的时间复杂度 O(logn)。

因此，我们将有一个 O(nlogn) 算法。