Nachbarschaftssuche in Mengen von planaren, nicht-konvexen, nicht-überschneidenden Polygonen (eBook, PDF) - Sokolov, Konstantin
Statt 17,95 €**
15,99 €
**Preis der gedruckten Ausgabe (Broschiertes Buch)

inkl. MwSt. und vom Verlag festgesetzt.
Sofort per Download lieferbar
  • Format: PDF

Studienarbeit aus dem Jahr 2010 im Fachbereich Informatik - Allgemeines, Rheinisch-Westfälische Technische Hochschule Aachen (Mensch-Maschine-Interaktion), Sprache: Deutsch, Abstract: Zwei Polygone sind benachbart wenn sie gemeinsame Kantensegmente teilen („Kanten- Nachbarschaft“) oder wenn sie gemeinsame Punkte auf einer Kante besitzen („Punkt- Nachbarschaft“) oder wenn sie sich gar nicht berühren, sondern in einer gewissen Nähe zueinander liegen („lose Nachbarschaft“). Die vorliegende Arbeit beschäftigt sich mit Verfahren zur Auffindung dieser drei Arten von Nachbarschaftsbeziehungen in…mehr

Andere Kunden interessierten sich auch für
Produktbeschreibung
Studienarbeit aus dem Jahr 2010 im Fachbereich Informatik - Allgemeines, Rheinisch-Westfälische Technische Hochschule Aachen (Mensch-Maschine-Interaktion), Sprache: Deutsch, Abstract: Zwei Polygone sind benachbart wenn sie gemeinsame Kantensegmente teilen („Kanten- Nachbarschaft“) oder wenn sie gemeinsame Punkte auf einer Kante besitzen („Punkt- Nachbarschaft“) oder wenn sie sich gar nicht berühren, sondern in einer gewissen Nähe zueinander liegen („lose Nachbarschaft“). Die vorliegende Arbeit beschäftigt sich mit Verfahren zur Auffindung dieser drei Arten von Nachbarschaftsbeziehungen in Mengen von planaren, nicht-konvexen sich nicht-überschneidenden Polygonen. Nach der Vorstellung eines bereits bekannten Algorithmus zur „Kanten-Nachbarschaft“-Suche werden im Hauptteil der Arbeit die beiden Algorithmen zur Auffindung der „Punkt-Nachbarschaft“ und der „losen Nachbarschaft“ entwickelt. Im worst case liegt die Zeitkomplexität dieser beiden Algorithmen in O(m²) (wobei m die Gesamtanzahl aller Kanten bzw. Eckpunkte ist). Eine Sortierung aller Eckpunkte nach der x-Koordinate und eine anschließende, effiziente Vorauswahl führen in der Praxis jedoch zu einem vielfachen Speedup der Laufzeiten (im Vergleich zu einer rein quadratischen Zeitkomplexität). Durch die Tatsache, dass die beiden Algorithmen hochgradig parallelisierbar sind, kann ein weiterer Speedup erreicht werden. Diese Möglichkeit wird zum Schluss der Arbeit diskutiert.