球形のボロノイ図の隣接リストを効率的に取得する方法は？

Question

球形のボロノイ図の領域の隣接関係リストを生成します。私はSciPyからSphericalVoronoi classを使用していますので、使用できる唯一の情報は図の中心と頂点です。

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) 

行うためのより効率的な方法があります：

彼らは共通の頂点を持っている場合、私は地域のすべてのペアをチェックして作ってみた最善のことは（vorはSphericalVoronoiのインスタンスです）この？

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)