Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


27. Geometrischer Schnitt



Ein natürliches Problem, das in geometrischen Anwendungen häufig entsteht, lautet: »Gegeben sei eine Menge von N Objekten; schneiden sich zwei beliebige von ihnen?« Die betreffenden »Objekte« können Linien, Rechtecke, Kreise, Polygone oder andere geometrische Objekte sein. Zum Beispiel ist es in einem System für die Entwicklung und Verarbeitung von integrierten Schaltkreisen oder Leiterplatten wichtig zu wissen, daß sich keine zwei Leiter schneiden und einen Kurzschluß hervorrufen. In einem industriellen System für den Entwurf von Plänen, die mit Hilfe einer CNC-Maschine ausgeführt werden sollen, ist es wichtig zu wissen, daß sich keine zwei Teile des Plans überschneiden. In der Computergraphik kann das Problem der Bestimmung, welches Objekt aus einer Menge von Objekten unter einem bestimmten Blickwinkel verdeckt wird, als ein Problem des geometrischen Schnitts der Projektionen der Objekte auf die Betrachtungsebene formuliert werden. Und in Operations Research führt die mathematische Formulierung vieler wichtiger Probleme in natürlicher Weise zu Problemen des geometrischen Schnitts.

Die offensichtliche Lösung des Schnittproblems besteht darin, jedes Paar von Objekten zu überprüfen und festzustellen, ob sie sich schneiden. Da es ungefähr N2/2 Paare von Objekten gibt, ist die Laufzeit dieses Algorithmus proportional zu N2. Für manche Anwendungen ist dies möglicherweise kein Problem, da andere Faktoren die Anzahl der zu bearbeitenden Objekte begrenzen. Bei vielen anderen Anwendungen ist es jedoch nicht ungewöhnlich, daß man es mit Hunderttausenden oder sogar Millionen von Objekten zu tun hat. Der grobe N2-Algorithmus ist für solche Anwendungen offenbar ungeeignet. Im vorliegenden Abschnitt untersuchen wir ein allgemeines Verfahren, mit dessen Hilfe in einer zu N log N proportionalen Zeit bestimmt werden kann, ob sich zwei beliebige Objekte aus einer Menge von N Objekten schneiden; dieses Verfahren beruht auf Algorithmen, die von M. Shamos und D. Hoey 1976 in einer richtungsweisenden Arbeit vorgestellt wurden.

Zuerst betrachten wir einen Algorithmus, der aus einer Menge von Linien, die ausschließlich horizontal oder vertikal verlaufen, alle sich schneidenden Paare zurückgibt. Dies macht das Problem in gewisser Hinsicht einfacher (horizontale und vertikale Linien sind relativ einfache geometrische Objekte), in anderer Hinsicht jedoch komplizierter (das Zurückgeben aller sich schneidenden Paare ist schwieriger, als einfach zu bestimmen, ob ein solches Paar existiert). Die Implementation, die wir entwickeln werden, wendet binäre Suchbäume und das Programm für die Bereichssuche in Intervallen aus dem vorangegangenen Kapitel in einem doppelt rekursiven Programm an.

Danach untersuchen wir das Problem, das darin besteht zu bestimmen, ob sich zwei beliebige Strecken aus einer Menge von N Strecken schneiden, ohne einschränkende Bedingungen für die Strecken. Dabei kann dieselbe allgemeine Strategie angewandt werden, die für den horizontal-vertikalen Fall benutzt wurde. Tatsächlich ist die gleiche Grundidee für das Auffinden von Schnitten zwischen vielen anderen Typen von geometrischen Objekten geeignet. Allerdings ist für Strecken und andere Objekte die erweiterte Aufgabenstellung, alle sich schneidenden Paare zurückzugeben, um einiges komplizierter als für den horizontal-vertikalen Fall.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]