寻求在不规则多边形中查找多个大矩形的算法方案

我完全理解你的困扰——从一堆线段组成的不规则多边形里提取可见的大矩形确实是个挺有挑战性的问题，改进BFS效果不佳也很正常，因为BFS更擅长轮廓追踪，对矩形这种结构化形状的针对性不强。下面我给你分享两种实用的思路，附C#代码示例，应该能帮你解决问题：

方法一：基于线段匹配的精确矩形检测 #

这个方法的核心是利用矩形的几何特征：两两平行且垂直的边，四个端点闭合相连。步骤如下：

1. 先把所有线段按水平/垂直方向分类（用小阈值处理浮点误差，避免因精度问题误判）
2. 对同一高度的水平线段，两两配对，检查它们的长度是否接近，且两端点是否有对应的垂直线段连接
3. 验证构造出的矩形内部是否被其他线段遮挡（确保是“可见”的）
4. 过滤掉被大矩形包含的小矩形，只保留面积较大的结果

C#代码实现 #

首先定义基础数据结构：

public class Segment
{
    public Point Start { get; set; }
    public Point End { get; set; }
    // 用小阈值判断水平/垂直，避免浮点精度问题
    public bool IsHorizontal => Math.Abs(Start.Y - End.Y) < 1e-3;
    public bool IsVertical => Math.Abs(Start.X - End.X) < 1e-3;
    public double Y => IsHorizontal ? Start.Y : double.NaN;
    public double X => IsVertical ? Start.X : double.NaN;
    public double Length => Math.Sqrt(Math.Pow(End.X - Start.X, 2) + Math.Pow(End.Y - Start.Y, 2));
}

public struct Point
{
    public double X { get; set; }
    public double Y { get; set; }
    public Point(double x, double y) => (X, Y) = (x, y);
    public override bool Equals(object obj) => obj is Point p && Math.Abs(X - p.X) < 1e-3 && Math.Abs(Y - p.Y) < 1e-3;
    public override int GetHashCode() => HashCode.Combine(Math.Round(X, 3), Math.Round(Y, 3));
}

public class Rectangle
{
    public Point BottomLeft { get; set; }
    public Point TopRight { get; set; }
    public double Left => BottomLeft.X;
    public double Right => TopRight.X;
    public double Bottom => BottomLeft.Y;
    public double Top => TopRight.Y;
    public double Area => (Right - Left) * (Top - Bottom);

    public Rectangle(Point bottomLeft, Point topRight) => (BottomLeft, TopRight) = (bottomLeft, topRight);

    // 获取矩形的四条边线段
    public List<Segment> GetEdges()
    {
        return new List<Segment>
        {
            new Segment { Start = BottomLeft, End = new Point(Right, Bottom) },
            new Segment { Start = new Point(Right, Bottom), End = TopRight },
            new Segment { Start = TopRight, End = new Point(Left, Top) },
            new Segment { Start = new Point(Left, Top), End = BottomLeft }
        };
    }
}

然后是核心检测逻辑：

public List<Rectangle> FindVisibleLargeRectangles(List<Segment> segments)
{
    var horizontalGroups = segments.Where(s => s.IsHorizontal).GroupBy(s => Math.Round(s.Y, 3)).ToList();
    var verticalGroups = segments.Where(s => s.IsVertical).GroupBy(s => Math.Round(s.X, 3)).ToList();
    var rectangles = new List<Rectangle>();

    // 遍历所有水平线段组
    foreach (var hGroup in horizontalGroups)
    {
        var sortedHorizontals = hGroup.OrderBy(s => Math.Min(s.Start.X, s.End.X)).ToList();
        // 两两配对水平线段
        for (int i = 0; i < sortedHorizontals.Count; i++)
        {
            var h1 = sortedHorizontals[i];
            for (int j = i + 1; j < sortedHorizontals.Count; j++)
            {
                var h2 = sortedHorizontals[j];
                // 检查长度是否相近
                if (Math.Abs(h1.Length - h2.Length) > 1e-2) continue;

                // 获取两条线段的左右端点
                var h1Left = new Point(Math.Min(h1.Start.X, h1.End.X), h1.Y);
                var h1Right = new Point(Math.Max(h1.Start.X, h1.End.X), h1.Y);
                var h2Left = new Point(Math.Min(h2.Start.X, h2.End.X), h2.Y);
                var h2Right = new Point(Math.Max(h2.Start.X, h2.End.X), h2.Y);

                // 检查左右是否有对应的垂直线段连接
                if (!HasVerticalSegment(verticalGroups, h1Left, h2Left)) continue;
                if (!HasVerticalSegment(verticalGroups, h1Right, h2Right)) continue;

                // 构造矩形
                var rect = new Rectangle(
                    new Point(Math.Min(h1Left.X, h2Left.X), Math.Min(h1Left.Y, h2Left.Y)),
                    new Point(Math.Max(h1Right.X, h2Right.X), Math.Max(h1Right.Y, h2Right.Y))
                );

                // 验证矩形是否可见（内部无遮挡线段）
                if (IsRectangleVisible(rect, segments))
                {
                    rectangles.Add(rect);
                }
            }
        }
    }

    // 去重并按面积降序排序，返回较大的矩形
    return rectangles
        .Distinct()
        .OrderByDescending(r => r.Area)
        .ToList();
}

