Нахождение прямоугольника с наибольшей площадью по набору отрезков

Вы можете использовать алгоритм строчной развертки с этой проблемой.

В этом случае вертикальные линии добавляются или удаляются из набора линий для учета при движении вверх. Оба запуска & amp; конечные точки или линии добавляются в набор, а горизонтальные линии добавляются в список.

• шаг 1: строка добавлена ​​в шаг activeVertical
• шаг 2: вторая строка добавлена ​​в шаг activeVertical
• 3: третья строка добавлена ​​к activeVertical (примечание: они в порядке X).
• шаг 4a: четвертая строка добавлена ​​к activeVertical
• шаг 4b: найдена горизонтальная линия, время создания прямоугольника без высоты
• шаг 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++;
            }
        }
    }
}

}

С помощью сканирования вы можете найти все пересечения между вертикальными и горизонтальными линиями. Пройдите все строки в порядке увеличения y. Поддерживать буфер, содержащий все вертикальные линии, включая текущее значение y. Сохраняйте буфер отсортированным по значению x для каждой вертикальной линии. Когда вы подходите к каждой горизонтальной линии, проверьте, не пересекает ли она какую-либо из строк в буфере. В худшем случае это происходит при наличии O (N ^ 2) пересечений.

Теперь у вас есть список пересечений и список, для каждой линии, где он пересекается. Для каждой горизонтальной линии нас будет интересовать, для каждого пересечения, насколько далеко вы можете пройти по вертикальной линии на этом пересечении. Сохраните эти значения в массиве. Разделите эти значения на пары и сохраните максимум каждой пары в массиве. Повторите процесс для каждого максимума и так далее. Это создает дерево значений, где листья являются исходными значениями в исходном порядке, и каждый узел несет максимальное значение, найденное в любом потомке. Общая стоимость этого является линейной по количеству пересечений.

Теперь возьмем каждое пересечение и предположим, что это нижний левый угол прямоугольника. Для каждого пересечения над ним на его вертикальной линии посмотрите на пересекающуюся горизонтальную линию и найдите крайнюю правую точку на этой линии, где вы можете спуститься хотя бы до пересечения. Вы построили дерево, которое позволяет вам находить это по времени логарифмически по количеству пересечений на этой линии: начните с вершины дерева и идите направо, если значение у этого потомка хотя бы настолько далеко, насколько вам нужно, остальное иди налево. Нахождение этого дает вам наибольший прямоугольник, используя эту левую нижнюю границу и эту горизонтальную линию, поэтому проверка этого для каждой горизонтальной линии дает вам наибольший прямоугольник, включая это пересечение как нижний левый, и повторение этого для каждого пересечения дает вам общий наибольший прямоугольник. [112 ]

Если линии образуют сетку N x N, то для каждого пересечения вы проверяете горизонтальные линии O (N) над ним по стоимости O (log N), поэтому общая стоимость этого этапа составляет O (N ^ 3log (N)). в худшем случае.

Пример, который вы предоставили:

фактически упрощается до чего-то подобного, когда мы извлекаем и объединяем только прямоугольники, образованные пересечениями:

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

Тогда возникает проблема нахождения наибольшего прямоугольника в прямолинейном (иначе ортогональном) многоугольнике, для которого существует множество литературы.