如何判断点列表对应的多边形是否包含孔洞（内部多边形）

针对由1×1正方形合并得到的多边形顶点列表，可通过以下几种核心算法判断是否存在孔洞：

1. 欧拉公式法（最简洁高效） #

利用平面图形的欧拉公式：V - E + F = 2，其中：

• V：顶点列表中的唯一顶点总数
• E：多边形的唯一轴对齐边数（仅水平或垂直，边长为1）
• F：面数（包含外部面和所有孔洞内部面）

计算步骤： #

• 统计唯一边数E：遍历每个顶点(x,y)，检查(x+1,y)和(x,y+1)是否存在于顶点列表中。每找到一对相邻顶点，记录一条边，最后去重得到总边数E。
• 推导面数F：通过公式变形得F = E - V + 2。若F > 1，说明存在孔洞，孔洞数量为F - 1（F=1时仅外部面，无孔洞）。

2. 包围盒+网格填充检测法 #

步骤： #

• 先计算多边形的最小包围盒：minX（所有顶点x的最小值）、minY（所有顶点y的最小值）、maxX（所有顶点x的最大值）、maxY（所有顶点y的最大值）。
• 遍历包围盒内所有1×1正方形的中心（坐标为(x+0.5, y+0.5)，其中x从minX到maxX-1，y从minY到maxY-1）。
• 对每个中心，用射线法判断是否在多边形内部：若某中心在内部，但对应的1×1正方形未被包含在合并区域中（可通过顶点列表还原合并区域），则该区域为孔洞。

3. 基于顶点链的剩余顶点检测法 #

结合你已有的顶点排序算法：

• 用现有算法从最左下点出发，生成一条闭合的外边界顶点链，统计该链包含的顶点数。
• 若总顶点数大于链的顶点数，说明存在未被遍历的顶点。对剩余顶点，用点包含算法判断其是否位于外边界内部：若在内部，则属于孔洞的内环，即存在孔洞；若在外部，则是分离的独立多边形。

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