// 检查是否存在连接两个点的垂直线段
private bool HasVerticalSegment(List<IGrouping<double, Segment>> verticalGroups, Point p1, Point p2)
{
    var xKey = Math.Round(p1.X, 3);
    var vGroup = verticalGroups.FirstOrDefault(g => Math.Abs(g.Key - xKey) < 1e-3);
    if (vGroup == null) return false;

    return vGroup.Any(v => 
        (Math.Abs(v.Start.Y - p1.Y) < 1e-3 && Math.Abs(v.End.Y - p2.Y) < 1e-3) ||
        (Math.Abs(v.End.Y - p1.Y) < 1e-3 && Math.Abs(v.Start.Y - p2.Y) < 1e-3));
}

// 验证矩形是否可见：无线段穿过内部
private bool IsRectangleVisible(Rectangle rect, List<Segment> segments)
{
    foreach (var seg in segments)
    {
        // 跳过矩形的边
        if (seg.IsHorizontal && (Math.Abs(seg.Y - rect.Top) < 1e-3 || Math.Abs(seg.Y - rect.Bottom) < 1e-3))
            continue;
        if (seg.IsVertical && (Math.Abs(seg.X - rect.Left) < 1e-3 || Math.Abs(seg.X - rect.Right) < 1e-3))
            continue;

        // 检查线段是否与矩形内部相交
        if (DoSegmentIntersectRectangle(seg, rect))
            return false;
    }
    return true;
}

// 判断线段是否与矩形相交
private bool DoSegmentIntersectRectangle(Segment seg, Rectangle rect)
{
    var rectEdges = rect.GetEdges();
    foreach (var rectEdge in rectEdges)
    {
        if (DoSegmentsIntersect(seg, rectEdge))
            return true;
    }
    return false;
}

// 跨立实验判断两条线段是否相交
private bool DoSegmentsIntersect(Segment a, Segment b)
{
    double CCW(Point p, Point q, Point r) => (q.X - p.X) * (r.Y - p.Y) - (q.Y - p.Y) * (r.X - p.X);

    var ccw1 = CCW(a.Start, a.End, b.Start);
    var ccw2 = CCW(a.Start, a.End, b.End);
    var ccw3 = CCW(b.Start, b.End, a.Start);
    var ccw4 = CCW(b.Start, b.End, a.End);

    // 标准跨立条件
    if (((ccw1 > 1e-3 && ccw2 < -1e-3) || (ccw1 < -1e-3 && ccw2 > 1e-3)) &&
        ((ccw3 > 1e-3 && ccw4 < -1e-3) || (ccw3 < -1e-3 && ccw4 > 1e-3)))
        return true;

    // 处理共线端点在另一条线段上的情况
    if (Math.Abs(ccw1) < 1e-3 && IsPointOnSegment(b.Start, a)) return true;
    if (Math.Abs(ccw2) < 1e-3 && IsPointOnSegment(b.End, a)) return true;
    if (Math.Abs(ccw3) < 1e-3 && IsPointOnSegment(a.Start, b)) return true;
    if (Math.Abs(ccw4) < 1e-3 && IsPointOnSegment(a.End, b)) return true;

    return false;
}

private bool IsPointOnSegment(Point p, Segment seg)
{
    return Math.Min(seg.Start.X, seg.End.X) - 1e-3 <= p.X && p.X <= Math.Max(seg.Start.X, seg.End.X) + 1e-3 &&
           Math.Min(seg.Start.Y, seg.End.Y) - 1e-3 <= p.Y && p.Y <= Math.Max(seg.Start.Y, seg.End.Y) + 1e-3;
}

方法二：网格采样的近似矩形检测 #

如果不需要绝对精确的矩形边界，这个方法更简单高效，适合快速找到近似的大可见区域：

1. 把多边形所在区域划分成均匀网格
2. 标记被线段覆盖或多边形外部的网格单元
3. 用BFS找出最大的连续可用网格区域，转化为矩形

C#代码实现 #

