Ψ Die Informatikseite

Menü
Informatik » Bachelor » Algorithmen der Informatik » Scanlines
Mustererkennung Algorithmen der Informatik Randomisierte Algorithmen
Unterabschnitte

Scanlines

Sichtbarkeitsproblem für horizontale Objekte

Aktive Linien verwalten wir in einem AVL-Blatt-Baum. Im AVL-Blatt-Suchbaum steht immer die y-Koordinate der Linien. Wir legen für jeden Anfang und jedes Ende einer Linie einen Scanlinestopp an. Kommen wir an den Anfang einer Linie, so aktivieren wir diese, indem wir sie in den AVL-Blatt-Baum einfügen. Wir können die doppelte Verknüpfung der Blätter nutzen, um festzustellen, ob wir direkte sichbare Nachbarn haben. Wenn wir Nachbarn finden, dann geben wir das Nachbarschaftspaar aus. Ähnlich verfahren wir mit dem Ende einer Linie. Wir entfernen sie aus dem AVL-Blatt-Baum und überprüfen danach, ob neue Nachbarschaften entstanden sind und geben diese ggf. aus.
Die Laufzeit hierfür ist $O(n\log{n})$, für das Sortieren der Linien, jeweils $O(\log{n})$ für das Einfügen und Löschen in den AVL-Blattbäumen an jedem Haltepunkt der Scanline. Macht zusammen die Laufzeit $O(n\log{n})$

Schnittproblem für horizontale und vertikale Objekte

Wir verfahren ähnlich wie oben. Wir fügen Scanlinestopps für jede vertikale Linie ein. Bei jeder vertikalen Linie testen wir, welche Linie im AVL-Blatt-Baum vorhanden sind, die die Linie schneiden. Hierfür kann man wieder die Doppeltverkettung der Blätter gut nutzen.
Die Laufzeit hierfür ist $O(n\log{n}+k)$, wobei k die Anzahl der Schnitte ist.

Geometrisches Divide&Conquer für horizontal und vertikal liegende Objekte

Wir unterteilen den Raum, in welchem die Graden enthalten sind, in zwei ungefähr gleich große Räume und führen auf diesen wieder ein Devide und Conquer durch. In unserem Beispiel aus der Vorlesung haben wir den Divide-Schritt nur einmal durchgeführt und dann sofort die Teile ,,geconquert''. Bei der Betrachtung der Teile können folgende Fälle auftreten:
  • Die vertikale Gerade schneidet die horizontale Gerade nicht. $\Rightarrow$ Es gibt keinen Schnittpunkt
  • Die vertikale Gerade schneidet die horizontale Gerade. $\Rightarrow$ Schnittpunkt ausgeben.
  • Die vertikale Gerade schneidet die horizontale Gerade, wobei ein Endpunkt der horizontalen Geraden in dem anderen Teil des vorher in zwei Teile zerteilten Raumes ist. $\Rightarrow$ Schnittpunkt ausgeben.
  • Die vertikale Gerade schneidet die horizontale Gerade, wobei der eine Endpunkt noch nicht einmal in dem anderen Teil des Raumes ist, mit welchem der Raum vor dem Cutschritt noch zusammenhing. $\Rightarrow$ Auch Schnittpunkt ausgeben.

Schnittproblem für (fast) beliebig liegende Objekte

Wir setzen bei diesem Algorithmus voraus, daß
  1. Die Anfangs und Endpunkte der Geraden von Beginn des Algorithmusses an feststehen.
  2. Keine Gerade parallel zur y-Achse also genau senkrecht verläuft.
  3. Sich nicht mehr als zwei Geraden in ein und demselben Punkt schneiden.
Das Problem ist, daß sich die Sortierung der einzelnen Linien dynamisch ändert. Wir ermitteln beim aktivieren einer Geraden, ob sich diese mit einer benachbarten Gerade schneidet. Wenn wir eine Gerade wieder deaktivieren ermitteln wir, ob die nun neuen Nachbarn sich schneiden. So bekommen wir alle Schnittpunkte heraus, da sich keine zwei Geraden schneiden können, wenn sie keine direkten Nachbarn sind. Den Schnitttest können wir mit Hilfe eines linearen Gleichungssystems machen. Die Laufzeit dieses Verfahrens ist $O(n\log{n})$, da die Sortierung der Haltepunkte die Laufzeit des Sortierverfahrens beansprucht ($O(n\log{n})$) und an jedem Haltepunkt eine kostante Anzahl an Operationen, nämlich eine Lösch oder Einfügeoperation und ein oder zwei Schnitttests stattfinden.
Das hier vorgestellte Verfahren untersucht übrigens nur einen Schnittpunkt. Es kann sein, daß eine Gerade mehrmals andere Geraden schneidet. Um dies zu überprüfen benötigen wir eine Umsortierung des AVL-Blattbaumes.

Voronoidiagramme

  • Das Voronoidiagramm unterstützt die Suche nach dem Nachbarknoten mit der geringsten Entfernung.
  • Die Kanten in diesem Diagramm liegen immer so, daß für benachbarte Knoten die Kante genau in der Mitte liegt. Für zwei benachbarte Knoten sind die Voronoi-Regionen Nachbarn.
  • Außen liegende Knoten, für die es keine Nachbarn mehr gibt, heißen unbeschränkte Voronoiregionen. Die Punkte heißen zusammen ,,Konvexe Hülle''.
  • Schnittpunkt die die Voronoikanten miteinander bilden, heißen Voronoiknoten.
  • Mittes Divide&Conquer kann ein Voronoidiagramm erstellt werden.
Mustererkennung Algorithmen der Informatik Randomisierte Algorithmen