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.