我有很多水平和垂直线，弥补了矩形，如在这个例子中。

I have many horizontal and vertical lines which make up rectangle such as in this example.

是否有一个算法或code，可以找到每一个不包含另一个矩形的矩形。我的意思是，在此图像中最大的矩形是不是我找的，因为它包含它里面其他矩形的矩形。

Is there an algorithm or code which can locate every rectangle which does not contain another rectangle. I mean, the largest rectangle in this image is not a rectangle I am looking for because it contains other rectangles inside of it.

我要寻找的矩形必须是空的。我有每行象（A，B）到（C，D）的起始点和结束点的列表。我想作为结果的矩形（X，Y，W，H）或等效的列表。

The rectangles I am looking for must be empty. I have a list of the starting points and end points of each line like (a,b) to (c,d). I want as a result a list of rectangles (x,y,w,h) or equivalent.

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

Note that some lines have lines intersecting them at right angles, for example the top line of the widest rectangle in this image is a single line it has an intersecting vertical line going downwards.

推荐答案

我觉得不同的重新presentation将帮助您解决问题。作为一个例子，考虑大矩形（而不在端块）。有四个唯一的x和y坐标，排序和索引它们。形象地它是这样的：

I think a different representation will help you solve your problem. As an example, consider the large rectangle (without the block on the end). There are four unique x and y coordinates, sort and index them. Pictorially it would look like this:

如果有一个长方形的一个角坐标（x_i，y_j）把它放在像这样一个矩阵：

If there is a corner of a rectangle on the coordinate (x_i, y_j) put it in a matrix like so:

__|_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）。递归算法很容易在这里和增加的速度使用记忆化，以prevent重复计算可见。

Now by definition, a rectangle in real space is a rectangle on the matrix coordinates. For example there is a rectangle at (3,2) (3,4) (4,4), (4,3) but it is not a "base" rectangle since it contains a sub-rectangle (3,3) (3,4), (4,4), (4,3). A recursive algorithm is easily seen here and for added speed use memoization to prevent repetitive calculations.