Comment obtenir efficacement une liste d'adjacence pour un diagramme sphérique de Voronoï?

Question

Je souhaite générer une liste d'adjacence pour les régions d'un diagramme sphérique de Voronoï. J'utilise le SphericalVoronoi class de SciPy donc la seule information que je peux utiliser est les centres et les sommets du diagramme.

La meilleure chose que je suis venu avec est de vérifier pour chaque paire de régions si elles ont un sommet commun (vor est l'instance de 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) 

Est-il possible de faire plus efficace ce?

Answer 1

Il est plus efficace de trouver pour chaque région de vertex dans laquelle il se trouve, et d'utiliser cette information pour trouver quelles régions sont voisines.

Quelque chose comme:

# 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)