Relative Neighborhood Graph
Zu jedem Zeitpunkt ist im obigen Video ein Relative Neighborhood Graph (RNG) zu sehen. Der RNG verbindet Knoten miteinander, die nahe beieinander sind. Für die Knotenmenge $V$ muss also eine Metrik definiert sein, sodass eine Distanz $d_{ij}$ zwischen zwei Knoten definiert ist. Dann verbindet der RNG alle Knoten, die die Bedingung $$ d_{ij} \le \max(d_{ik}, d_{kj}) \quad \forall k \in V\setminus{i, j} $$ erfüllen.
Dementsprechend simpel kann man einen RNG erzeugen.
import random
import networkx as nx
import matplotlib.pyplot as plt
def dist(n1, n2):
"""Euclidean distance"""
return ((n1[0] - n2[0])**2 + (n1[1] - n2[1])**2)**0.5
def rng(G):
"""Insert edges according to the RNG rules into the graph G"""
for c1 in G.nodes():
for c2 in G.nodes():
d = dist(c1, c2)
for possible_blocker in G.nodes():
distToC1 = dist(possible_blocker, c1)
distToC2 = dist(possible_blocker, c2)
if distToC1 < d and distToC2 < d:
# this node is in the lune and blocks
break
else:
G.add_edge(c1, c2)
if __name__ == "__main__":
# generate some random coordinates
coordinates = [(random.random(),random.random()) for _ in range(100)]
G = nx.Graph()
for x, y in coordinates:
G.add_node((x, y), x=x, y=y)
rng(G)
# draw the graph G
pos = {n: (n[0], n[1]) for n in G.nodes()}
nx.draw_networkx_nodes(G, pos=pos, node_shape="o")
nx.draw_networkx_edges(G, pos=pos)
plt.show()
Interessanterweise tauchen alle Kanten des RNG auch in der Delaunay Triangulation der gleichen Knotenmenge auf. Dies kann man nutzen, um RNGs in $\mathcal{O}(N \log N)$ zu konstruieren.
Meiner persönlichen Meinung nach, bildet der RNG mit dem Verhältnis von Knoten zu Kanten ein ästhetisches Optimum.