如何从二维点闭合环中高效去除Sliver（狭长）区域？

需求背景 #

需要从给定的二维闭合点环中移除面积趋近于0的狭长（Sliver）区域，得到可用的闭合区域以用于网格生成。

原始节点数据 #

Node_ID    U_param    V_param
298        -1.570694  1.933077
859        -1.570804  1.637394
860        -1.570801  1.331141
861        -1.570797  1.047667
862        -1.570806  0.775248
863        -1.570798  0.502410
864        -1.570798  0.217605
865        -1.570806 -0.089721
866        -1.570797 -0.383541
867        -1.570801 -0.659983
868        -1.570804 -0.931217
133        -1.570796 -1.208516
763        -1.355953 -1.208516
134        -1.141109 -1.208516
963        -1.141265 -0.968128
962        -1.141443 -0.732077
961        -1.141122 -0.491922
960        -1.141160 -0.250871
959        -1.140885  0.013409
309        -1.141109  0.276746
1527       -1.345324  0.430356
212        -1.491354  0.602793
211        -1.570592  0.855809
1079       -1.570592  1.109513
1078       -1.570592  1.375016
1077       -1.570592  1.660328
298        -1.570694  1.933077

环示意图说明 #

图中可见闭合环在中下部存在一处向内凹陷的狭窄区域，该区域面积趋近于0，属于需要移除的Sliver区域。

高效实现方法 #

核心逻辑 #

狭长区域由连续冗余节点构成，这类节点的特征是：连续三点构成的三角形面积极小（趋近于0），或相邻线段夹角接近180°（共线或近似共线）。通过识别这类节点并移除，即可得到无狭长区域的闭合环。

具体步骤 #

1. 数据预处理：将原始节点按顺序存储，去除首尾重复的节点（原数据首尾均为298，保留一个即可）。
2. 冗余节点识别：
   • 面积判断法：遍历连续三点P(i-1), P(i), P(i+1)，计算三点构成的三角形面积，当面积小于设定阈值（如1e-6，可根据数据精度调整）时，标记P(i)为冗余节点。
   • 夹角判断法：计算相邻线段P(i-1)→P(i)与P(i)→P(i+1)的夹角，当夹角接近180°（误差范围可设为±1°）时，标记P(i)为冗余节点。
3. 节点过滤与环闭合：移除所有标记的冗余节点，将剩余节点按顺序排列，最后添加第一个节点形成闭合环。
4. 结果验证：检查新环的闭合性，计算整体面积，确认狭长区域已被移除。

代码实现示例（Python） #

# 预处理后的节点列表（去重首尾重复项）
nodes = [
    (298, -1.570694, 1.933077),
    (859, -1.570804, 1.637394),
    (860, -1.570801, 1.331141),
    (861, -1.570797, 1.047667),
    (862, -1.570806, 0.775248),
    (863, -1.570798, 0.502410),
    (864, -1.570798, 0.217605),
    (865, -1.570806, -0.089721),
    (866, -1.570797, -0.383541),
    (867, -1.570801, -0.659983),
    (868, -1.570804, -0.931217),
    (133, -1.570796, -1.208516),
    (763, -1.355953, -1.208516),
    (134, -1.141109, -1.208516),
    (963, -1.141265, -0.968128),
    (962, -1.141443, -0.732077),
    (961, -1.141122, -0.491922),
    (960, -1.141160, -0.250871),
    (959, -1.140885, 0.013409),
    (309, -1.141109, 0.276746),
    (1527, -1.345324, 0.430356),
    (212, -1.491354, 0.602793),
    (211, -1.570592, 0.855809),
    (1079, -1.570592, 1.109513),
    (1078, -1.570592, 1.375016),
    (1077, -1.570592, 1.660328)
]

def calculate_triangle_area(p_prev, p_curr, p_next):
    # 计算三点构成的三角形面积（绝对值的1/2）
    return abs((p_curr[1] - p_prev[1]) * (p_next[2] - p_prev[2]) - 
               (p_curr[2] - p_prev[2]) * (p_next[1] - p_prev[1])) / 2

# 设置面积阈值，根据数据精度调整
AREA_THRESHOLD = 1e-6

# 过滤冗余节点
filtered_nodes = [nodes[0]]
for i in range(1, len(nodes)-1):
    prev_node = filtered_nodes[-1]
    curr_node = nodes[i]
    next_node = nodes[i+1]
    area = calculate_triangle_area(prev_node, curr_node, next_node)
    # 面积大于阈值则保留当前节点
    if area > AREA_THRESHOLD:
        filtered_nodes.append(curr_node)

# 添加最后一个节点并闭合环
filtered_nodes.append(nodes[-1])
filtered_nodes.append(filtered_nodes[0])

# 输出结果
print("过滤后的闭合环节点：")
print(f"{'Node_ID':<8} {'U_param':<10} {'V_param':<10}")
for node in filtered_nodes:
    print(f"{node[0]:<8} {node[1]:<10} {node[2]:<10}")

结果说明 #

运行上述代码后，会自动移除如763这类共线冗余节点（133、763、134三点构成的三角形面积为0），最终得到的闭合环无狭长区域，可直接用于网格划分软件的网格生成。

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