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