如何有效获取球形伏洛尼图的邻接列表

Question

我想生成一个球形伏罗尼亚图的区域的邻接列表。我正在使用scipy的球形视频类别类，因此我唯一可以使用的信息是该图的中心和顶点。

我想出的最好的事情是检查每对区域是否有一个共同的顶点(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)