如何有效地获得球形Voronoi图的邻接表？

Question

我想为一个球形Voronoi图的区域生成一个邻接表。我使用SciPy的SphericalVoronoi class，因此我可以使用的唯一信息是图的中心和顶点。

我已经拿出正在检查每对区域的，如果他们有一个共同的顶点的最好的事情（vor是SphericalVoronoi的实例）：

def adjacent(vor, reg1, reg2): 
    for i in vor.vertices[reg1]: 
     if i in vor.vertices[reg2]: return True 
    return False 

adjacencies = [[] for i in range(len(vor.regions))] 
for i in range(npoints): 
    for j in range(i,npoints): 
     if adjacent(vor,vor.regions[i],vor.regions[j]): 
      adjacencies[i].append(j) 
      adjacencies[j].append(i) 

有没有更有效的方式做到这个？

Answer 1

找到它所处的每个顶点区域更有效，并使用该信息来找出哪些区域是邻居。

喜欢的东西：

# Vertex - region adjacencies 
vert2region = defaultdict(list) 
for i, region in enumerate(vor.regions): 
    for v in region: 
    vert2region[v].append(i) 

# Region - region adjacencies 
adjacencies = defaultdict(set) # set is important not to have same adjacency twice 
for v, regions in vert2region.items(): 
    for r1, r2 in itertools.combinations(regions, 2): 
    adjacencies[r1].add(r2) 
    adjacencies[r2].add(r1)