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
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
Meiner persönlichen Meinung nach, bildet der RNG mit dem Verhältnis von Knoten zu Kanten ein ästhetisches Optimum.