假设我给了你一组 [(x1, y1), (x2, y2)]
形式的线段。我们有两个定义线段的点。出于我们的目的,该段将始终是水平或垂直的。我想找到由线段包围的任何矩形的最大面积。
例如,当给定以下线段集时,结果应该是绿色阴影区域的面积:
到目前为止,我能想到的唯一解决方案是蛮力 - 每对水平线段 (O(N^2)
) 与每对垂直线段 (O( N^2)
) 对于 O(N^4)
运行时。显然,我们可以通过预先计算哪些段可以放在一起来对此进行优化,但这仍会将时间复杂度保持在 O(N^4)
。
我正在寻找一个理想的 O(N^2)
解决方案,但如果您有任何小于 O(N^4)
的解决方案,请分享!
最佳答案
你可以使用线扫描算法来解决这个问题。
在这种情况下,垂直线被添加或从线集中删除,以便在向上移动时考虑。线的起点和终点都添加到扫描集中,水平线按顺序添加到列表中。
- 第 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++;
}
}
}
}
关于algorithm - 给定一组线段寻找面积最大的矩形,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/54954849/