如何从轴对齐大矩形中减去小矩形，生成不相交矩形列表？

需求说明 #

现有一个轴对齐的大矩形（即示例中的红色待减矩形），需从中减去若干可能互相重叠的轴对齐小矩形（示例中的黑色要减去的矩形），最终输出一组无重叠的轴对齐矩形列表（示例中的绿色结果）。所有矩形的Left、Top、Width、Height均为整数，结果集无需做最小化处理。

核心实现思路 #

采用逐步分割法，每次用一个待减矩形切割当前的结果矩形集合，最终得到无重叠的矩形列表：

• 初始时，将原始大矩形作为唯一元素放入结果列表
• 遍历每个待减矩形：
  • 对当前结果列表中的每个矩形，先判断它和待减矩形是否存在交集
  • 无交集则直接保留该矩形
  • 有交集则将原矩形拆分为最多4个无重叠的子矩形（分别对应交集的上方、下方、左方、右方区域，仅保留面积大于0的有效区域）
  • 用拆分后的子矩形替换原矩形，进入下一轮处理
• 遍历完所有待减矩形后，结果列表即为符合要求的无重叠矩形集合

关键分割逻辑 #

假设原矩形为R，待减矩形为S，两者的交集为I：

• 上方区域：若R.Top < I.Top，生成从R.Top到I.Top的矩形
• 下方区域：若R.Bottom > I.Bottom（R.Bottom = R.Top + R.Height），生成从I.Bottom到R.Bottom的矩形
• 左方区域：若R.Left < I.Left，生成从R.Left到I.Left的矩形，高度与交集I一致
• 右方区域：若R.Right > I.Right（R.Right = R.Left + R.Width），生成从I.Right到R.Right的矩形，高度与交集I一致

C# 扩展方法实现 #

using System.Collections.Generic;
using System.Linq;

public static class RectangleExtensions
{
    public static IEnumerable<Rectangle> Subtract(this Rectangle bounds, IList<Rectangle> subtractions)
    {
        var result = new List<Rectangle> { bounds };

        foreach (var subtraction in subtractions)
        {
            var updatedResult = new List<Rectangle>();
            foreach (var currentRect in result)
            {
                // 计算两个矩形的交集边界
                int intersectLeft = System.Math.Max(currentRect.Left, subtraction.Left);
                int intersectTop = System.Math.Max(currentRect.Top, subtraction.Top);
                int intersectRight = System.Math.Min(currentRect.Left + currentRect.Width, subtraction.Left + subtraction.Width);
                int intersectBottom = System.Math.Min(currentRect.Top + currentRect.Height, subtraction.Top + subtraction.Height);

                // 无交集，直接保留当前矩形
                if (intersectLeft >= intersectRight || intersectTop >= intersectBottom)
                {
                    updatedResult.Add(currentRect);
                    continue;
                }

                // 拆分上方区域
                if (currentRect.Top < intersectTop)
                {
                    updatedResult.Add(new Rectangle(
                        currentRect.Left,
                        currentRect.Top,
                        currentRect.Width,
                        intersectTop - currentRect.Top));
                }

                // 拆分下方区域
                if (currentRect.Top + currentRect.Height > intersectBottom)
                {
                    updatedResult.Add(new Rectangle(
                        currentRect.Left,
                        intersectBottom,
                        currentRect.Width,
                        (currentRect.Top + currentRect.Height) - intersectBottom));
                }

                // 拆分左方区域
                if (currentRect.Left < intersectLeft)
                {
                    updatedResult.Add(new Rectangle(
                        currentRect.Left,
                        intersectTop,
                        intersectLeft - currentRect.Left,
                        intersectBottom - intersectTop));
                }

                // 拆分右方区域
                if (currentRect.Left + currentRect.Width > intersectRight)
                {
                    updatedResult.Add(new Rectangle(
                        intersectRight,
                        intersectTop,
                        (currentRect.Left + currentRect.Width) - intersectRight,
                        intersectBottom - intersectTop));
                }
            }
            result = updatedResult;
        }

        // 过滤掉无效的（宽或高为0的）矩形
        return result.Where(r => r.Width > 0 && r.Height > 0);
    }
}

实现说明 #

• 每次处理一个待减矩形时，都会重新构建结果列表，确保所有矩形无重叠
• 拆分逻辑仅保留有效区域，自动过滤掉面积为0的无效矩形
• 无需额外的去重或最小化操作，符合需求中“结果集无需最小化”的要求

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