如何有效地獲得球形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)