基于二维点集的最大填充矩形网格检测算法求解

本文定义的网格是指无空缺的填充矩形点集合，不考虑旋转网格。

示例1：有效网格 #

A B C
D E F
G H I

上述点集构成有效网格，矩形区域内无空缺。

示例2：无效网格（存在空缺） #

A B C
D   F
G H I

移除点E后，矩形区域内有空缺，不再是有效网格。

示例3：最大网格定义 #

A B C
D E F

尽管{A,B,C,D}构成小网格，但输出应是更大的{A,B,C,D,E,F}——它是包含前者的最大有效网格。

示例4：重叠网格 #

A B
C D E
  F G

{A,B,C,D}和{D,E,F,G}各自构成独立的有效网格，允许重叠。

应用场景 #

开发Figma插件，检测重复元素并转为可复用组件，该网格检测是算法核心环节之一。

• 先对所有点的x坐标、y坐标分别运行DBSCAN算法，找出垂直/水平对齐的点列表（允许存在一定误差，处理点未完美对齐的情况）
• 后续遇到瓶颈，考虑过遍历每个点作为潜在网格的左上角，搜索所有可能尺寸，但担心效率过低

1. 预处理：完成坐标聚类映射 #

基于已完成的DBSCAN结果，把x坐标聚类视为网格列基准，y坐标聚类视为网格行基准。给每个x聚类分配唯一列ID，每个y聚类分配唯一行ID，将每个原始点映射为(列ID, 行ID)的离散网格坐标。

2. 构建网格存在矩阵 #

创建二维布尔矩阵grid_matrix，其中grid_matrix[row_id][col_id] = True表示该网格位置存在对应点，否则为False。这一步把连续的二维点集转化为离散网格，大幅简化后续矩形检测逻辑。

3. 高效检测所有有效矩形网格 #

遍历矩阵中所有可能的矩形区域，可通过前缀和矩阵优化检测效率：

• 提前计算前缀和矩阵：prefix[row][col]表示从左上角到(row,col)的点总数
• 对任意左上角(row1, col1)、右下角(row2, col2)，计算矩形内点总数：sum = prefix[row2][col2] - prefix[row1-1][col2] - prefix[row2][col1-1] + prefix[row1-1][col1-1]
• 若sum等于矩形面积(row2-row1+1)*(col2-col1+1)，说明区域内无空缺，是有效网格

4. 筛选最大网格 #

对所有有效网格进行去重和筛选：

• 若网格A的行范围完全覆盖网格B的行范围，且列范围也完全覆盖B，则排除B，只保留A
• 最终留存的即为所有最大网格

5. 效率优化要点 #

• 跳过面积小于2x2的网格（若1xN或Nx1类型的线性点集也算网格，可调整阈值）
• 遍历矩形时，一旦发现某行/列存在空缺，立即终止该方向的扩展（比如从左上角向右扩展列，遇到空缺就停止继续向右）
• 仅在有连续行/列聚类的区域内搜索，减少无效遍历范围

Figma场景适配建议 #

• 若“点”是元素的锚点（比如左上角），可额外校验网格内元素的尺寸一致性，过滤尺寸差异过大的网格（符合组件复用的需求）
• 可加入误差容差：允许矩阵中少量位置空缺（比如1个），适配Figma设计中偶尔的元素缺失情况

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