Institut für Kartographie und Geoinformation Prof. Dr. Lutz Plümer Diskrete Mathematik II Vorlesung 5 SS 2001 Segmentschnitt II (n Segmente)

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

Diskrete Mathematik IIVorlesung 5

SS 2001

Segmentschnitt II (n Segmente)

Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 5 Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 5

2 2

Übersicht I

• Von 2 zu n Segmenten• Vorgehen• Reduktion von 2-dim auf 1-dim• Was haben wir davon?• Scan-Line-Verfahren• Idee• Scan-Line-Verfahren• Ist das wirklich schon der tolle Algorithmus,

den wir suchen?• Gegenbeispiel


3 3

Übersicht II

• Und nun?• Nachbarschaft• Ausnutzung der Nachbarschaft• Ordnungsrelation „x <‘‘• Ordnung der Segmente durch die Scan-Line• Scan-Line & dynamische Ordnung• Zusatzfrage: Wann wird der Schnittpunkt S1 erkannt?• Vereinfachende Annahmen• Algorithmus Scan-Line• Algorithmus (II)


4 4

Von 2 zu n Segmenten

• naheliegendes Vorgehen:überprüfe jedes Paar von Segmenten

• Wie viele Paare gibt es?– O(n2 )

• wende den zuvor skizzierten Algorithmus auf diese Paare an

• geht es auch schneller?• optimal wäre O(n * log n) (so schnell wie Sortieren)

0

10

20

30

40

50

0 2 4 6 8 10 12 14 16 18 20

n²

n log n

}n> n alle für f(n)cg(n) mit

