8

我有许多水平和垂直线组成矩形，例如在这个例子中。

横竖线图片

是否有一种算法或代码可以定位每个不包含另一个矩形的矩形。我的意思是，这张图片中最大的矩形不是我要找的矩形，因为它里面包含其他矩形。

我正在寻找的矩形必须是空的。我有每条线的起点和终点的列表，例如（a，b）到（c，d）。因此，我想要一个矩形列表 (x,y,w,h) 或等效项。

请注意，有些线的线与它们成直角相交，例如，此图像中最宽矩形的顶线是一条线，它有一条向下相交的垂直线。

4

4 回答 4

2

我认为不同的表示将帮助您解决问题。例如，考虑大矩形（末端没有块）。有四个唯一的 x 和 y 坐标，对它们进行排序和索引。从图形上看，它看起来像这样：

在此处输入图像描述

如果坐标上有一个矩形的角，(x_i, y_j)则将其放入矩阵中，如下所示：

__|_1__2__3__4_
1 | x  x  0  x
2 | x  x  0  0
3 | 0  x  x  x
4 | x  x  x  x

现在根据定义，真实空间中的矩形是矩阵坐标上的矩形。例如，有一个矩形，(3,2) (3,4) (4,4), (4,3)但它不是“基本”矩形，因为它包含一个子矩形(3,3) (3,4), (4,4), (4,3)。这里很容易看到递归算法，为了提高速度，请使用记忆化来防止重复计算。

于 2013-04-24T17:36:08.713 回答
2

扫线算法...

所需结构：

  • V = 一组垂直线，按 x 坐标排序。

  • H = 一组水平线的所有起点和终点（并让每个点保持对线的引用）并按 x 坐标排序。

  • CH =当前水平线的一组（最初为空）排序（按 y 坐标） 。

  • CR = 一组已排序（按 y 坐标）的当前矩形。这些矩形将具有左、上和下坐标，但还没有右坐标。请注意，此集合中不会有重叠。

算法：

从左到右同时处理 V 和 H。

每当遇到水平线的起点时，将该线添加到 CH。

每当遇到水平线的末端时，将其从 CH 中删除。

每当遇到垂直线时：

  • 从 CR 中删除与该线重叠的所有矩形。对于所有移除的矩形，如果它完全包含在该行内，则将其大小与迄今为止最好的矩形进行比较，如果更好则将其存储。

  • 在行的底点和顶点之间迭代地处理 CH 中的每个元素，如下所示：

    • 向 CR 添加一个矩形，最后处理的点为底部，当前点为顶部，垂直线的 y 坐标为左侧。

完毕。

笔记：

当水平起点或终点或垂直线的 x 坐标相等时，必须保持以下顺序：

x of horizontal start < x of vertical line < x of horizontal finish

否则你会错过矩形。

于 2013-04-24T18:04:13.773 回答
2

Computational Geometry一些标准算法在很大程度上回答了这类问题。我可以vertical sweep line为这个特定问题想出一个算法。

假设一个矩形由一对点表示(p1, p2)，其中p1是左上角，p2是右下角。一个点有两个属性（可以访问为p.x和p.y）。

这是算法。

  1. 对所有点对进行排序 -O(n log n)
  2. 初始化一个名为 的列表sweep line status。这将保存到目前为止遇到的所有矩形，即alive. 还要初始化另一个名为的列表event queue，该列表包含即将发生的事件。这event queue目前包含所有矩形的起点。
  3. 处理事件，从event queue.
    • 如果事件是 a start point，则将该矩形添加到sweep line status（按 y 坐标排序）（O(log n)及时），并将其右下角添加到event queue适当位置的 （按点排序）（再次O(log n)及时）。当您将它添加到 时sweep line status，您只需要检查该点是否位于sweep line status. 如果它确实位于内部，则这不是您的矩形，否则，请将其添加到所需矩形列表中。
    • 如果事件是一个端点，只需从sweep line status.

运行时间（对于 n 个矩形）：

  • 排序需要O(n log n).
  • 事件数 = 2*n =O(n)
  • 每个事件都需要O(log n)时间（对于插入event queue以及sweep line status. 所以总数是O(n log n).

因此，O(n log n)。

更多细节请参考Bentley-Ottmann 算法。以上只是对此的简单修改。

编辑：

刚刚意识到输入是线段，但由于它们总是形成矩形（根据问题），预处理的线性遍历可以将它们转换为矩形（点对）形式。

于 2013-04-24T18:19:08.940 回答
0

你所有的线都平行于 x 轴还是 y 轴？或者，你所有的线都是平行的还是垂直的？

从您给出的示例中，我假设您的所有线都平行于 x 或 y 轴。在这种情况下，您的行将是 [(a,b), (a,d)] 或 [(a,b), (c,b)]。

无论如何，首要任务是找到角落。那是两条垂直线相交的点的集合。

第二个任务是检测矩形。对于每一对角，您可以检查它们是否形成矩形。

第三个任务是查找矩形内部是否有任何矩形。

对于第一个任务，您需要将线条分成两组：垂直和水平。在那之后排序一组。前任。根据 x 轴坐标对垂直线进行排序。然后你可以取所有水平线并进行二进制搜索以找到所有相交点。

对于第二个任务，考虑每一对角并查看其他两个角是否存在。如果是，则查看是否有连接所有这四个角的线。如果是，你有一个矩形。

对于第三个任务，将所有矩形放在一个区间树中。之后，您可以检查两个矩形是否重叠。

于 2013-04-24T17:29:17.310 回答