如何从二值化高度图提取区域有序边界顶点（含孔洞处理）

一、区分外轮廓与内部孔洞边界 #

无需复杂图像分割，基于单元格邻接关系与遍历规则即可实现：

• 连通分量标记：先给所有可通行区域分配唯一ID，区分独立连通块。
• 边界单元格分类规则：
  1. 邻域分布判断：外轮廓的边界单元格，其"外侧"（超出网格范围或大面积不可通行区域的方向）无关联可通行区域；孔洞边界的边界单元格，外侧是同ID的可通行区域。
  2. 走向验证：顺时针遍历边界单元格的边缘顶点，外轮廓序列为顺时针方向，孔洞为逆时针方向；计算轮廓有向面积，外轮廓面积为正，孔洞面积为负，可快速校验分类结果。
  3. 1格宽区域适配：这类区域的所有单元格均为边界单元格，通过相邻可通行单元格的方向（左右/上下）判断轮廓走向，避免误判为孔洞——其轮廓属于外轮廓范畴，是两条并行的闭合边。

二、生成沿单元格边缘的有序顶点列表 #

目标是生成连续闭合的顶点环，适配道格拉斯-普克简化与CDT：

• 坐标映射规则：定义单元格与顶点的对应关系，例如单元格(i,j)的四个顶点为(i, j)、(i+1, j)、(i+1, j+1)、(i, j+1)（可根据自身坐标系调整）。
• 有序遍历生成顶点：
  1. 从任意边界单元格的目标边缘顶点出发（如外轮廓单元格的左侧边缘顶点），沿单元格边界边缘按固定方向（顺时针/逆时针）遍历：仅提取与不可通行区域相邻的边的两个顶点，保证序列连续。
  2. 衔接逻辑：当前单元格的右下角顶点，对应下一个相邻边界单元格的左下角顶点，确保轮廓无断点。
  3. 1格宽区域处理：分别提取区域两侧的边缘顶点形成两条并行链，再将首尾顶点连接为闭合细长环，确保后续算法可正常处理。
• 后处理优化：遍历完成后去除重复顶点，验证环的闭合性（首尾顶点重合），即可直接输入道格拉斯-普克算法简化，或用于约束Delaunay三角化（注意孔洞环需保持逆时针方向）。

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