curs14

Intersectia segmentelorSuprapunerea straturilor tematice

Intersectii

Mihai-Sorin Stupariu

Curs 14, Sem. I, 2011-2012

Mihai-Sorin Stupariu Intersectii

Structuri de date utilizate

I Q coada de evenimente (puncte)

I T arbore binar echilibrat de cautare (segmente)

Structuri de date utilizate

I Q coada de evenimente (puncte)

I T arbore binar echilibrat de cautare (segmente)

Algoritm INTERSECTII

I Input. O multime de segmente din planul R2.

I Output. Multimea punctelor de intersectie; pentru fiecarepunct de precizeaza segmentele pe care se gaseste.

1. Q ← ∅. Insereaza extremitatile segmentelor ın Q; ımpreuna cumarginea superioara a unui segment memoreaza si segmentul

2. T ← ∅.3. while Q 6= ∅4. do determina evenimentul p care urmeaza ın Q si ıl sterge

5. ANALIZEAZA (p)

2. T ← ∅.

3. while Q 6= ∅4. do determina evenimentul p care urmeaza ın Q si ıl sterge

5. ANALIZEAZA (p)

2. T ← ∅.3. while Q 6= ∅

4. do determina evenimentul p care urmeaza ın Q si ıl sterge

5. ANALIZEAZA (p)

ANALIZEAZA (p)

1. Fie U(p) multimea segmentelor a caror extremitate superioaraeste p (pentru cele orizontale este marginea din stanga) -stocata cu p ın Q

2. Determina toate segmentele care contin p: sunt adiacente ınT (de ce?) Find all segments stored in T that contain p; theyare adjacent in T. Fie L(p), respectiv C (p), multimeasegmentelor care au p drept margine inferioara, respectivcontin p ın interior

3. if L(p) ∪ U(p) ∪ C (p) contine mai mult de un segment

4. then raporteaza p ca punct de intersectie, ımpreuna cusegmentele din L(p), U(p), C (p)

ANALIZEAZA (p)

5. sterge segmentele din L(p) ∪ C (p) din T

6. insereaza segmentele din U(p) ∪ C (p) ın T (ordineasegmentelor pe frunzele lui T coincide cu ordinea ın care suntintersectate de o linie de baleiere situata imediat sub p)

ANALIZEAZA (p)

5. sterge segmentele din L(p) ∪ C (p) din T6. insereaza segmentele din U(p) ∪ C (p) ın T (ordinea

segmentelor pe frunzele lui T coincide cu ordinea ın care suntintersectate de o linie de baleiere situata imediat sub p)

ANALIZEAZA (p)

7. if U(p) ∪ C (p) = ∅

8. then fie sl si sr vecinii din stanga/dreapta ai lui p din T9. DETERMINAEVENIMENT (sl , sr , p)

10. else fie s ′ din U(p) ∪ C (p) cel mai ın stanga ın T11. fie sl vecinul din stanga al lui p

12. DETERMINAEVENIMENT (sl , s ′, p)

13. fie s ′′ din U(p) ∪ C (p) cel mai ın dreapta ın T14. fie sr vecinul din dreapta al lui p

15. DETERMINAEVENIMENT (s ′′, sr , p)

ANALIZEAZA (p)

7. if U(p) ∪ C (p) = ∅8. then fie sl si sr vecinii din stanga/dreapta ai lui p din T

9. DETERMINAEVENIMENT (sl , sr , p)

ANALIZEAZA (p)

7. if U(p) ∪ C (p) = ∅8. then fie sl si sr vecinii din stanga/dreapta ai lui p din T9. DETERMINAEVENIMENT (sl , sr , p)

ANALIZEAZA (p)

10. else fie s ′ din U(p) ∪ C (p) cel mai ın stanga ın T

11. fie sl vecinul din stanga al lui p

ANALIZEAZA (p)

13. fie s ′′ din U(p) ∪ C (p) cel mai ın dreapta ın T

14. fie sr vecinul din dreapta al lui p

ANALIZEAZA (p)

DETERMINAEVENIMENT (sl , sr , p)

1. if sl si sr se intersecteaza sub linia de baleiere si punctul deintersectie nu este deja ın Q

2. then insereaza punctul de intersectie ca eveniment ın Q

DETERMINAEVENIMENT (sl , sr , p)

1. if sl si sr se intersecteaza sub linia de baleiere si punctul deintersectie nu este deja ın Q

2. then insereaza punctul de intersectie ca eveniment ın Q

Rezultatul principal (intersectii de segmente)

