IT-Zeitschriften, Fachbücher, eBooks, digitale Magazine und vieles mehr - direkt im heise shop online kaufen
Warenkorb Ihr Warenkorb ist noch leer.

  •  
     
    Neu im heise shop: FLIRC-Set mit Raspberry Pi
4,99 €*

Nachbarschaftssuche in Mengen von planaren, nicht-konvexen, nicht-überschneidenden Polygonen

eBook

Bewerten Sie dieses Produkt als Erster

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 (...
Sofortige Lieferung
Autor: Konstantin Sokolov
Anbieter: Grin Verlag
Sprache: Deutsch
EAN: 9783640576890
Veröffentlicht: 26.03.2010
Format: PDF
Schutz: DRMfrei Diese Digitale Ausgabe ist ohne DRM-Schutz.
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 mitVerfahren zur Auffindung dieser drei Arten von Nachbarschaftsbeziehungen in Mengenvon planaren, nicht-konvexen sich nicht-überschneidenden Polygonen. Nach der Vorstellungeines bereits bekannten Algorithmus zur „Kanten-Nachbarschaft“-Suche werden imHauptteil der Arbeit die beiden Algorithmen zur Auffindung der „Punkt-Nachbarschaft“und der „losen Nachbarschaft“ entwickelt. Im worst case liegt die Zeitkomplexität dieserbeiden Algorithmen in O(m²) (wobei m die Gesamtanzahl aller Kanten bzw. Eckpunkteist). Eine Sortierung aller Eckpunkte nach der x-Koordinate und eine anschließende, effiziente Vorauswahl führen in der Praxis jedoch zu einem vielfachen Speedup derLaufzeiten (im Vergleich zu einer rein quadratischen Zeitkomplexität). Durch die Tatsache,dass die beiden Algorithmen hochgradig parallelisierbar sind, kann ein weitererSpeedup erreicht werden. Diese Möglichkeit wird zum Schluss der Arbeit diskutiert.
Um bewerten zu können, melden Sie sich bitte an