Carte Tradusa

7/26/2019 Carte Tradusa

1/17

Linia de segment intersectie

Tematica: harta de acoperire

Cand vizitati o tara, hartile sunt o sursa nepretuita de informatii. Ele va arata unde sunt situate obiectele turistice,ele indica drumurile si liniile de cale ferata pentru a ajunge acolo, ele arata mici lacuri, si asamai departe. Din pacate, ele pot fi o sursa de frustrare, asa cum este adesea dificil de gasit informatii:chiar si atunci cand stii pozitia aproximativa a unui oras mic, poate fi dificil de gasit pe harta.Pentru a face harti mai usor de citit, sistemele de informatii geografice le-a impartit in mai multe straturi.iecare strat este o harta tematica care stocheaza doar un singur fel de informatii. !stfel va exista unstarat de stocare al drumurilor, un strat de stocare al oraselor, un strat de stocare al raurilor, si asa maideparte. "ema unui strat poate fi mai abstract . De exemplu, poate exista un strat de densitate alpopulatiei, de precipitatii a mediului, habitat ursului grizzl# sau pentru vegetatie. $nformatiile de tipulgeometric pot fi stocate in straturi diferite: stratul pentru un parcurs ar putea stoca drumuri ca fiind

colectii de segmente de linie%sau curbe, probabil&,stratul de orase ar putea contine puncte etichetate cunumele de oras, iar stratul de vegetatie ar putea stoca o subdiviziue a hartii in regiunile etichetate cu tipulde vegetatie.

'tilizatorii unui sistem de informatii geografice pot selecta una dintre tematicile afisate pentru harti.Pentru a gasi un oras mic ar selecta stratul stocare orase, si nu ar fi distras de informatii, cum ar fi numeleraurilor si al lacurilor. Dupa ce s-a reperat orasul probabil doriti sa stiti cum sa ajungeti acolo. $n acestsens sistemele de informatii geografice permite utilizatorilor sa vizualizeze o suprapunere de mai multeharti.olosind o suprapunere de parcurs si harta de stocare a oraselor, acum va puteti da seama cum obtineti unoras. !tunci cand doua sau mai multe straturi tematice ale harti sunt reprezentate impreuna, intersectiiledin suprapunere sunt pozitii de interes deosebit. De exemplu, atunci cand vizualizati suprapunerea a

stratului pentru drumuri si a stratului pentru rauri, ar fi util ca intersectiile sa fie in mod clar marcate.$n acest exemplu doua harti sunt practice retele si intersectiile sunt puncte. $n alte cazuri, unul esteinterest de intersectia regiunilor complete. De exemplu, geografii studiaza climatice ce ar putea fiinteresante in gasirea de regiuni in care exista o padure de pini si precipitatii anuale intre ()))mm si (*))mm. !ceste regiuni sunt intersectiile regiunilor etichetate ca+Padurea de pini+in harta vegetatiei siregiunile cu eticheta ()))-(*))+ in arta precipitatiilor.

