这是个挺有意思的几何重建问题，我来分享下实际工程中常用的可靠思路：

1. 无孔洞多边形的角点提取与排序 #

角点提取 #

每个正方形的4个顶点中，内部共享顶点会被至少两个正方形拥有，而我们要找的轮廓角点（示例中的红点）只属于一个正方形。具体步骤：

• 收集所有正方形的所有顶点坐标（注意：如果是浮点坐标，不能直接用全等判断，要设定一个极小的阈值epsilon，比如1e-6，两个点的欧氏距离小于epsilon就视为同一个点）。
• 统计每个顶点的出现次数，筛选出出现次数为1的顶点，这些就是多边形的轮廓角点。

角点排序 #

排序的核心是还原轮廓的闭合环，推荐用轮廓边拼接法，比纯点遍历更稳定：

1. 提取轮廓边：遍历所有正方形的四条边，每条边用两个顶点的有序对（或无序对，但要统一判断逻辑）表示；统计每条边的出现次数，出现次数为1的边就是多边形的轮廓边（内部共享边会被两个正方形各算一次，出现次数为2）。
2. 拼接轮廓环：
   • 随便选一条轮廓边作为起始边，记录它的起点和终点。
   • 从剩余的轮廓边中，找起点等于当前边终点的边，把这条边的终点加入序列，然后将这条边标记为已使用。
   • 重复上一步，直到回到起始边的起点，此时得到的顶点序列就是正确的连接顺序。
   • 额外优化：如果要保证是逆时针（或顺时针）方向，可以用叉积判断相邻边的转向，调整边的方向。

2. 带孔洞多边形的角点提取与排序 #

角点提取 #

逻辑和无孔洞情况基本一致：

• 同样统计顶点出现次数，筛选出现次数为1的顶点（孔洞的轮廓顶点也只属于一个正方形，因为孔洞旁边的正方形只有单侧在孔洞边界）。
• 或者直接用轮廓边的方法，提取所有出现次数为1的边，这些边会包含外轮廓边和所有孔洞的轮廓边。

角点排序 #

需要区分外轮廓和孔洞，并分别排序：

1. 拆分轮廓环：用上面的轮廓边拼接法，把所有轮廓边拆分成多个独立的闭合环（每个环对应一个外轮廓或一个孔洞）。
2. 区分外轮廓与孔洞：
   • 方法一：计算每个环的面积（用 shoelace公式），面积绝对值最大的环就是外轮廓，其余是孔洞。通常外轮廓是逆时针方向（面积为正），孔洞是顺时针方向（面积为负），可以根据这个特性调整方向。
   • 方法二：取一个明显在多边形外部的点（比如所有顶点坐标的最小值再往外拓展一点），用点-in-polygon算法判断该点是否在某个环内部：不在任何环内部的环是外轮廓，在外轮廓内部的环是孔洞。
3. 分别排序每个环：每个环的排序方法和无孔洞时一致，确保每个环的方向符合约定（比如外轮廓逆时针，孔洞顺时针）。

注意事项 #

• 浮点坐标的精度问题一定要处理，否则会出现顶点或边重复统计错误的情况。
• 如果正方形的排列有“凹”的情况，纯点的贪心遍历可能会出错，用轮廓边拼接的方法更稳妥。

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