如何用scipy.spatial.Delaunay获取点所属的所有单纯形/三角形？

你提到的问题很常见——find_simplex()确实只会返回一个包含点的单纯形，但要拿到所有关联的三角形，其实可以利用scipy Delaunay对象自带的结构信息来实现，分两种情况处理：

情况1：目标点是剖分的顶点（比如你例子中的点6） #

如果点本身就是Delaunay剖分里的顶点，那直接用预计算的邻接信息就能高效获取所有包含它的三角形，不用遍历全部单纯形：

代码示例 #

from scipy.spatial import Delaunay
import numpy as np

# 构造你的点集（这里模拟你提到的场景，点6是中心顶点）
points = np.array([
    [0, 0], [2, 0], [2, 2], [0, 2],  # 外围顶点
    [1, 0], [2, 1], [1, 1], [0, 1], [1, 2]  # 点6对应索引6的中心
])
tri = Delaunay(points)

# 目标点的索引（假设你的点6对应points里的索引6）
target_vertex_idx = 6

# 获取每个顶点关联的单纯形索引
indptr, indices = tri.vertex_neighbor_vertices
# 提取目标顶点对应的所有单纯形索引
all_simplex_indices = indices[indptr[target_vertex_idx]:indptr[target_vertex_idx+1]]

# 输出结果：所有包含点6的三角形索引和对应的顶点
print("包含点6的三角形索引：", all_simplex_indices)
print("这些三角形的顶点：", tri.simplices[all_simplex_indices])

原理说明 #

tri.vertex_neighbor_vertices是scipy在构建Delaunay剖分时预计算好的结构，返回两个数组：

• indptr：标记每个顶点关联单纯形的起始/结束位置
• indices：存储所有单纯形的索引

通过indptr[target_idx]到indptr[target_idx+1]的切片，就能直接拿到该顶点所有关联的三角形，效率比遍历全部单纯形高得多。

情况2：目标点不是剖分的顶点（在边或内部） #

如果点是在某个单纯形的边上或者内部，就需要通过BFS遍历邻接单纯形，结合find_simplex()验证是否包含该点：

代码示例 #

def find_all_containing_simplices(tri, point):
    initial_simplex = tri.find_simplex(point)
    if initial_simplex == -1:
        return []  # 点在凸包外部，没有包含它的单纯形
    
    visited = set()
    queue = [initial_simplex]
    visited.add(initial_simplex)
    
    while queue:
        current_simplex = queue.pop()
        # 遍历当前单纯形的所有邻接单纯形
        for neighbor_simplex in tri.neighbors[current_simplex]:
            if neighbor_simplex != -1 and neighbor_simplex not in visited:
                # 检查点是否在邻接单纯形内
                if tri.find_simplex(point, simplex=neighbor_simplex) != -1:
                    visited.add(neighbor_simplex)
                    queue.append(neighbor_simplex)
    
    return list(visited)

# 使用示例
test_point = np.array([1.5, 1.0])  # 假设这是一个在边上的点
simplices_containing_point = find_all_containing_simplices(tri, test_point)
print("包含该点的三角形索引：", simplices_containing_point)

原理说明 #

1. 先用find_simplex()找到任意一个包含点的单纯形作为起点
2. 利用tri.neighbors获取该单纯形的所有邻接三角形
3. 逐个验证邻接三角形是否包含目标点，同时用集合记录已访问的单纯形避免重复
4. 最终集合里的就是所有包含该点的单纯形

针对你提到的例子，点6应该是剖分的顶点，所以用第一种方法就能直接拿到所有关联的三角形（1、2、3、4、9、10）啦。

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