Skip to main content
 首页 » 编程设计

python之scipy voronoi 3d之并未显示所有山脊点

2025年05月04日9lvdongjie

我在使用 scipy 的 Voronoi 函数时遇到了问题。我遵循了 2d 示例,但是当我在 3d 中执行类似示例时,并不是所有的 ridge_points 都被计算。我的数据是 [0,2]x[0,2]x[0,2] 中的 27 个点的框:

points = np.array([ 
    # bottom plane 
    [0,2,0], [1,2,0], [2,2,0], 
    [0,1,0], [1,1,0], [2,1,0], 
    [0,0,0], [1,0,0], [2,0,0], 
    # middle plane 
    [0,2,1], [1,2,1], [2,2,1], 
    [0,1,1], [1,1,1], [2,1,1], 
    [0,0,1], [1,0,1], [2,0,1], 
    # top plane 
    [0,2,2], [1,2,2], [2,2,2], 
    [0,1,2], [1,1,2], [2,1,2], 
    [0,0,2], [1,0,2], [2,0,2] 
    ]) 
 
vor = Voronoi(points) 
 
print vor.ridge_points 
# outputed 
array([[ 4,  7], 
       [ 4,  5], 
       [ 4,  3], 
       [ 4,  1], 
       [ 4, 13], 
       [ 3, 12], 
       [ 7, 16], 
       [15, 12], 
       [15, 16], 
       [ 9, 12], 
       [ 9, 10], 
       [ 1, 10], 
       [12, 21], 
       [12, 13], 
       [23, 14], 
       [23, 22],  
       [14, 17], 
       [14, 11], 
       [14,  5], 
       [14, 13], 
       [22, 19], 
       [22, 21], 
       [22, 13], 
       [22, 25], 
       [17, 16], 
       [11, 10], 
       [25, 16], 
       [16, 13], 
       [13, 10], 
       [19, 10], dtype=int32) 

我注意到角落上的点:

points[0] = array([0, 2, 0]) 
points[2] = array([2, 2, 0]) 
points[6] = array([0, 0, 0]) 
points[8] = array([2, 0, 0]) 
points[18] = array([0, 2, 2]) 
points[20] = array([2, 2, 2]) 
points[24] = array([0, 0, 2]) 
points[26] = array([2, 0, 2]) 

没有任何脊点。我会假设(就像 2d 的情况)角落会有脊点。例如,我假设 points[6]=[0,0,0] 的脊点为 [1,0,0]、[0,1,0] 和 [0,0,1]。这不可能用 scipy 计算还是我一直在想这个错误?

请您参考如下方法:

Scipy 使用 Qhull用于 Delaunay/Voronoi/Convexhull 计算。 ridge_points 中包含的数据是 qvoronoi Fv 报告的数据,尽管山脊不一定按相同顺序列出。 (作为支票:https://gist.github.com/pv/2f756ec83cdf242ce691)

Fv ( http://www.qhull.org/html/qh-optf.htm#Fv2 ) 的 Qhull 文档提到了一个似乎与此处相关的警告:

Option 'Fv' does not list ridges that require more than one midpoint. For example, the Voronoi diagram of cospherical points lists zero ridges (e.g., 'rbox 10 s | qvoronoi Fv Qz'). Other examples are the Voronoi diagrams of a rectangular mesh (e.g., 'rbox 27 M1,0 | qvoronoi Fv') or a point set with a rectangular corner (e.g., 'rbox P4,4,4 P4,2,4 P2,4,4 P4,4,2 10 | qvoronoi Fv'). Both cases miss unbounded rays at the corners. To determine these ridges, surround the points with a large cube (e.g., 'rbox 10 s c G2.0 | qvoronoi Fv Qz'). The cube needs to be large enough to bound all Voronoi regions of the original point set. Please report any other cases that are missed. If you can formally describe these cases or write code to handle them, please send email to qhull@qhull.org.

文中提到的 rbox 27 M1,0 与您的示例中的点集完全相同(顺序不同)。

通常,Qhull 在处理几何退化方面存在问题,例如在矩形网格中发生的退化。一个通用的解决方法是设置 qhull_options="QJ" 告诉它向数据点添加随机扰动,直到退化得到解决。这通常会生成带有几个附加单纯形/脊的镶嵌/voronoi 图,但可能会解决此类问题。