0c|NN :{g O(f)

0

00


6 6

Vorgehen

• was wissen wir, was können wir ausnutzen?– Vermeidung unnötiger Berechnungen, deren Ergebnis durch

systematische Überlegung gewonnen werden kann

• was ist eine besonders einfache Variante dieses Problems?– alle Segmente liegen auf einer Geraden ( x-Achse)– eindimensionale Problemstellung

Können wir die allgemeine (schwierige) Variante auf die spezielle (einfache) zurückführen?


7 7

Reduktion von 2-dim auf 1-dim

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


8 8

Was haben wir davon?

• nur Segmente, deren horizontale Projektionen sich überlappen, können sich auch schneiden

• man kann die Prüfung auf diese Segmente einschränken

• Überprüfen aller Segmente durch sequentielles Vorgehen von links nach rechts („Scannen“)

• „Scan-Line“


9 9

Scan-Line-Verfahren

A

BF

C

D

ES1

S3

S2

S4


10 10

Idee:

• horizontale Scan-Line über die Ebene schieben– aktive Elemente: Schnitt mit der Scan-Line– nur aktive Elemente können horizontale Überschneidungen

haben– überprüfe aktive Elemente auf Schnittfreiheit

• Problem: wo sind die Haltepunkte der Scan-Line– Anfangspunkt eines Segments

– Endpunkt eines Segments

– interessant sind also die x-Koordinaten der Anfangs- und Endpunkte

• 1. Schritt: sortiere alle Punkte nach aufsteigenden x-Koordinaten– anders ausgedrückt: sortiere die x-Koordinaten und statte jede

x-Koordinate mit einem Verweis auf den zugehörigen Punkt aus


11 11

Scan-Line-Verfahren

A

BF

C

D

ES1

S3

S2

S4


12 12

Scan-Line-Verfahren

A

BF

C

D

ES1

S3

S2

S4


13 13

Scan-Line-Verfahren

A

BF

C

D

ES1

S3

S2

S4


14 14

Scan-Line-Verfahren

A

BF

C

D

ES1

S3

S2

S4


15 15

Scan-Line-Verfahren

A

BF

C

D

ES1

S3

S2

S4


16 16

Scan-Line-Verfahren

A

BF

C

D

ES1

S3

S2

S4


17 17

Scan-Line-Verfahren

A

BF

C

D

ES1

S3

S2

S4


18 18

Scan-Line-Verfahren

A

BF

C

D

ES1

S3

S2

S4


19 19

Scan-Line-Verfahren

A

BF

C

D

ES1

S3

S2

S4


20 20

Scan-Line-Verfahren

A

BF

C

D

ES1

S3

S2

S4


21 21

Scan-Line-Verfahren

A

BF

C

D

ES1

S3

S2

S4


22 22

Ist das wirklich schon der tolle Algorithmus, den wir suchen?


23 23

Gegenbeispiel

zu viele Elemente gleichzeitig aktiv O(n2)


24 24

Und nun?

• Scannen allein reicht nicht• zu viele Elemente gleichzeitig aktiv• wir können uns an jedem Haltepunkt der Scan-Line

maximal ein oder zwei (oder konstant viele) Tests erlauben

• also müssen wir sparen ...• und zusätzliches Wissen einspeisen• „nur benachbarte Segmente können sich schneiden“


25 25

Nachbarschaft

-Umgebung

A

B


26 26

Ausnutzung der Nachbarschaft

• wie definiert man „Nachbarschaft“ ...• ... so, daß man sehr schnell erkennt, ob zwei

Segmente benachbart sind?• Nutzung der Scan-Line

– Betrachte die Schnittpunkte der aktiven Segmente mit der Scan-Line

– ordne die Segmente nach den y-Koordinaten ihrer Schnittpunkte mit der Scan-Line

– nenne diese Ordnung „x <‘‘


27 27

Ordnungsrelation „x <‘‘

x x‘

B

A

C

Ax < B

Ax < C

Cx‘ < A

Cx < B

Ax‘ < B

Cx‘ < B


28 28

Ordnung der Segmente durch die Scan-Line

x< ist eine „partielle“ Ordnung ...– ... die nur auf der Menge der aktiven Elemente definiert ist– die Ordnung x< zwischen zwei Elementen wird an ihren

Schnittpunkten umgedreht• aus a x< b wird

b x< aam Schnittpunkt s von a und b

• diese Ordnung ist natürlich eindimensional• und für die aktiven Elemente vollständig• sie ist abhängig vom Haltepunkt x der Scan-Line• diese Ordnung ist also dynamisch und hängt von x als

Parameter ab• tun wir vorübergehend so, als hätten wir diese Ordnung „im Griff“


29 29

Scan-Line & dynamische Ordnung

A

BF

C

D

ES1

S3

S2

S4


30 30


A

BF

C

D

ES1

S3

S2

S4

A


31 31


A

BF

C

D

ES1

S3

S2

S4

AE


32 32


A

BF

C

D

ES1

S3

S2

S4

B

EA


33 33


A

BF

C

D

ES1

S3

S2

S4

B

DA

E


34 34


A

BF

C

D

ES1

S3

S2

S4

B

CA

DE


35 35


A

BF

C

D

ES1

S3

S2

S4

B

DC

E


36 36


A

BF

C

D

ES1

S3

S2

S4

B

EC

D


37 37


A

BF

C

D

ES1

S3

S2

S4

F

CB

ED


38 38


A

BF

C

D

ES1

S3

S2

S4

B

CF

ED


39 39


A

BF

C

D

ES1

S3

S2

S4

B

CF

E


40 40


A

BF

C

D

ES1

S3

S2

S4

C

EF


41 41


A

BF

C

D

ES1

S3

S2

S4

C

FE


42 42


A

BF

C

D

ES1

S3

S2

S4

C


43 43


A

BF

C

D

ES1

S3

S2

S4


44 44

Zusatzfrage: Wann wird der Schnittpunkt S1 erkannt?

A

S1

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

C

D

E

B


45 45

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


46 46

Algorithmus Scan-Line

Input:

S: eine Menge von Segmenten

Output:

die Schnittpunkte der Elemente von S

Sei

T = 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 pT

x 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)


47 47

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 die Menge L an der Stelle x

nachfolger(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 Schnittpunkt p und fügt ihn als neuen Haltepunkt in T ein.

offene Probleme:

eine geeignete Datenstruktur für T

eine geeignete Datenstruktur für L

Prüfung auf Schnitt, Berechnung des Schnittpunkts

Documents

Institut für Kartographie und Geoinformation Prof. Dr. Lutz Plümer Diskrete Mathematik II Vorlesung 5 SS 2001 Segmentschnitt II (n Segmente)