$ntersectia de segment linie .(

/om studia in primul rand cea mai simpla forma de acoperire harta problema, in cazul in care cele douastraturi ale harti sunt retelele reprezentate ca fiind colectii de segmente de linie. De expemlu, o harta cu

un strat de stocare al drumurilor, a cailor ferate sau a raurilor, la o scara mica. 0etineti ca puteti asa putetisa puneti curbe apropiate de un numar mic de segmente. 1a inceput nu vom fi intersesati in regiunileinduse de aceste segmente de linie. 2ai tarziu vom vedea mai multe situatii mult mai complexe undehartile nu sunt doar retele. Pentru a rezolva in reteaua suprapunere ,in primul rand problema trebuie sa seafirme ca intr-un d3cor geometric. Pentru acoperirea a doua retele geometrice avem urmatoarea situatie:se dau doua seturi de segmente de linie, calculeaza toate intersectiile dintre un segment dintr-un set si unsegment din alt set. Cu aceasta specificatie problema nu este destul de precisa cu toate acestea, nu putemdefini cum doua segmente se intersecteaza. $n special, doua segmente se intersecteaza atunci cand unpunct se afla sau nu pe celalalt4 $n alte cuvinte, trebuie sa specificati daca segmentele de intrare sunt


2/17

deschise sau inchise. Pentru a face aceasta decizie ar trebui sa mergem inapoi la cerere, acoperire reteaproblema. Drumurile intr-o harta rutiera si raurile intr-o harta de rauri sunt reprezentate de lanturi dsegmente, astfel incat o trecere a unui drum si a unui rau corespunde la interior de un lant si seintersecteaza in interior cu un alt lant. !cest lucru nu inseamna ca nu exista o intersectie intre interiorul adoua segmente: intersectia unui punct s-ar putea intampla pentru a coincide cu punctual unui segmentdintr-un lant. $n fapt, aceasta situatie nu este neobijnuta pentru ca vanturile si raurile sunt reprezentate de

mai multe segmente mici si coordinate de obiective ce pot fi rotunjite cand hartile sunt digitalizate. Putemconcluziona ca ar trebui sa definim segmentele pentru a fi inchise, astfel incat un punct al unui segmentcalculat pe alt segment calculat se considera o intersectie. Pentru a simplifica descrierea oarecum ne punem segmente din ambele seturi intr-un singur set, sicalculam toate intersectiile dintre segmente in acest set.$n acest fel vom gasi cu siguranta toate intersectiile pe care le vrem. !m gsit, de asemene a intersectiiledintre segmentele din acelasi set. !lte intersectii pot fi filtrate dupa aceea verificand pur si simpluverificand fiecare intersectie raportata. Daca cele doua segmente implicate fac parte din acelasi set. Deciproblema noastra, caietul de sarcini este dupa cum urmeaza: avand in vedere un set 5n segmente inchisein plan, raporteaza toate punctele de intersectie dintre segmentele 5.!ceasta nu pare a fi o problema provocatoare: pur si simplu ne putem lua fiecare perechea de segmente,calcula daca acestea se intersecteaza si daca este asam aprorteaza intersectia punctelor lor. !cest alogorit

necesita timp in mod special 6%n&. $ntr-un sens acesta este optim: cand fiecare pereche de segmenteintersecteaza orice algoritm trebuie sa iasa 7%n& timp, pentru ca are de raportat toate intersectiile .Poatefi dat un exemplu similar cand este considerata suprapunerea a doua retele. $n situatiile practice, cu toateacestea, cele mai multe segmente s eintersecteaza numarul sau doar alte cateva segmente,astfel incatnumarul total de puncte de intersectie sa fie mai mic decat patratica. !r fi frumos sa aiba un algoritm careeste mai rapid in astfel de situatii. Cu alte cuvinte, ne dorim un algoritm al carui timp de rurale depinde nunumai de numarul de segmente in introducere, ci si de numarul de puncte din intersectie . 'n astfel dealgoritm este numit un algoritm sensibil la iesire: timpul de executie al algoritmului este sensibil lamarimea de iesire. !m putea apela, de asemenea, un astfel de algoritm sensibil la inersectie, deoarecenumarul de intersectii este ceea ce determina marimea de iesire.Cum putem evita toate perechiile de segmente pentru intersectia de testare4 !ici ne trebuie sa facem uz degeometrie a situatiei: segmentele care sunt apropiate sunt candidate pentru intersectie, spre doasebire de

segmentele care sunt departe una de cealalta. 2ai jos vom vedea cum putem folosi acesta observatiepentru a obtine un algortim de iesire- sensibil pentru lina de segment intersectie.

ie 5:89 s1 , s2 ,..., sn multimea de segmente pentru care noi ne dorim sa calculam toate

intersectiile. Dorim sa evitam perechile de segmente de testare, care sunt departe unele de altele. Dar cumputem face acest lucru4 ai sa incercam mai intai intr-un caz simplu. Definim #- un interval de segmentcare sa fie proiectie ortogonala pe axa #. Cand intervalul # are o pereche de segmente care nu se suprapun,am putea spune ca aceasea sunt departe in afara, segmentele # nu se pot intersecta. Prin urmare, avemnevoie doar pentru a testa perechi de segmente ale caror interval # sa se suprapuna, adica perechi care auo linie orizontala care se suprapune cu ambele segmente. Pentru a gasi aceste perechi ne imaginam o linie

de maturat strada 1 in sos, deaspura planului, pornind de la o pozitie mai presus de toate segmentele. $ntimp ce noi maturam linia imaginara, vom tine evident tuturor segmentelor intersectand detalii cu privirela acest lucru ce va fi explicat mai tarziu, astfel incat sa putem gasi perechile de care avem nevoie.

!cest tip de algoritm este numit un algoritm ce matura avinul si linia 1 se numeste linia de rotire. 1iniade rotire este setul de segmente ce se intersecteaza. 2odifica statutul in timp ce matura linie se muta injos, dar nu continuu. ;umai punctele speciale sunt o actualizare a statutului necesara. ;oi numim acesrepuncte, puncte eveniment de avion matura algoritm. $n acest algoritm punctele de exeniment sunt capetelesegmentelor.


3/17

2omentele in care linia de rotire ajunge la un punct de eveniment sunt numai moment candalgoritmul de fapt face ceva: actualizeaza statutului liniei de rotire si efectueaza unele teste aleintersectiei. $n special, daca evenimentul punctului este punctul final superior al unui segment,atunci noulsegment incepe intersectarea liniei matura si adauga starea. !cest segment este testat impotriva liniilor derotire deja intersectate. Daca la final un punct este mai mic,segmental se opreste din intersectia liniilor derotire si il elimina din statut. $n acest fel am testat numai perechi de segmente pentru care exista o linie

orizonatala care intersecteaza ambele segmente. Din pacate, acesta nu este suficient: inca mai existasituati in care am testat un numar patratic de perechi, intrucat exista doar un numar mic de puncte deintersectie. 'n exemplu simplu este un set de segmente vertical care se intersecteaza de axa


4/17

Prin urmare, trebuie sa existe un eveniment unde punctual >,si si

sj devin adiacente si sunt testate

pentru intersectie.

Deci, abordarea noastra este corecta, cel putun cand uitam despre cazurile urate pe care le-ammentionat mai devreme. !cum putem contiuna cu dezvoltarea algoritmului avion-matura. 5a recapitulam

pe scurt abordarile gloabale. ;e imaginam ca se deplaseaza in jos o linie orizontala matura 1 peste plan.1inia de rotiri opriri la anumite puncte de eveniment= in cazul nostrum,acestea sunt caracteristicile desegment, care se stiu in preabalil, si punctele de intersectie,care sunt calculate din zbor. $n timp ce linia derotire pastreaza secvente comandate de segmente intersectate de acesta. Cand linia de rotire se opreste laun punct eveniment, secventa segmentelor se modifica si in functie de tipul de punct eveniment, trebuiesa luam mai multe decizi pentru a actualize starea si a detecta intersectiile.

!tunci cand punctul de eveniment este punctul final superior al unui segment, exista un nou segmentcare intersecteaza linia de rotire. !cest segment trebuie sa fie testat impotriva intersectiei celor doi veciniai sai de-a lungul liniei de rotire. Doar punctele de intersectie de sub linia de rotire sunt importante= cele

de mai sus de linia de rotire au fost deja detectate. De exemplu, in cazul in care segmentelesi si

sk

sunt adiacente pe linia de rotire, atunci trebuie sa testati sj pentru intersectia cu si si sk . Daca

vom gasi o intersectie sub linia de rotire, am gasit un nou punct de eveniment. Dupa ce punctul finalsuperior este atins vom continua cu urmatorul punct de eveniment. !tunci cand punctul de eveniment este o intersectie, cele doua segmente care se intersecteaza isi vorschimba ordinea. icare dintre ei devine %cel mult& un nou vecin impotriva caruia este testata o nouaintersectie. Din nou, numai intersectiile de sub linia de rotire sunt inca interesante. 5a presupunem ca

patru segmente sj , sk , s l si sm apar in aceasta ordine pe linia de rotire atunci cand se ajunge

la punctual de intersectie al segmentelor sk si sl . !poi sk si sl isi comuta pozitiile si

trebuie sa testam sk si sl sub linia de rotire, si deasemenea, si sl si sm . $ntersectiile noi

pe care le gasim sunt, de sigur, asemenea puncte de eveniment ale algoritmului. 0etineti, totusi, ca esteposibil ca aceste evenimente sa fi fost deja detectate, si anume in cazul in care o pereche a devenitadiacenta, aceasta sa fi fost si inainte adiacenta.

!tunci cand punctul de eveniment este punctul final mai mic al unui segment, cei doi vecini ai saidevin adiacenti si trebuie sa fie testati pentru intersectie. $n cazul in care se intersecteaza sub linia derotire, punctual sau de intersectie este un punct de eveniment. % Din nou, aceste eveniment ar putea sa fie

deja detectat&. Presupunem trei segmentesk ,

sl si sm care apar in aceasta ordine pe linia de

rotire ,atunci se intalneste obiectivul final inferiorsl . !tunci sk si sm vor devein adiacente

cand a fost testate intersectia. Dup ace ne-am cuprins intregul plan ? mai exact, dupa cce vom testat si ultimul punct eveniment- amcalculate toate punctele de intersectie. !ceste lucruri sunt garantat invariante, ce detine in acest momenttimpul de rotire : toate punctele de intersectie deasupra liniei de rotire au fost calculate corect.

Dupa aceasta schita a algoritmului, este timpul pentru a merge in detaliu. Este timpul sa se uite lacazurile degenerate care pot aparea, cum ar fi trei sau mai multe segmente intalnite intr-un punct. ;oitrebuie sa specificam in primul rand ceea ce asteptam de la algoritm in aceste cazuri. !m putea cere caalgoritmul sa raporteze pur si simplu fiecare punct de intersectie o singura data, dar se pare ca este mai


5/17

util daca raporteaza pentru fiecare punct cate o lista de segmente care trec prin ea, sau sa-l afiseze unpunct final. Exista un alt caz special pentru care noi ar trebui sa definim iesirea necesara mai cu atentie, sianume doua segmente partial suprapuse, dar pentru simplitate trebuie sa ignoram acest caz din aceastasectiune.

$ncepem prin a descrie structurile de date ale algoritmului.

$n primul rand avem nevoie de o structura de date- numita coada eveniment- care sticheazaevenimentele. /om desemna coada eveniment @. !vem nevoie de o operatie care elimina uramtoruleveniment care va avea loc in @, si sa facem in asa fel incat sa fie tratata. !cest eveniment este cel maimare eveniment de sub linia de rotire. $n cazul in care doua puncte de eveniment cu coordonatele # si x sucoordinate mai mici acestea vor fi returnate. Cu alte cuvinte, punctele de eveniment de pe linia orizontalasunt tratate de la stanga la dreapta. !cest lucru implica faptul ca ar trebui sa consideram punct final stangun segment orizontal care ar fi punct final superior,si punctual sau final drept sa fie mai mic. /a putetigandi, de asemenea, la conventia noastra dupa cum urmeaza: in loc de un eveniment orizontal linie,imaginati-va ca este inclinat doar un pic in sus.0ezultatul liniei de rotire ajunge la punctul final stang alunui segment orizontal chiar inainte de a ajunge la punctual final din dreapta. Coada de evenimentetrebuie sA permitA inserAri, deoarece noi evenimente vor fi calculate pe zbor. 6bservati ca doua puncte deeveniment pot coincide. De exemplu, pot coincide capetele superioare a doua segmente distinct. Este

convenabil de a trata acest lucru ca un punct eveniment. Prin urmare, o inseratie trebuie sa fie capabila saverifice daca un eveniment este eja present in @. /om implementa coada de eveniment dupa cum urmeaza. Definiti un ordin eveniment carereprezinta ordinea in care vor fi tratate. Prin urmare, daca p si > sunt doua puncte de eveniment atunci

avem p> daca si numai daca py>qy sau py= qy si px


6/17

p. 0ezulta ca fiecare operatiune de cautare si actualizare a vecinilor ia 6% log n & timp. Coada de

eveniment @ si structura de stare " sunt structure de date doar daca avem nevoie. !lgoritmul global poatefi descris dupa cum urmeaza.

!lgoritmul Cauta$ntersectii %5&

$ntrare. 5etul 5 de segmente de linie din avion.$esire. 5etul de intersectie intre punctele segmentelor din 5, cu fiecare punct care contine intersectiasegmentelor.

(. $nitializeaza un gol eveniment coada @. !poi, intersectati capetele segmentului in @= atunci candse intersecteaza un punct sfarsit superior, segmentul corespondent ar trebui sa fie depozitat cuacesta.

. $nitializeaza un gol structura de stare ".. while @ nu este gol.. do determina urmatorul punct eveniment p in @ si il sterge*. punctul coada eveniment %p&

!m vazut deja modul in care evenimentele sunt manipulate: la capetele de segmente noi trebuie sainserati sau sa stergeti segmentele din structura de stare ", si la punctele de intersectie putem schimba

ordinea celor doua segmente. $n ambele cazuri, de asemenea- in cazul in care mai multe segmente suntimplicate intr-un singur punct de eveniment-detaliile sunt un pic mai complicate. 'rmatoarea proceduradescrie modul in care sa se punctele de eveniment corect.

Punct de coada eveniment %p&

(. ie '%p& sa fie setul de segmente al caror punct superior este p= aceste segmente sunt stocate cupunctul de eveniment p. %Pentru segmentele orizontale, obiectivul final superior este prin defini iefinal la stnga.&

. Fasiti toate segmentele stocate in " care contin p= ele sunt adiacente in ". ie 1%p& ce denota unsubset de segmente constatate al carui obiectiv final inferior este p, si fie C%p& ce denota un subsetde segmente gasite care contin p in interiorul lor.

. If 1%p&' %p& C %p& contine mai mult de un segment.. Then 0aporteazA p ca o intersectie, BmpreunA cu 1 %p&, ' %p& si C %p&.*. 5tergeti segmentele din 1 %p& C %p& de la ".


7/17

G. $ntroduce i segmentele din ' %p& C %p& Bn ". 6rdinea segmentelor din " ar trebui sAcorespundA cu ordinea Bn care acestea sunt intersectate de o matura line chiar mai jos p.Hn cazul Bn care existA un segment orizontal,ultimul segment il contine pe p.

I. %J tergerea i re-introducerea segmentelor de C %p& inverseazA ordinea lor. J& K. If ' %p& C %p& 8 L

M. Then lasa sl si sr la stanga si la dreapta vecinilor lui p in ".

(). F!5$"$ '; P06$EC" ;6'% s

l ,sr ,p&

((. Else s sA fie segmentul ' din stnga %p& C %p& Bn ".

(. ie sl vecinul din stnga al lui s Bn ".

(. F!5$"$ '; P06$EC" ;6' % sl , s,p&

(. ie s segmentul ' din stnga %p& C %p& Bn ".

(*. ie sr vecinul din dreapta al lui s Bn ".

(G. F!5$"$ ;6$ E/E;$2E;"E %s , sl , p&

0etineti ca in liniile K-(G putem presupune ca sl si sr exista in realitate. $n cazul in

care nu exista masutile corespunzatoare, acesta nu ar trebui , evident ,sa fie efectuat.Procedurile pentru gasirea unor noi intersectii sunt usoare: testeaza pur si simplu doua segmente deintersectie. 5ingurul lucru la care trebuie sa fim atenti este, atunci cand vom gasi o intersectie, dacaaceasta intersectie a fost deja verificata sau nu. !tunci cand nu exista segmente orizontale, intersectiainca nu a fost verificata , atunci cand intersectia nu se afla sub linia de rotire.Dar, cum ar trebui sa se ocupe segmentele orizontale4sa ne amintim ca in convenctia noastraevenimentele de coordinate # sunt tratate de la stanga la dreapta. !sta implica ca suntem inca interesati depunctele de intersectie situate la dreapta punctului eveniment. Prin urmaare, procedura F!5E5"E ;6$

E/E;$2E;"E este definite dupa cum urmeaza.

F!5$"$ '; P06$EC" ;6'% s

l ,sr ,p&

(. if sl si sr se intersecteaza sub linia de rotire, sau pe ea si la dreapta actualul punct de

eveniment p, intersectia nu este inca prezenta ca eveniment in @.. then introduce punctul de intersectie ca un eveniment in @.

Cum ramane cu corectitudinea algoritmului nostrum4 Este clar ca trebuie sa gasim intersectiile careraporteaza doar punctele adevarate de intersectii, doar cum gasim toate acestea4 1ema urmatoare afirmacand este intradevar cazul.

Demonstratie: 5a ne amintim ca prioritatea unu eveniment este data de coordonatele #, si ca atunci candcele doua evenimente au aceleasi coordinate #, mai mici decat coordonata x, se acorda proritatea maimare. /om dovedi lema prin inductia prioritatii punctelor de eveniment.ie p un punct de intersectie si sa presupunem ca toate punctele de intersectie > cu o prioritate mai mareau fost calculate correct. /om dovedi ca p si segmentele care il contin pe p sunt calculate corect.ie '%p& multimea segmentelor care au ca obiectiv punctul p superior%sau, pentru segmenteleorizontale ale acestora, la punct final la stanga&, lasati 1%p& sa fie setul de segmente avand p ca


8/17

punct final inferior%sau, pentru segmentele orizontale, obiectivul lor final fiind dreapta&, si lasatiC%p& multimea segementelor avand p in interiorul lor.$n primul rand, sa presupunem ca p este un punct final al unuia sau mai multor segmente. $nacest caz p este stocat in coada de eveniment @ la inceputul algoritmului. 5egmentele de la 1%p&de la '%p& sunt stocate cu p, astfel incat acestea vor fi gasite. 5egmentele de la 1%p& si C%p& sunt

stocate in " cand p este manipulate, astfel incat acestea vor fi gasite in lina si C%p& sunt stocatein " cand p este manipulate, astfel incat acestea vor fi gasite in linia P';C"'1 DEE/E;$2E;"E C6!D!. !stfel, p si toate segmentele implicate sunt determinate corect cand peste un punct final al unuia sau mai multor segmente.

!cum, presupunem ca p nu este un punct final al unui segment. "ot ceea ce trebuie sa aratameste ca p va fi inserat in @ la un moment dat. 0etineti ca toate segmentele care sunt implicate au

p in interiorul lor. Comandati aceste segmente de unghi in jurul valorii p, si lasati si si sj

sa fie doua segmente invecinate. Ca urmare in lema precedent vedem ca exista un punct de eveniment cu

o prioritate mai mare decat p astfel incat si si sj devin adiacente cand > este trecut. $n lema .(

ne-am asumat pentru simplitate pentru care si si sj sunt non-orizontale, dar este simplu sa se

adapteze dovada pentru segmentele orizontale. Prin inductie, punctul de eveniment > a fost executat inmod corect, ceea ce inseamna ca p este detectat si stocat in @

!sa ca avem un algoritm corect. Dar, am reusit in dezvoltarea unei representative a

algoritmului4 0aspunsul este da: timpul de rulare al algoritmului este 6%%nNO& log n &&, unde O

este marimea de iesire. 'rmatoare lema este un rezultat chiar mai puternic: timpul de rulare este 6%%nN$&log n &, unde $ este numarul de intersectii. !cest lucru este mai puternic, deoarece pentru o intersectie

iesirea poate consta intr-un numar mare de segmente, si anume in cazul in care mai multe segmente se

intersecteaza intr-un punct comun.

1ema . Perioada de functionare a algoritmului de gasire a intersectiilor pentru un set 5 de segmente n in

plan este 6%n log n N$ log n &&, unde $ este numarul de puncte de intersectie ale segmentelor din 5.

Demonstratie: !lgoritmul incepe prin construirea cozi de eveniment pe segmentul obiectiv. Pentru ca am

implementat coada de eveniment ca un arbore binar echilibrat, acesta ia 6%n log n & timp. $nitializeaza

structura de stare in constanta de timp. !poi coada avionului incepe si toate evenimentele suntmanipulate. 1a maner un eveniment poate efectua trei operatii pe coada de eveniment @: evenimentul insine se elimina de la @ in linia de $;"E05EC"$$ F!5$"E, si nu poate fi una sau doua apeluri laF!5$"$ E/E;$2E;" ;6', ceea ce poate provoca cel mult doua noi evenimente in @. 5tergetii si

inserati de la @ in 6% logn

& timp pentru fiecare. ;oi de asemenea, efectuam operatiuni de inserare,stergere si de gasirea unui vecin din structura ", care ia 6% logn & timp pentru fiecare. ;umarul de

operatii este liniar in numarul m%p&:8 cartela%1 %p& ' %p& C %p&& din segmentele care sunt implicate ineveniment. Daca notam suma tuturor m%p&, in toate punctele de eveniment p, prin m, timpul de rulare al

algoritmului este 6%m log n &.

Este clar ca m86%nNO&, unde O este marimea de iesire= dupa toate acestea, ori de cate ori m%p&(raportam toate segmentele implicate in eveniment, iar singurul eveniment care implica un segment sunt


9/17

punctele finale ale segmentelor. Dar vrem sa dovedim ca m86%nN$&, unde $ este numarul de puncte deintersectie. 1a acest lucru, vom interpreta un set de segmente ca un graf planar incorporate in avion. %dacanu sunteti familiarizati cu tehnologia grafica in plan, trebuie sa cititi primele paragrafe din dectiunea .mai inati&. ;odurile sale sunt capetele segmentelor si punctele de intersectie ale segmentelor, iar muchiilesale sunt piesele de segmente la care se conecteaza nodurile. 5a consideram un punct de eveniment p. esteun varf de pe grafis si m%p& este delimitat de gaful nodului. Prin urmare, m este delimitat de suma

gradelor tuturor nodurilor din graficul nostru. iecare margine a grafului contribuie la gradul de exactdoua noduri %punctele finale ale acestuia&, asa ca m este marginita de ne , unde ne este numarul de

muchii ale grafului. ai sa ne legam de termeni n si $. Prin definitie, nv , numarul de noduri, este de

cele mai multe ori nN$. Este bine cunoscut faptul ca in graficele plane ne 86% nv &, ceea ce

demonstreaza cererea noastra. Dar, pentru completare, sa ne dea argumentul aici. iecare fata a graficuluieste delimitate de ce putn trei mucii, cu conditia sa existe cel putin trei segmente si o margine poate legata

de cel mult doua fete diferite. Prin urmare n f , numarul de fete ,este ne Q. ;oi folosim acum

formula lui Euler, care prevede ca pentru orice graphic planar cu nv noduri, muchiile ne se

confrunta , in n f urmatoarea relatie detine : nv - ne N n f .

!re loc egalitatea daca si numai daca graficul este conectat. !stuparea limitelor privind nc si

n f in aceasta formula, obtinem : %nN$&- ne N ne Q8%nN$&- ne Q.

Deci ne GnN$-G, si mR (nNG$-(, si leaga timpul de executare urmator.

;oi inca mai trebuie sa analizam celalalt aspect de complexitate, cantitatea de stocare utilizata dealgoritm. 2arginile arborelui " este un segment de cel mult o data, asa ca foloseste 6%n& de depozitare.

2arimea @ poate fi mai mare, cu toate acestea. $nsertiile algoritmului intersectie sunt subliniate in @atunci cand sunt detectate si eliminate atunci cand acestea sunt manipulate. !tunci cand este nevoie de olunga perioada de timp intersectiile sunt tratate inainte, s-ar putea intampla ca @ sa devina foarte mare.Sineinteles ca dimensiunea sa este intotdeauna delimitate de 6%nN$&, dar ar fi mai bine daca datele delucru sunt intotdeauna liniare. Exista o modalitate relative simpla de a realize acest lucru: doar punctele magazin de intersec ie aleperechilor de segment sunt Bn prezent adiacente pe linia de rotire . !lgoritmul dat mai sus, de asemenea,stocheaza punctele de intersectie ale segmentelor care au fost orizontal adiacente, dar nu mai sunt.;umai in stocarea de intersectii intre segmentea adiacente, numarul de puncte de eveniment in @ este maimult liniar. 2odificarea necesara in algoritm este ca puctul de intersectie dintre doua segmente trebuie safie sters atunci cand nu mai sunt adiacente. !ceste segmente trebuie sa devina adiacente din nou, inaintede a se ajunge la punctul de intersectie, astfel incat punctul de intersectie va fi in continuare raportat

corect. "impul total luat de algoritm ramane 6%n log n+ $ log n &. 6btinem urmatoarea teorema:

Teorema 2.4. ie 5 un set de segmente n linie in plan. "oate punctele de intersectie din 5, cu fiecare

intersectie a segmentelor punct intersectie in aceasta, pot fi raportate in 6 %n log n+ $ log n & timp

si 6%n& spatiu, unde este numarul de puncte de intersectie.


10/17

2.2 Lista de doua puncte dublu conectate pe muchie

!m rezolvat cel mai simplu caz al hartei de suprapunere, in cazul in care cele doua harti sunt retelereprezentate ca colectii de segmente. $n generat, hartile au o structura mai complicate: ele suntsuubdiviziuni ale planului in regiuni etichetate. 6 harta tematica a padurilor din Canada, de exemplu, ar fi

o subdiviziune a Canadei in regiunile cu etichete, cum ar fi +pin+, foioase+, mesteacan+ si mixt+.$nainte de a putea da un algoritm de calcul prin suprapunerea a doua subdiviziuni, trebuie sa dez voltam oreprezentare adecvata pentru o subdiviziune. 5tocarea unei subdiviziuni ca o stocare de segmente de linienu este o idee buna. 6peratiuni cum ar fi raportarea la limita a unei regiuni ar fi destul de complicata. Estemai bines a include, informatii structurate topologic: ce segmente lega o anumita regiune, care regiuneeste adiacenta, si asa mai departe.

artile pe care le consideram subdiviziuni plane induse de incorporarea graficelor plane. 6 astfel desubdiviziune este conectata in cazul in care graficul de baza este conectat. $ncastrarea unui nod algraficului este numit nod, iar incastrarea unui arc se numeste margine. ;oi consideram doar incorporarein cazul in care fiecare muchie este degment de linie dreapta. $n principiu, marginile intr-o subdiviziunenu trebuie sa fie drepte.

6 subdiviziune nu trebuie sa fie chiar o incastrare plana a unui graphic, deoarece pot avea margininemarginite. $n aceasta sectiune, cu toate acestea, noi nu consideram o subdiviziune mai generala. ;oiconsidera ca o margine sa fie deschisa, adica, obiectivele sale sunt nodurile din care nu fac parte dinsubdiviziune. 6 fata a subdiviziunii este un subset maximal conectat cu planul, care nu contine un punctsituate pe o margine sau nod. !stfel, o fata este o regiune poligonala deschisa a carei limita este formatadin margini si varfuri din subdiviziune. Complexitatea subdiviziunii este de fapt ca suma numarului denoduri. $n cazul in care un varf este un obiectivul unei margini, atunci spunem ca varful si marginea suntincidente. $n mod similar, o fata si o margine de pe linia ei sunt incidente, si o fata a nui varf alfrontierelor sale sunt incidente. Ce ar trebui sa cerem de la o reprezentare a unei subdiviziuni4 6 operaties-ar putea cere pentru a determina o suprafata care contine un anumit punct. !cesta este cu siguranta utilin unele aplocatii, intr-adevar, intr-un capitol urmattor avem proiectarea unei structure de date pentruacesta, dar este putin cam mult pentru a cere o reprezentare de la o baza. 1ucrurile pe care le putem cere

ar trebuii sa fie mai locale. De exemplu, este rezonabil sa impunem ca putem merge in jurul valorii limitaa unui anumit chip, sau ca am putea avea acces la o singura fata dintr-o alta invecinata, dca ni se da ocomuna margine. 6 alta operatiune care ar putea fi utila este de a vizita marginile din jurul unui varf dat.0eprezentarea pe care o vom discuta sustine aceste operatiuni. 5e numeste lista de margine dublu-conectat.

6 listA de margine dublu-conectat con ine o Bnregistrare pentru fiecare fa A, margine, i vrfurile subdiviziunii. Pe langa geometricA i topologicA informa iile sunt descries Bn scurt timp, fiecare Bnregistrare poate stoca, de asemenea, informa ii suplimentare. De exemplu, Bn cazul Bn care osubdiviziune reprezintA o hartA tematicA pentru vegeta ie, 1ista dublu conectata de margine s-ar stoca Bnfiecare Bnregistrare a tipul de vegeta ie si a regiunii corespunzAtoare. $nforma iile de suplimentare sunt, de asemenea, numite atribut de informa ie. $nforma iile geometrice i topologice stocate Bn 1ista dublu

inlantuita de margine ar trebui sA ne permitA sA efectueze opera iile de bazA men ionate mai devreme. Pentru a putea sA se plimbe Bn jurul fe ei, Bn ordine invers acelor de ceasornic vom pAstra un pointer de lafiecare margine la alta. Ea poate veni, de asemenea, la BndemnA sA se plimbe Bn jurul valorii de a oconfruntA cu un alt mod, asa ca am stocat, de asemenea, un pointer la marginea anterioarA. 6 margine deobicei, are douA fe e mArgine te, deci avem nevoie de douA perechi de indicii pentru ea. Este convenabil pentru a vizualiza diferitele pAr i ale unei muchii ca douA jumAtA i de margini distincte, astfel Bnct sA avem un unic urmAtor de jumAtate de orA i jumAtate anterior de vrf pentru fiecare jumAtate de margine.Acesta de asemenea inseamna ca are un hotar jumatate de margined oar o singurafata. Cele doua jumatati de margini pe care le primim de la marginea data sunt


11/17

numite gemeni. Denind urmatoarea jumatate de margine a unei anumite jumatatide margine in ceea ce priveste o traversare inversa a acelor de ceasornic a uneifete induce o orientare asupra ecarei jumatati de margine: ea este orientate astfelincat fata pe care o margineste sta la stanga ei pentru un observator de mers pejos de-a lungul marginii. Pentru ca jumatatile de margine sunt orientate putem savorbim despre originea si destinatia jumatatii de margine. n ca!ul in care o

jumatate de margine e are v ca origine si " ca destinatie# apoi are dublu t"in$

e % cu " ca punct de origine si v ca destinatie. Pentru a ajunge la limita unei fete

avem nevoie doar sa stocam un singur indicator in inregistrarea fata de un arbitrarpe o jumatate de margine care delimitea!a fata. Pornind de la acea jumatate demargine# putem pas cu pas sa ajungem de la o jumatate de margine la alta si injurul valorii ei. Ceea ce am spus pur i simplu nu de ine destule limite de gAuri Bntr-un chip: Bn cazul Bn care acestea sunt traversate Bn ordine inversa a acelor de ceasornic, apoi fa a se aflA la dreapta. !ceastava fi convenabil sA se orienteze jumAtate din margini, astfel Bnct fa a lor sa se aflA Bntotdeauna la aceea i distant , astfel Bnct sA schimbAm direc ia traversala pentru limita unei gAuri pentru sensul acelor deceasornic. !cum o fa A se aflA Bntotdeauna la stnga oricArei jumAtati de margine de pe marginea sa.

6 altA consecin A este cA jumAtatile marginilor gemene au Bntotdeauna orientAri opuse.Prezen a gAurilor Bntr-un chip BnseamnA, de asemenea, cA un singur indicator de pe fataarbitrarA a jumAtatii de margine de pe marginea sa nu este suficienta pentru a vizita intreaga limita:avem nevoie de un pointer la o jumAtate de orA Bn fiecare componentA de delimitare. Hn cazul Bn care o fa Aare vrfuri izolate aceasta nu are nici o margine de incident, deci putem stoca indicii pentru a ledeasemenea. Pentru simplificare, vom ignora acest caz.

aideTi sA rezumam. 1ista marginii dublu conectate constA in trei colectii de inregistrari:unul pentru nodurile, unul pentru feTe Ui unul pentru marginile jumAtati.!ceste BnregistrAri pAstreazA elementele geometrice si topologice prin urmAtoarele:

0ecord de noduri de un nod v inmagazineaza coordonatele lui v Bntr-un domeniu numit

Coordinate%v&. 5e stocheazA, de asemenea, un indicator $ncident Edge%v& spre o arbitrarejumAtate-marginea a carui v este originea sa. 0ecord de fata de la o fata f stocheazA un pointer 6uterComponent %f& la o

jumAtate-margine spre limita sa exterioarA. Pentru fata nemArginitA acest indicator este nul.5e stocheazA, de asemenea, o listA de componente interioarA %f&, care conTine, pentru fiecare gaura infata un pointer la o jumAtate-margine pe marginea gAurii.

0ecordul jumatate de margine a unei jumatati de varf e stocheaza un pointer de origine%

e & la originea sa, un pointer tVin% e & dublu cu jumatate de margine, si un pointer

$ncidentace% e & fata de limita sa. ;oi nu avem nevoie de destinatia unei margini pentru a

stoca, deoarece este egala cu originea% "Vin% e

&&. 6riginea este aleasa astfel incat$ndiceleace% e & se afla in stanga4 Este atunci cand este traversat de originea destinatiei.

0ecordul jumatate de margine stocheaza, de asemenea, indicia urmatori % e & si Prec% e & la

marginea urmatoare si anterioara cu privire la limita $ndiceace% e &. Prin urmare in continuare

% e & este unica pe jumatatea de margine a granite $ndiceace% e & care are destinatia e ca


12/17

originea sa, si precedeul % e & este unic pe jumatate de margine de pe limita de $ncidentace%

e & care isi are originea % e & ca destinatie.

6 cantitate constantA de informa ii se utilizeazA pentru fiecare nod i margine. 6 fa A poate

necesita mai multe date de stocare, deoarece $nnerComponents din lista %f& au ct mai multe elementedeoarece existA gAuri Bn fa A. Pentru cA pentru orice jumAtate de margine este indicat cel mult o datAdin toate $nnerComponents %f&cu liste BmpreunA, am ajuns la concluzia cA valoarea de stocare este liniarABn complexitatea subdiviziunii. 'n exemplu de lista de margine dublu conectata pentru o subdiviziunesimplA este prezentatA mai jos. Cele douA jumAtA i de margini corespunznd unei margini sunt etichetatee i ,1 sie i ,2 .

&arf Coordonate 'uchia incidenta

v1 $(#)%

e1,1

v2 $*#)%e4,2

v3 $*#*%

e2,1

v 4 $+#+%

e2,2

Faa Componente exterioar Componente interioare

f1 zeroe1,1

f*e4,1 !ero

,umatate de muchie rigine dublu$t"in% ata de indice /rmatorulAnteriorule1,1 v+

e1,2 f+

e 4,2 e3,1

e1,2 v*e

1,1 f*

e3,2

e 4,1

e2,1 v0e2,2 f+

e2,2 e 4,2

e2,2 v)e2,1 f+

e3,1 e2,2


13/17

e3,1 v0e

3,2 f+

e1,1 e2,2

e3,2 v+e

3,1 f*

e 4,1 e1,2

e4,1 v0e4,2 f*

e1,2 e3,2

e4,2 v*e4,1 f+

e2,1 e1,1

$nformatia stocata in lista de margine dublu-conectat este suficienta pentru a efectua operaatiile de baza.De exemplu, putem merge in jurul limitei exterioare unui anumit chip f urmand urmatoarele indicii,pornind de la o jumatate de margine Componenta exterioara%f&. De asemenea,putem vizita toate marginileincidente la un varf v. Este un exercitiu bun pentru a ne da seama cum sa facem acest lucru.

!m descries o versiune destul de generala a liste de margine dublu-conectate. $n aplicatiile in carenodurile nu transporta informatii atribut am putea stoca coordonatele lor direct in campul de origine%& almarginii= nu e nevoie stricta pentru un tip separate de inregistrare la varf. Chiar si mai important este sarealizam ca in multe aplicatii fetele subdiviziunii nu purta nici un sens interesant %Cred ca a retelei derauri sau drumuri pe care ne-am mai uitat inainte&. $n cazul in care ne putem uita complet peinregistrarile fetei, $ndicele din fata%& este camp de jumatati de margini. Dupa cum vom vedea, algoritmulsectiunii urmatoare nu are nevoie de aceste campuri%si este de fapt mai simplu de a pune in aplicare acest

caz in care nu avem nevoie sa se actualizeze&. 'nele implementari e liste de margini dublu-conectate pot,de asemenea insista asupra faptului ca graficul de varfuri si muchiile subdiviziunii sa die conectate. !cestlucru poate fi intotdeauna realizat prin introducerea marginilor false si are doua avantaje. $n primul rand,un grafic simplu transversal poate fi folosit pentru a vizita toate jumatatile de margini, iar pe de alta parte,la Componentele $nterioare%& lista de fete nu este necesara.

2.3 Calcul Suprapunere a doua subdii!iuni

!cum ca ne-am proiectat o buna reprezentare a unei subdiviziuni, putem aborda problema generalaa harti supapunere. /om defini suprapunerea a doua subdiviziuni 5( si 5 sa fie compartimentate6%5(,5&, astfel iincat sa existe o fata f in 6%5(,5& daca si numai daca exista fete f( in 5( si 5 in

astfeO incat f este maxim un subgroup conectat de f(

f. !cest lucru suna mai complicatdecat este: ce inseamna ca suprapunerea este subdiviziune a planului indus de marginile de la 5( si5. igura de mai jos ilustreaza acest lucru. Problema generala este harta de suprapunere carecalculeaza o lista de margine dublu-conectata pentru 6%5(,5&, avand in vedere listele de marginedublu-conectate 5( si 5. 5olicitam ca fiecare fata in 6%5(,5& sa fie etichetate cu etichetele fetelordin 5( si 5 pe care le contin. !stfel, au acces la informatiile despre attribute stocate pentru acestefete. $ntr-o suprapunere a unei harti de vegetatie si o harta de precipitare, acestea ar insemna ca noistim pentru fiecare regiune in suprapunere tipul de vegetatie si cantitatea de precipitatii.


14/17

5a vedem mai intai cat mai multe informatii din listele de margini dublu-conectate pentru 5( si 5,ce putem re-utiliza in lista de margine dublu-conectata pentru 6%5(,5&. 1uati in considerare reteau

de muchii si varfuri ale lui 5(. !ceasta retea este taiata in bucati de marginele lui 5. !ceste piesesunt pentru o mare parte re-utilizabile= numai marginile care au fost taiate de marginile lui 5( artrebui sa fie reinnoite. Dar oare acest lucru detine, de asemenea pentru inregistrarile de jumatate demargine in lista de margine dublu-conectate,care corespund pieselor4 $n cazul in care orientareajumatatilor de margine s-ar schimba, am fi in continuare nevoiti sa schimbam informatiile cuprinse inaceste inregistrari. Din fericire, acest lucru nu este cazul. Wumatatile de margine sunt orientate astfelincat fatele care au legat falsuri la stanga= forma fetei se poate schimba in suprapunere,dar va ramanepe aceasi parte a jumatatii de margine. Prin urmare, putem re-utiliza inregistrarile jumatatilor demargine corespunzatoare marginii care nu sunt intersectate de marginile din cealalta harta. !stfelspus, inregistreaza doar o jumatate de margine in lista de margine dublu-conectata pentru 6%5(,5& pecare nu le putem imprumuta de la 5( sau 5 sunt cele care sunt incidente intr-o intersectie intremarginile din diferitele harti.

!cest lucru sugereaza urmatoarea abordare. $n primul rand, copiati listele de margine dublu-conectate ale lui 5( si 5 intr-o noua lista de margine dublu-conectata. ;oua lista de margine dublu-conectata nu este o lista de margine dublu-conectata valida, desigur, in sensul ca aceasta nu reprezintainca o subdiviziune plana. !ceasta este sarcina algoritmului de suprapunere: acesta trebuie satransforme lista de margine dublu-conectat in o lista valida de margine dublu-conectata pentru6% 5(,5&, prin calculul intersectiei intre cele doua retele de margini, si care leaga impreuna partileadecvate din cele doua liste de margine dublu-conectate.;-am discutat despre noile recorduri inca. $nformatiile pentru acestea inregistrari sunt mai dificil decalculat, asa ca vom lasa asta pentru mai tarziu. ;oi descriem mai intai intr-un mod mai indetaliat incare sunt calculate inregistratile nodurilor si jumatatilor de margini ale listei d margine coectate dedoua ori pentru 6%5(,5&.

!lgoritmul nostru se bazeaza pe algoritmul planului de rotatie de la sectiunea .( pentru calculareaintersectiilor dintr-un set de segmente. 0ularea acestui algoritm se face pe seturi de segmente caresunt unirea dintre seturile de margini ale celor doua subdiviziuni 5( si 5. !ici consideram marginilecare urmeaza sa fie inchise. 5a ne amintim ca algoritmul este sustinuit de doua structuri de date: un @coada eveniment, care stocheaza evenimentul in puncte, iar structura de stare ", care este un binar# decautare care stocheaza arborele care echilibreaza segmentele ce se intersecteaza cu liniile de rotire,comandat de la stanga la dreapta. ;oi acum mentinem,de asemenea, o lista de margine dublu-conectate D. $nitial, D contine o copie din lista de margine dublu-conectata pentru 5( si o copie dinlista de margine pentru 5. $n timpul algoritmului matura, vom transforma D la o corecta lista de


15/17

margine dublu conectata pentru 6%5(,5&. Cu alte cuvinte, in ceea ce priveste varful si inregistrarilepe jumatate de margine sunt in cauza= informatia nominal va fi calculate mai tarziu. ;oi pastramindicia incrucisati intre marginile din structura de stare " si inregistratile de jumatate de margine in Dcare le corespund. $n acest fel putem accesa o parte din D, care trebuie sa fie schimbat, atunci candne intalnim cu un punct de intersectie. $nvariantul in care ne mentine faptul ca, in orice moment peparcursul algoritmului matura, partea de suprapunere de deasupra liniei de rotire a fost calculata

corect.!cum, se ia in considerare ceea ce trebuie sa facem cand ajungem la un punct de eveniment. Prima

data am actualizat " si @ ca in algoritmul de intersectie de segment de linie. $n cazul in careevenimentul implica margini doar la una dintre cele doua subdiviziuni, acesta este tot= Evenimentulpunct este un nod care poate sa faca modificari locale la D pentru a lega lista de margi dubluconectate ale celor doua subdiviziuni orginale la punctul de intersectie. !sta e obositor, dar nu estedificil.

situa ia geometricA, a lista margine dublu conectata douA liste de margine dublu-conectate dupa intersectia de manipulare

Bnainte de a manipula intersec ia

;oi descriem detaliile pentru una dintre posibilele cazuri, si anume atunci cand o margine e de la5( trece printr-un varf v din 5, a se vedea mai sus. 2uchia e trebuie sa fie inlocuita cu douamargini notate e i e . $n lista de margine dublu-conectata, doua jumatati de margini pentru e trebuie sa devina patru. ;oi cream doua noi recorduri de jumatate de margine, cu v ca origine.Cele doua existente jumatati de margini pentru e mentin capetele e ca si originea lor, asa cum searata in fig. .*. !poi vom asocial pana la jumatate de marginile existente cu noile jumatati demargini prin setarea unor indici tVin%&. !sa ca e este reperzentat de unul nou si unul existent pejumatate de margine, iar acelasi lucru este valabil pentru e . !cum noi trebuie sa stabilim unnumar de Prec%& si ;ext%& indicii. ;oi mai intai pentru a face fata situatiei in jurul valorii decapetele e= mai tarziu ne vom face griji cu privire la situatie din jurul lui v. ;ext%& cursoarelecelor doua noi jumatati de margini cu exemplarul urmator%& pointerul vechi de jumatate demargine, care nu este geamanul sau. Wumatatile de margini la care indicii indica ca trebuie sa seactualizeze, de asemenea, indicatorul Prec%& setat la noi jumatati de margini. Corectitudineaacestui pas poatte fi verificata cel mai bine prin ultima cifra. 0amane de corectat situatia in jurul valorii varfului v. trebuie sa setati ;ext%& si Perv%&indicii la cele patru margini reprezentand e1i e , si cele patru jumatati de muchii incidente dela 5 la v. !m localiza aceste patru semi-muchii din 5 , unde e1i e ar trebui sa fie in ordine


16/17

ciclica a marginilor in jurul nodurilor v. Exista patru perechi de jumatati de muchii care devinlegate printr-un urmator%& pointer din unul si un indicator Proc%& de cealalta. 1uati in considerareo jumatate de margine pentru e care are v ca destinatie. !cesta trebuie sa fie legat de primajumatate de margine, vazut in sensul acelor de ceasornic de la e, cu v ca originea sa. Wumatate-margine pentru e cu v ca originea sa trebuie sa fie legata de prima jumatate, invers acelor de ceasornic-

argine cu v ca destinatie. !celeasi afirmatii sunt si pentru e . Cele mai multe dintre pasii din descrierea de mai sus necesita timp numai constant. ;umaiunde e1i e apar in ordinea ciclica in jurul valorii lui v poate dura mai mult: va fi nevoie detimp liniar de gradul v. Celelalte cazuri care pot fi punctele de trecere a doua margini dindiferitele harti, si care coincid nu au nodurile mai dificile decat in cazul tomcai discutat. !cestecazuri, de asemenea, iau timp 6%m&, unde m este numarul de muchii incidente la punctulevenimentului. !cesta inseamna ca actualizarea D nu creste timpul de functionare al intersectieisegmentului liniei algoritmului as#mptotic. 6bservati ca fiecare intersectie pe care o gasim areeste nod de suprapunere. 0ezulta ca inregistrarile nodurilor si inregistrarile pe jumatate demargine ale listei de margine dublu-conectate pentru 6%5(,5& poate fi calculate in 6%n log n+klogn & timp, in cazul in care n reprezinta suma complexitatii 5( si 5, iar O este

complexitatea suprapunerii. Dupa ce campurile implica jumatati de margine recordurile sunt stabilite, ramane de calculateinformatiile despre fetele 6%5(,5&. 2ai precis, trebuie sa creeze un record de fata pentru fiecarefata f in 6%5(,5&, trebuie sa facem Compomentul de iesire%f& indica o jumatate de margine de pelimita exterioara f, si noi trebuie sa facem o lista de componente interne%f& indicii jumatatilor demargine pe limitele gaurilor inferioare f. 2ai mult decat atat, trebuie sa setati $ndicele din fata%&campuri din jumatate de margini la limita lui f, astfel incat ele indica inregistrarea fetei lui f. $ncele din urma, fiecare dintre fetele noi trebuie sa fie etichetate cu numele fetelor din vechiilesubdiviziuni pe care le contin. Cat de multe inregistrari cu care ne confruntam vor fi acolo4 Ei bine, cu exceptia feteinemarginite, fiecare chip are o limita exterioara unica, astfel incat numarul de inregistrari de fata

este egal cu numarul limitelor exterioare plus unu. Din partea listei de margine dublu-conectatconstruite putem extrage cu usurinta toate ciclurile limita. Dar cum stim daca un ciclu este olimita exterioara sau limita unei gauri intr-o fata4 !cest lucru poate fi decis de catre un varf v dinextremitatea stanga a ciclului, sau, in cazul unor legaturi, la cea mai mica dintre extreme. 5a neamintim ca jumatate din margini sunt orientate in asa fel incat fata lor incidenta sa se afle la nivellocal spre stanga. 1uati in considerare cele doua jumatati de margini ale ciclului, care suntincidente la v. Pentru ca noi stim ca fata incidentului se afla la stanga, putem calcula unghiulacestor doua jumatati de muchii in interiorul fetei incidente. $n cazul in care acest unghi este maimic decat +2(3atunci ciclul este o limita exterioara, si in caz contrar este limita unei gauri.!ceasta proprietate este valabila si pentru varful unui ciclu la stanga, dar nu neaparat pentru altenoduri ale acestui ciclu.

Pentru a decide care ciclu de frontier leaga aceasi fata vom construe graficul F. Pentru fiecareciclu de delimitare-interior si exterior exista un nod in F. Exista, de asemenea, un nod pentrulimita exterioara imaginara a fetei nemarginita. Exista un arc intre cele doua cicluri, daca sinumai daca unul dintre cicluri este aceea delimitate a unei gauri, iar celalalt ciclu are o jumatatede margine imediat la stanga din stanga varfului acelui ciclu gaura. $n cazul in care nu exista nicojumatate de margine in partea stanga la cel mai din stanga nod al ciclului, atunci modul carereprezinta ciclul este legat de grupa nodului nemarginit. Ciclurile hole sunt prezentate ca cercurisingular, iar ciclurile de delimitare exterioare sunt reprezentate ca dublu cercuri. 5e observa ca


17/17

C si CG sunt cicluri dde gauri in suprafata exterioara a carei delimitare este C. $n cazul in careexista doar o singura gaura intr-o fata f, atunci graficul F leaga granita ciclului la limitaexterioara f. $n general, acest lucru nu trebuie sa fie : o gaura poate fi, de asemenea, legat de oalta gaura, dupa cum se poate vedea in fig. .G. !ceasta gaura, care se afla in aceasi figura f,poate fi legata de limita exterioara f, sau poate fi legata de o alta gaura. Dar, in cele din urma

trebuie sa se incheie la conectarea unei gauri de la limita exterioara, asa cum lema urmatoarearata.1ema: .* iecare component conectata la graficul F corespunde exact setului de cicluri deincidente ai unei singure fete.Demonstratie: 5a consideram un ciclu C, delimitand o gaura intr-un chip f. Pentru ca f se afla lanivel local spre stanga varfului C, C trebuie sa fie conectat la un alt ciclu care margineste si f.0ezulta de aici ca, in cicluri de aceasi component conexa a lui F este legata aceasi fata.

Pentru a termina demonstratia, ne arata ca fiecare ciclu care delimiteaza o gaura in f este inaceeasi component conectata ca in limita exterioara f. 5a presupunem ca exista un ciclu pentru care acestlucru nu este cazul. ie C astfel un ciclu de extrema stanga, si anume, unul

Carte Tradusa

Documents

Transcript of Carte Tradusa