Nachtrag zum Bestimmen der Facettenlabel bei Map-Overlay

Da gestern am Ende nicht mehr viel Zeit war um die Verwirrung wegen (vermeintlicher) Probleme durch unzusammenhängende Graphen beim Zuweisen von Facettenlabels zu klären, kommt hier noch ein kurzer Nachtrag.

Um das Label einer Facette f zu finden betrachten wir einen beliebigen Knoten v am Rand von f. Falls v ein Schnittpunkt einer Kante aus G_2 und einer Kante aus G_2 ist, können wir so auf die Label der beiden alten Facetten zugreifen und diese f zuweisen.

Falls andernfalls v kein Schnittpunkt war sondern ein Knoten aus (oBdA) G_1, so können wir das entsprechende Label aus G_1 direkt ablesen. Um nun noch das Label von G_2 zu finden greifen wir auf folgende Vorberechnung zurück: mit einem einfachen Sweepline Algorithmus lässt sich für jeden Knoten aus G_1 speichern in welcher Facette von G_2 er liegt (und andersherum). Wir können das zweite Label von f also ebenfalls von v ablesen.

Bei diesem Ansatz stellen unverbundene Graphen kein Problem dar: Falls v Schnittpunkt ist, so ist der für die aktuelle Facette relevante Bereich des Graphen zusammenhängend. Falls v kein Schnittpunkt ist, dann ist es kein Problem, wenn das Label G_2 aus einer weit entfernte Zusammenhangskomponente f_far kommt, da wir die benötigte Information (dass v in f_far liegt) schon bei der Vorberechnung herausgefunden haben.