如何按局部平均边长准则筛选Delaunay三角剖分的边并绘制结果

1. 边筛选逻辑实现 #

实现思路：首先提取Delaunay剖分的所有唯一无向边，对每条边校验是否同时满足两个端点的长度要求：仅当边长小于两个顶点各自的局部平均边长时，才保留该边，否则移除。

# 建立点坐标到索引的映射，避免浮点数匹配误差
point_to_idx = {tuple(p): i for i, p in enumerate(points)}
# 将局部平均边长转成索引为key的数组，提升查询效率
mean_length_arr = np.zeros(len(points))
for p, mean_val in local_mean_edge_lengths.items():
    mean_length_arr[point_to_idx[p]] = mean_val

# 提取所有唯一无向边，按索引升序存储避免重复计数
edges = set()
for simplex in tri.simplices:
    edges.add(tuple(sorted((simplex[0], simplex[1]))))
    edges.add(tuple(sorted((simplex[1], simplex[2]))))
    edges.add(tuple(sorted((simplex[2], simplex[0]))))
edges = list(edges)

# 按规则筛选边
kept_edges = []
for (i, j) in edges:
    p1, p2 = points[i], points[j]
    edge_len = np.linalg.norm(p1 - p2)
    # 需同时满足两个端点的长度要求才保留
    if edge_len < mean_length_arr[i] and edge_len < mean_length_arr[j]:
        kept_edges.append((i,j))

2. 筛选结果绘制 #

使用matplotlib实现可视化：

import matplotlib.pyplot as plt

plt.figure(figsize=(8,6))
# 绘制原始点
plt.scatter(points[:,0], points[:,1], c='red', s=50, zorder=2)
# 可选：绘制原始Delaunay三角剖分的灰色虚线作为对比
# plt.triplot(points[:,0], points[:,1], tri.simplices, color='lightgray', linestyle='--', zorder=1)
# 绘制筛选后保留的边
for (i,j) in kept_edges:
    plt.plot([points[i,0], points[j,0]], [points[i,1], points[j,1]], c='blue', linewidth=1.5, zorder=1)

plt.xlabel('X坐标')
plt.ylabel('Y坐标')
plt.title('筛选后的Delaunay剖分边结果')
plt.axis('equal')
plt.show()

补充：保留完整三角形的处理 #

如果你需要保留完整的三角形结构而非仅独立边，可以增加额外校验：只有三角形的三条边都被保留时，才保留整个三角形：

kept_simplices = []
kept_edge_set = set(kept_edges)
for simplex in tri.simplices:
    e1 = tuple(sorted((simplex[0], simplex[1])))
    e2 = tuple(sorted((simplex[1], simplex[2])))
    e3 = tuple(sorted((simplex[2], simplex[0])))
    if e1 in kept_edge_set and e2 in kept_edge_set and e3 in kept_edge_set:
        kept_simplices.append(simplex)
# 可直接用triplot绘制保留的三角形
# plt.triplot(points[:,0], points[:,1], kept_simplices, c='blue')

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