Institut für Kartographie und Geoinformation Prof. Dr. Lutz Plümer Diskrete Mathematik II Foliendesign: Jörg Steinrücken & Tobias Kahn Vorlesung 6 18.05.00

Institut für Kartographie und GeoinformationProf. Dr. Lutz Plümer

Diskrete Mathematik II

Foliendesign: Jörg Steinrücken & Tobias Kahn

Vorlesung 618.05.00

Segmentschnitt III

Lutz Plümer - Diskrete Mathematik II - SS 2000 - Vorlesung 6 - 18.05.00 2

Reduktion von 2-dim auf 1-dim

• Überlappung der horizontalen Projektionen ist notwendig, aber nicht hinreichend für einen Schnitt


Scan-Line-Verfahren

A

B F

C

D

ES1

S3

S2

S4


Gegenbeispiel

zu viele Elemente gleichzeitig aktiv O(n2)


Nachbarschaft

-UmgebungA

B


Ordnungsrelation „x <‘‘

x x‘

B

A

C

Ax < B

Ax < C

Cx‘ < A

Cx < B

Ax‘ < B

Cx‘ < B


Scan-Line & dynamische Ordnung

A

B F

C

D

ES1

S3

S2

S4



A

B F

C

D

ES1

S3

S2

S4

A



A

B F

C

D

ES1

S3

S2

S4

AE



A

B F

C

D

ES1

S3

S2

S4

B

EA



A

B F

C

D

ES1

S3

S2

S4

B

DA

E



A

B F

C

D

ES1

S3

S2

S4

B

CA

DE



A

B F

C

D

ES1

S3

S2

S4

B

DC

E



A

B F

C

D

ES1

S3

S2

S4

B

EC

D



A

B F

C

D

ES1

S3

S2

S4

F

CB

ED



A

B F

C

D

ES1

S3

S2

S4

B

CF

ED



A

B F

C

D

ES1

S3

S2

S4

B

CF

E



A

B F

C

D

ES1

S3

S2

S4

C

EF



A

B F

C

D

ES1

S3

S2

S4

C

FE



A

B F

C

D

ES1

S3

S2

S4

C



A

B F

C

D

ES1

S3

S2

S4


Zusatzfrage: Wann wird der Schnittpunkt S1 erkannt?

A

S1

Übung: Wird ein Schnittpunkt ggf. mehr als einmal erkannt?

C

D

E

B


Vereinfachende Annahmen

Annahme• 2 Segmente schneiden sich

höchstens in einem Punkt

• in keinem Punkt schneiden sich mehr als 2 Segmente

• die x-Koordinaten aller Segmente sind paarweise verschieden

• kein Segment ist vertikal

Gegenbeispiele


Algorithmus Scan-Line

Input:S: eine Menge von SegmentenOutput:die Schnittpunkte der Elemente von SSeiT = Endpunkte der Segmente von S

nach x-Koordinaten sortiert (Haltepunkte)

L = // aktive Segmente von S while T do bestimme und entferne

den nächsten Punkt pTx ist x-Koordinate von p

case: p ist linker Endpunkt von sfuege_ein(s,x,L)sl = vorgaenger(s,x,L)sr = nachfolger(s,x,L)schnitt(sl,s,T);schnitt(s,sr,T);

p ist rechter Endpunkt von ssl = vorgaenger(s,x,L)sr = nachfolger(s,x,L)entferne(s,x,L)schnitt(sl,sr,T)p ist Schnittpunkt von s und tvertausche(s,t,L,x) // t < ssl = vorgaenger(t,x,L)sr = nachfolger(s,x,L)schnitt(sl,t,T)schnitt(s,sr,T)


Algorithmus (II)

fuege_ein(s,x,L): fügt das Segment s in die Menge L ein entsprechend der Ordnung an der Stelle x

entferne(s,x,L): entfernt das Segment s aus L an der Stelle xnachfolger(s,x,L): liefert den Nachfolger von s in L an der Stelle x, falls

vorhanden

vorgaenger(s,x,L): liefert den Vorgänger von s in L an der Stelle x, falls vorhanden

schnitt(s,t,T): prüft s und t auf Schnitt. Berechnet ggf. den Schnitt-punkt p und fügt ihn als neuen Haltepunkt in T ein.

offene Probleme: eine geeignete Datenstruktur für Teine geeignete Datenstruktur für LPrüfung auf Schnitt, Berechnung des Schnittpunkts


Datenstrukturen für T und S

• Datenstrukur für T– AVL-Baum– letztes Semester

• was ist ein AVL-Baum– erstens ein Suchbaum– zweitens ausgeglichen

• Datenstruktur für L– AVL-Baum?– Problem: „Vorgänger“ und „Nachfolger“ finden

das wird vom AVL-Baum nicht unterstützt– also: Variante des AVL-Baums

• alle Informationen sind in Blättern (nicht in inneren Knoten)• die Blätter bilden eine doppelt verkettete Liste


Eine Variante des AVL-Baums

• mit einer doppelt verketteten Liste der Blätter

• für die Menge der aktiven Elemente


für die Haltepunkte ...

• ...mit den Operationen– Einfügen eines gefundenen Schnittpunktes– Finden und Entfernen des nächsten (also minimalen)

Elements ...

• ... genügt ein „normaler“ AVL-Baum• obwohl man mit Kanonen auf Spatzen schießt• besser: ein Heap (wie bei Dijkstra)

Documents

Institut für Kartographie und Geoinformation Prof. Dr. Lutz Plümer Diskrete Mathematik II Foliendesign: Jörg Steinrücken & Tobias Kahn Vorlesung 6 18.05.00