给定一组线段，找到面积最大的矩形

Question

假设我给你一组形如 [(x1, y1), (x2, y2)] 的线段。我们有两个点来定义一个线段。对于我们的目的，这个线段总是水平或垂直的。我想找到由这些线段所围成的矩形中最大的面积。

例如，当给定以下线段集合时，结果应该是绿色阴影区域的面积：

到目前为止，我所能想到的唯一解决方案是蛮力法-每对水平线段（O(N^2)）与每对垂直线段（O(N^2)）进行检查，运行时间为O(N^4)。显然，我们可以通过预计算哪些线段可以组合在一起来优化这个过程，但这仍然会保持时间复杂度为O(N^4)。我正在寻找理想情况下的O(N^2)解决方案，但如果你有任何小于O(N^4)的解决方案，请分享！

- Mark Tyler

Answer 1

你可以使用线扫描算法解决这个问题。

在这种情况下，当向上移动时，垂直线被添加或从线集中删除。线的起始和结束点都被添加到扫描集中，水平线按顺序添加到列表中。 步骤1：将线添加到activeVertical中 步骤2：将第二条线添加到activeVertical中 步骤3：将第三条线添加到activeVertical中（注意：它们按X顺序排列）。 步骤4a：将第四条线添加到activeVertical中 步骤4b：找到水平线，创建一个高度为0的矩形 步骤5：找到第二条水平线，检查前一个矩形是否已完成

以下是代码（C＃）。您可以在此处找到有关线扫描算法的更多详细信息：https://en.wikipedia.org/wiki/Sweep_line_algorithm

using System;
using System.Collections.Generic;
using System.Linq;

namespace tt
{
    public class Point
    {
        public Point(double X, double Y)
        {
            this.X = X;
            this.Y = Y;
        }
        public double X { get; set; }
        public double Y { get; set; }
    }
    public class Line
    {
        public Point Start { get; set; }
        public Point End { get; set; }
    }

    public class Rectangle
    {
        public Rectangle()
        { }
        public Rectangle(Point BottomLeft, Point TopRight)
        {
            this.BottomLeft = BottomLeft;
            this.TopRight = TopRight;
        }
        public Point BottomLeft { get; set; }
        public Point TopRight { get; set; }
    }

    public class XComparer : IComparer<Line>
    {
        public int Compare(Line x, Line y)
        {
            return x.Start.X.CompareTo(y.Start.X);
        }
    }

    public class Program
    {
        public static int GetMinIndex(List<Line> Lines, Line Horizontal)
        {
            var xComp = new XComparer();
            int minIndex = Lines.BinarySearch(Horizontal, xComp);
            if (minIndex < 0) minIndex = ~minIndex;
            return minIndex;
        }

