如何从2D点列表中识别正方形并确定其边缘？

一、判断图形为正方形的核心算法 #

1. 点集预处理 #

先对输入的2D点集做降噪和抽稀：

• 用道格拉斯-普克算法（Ramer-Douglas-Peucker）去除冗余点，保留关键拐点；
• 用移动平均法平滑点集，过滤手绘时的抖动噪声。

2. 多边形拟合与初步筛选 #

• 直线段检测：用霍夫变换（Hough Transform）检测点集中的直线段，统计有效直线数量，若不等于4则直接排除正方形可能；
• 残差判断：对所有点进行直线拟合，计算整体残差，若残差过大（超过设定阈值），说明是曲线/圆弧，直接排除。

3. 正方形特征验证 #

通过以下三个核心特征交叉验证：

• 边长一致性：计算四条拟合直线段的长度，要求四条边长的相对误差在5%以内（可根据手绘精度调整阈值）；
• 垂直性验证：计算相邻边的向量点积，若点积绝对值接近0（误差在阈值内），说明邻边垂直；同时四个内角需接近90度（误差±5度）；
• 对角线验证：计算两条对角线的长度，要求长度相等（误差阈值内），且对角线互相垂直（点积接近0），同时两条对角线的中点坐标重合（误差在像素级范围内）。

二、确定正方形边缘的算法 #

1. 鲁棒直线拟合 #

用RANSAC算法对四条边分别做鲁棒拟合，排除手绘时的离群点，得到每条边的精确直线方程（如ax + by + c = 0形式）。

2. 顶点计算与排序 #

• 对四条直线两两求解交点，得到四个顶点坐标；
• 计算顶点的凸包，按顺时针或逆时针顺序排列顶点，确保边缘的连续性。

3. 边缘规整优化 #

• 以四个顶点的中心为正方形中心，以平均边长为标准边长，调整四条边为严格垂直且等长的直线；
• 最终输出每条边的起止顶点坐标，作为矢量图形的正方形边缘数据。

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