如何使用scipy的Delaunay查找两个不同点集中点的Delaunay邻居

你不需要逐个插入X_的点重建Delaunay三角剖分，利用Delaunay三角剖分的特性配合scipy自带的接口就能实现高效查询，核心逻辑如下：

• Delaunay三角剖分满足特性：任意查询点的最近邻原始点，一定属于该查询点所在的Delaunay单形（本场景中就是三角形）的顶点集合。你已经提前用points构建好了静态Delaunay三角网，直接对X_的点做位置查询即可，不需要修改原有三角网结构。
• 如果查询点落在原始点集的凸包外，find_simplex会返回-1，这种情况可以额外计算和所有凸包顶点的距离取最近即可，或者直接用KDTree做补充查询，整体耗时仍远低于反复重建三角网。

实现代码 #

在你原有代码的基础上追加以下逻辑即可：

# 接你原有代码
from scipy.spatial.distance import cdist

# 查找每个X_点所在的三角形索引
simplex_ids = tri.find_simplex(X_)
nearest_ids = []

for idx, simplex_id in enumerate(simplex_ids):
    if simplex_id == -1:
        # 点在凸包外，直接和所有原始点算距离取最近（点集大的话可以提前建KDTree优化）
        dists = cdist([X_[idx]], points)[0]
        nearest_ids.append(dists.argmin())
    else:
        # 取所在三角形的三个顶点作为候选
        candidate_inds = tri.simplices[simplex_id]
        dists = cdist([X_[idx]], points[candidate_inds])[0]
        nearest_ids.append(candidate_inds[dists.argmin()])

# 输出每个X_点对应的最近points点索引
for i, near_id in enumerate(nearest_ids):
    print(f"X_的第{i}个点，最近的points点索引为{near_id}")

补充优化建议 #

如果你的原始points或者查询集X_规模很大，可以提前为points构建KDTree，凸包外的点查询直接用KDTree的query接口，时间复杂度可以控制在O(N log N)级，远低于你原来每次重建三角网的O(N^2)级开销。另外你代码里开了incremental=True也可以不用，静态三角网完全满足查询需求，增量模式是给需要频繁新增原始点的场景用的，你这个场景不需要。

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