        public static int GetMaxIndex(List<Line> Lines, Line Horizontal)
        {
        var xComp = new XComparer();
        int maxIndex = Lines.BinarySearch(new Line() { Start = Horizontal.End }, xComp);
        if (maxIndex < 0) maxIndex = ~maxIndex - 1;
        return maxIndex;
    }
    public static void Main()
    {
        List<Line> lines = new List<Line>();
        lines.Add(new Line() { Start = new Point(0.5, 12.5), End = new Point(10, 12.5)  });
        lines.Add(new Line() { Start = new Point(2.5, 9.5), End = new Point(15.8, 9.5) });
        lines.Add(new Line() { Start = new Point(6, 8.5), End = new Point(16.3, 8.5) });
        lines.Add(new Line() { Start = new Point(3.5, 8.5), End = new Point(3.5, 12.5) });
        lines.Add(new Line() { Start = new Point(7, 4.2), End = new Point(7, 13.8) });
        lines.Add(new Line() { Start = new Point(10, 5.8), End = new Point(10, 14.2) });
        lines.Add(new Line() { Start = new Point(15.6, 0), End = new Point(15.6, 16) });
        lines.Add(new Line() { Start = new Point(1.6, 20), End = new Point(15.6, 20) });

        var activeVertical = new List<Line>();

        SortedList<double, List<Line>> sweepSet = new SortedList<double, List<Line>>();

        foreach (Line oneLine in lines.Where(x => x.Start.X == x.End.X))
        {
            if (!sweepSet.ContainsKey(oneLine.Start.Y)) sweepSet.Add(oneLine.Start.Y, new List<Line>());
            sweepSet[oneLine.Start.Y].Add(oneLine);

            if (!sweepSet.ContainsKey(oneLine.End.Y)) sweepSet.Add(oneLine.End.Y, new List<Line>());
            sweepSet[oneLine.End.Y].Add(oneLine);
        }

        var linesHorizontal = lines.Where(x => x.Start.Y == x.End.Y).OrderBy(x => x.Start.Y).ToList();

        List<Rectangle> rectangles = new List<Rectangle>();
        List<Rectangle> completedRectangles = new List<Rectangle>();
        var xComp = new XComparer();

        int horIndex = 0;
        int sweepIndex = 0;
        while (sweepIndex < sweepSet.Count)
        {
            double y = Math.Min(sweepSet.Keys[sweepIndex], linesHorizontal[horIndex].Start.Y);

            double verValue = linesHorizontal[horIndex].Start.Y;
            //add lines which are influencing
            if (sweepSet.ContainsKey(y))
            {
                foreach (Line oneLine in sweepSet[y].Where(x => x.Start.Y == y))
                {

                    int index = activeVertical.BinarySearch(oneLine, xComp);
                    if (index < 0) index = ~index;
                    activeVertical.Insert(index, oneLine);
               }
            }
            if (y == verValue)
            {
                int minIndex = GetMinIndex(activeVertical, linesHorizontal[horIndex]);
                int maxIndex = GetMaxIndex(activeVertical, linesHorizontal[horIndex]);


                if (minIndex != maxIndex && minIndex < activeVertical.Count && maxIndex < activeVertical.Count)
                {
                    double minX = activeVertical[minIndex].Start.X;
                    double maxX = activeVertical[maxIndex].Start.X;

                    foreach (Rectangle oneRec in rectangles)
                    {
                        if (minX > oneRec.BottomLeft.X) oneRec.BottomLeft.X = minX;
                        if (maxX < oneRec.TopRight.X) oneRec.TopRight.X = maxX;
                        oneRec.TopRight.Y = verValue;
                    }
                    completedRectangles.AddRange(rectangles);
                    rectangles.Clear();


                    rectangles.Add(new Rectangle(new Point(activeVertical[minIndex].Start.X, verValue), new Point(activeVertical[maxIndex].Start.X, verValue)));
                }
                else rectangles.Clear();
            }
            //Cleanup lines which end
            if (sweepSet.ContainsKey(y))
            {
                foreach (Line oneLine in sweepSet[y].Where(x => x.End.Y == y))
                {

                    activeVertical.Remove(oneLine);
                }
            }

            if (y >= verValue)
            {
                horIndex++;
                if (horIndex == linesHorizontal.Count) break;
                if (y == sweepSet.Keys[sweepIndex]) sweepIndex++;
            }
            else
            {
                sweepIndex++;
            }
        }
    }
}

}

- Aldert

Answer 2

使用扫描法可以找到所有垂直线和水平线的交点。按y值递增的顺序处理所有线条。维护一个缓冲区，包含所有垂直线，包括当前y值。为每个垂直线的x值保持缓冲区排序。当遇到每条水平线时，检查它是否与缓冲区中的任何线相交。最坏情况下的成本是O(N^2)个交点。

现在你有一个交点列表，以及每条线段被交叉的位置的列表。对于每条水平线，我们将关注每个交点，在该交点处沿着垂直线可以向下走多远。将这些值存储在数组中。将这些值分成一对，并将每对中的最大值存储在数组中。对于每个最大值，重复此过程。这构建了一个值树，其中叶子是原始值，按原始顺序排列，每个节点携带在任何后代中找到的最大值。总成本与交点数量成线性关系。

现在对于每个交点，假设它是一个矩形的左下角。对于其上方的每个交点所在的垂直线，找到与之相交的水平线并在该线上找到最右边的点，使得你可以向下走至少到达交点。这样建立了一棵树，可以在时间复杂度为垂直线上的交点数的对数级别内找到这个点：从树的顶部开始，如果该子节点的值至少与你需要前进的距离相等，则向右走，否则向左走。这样可以找到使用该左下角和该水平线的最大矩形，因此对于每条水平线检查此内容会给出包括该交点作为左下角的最大矩形，对于每个交点重复此操作会给出整体最大矩形。

如果线条形成N x N网格，则对于每个交点，在其上方检查O(N)条水平线的成本为O(log N)，因此这个阶段的总成本在最坏情况下为O(N^3log(N))。

- mcdowella

Answer 3

您提供的例子：

实际上，一旦我们提取并合并仅由交叉点形成的矩形，它就会简化为类似于这样的东西：

---------------------
|                   |
|                   |
|                   |
|                   |
---------           ------------------
        |                            |
        |____________________________|

那么问题就变成了在一个直角（也称为正交）多边形中找到最大的矩形，这方面有很多文献可供参考。

- גלעד ברקן