Finding rectangle with largest area given a set of line segments

Question

Imagine I gave you a set of line segments in the form [(x1, y1), (x2, y2)]. We've got two points that define a line segment. For our purposes this segment will always be horizontal or vertical. I want to find the largest area of any rectangle enclosed by the line segments.

For example when given the set of the following line segments the result should be the area of the green shaded area:

So far the only solution I can think of is brute force - every pair of horizontal segments (O(N^2)) being checked with every pair of vertical segments (O(N^2)) for an O(N^4) runtime. Obviously we can optimize this by precomputing which segments can be put together, but that will still keep the time complexity at O(N^4).

I'm looking for ideally an O(N^2) solution but if you have anything less than O(N^4) please share!

Answer 1

You can use the line-sweep algorithm with this problem.

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.

• step 1: line is added to activeVertical
• step 2: second line added to activeVertical
• step 3: third line added to activeVertical (note: they are in order of X).
• step 4a: fourth line added to activeVertical
• step 4b: Horizontal line found, time to create a rectangle which does not have any height
• step 5: second horizontal line found, time to check finish previous rectangle

etc.

Below the code (C#). Yuo can find more details on line sweep algorithm here: 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++;
            }
        }
    }
}

}

Answer 2

You can find all intersections between vertical lines and horizontal lines with scan. Work through all lines in order of increasing y. Maintain a buffer containing all vertical lines including the current value of y. Keep the buffer sorted on the x value for each vertical line. As you come to each horizontal line, check to see if it intersects any of the lines in the buffer. The worst case cost of this is when there are O(N^2) intersections.

Now you have a list of intersections, and a list, for each line, of where it is intersected. For each horizontal line we will be interested, for each intersection, in how far down you can go following the vertical line at that intersection. Store these values in an array. Divide these values up into pairs and store the maximum of each pair in the array. Repeat the process for each maximum, and so on. This builds a tree of values where the leaves are the original values, in the original order, and each node carries the maximum value found in any descendant. The total cost of this is linear in the number of intersections.

Now take every intersection and assume it is the bottom left corner of a rectangle. For each intersection above it on its vertical line look at the intersecting horizontal line and find the rightmost point on this line where you can go down at least as far as the intersection. You have built a tree that allows you to find this in time logarithmic in the number of intersections on that line: start from the top of the tree and go right if the value at that child is at least as far as you need to go, else go left. Finding this gives you the largest rectangle using that bottom left and that horizontal line, so checking this for each horizontal line gives you the largest rectangle including that intersection as bottom left, and repeating this for each intersection gives you the overall largest rectangle.

If the lines form an N x N grid then for each intersection you check O(N) horizontal lines above it at cost O(log N) so the total cost of this stage is O(N^3log(N)) in the worst case.

Answer 3

The example you provided:

actually simplifies to something like this once we extract and merge only the rectangles formed by intersections:

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

Then the problem becomes finding the largest rectangle in a rectilinear (aka orthogonal) polygon, for which there is a bunch of literature out there.