public List<Rectangle> FindApproximateLargeRectangles(List<Segment> segments, double gridSize = 10.0)
{
    // 计算多边形的边界范围
    var allPoints = segments.SelectMany(s => new[] { s.Start, s.End }).ToList();
    double minX = allPoints.Min(p => p.X);
    double maxX = allPoints.Max(p => p.X);
    double minY = allPoints.Min(p => p.Y);
    double maxY = allPoints.Max(p => p.Y);

    int gridWidth = (int)Math.Ceiling((maxX - minX) / gridSize);
    int gridHeight = (int)Math.Ceiling((maxY - minY) / gridSize);

    // 网格：true表示被占用（线段覆盖/多边形外），false表示可用
    bool[,] grid = new bool[gridWidth, gridHeight];
    bool[,] visited = new bool[gridWidth, gridHeight];

    // 标记被线段覆盖的网格
    foreach (var seg in segments)
    {
        foreach (var p in GetGridPointsAlongSegment(seg, gridSize, minX, minY))
        {
            if (p.X >= 0 && p.X < gridWidth && p.Y >= 0 && p.Y < gridHeight)
                grid[p.X, p.Y] = true;
        }
    }

    // 标记多边形外部的网格
    for (int x = 0; x < gridWidth; x++)
    {
        for (int y = 0; y < gridHeight; y++)
        {
            if (!grid[x, y])
            {
                var center = new Point(minX + x * gridSize + gridSize/2, minY + y * gridSize + gridSize/2);
                if (!IsPointInPolygon(center, segments))
                    grid[x, y] = true;
            }
        }
    }

    // 寻找最大的连续可用矩形
    var rectangles = new List<Rectangle>();
    for (int x = 0; x < gridWidth; x++)
    {
        for (int y = 0; y < gridHeight; y++)
        {
            if (!grid[x, y] && !visited[x, y])
            {
                // BFS遍历连通区域
                Queue<(int X, int Y)> queue = new Queue<(int X, int Y)>();
                queue.Enqueue((x, y));
                visited[x, y] = true;
                int minGridX = x, maxGridX = x;
                int minGridY = y, maxGridY = y;

                while (queue.Count > 0)
                {
                    var (cx, cy) = queue.Dequeue();
                    minGridX = Math.Min(minGridX, cx);
                    maxGridX = Math.Max(maxGridX, cx);
                    minGridY = Math.Min(minGridY, cy);
                    maxGridY = Math.Max(maxGridY, cy);

                    // 检查四个方向的邻居
                    var neighbors = new[] { (cx-1, cy), (cx+1, cy), (cx, cy-1), (cx, cy+1) };
                    foreach (var (nx, ny) in neighbors)
                    {
                        if (nx >= 0 && nx < gridWidth && ny >= 0 && ny < gridHeight && !grid[nx, ny] && !visited[nx, ny])
                        {
                            visited[nx, ny] = true;
                            queue.Enqueue((nx, ny));
                        }
                    }
                }

                // 转化为实际坐标矩形
                var rect = new Rectangle(
                    new Point(minX + minGridX * gridSize, minY + minGridY * gridSize),
                    new Point(minX + (maxGridX + 1) * gridSize, minY + (maxGridY + 1) * gridSize)
                );
                rectangles.Add(rect);
            }
        }
    }

    // 返回面积最大的前N个矩形
    return rectangles.OrderByDescending(r => r.Area).Take(5).ToList();
}

// 获取线段覆盖的网格坐标
private List<(int X, int Y)> GetGridPointsAlongSegment(Segment seg, double gridSize, double minX, double minY)
{
    var points = new List<(int X, int Y)>();
    double dx = seg.End.X - seg.Start.X;
    double dy = seg.End.Y - seg.Start.Y;
    int steps = (int)Math.Max(Math.Abs(dx), Math.Abs(dy)) / (int)gridSize;
    steps = Math.Max(steps, 1); // 至少走一步

    double xStep = dx / steps;
    double yStep = dy / steps;

    for (int i = 0; i <= steps; i++)
    {
        double x = seg.Start.X + xStep * i;
        double y = seg.Start.Y + yStep * i;
        int gridX = (int)Math.Floor((x - minX) / gridSize);
        int gridY = (int)Math.Floor((y - minY) / gridSize);
        points.Add((gridX, gridY));
    }
    return points.Distinct().ToList();
}

// 射线法判断点是否在多边形内
private bool IsPointInPolygon(Point p, List<Segment> segments)
{
    bool inside = false;
    foreach (var seg in segments)
    {
        var a = seg.Start;
        var b = seg.End;

        // 检查点是否在边的y范围内，且射线与边相交
        if (((a.Y > p.Y) != (b.Y > p.Y)) &&
            (p.X < (b.X - a.X) * (p.Y - a.Y) / (b.Y - a.Y) + a.X))
        {
            inside = !inside;
        }
    }
    return inside;
}

使用建议 #

• 如果你需要精确的矩形边界，优先用方法一，注意调整浮点误差的阈值（根据你的线段坐标精度）
• 如果追求效率和近似效果，方法二更合适，网格大小可以根据你的需求调整（越小越精确，但速度越慢）
• 两种方法都可以根据你的场景进一步优化，比如添加面积过滤（只保留大于某个阈值的矩形）

内容的提问来源于stack exchange，提问作者Joe Morgan