Teorema. Fie S o multime care contine n segmente din planul R2.Toate punctele de intersectie ale segmentelor din S, ımpreuna cupunctele corespunzatoare, pot fi determinate ın O(n log n + I log n)timp, folosind O(n) spatiu, unde I este numarul punctelor deintersectie.

Subdiviziuni planare

I Conceptul de subdiviziune planara.

I Lista dublu ınlantuita (trei ınregistrari: varfuri, fete, muchiiorientate (semi-muchii)).

I Varf v : coordonatele lui v ın Coordinates(v), pointerIncidentEdge(v) spre o muchie orientata care are v ca origine

I Fata f : pointer OuterComponent(f ) spre o muchie orientatacorespunzatoare frontierei externe (pentru fata nemarginitaeste nil); lista InnerComponents(f ), care contine, pentrufiecare gol, un pointer catre una dintre muchiile orientate depe frontiera

I Muchie orientata→e : pointer Origin(

→e ), pointer Twin(

→e )

pointer IncidentFace(→e ), pointer Next(

→e ), pointer Prev(

→e ).

Subdiviziuni planare

I Conceptul de subdiviziune planara.I Lista dublu ınlantuita (trei ınregistrari: varfuri, fete, muchii

orientate (semi-muchii)).I Varf v : coordonatele lui v ın Coordinates(v), pointer

IncidentEdge(v) spre o muchie orientata care are v ca origineI Fata f : pointer OuterComponent(f ) spre o muchie orientata

corespunzatoare frontierei externe (pentru fata nemarginitaeste nil); lista InnerComponents(f ), care contine, pentrufiecare gol, un pointer catre una dintre muchiile orientate depe frontiera

I Muchie orientata→e : pointer Origin(

→e ), pointer Twin(

→e )

pointer IncidentFace(→e ), pointer Next(

→e ), pointer Prev(

→e ).

Algoritm SUPRAPUNERE (S1,S2)

I Input. Doua subdiviziuni planare S1, S2 memorate ın listedublu ınlantuite D1,D2

I Output. Overlay-ul dintre S1,S2, memorat ıntr-o lista dubluınlantuita D

1. Copiaza listele D1,D2 ıntr-o noua lista dublu ınlantuita D2. Calculeaza toate intersectiile de muchii dintre S1 si S2 cu

algoritmul INTERSECTII. La fiecare eveniment, pe langaactualizarea lui Q si T , efectueaza:

I Actualizeaza D, ın cazul ın care evenimentul implica muchii alelui S1, S2

I Memoreaza noile muchii orientate adecvat

1. Copiaza listele D1,D2 ıntr-o noua lista dublu ınlantuita D

2. Calculeaza toate intersectiile de muchii dintre S1 si S2 cualgoritmul INTERSECTII. La fiecare eveniment, pe langaactualizarea lui Q si T , efectueaza:

3. Determina ciclii de frontiera din O(S1,S2), stabileste natura(exteriori/interiori)

4. Construieste graful G ale carui noduri corespund ciclilor defrontiera si ale carui arce unesc fiecare ciclu corespunzand uneigauri cu ciclul de la stanga varfului cel mai din stanga sidetermina componentele conexe ale lui G

5. for fiecare componenta a lui G6. do Fie C unicul ciclu de frontiera exterioara a

componentei si fie f fata marginita a ciclului. Creeazao ınregistrare pentru f , seteaza OuterComponent(f )(catre una din muchiile lui C), construieste listaInnerComponents(f ) (pentru fiecare gol, pointer catreuna dintre muchiile orientate). Pentru fiecare muchieorientata, IncidentFace() catre ınregistrarea lui f

7. Eticheteaza fiecare fata a lui O(S1,S2)

5. for fiecare componenta a lui G

6. do Fie C unicul ciclu de frontiera exterioara acomponentei si fie f fata marginita a ciclului. Creeazao ınregistrare pentru f , seteaza OuterComponent(f )(catre una din muchiile lui C), construieste listaInnerComponents(f ) (pentru fiecare gol, pointer catreuna dintre muchiile orientate). Pentru fiecare muchieorientata, IncidentFace() catre ınregistrarea lui f

Rezultatul principal (overlay-ul hartilor)

Teorema. Fie S1 o subdiviziune de complexitate n1, S2 osubdiviziune de complexitate n2, fie n := n1 + n2. Overlay-ul dintreS1 si S2 poate fi construit ın O(n log n + k log n), unde k estecomplexitatea overlay-ului.

curs14

Documents