如何检测约束Delaunay三角剖分中边/面是否处于闭合轮廓内部？

假设存在如下约束Delaunay三角剖分：

已知如何从图a处理得到图c，但针对图c这类形状，如何检测某条边或某个面是否位于闭合轮廓内部，从而对其执行删除操作？

一、核心判断逻辑：点-in-多边形算法 #

不管是判断三角面还是边，核心都是先确定面的位置，再推导边的状态：

• 三角面判断：取三角面的重心（或任意内部点），用两种主流算法判断是否在闭合轮廓内：
  • 射线法：从该点向x轴正方向发射射线，统计与轮廓边的交点数——奇数则在内部，偶数则在外部。实现简单，适合大部分场景。
  • 环绕数算法：计算点相对于轮廓的环绕次数，非零则在内部。能处理射线恰好经过轮廓顶点/边的特殊情况，精度更高。
• 边的判断：
  • 公共边：若一条边属于两个三角面，且两个面一个在内部一个在外部，这条是轮廓边界边，需保留；若两个面都在内部，这条是内部冗余边，可删除。
  • 边界边：若一条边只属于一个面，判断该面是否在内部，若在则这条边是内部边界，可删除；反之保留。

二、结合约束Delaunay剖分特性优化 #

利用约束剖分的拓扑特性可以减少计算量：

• 先标记所有约束边（也就是构成闭合轮廓的原始边）为“边界保留边”，这些边绝对不能删除。
• 遍历所有三角面：
  • 若面的三条边中没有约束边，且重心在轮廓内部，标记为待删除面；
  • 若面包含至少一条约束边，直接保留（如果是内部有洞的场景，需要额外判断约束边是外轮廓还是内洞）。
• 删除待删除面后，没有面引用的内部边会自动成为无主边，直接清理即可。

三、伪代码示例 #

# 1. 提前标记所有闭合轮廓的约束边
constraint_edge_ids = {edge.id for edge in contour_edges}

# 2. 遍历所有三角面，标记待删除项
for tri in all_triangles:
    # 计算三角面重心
    centroid = (tri.p1 + tri.p2 + tri.p3) / 3
    # 判断重心是否在轮廓内部
    is_inside = point_in_polygon(centroid, contour_vertices)
    # 检查面是否包含约束边
    has_constraint = any(edge.id in constraint_edge_ids for edge in tri.edges)
    
    if is_inside and not has_constraint:
        tri.to_delete = True

# 3. 执行删除操作
all_triangles = [tri for tri in all_triangles if not tri.to_delete]
# 清理无引用的内部边
unused_edges = [edge for edge in all_edges if len(edge.adjacent_triangles) == 0]
all_edges = [edge for edge in all_edges if edge not in unused_edges]

四、注意事项 #

• 浮点数精度：判断点是否在边上、射线交点时，必须设置合理的误差阈值（比如1e-8），避免因精度问题导致误判。
• 嵌套轮廓：如果场景存在内部洞，需要修改点-in-多边形算法，区分“奇数层”（内部）和“偶数层”（外部）的区域。

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