Praxisnahe serielle und parallelisierte Verfahren zur Bestimmung der Schnittpunkte von Liniensegmenten in der Ebene

ihre Anwendung in vielen Bereichen, z. B. in der Computergrafik, bei CAD
oder in der Kartographie. Mit der Berechnung der Schnittpunkte einer Menge
von Segmenten in der Ebene meint man die Bestimmung aller Paare von
Segmenten, die mindestens einen Punkt gemeinsam haben.

Es gibt verschiedene Algorithmen zur Bestimmung dieser Schnittpunkte.
In diesem Vortrag werden einige serielle Verfahren vorgestellt und diese unter Benutzung
verschiedener Eingabearten (zuf"allige Segmente, Segmentmengen mit
H"aufungsgebieten, Polygonnetze) miteinander verglichen. Da sich
nicht alle Verfahren parallelisieren lassen, werden parallele
Varianten einer Auswahl dieser seriellen Algorithmen vorgestellt.
Bei der Entwicklung von Algorithmen zur Bestimmung der Schnittpunkte
von Liniensegmenten machen besonders degenerierte F"alle
Schwierigkeiten. Solche Sonderf"alle bilden z. B. Segmente, deren
Endpunkte genau auf einem anderen Segment liegen. Ausser bei dem
Algorithmus von Balaban werden bei den vorgestellten Verfahren
alle degenerierten F"alle betrachtet.

Da die vorgestellten Algorithmen unter Benutzung der Fliesskommaarithmetik
im Rahmen meiner Diplomarbeit implementiert wurden, ergibt sich besonders
bei degenerierte F"allen das Problem der Rechenungenauigkeit.
Besonders bei der Entwicklung des randomisiertes Gitterverfahrens
wird versucht, unn"otige Rechenungenauigkeiten zu vermeiden.
In der Arbeit wie auch im Vortrag wird jedoch das Problem der
Rechenungenauigkeit nicht gel"ost.