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

想象一下我给了你一组如下形式的线段[(x1, y1), (x2, y2)]。我们有两个点定义了一条线段。就我们的目的而言，该部分始终是水平或垂直的。我想找到由线段包围的任何矩形的最大面积。

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

到目前为止，我能想到的唯一解决方案是蛮力 - 每对水平段（O(N^2)）用每对垂直线段（O(N^2)） 为O(N^4)运行。显然，我们可以通过预先计算哪些片段可以放在一起来优化这一点，但这仍然会将时间复杂度保持在O(N^4).

我正在寻找理想的O(N^2)解决方案，但如果你有任何小于O(N^4)请分享！

您可以使用线扫描算法来解决此问题。

In this case, the vertical lines are added or removed from the set of lines to take into account when moving up. Both start & end points o the lines are added to the sweepset and the horizontal lines are added in order to a list.

• 第 1 步：将线添加到 activeVertical
• 步骤 2：将第二行添加到 activeVertical
• 步骤3：将第三行添加到activeVertical（注意：它们按X的顺序排列）。
• 步骤 4a：将第四行添加到 activeVertical
• 步骤 4b：找到水平线，是时候创建一个不存在的矩形了 有任意高度
• 步骤 5：找到第二条水平线，检查完成前一个矩形的时间

etc.

下面是代码（C#）。您可以在此处找到有关线扫描算法的更多详细信息：https://en.wikipedia.org/wiki/Sweep_line_algorithm 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++;
            }
        }
    }
}

}