35 Geometrie computaţională

Geometria computaţională este ramura ştiinţei informaticii care studiază algoritmi pentrurezolvarea problemelor geometrice. Geometria computaţională are aplicaţii în ingineria moder-nă, în matematică şi în alte domenii cum ar fi grafica pe calculator, robotica, proiectarea VLSI,proiectarea asistată de calculator şi statistica. Datele de intrare, pentru o problemă de geometriecomputaţională, sunt, de obicei, o descriere a unei mulţimi de obiecte geometrice, ca o mulţime depuncte, o mulţime de segmente de dreaptă sau o mulţime de vârfuri ale unui poligon, ordonateîn sens trigonometric. Ieşirea este, adesea, un răspuns la o întrebare despre obiecte, cum arfi intersectarea unor drepte sau un nou obiect geometric, de exemplu, învelitoarea convexă amulţimii de puncte (cel mai mic poligon convex care le include).

În acest capitol, urmărim câţiva algoritmi de geometrie computaţională în două dimen-siuni, adică în plan. Fiecare obiect de intrare este reprezentat ca o mulţime de puncte pi,unde pi = (xi, yi) şi xi, yi ∈ R. De exemplu, un poligon P cu n vârfuri este reprezentat prinsecvenţa 〈p0, p1, p2, ..., pn−1〉 a vârfurilor sale în ordinea apariţiei lor în P . De asemenea, geometriacomputaţională se poate face în trei dimensiuni şi chiar în spaţii dimensionale mai mari, dar astfelde probleme şi soluţiile lor pot fi vizualizate foarte greu. Chiar şi în două dimensiuni, putem vedeaexemple bune de tehnici de geometrie computaţională.

În secţiunea 35.1 prezentăm răspunsuri corecte şi eficiente la întrebări simple despre segmentede dreaptă: dacă un segment este în sensul acelor de ceasornic sau în sens trigonometric faţăde un alt segment cu care are un capăt comun, în ce mod ne întoarcem când parcurgem douăsegmente de dreaptă adiacente, dacă două segmente de dreaptă se intersectează. În secţiunea 35.2se prezintă o tehnică numită “baleiere” pe care o vom folosi pentru a dezvolta un algoritm de timpO(n lgn) care determină dacă există intersecţii pentru o mulţime de n segmente de dreaptă. Însecţiunea 35.3 se prezintă doi algoritmi de “baleiaj rotaţional” care calculează învelitoarea convexăpentru o mulţime de n puncte (cel mai mic poligon convex care le include): scanarea lui Graham,care se execută în timpul O(n lgn), şi potrivirea lui Jarvis, care are timpul de execuţie O(nh),unde h este numărul de vârfuri ale învelitorii convexe. În final, în secţiunea 35.4 se prezintă unalgoritm divide şi stăpâneşte de timp O(n lgn) pentru determinarea celei mai apropiate perechide puncte dintr-o mulţime de n puncte din plan.

35.1. Proprietăţile segmentului de dreaptă

În acest capitol, majoritatea algoritmilor de geometrie computaţională vor cere răspunsurila întrebări despre proprietăţile segmentelor de dreaptă. O combinare convexă a două punctedistincte p1 = (x1, y1) şi p2 = (x2, y2) este un punct p3 = (x3, y3), astfel încât pentru un αoarecare, în intervalul 0 ≤ α ≤ 1, avem x3 = αx1 + (1 − α)x2 şi y3 = αy1 + (1 − α)y2. Deasemenea, vom scrie că p3 = αp1 +(1−α)p2. Intuitiv, p3 este pe dreapta care trece prin punctelep1 şi p2 şi este în afară sau între p1 şi p2 pe această dreaptă. Pentru două puncte p1 şi p2 date,segmentul de dreaptă p1p2 este mulţimea combinărilor convexe ale lui p1 şi p2. Numim p1 şip2 capetele segmentului p1p2. Câteodată, contează ordinea punctelor p1 şi p2, atunci vorbimdespre segment orientat

−→p1p2. Dacă p1 este originea (0, 0), atunci putem trata segmentul

760 Capitolul 35 Geometrie computaţională

orientat−→p1p2 ca fiind vectorul p2.

În această secţiune, vom căuta răspunsuri la următoarele întrebări:

1. Dându-se două segmente orientate−→p0p1 şi

−→p0p2 ţinând seama de capătul lor comun p0 este−→

p0p1 în sensul acelor de ceasornic de la−→p0p2?

2. Fiind date două segmente de dreaptă p1p2 şi p2p3, dacă parcurgem p1p2 şi apoi p2p3, facemo întoarcere la stânga în punctul p2?

3. Se intersectează segmentele de dreaptă p1p2 şi p3p4?

Nu există restricţii pentru punctele date.Putem răspunde la fiecare întrebare în timpul O(1), ceea ce ar trebui să nu ne surprindă

deoarece dimensiunea datelor de intrare, pentru fiecare întrebare, este O(1). Mai mult, metodelenoastre folosesc doar adunări, scăderi, înmulţiri şi comparaţii. Nu avem nevoie nici de împărţiri,nici de funcţii trigonometrice, amândouă pot necesita calcule costisitoare şi sunt predispuseproblemelor generate de erori de rotunjire. De exemplu, o metodă “simplă” pentru a determinadacă două segmente se intersecteză – calculăm ecuaţia dreptei în forma y = mx + b pentrufiecare segment (m este panta şi b este intersecţia dreptei cu Oy), găsim punctul de intersecţieal celor două drepte şi verificăm dacă el aparţine ambelor segmente – folosim împărţirea pentrua determina punctul de intersecţie. Când segmentele sunt aproape paralele, această metodăeste foarte sensibilă la precizia operaţiei de împărţire pe un calculator real. În această secţiune,metoda care evită operaţia de împărţire este mult mai exactă.

Produse încrucişateCalcularea produsului încrucişat este esenţa metodelor noastre. Considerăm vectorii p1 şi

p2, prezentaţi în figura 35.1(a). Produsul încrucişat p1 × p2 poate fi interpretat ca fiind ariacu semn a paralelogramului format din punctele (0, 0), p1, p2 şi p1 + p2 = (x1 + x2, y1 + y2). Odefiniţie echivalentă, dar mult mai utilă, pentru produsul încrucişat este dată de determinantulmatricei:1

p1 × p2 = det(x1 x2

y1 y2

)= x1y2 − x2y1 = −p2 × p1.

Dacă p1 × p2 este pozitiv, atunci p1 este în sensul acelor de ceasornic faţă de p2 ţinând cont deoriginea (0, 0); dacă acest produs încrucişat este negativ, atunci p1 este în sens trigonometric faţăde p2. În figura 35.1(b) se prezintă regiunile relative la vectorul p, în sensul acelor de ceasornicşi în sensul trigonometric. Condiţia limită apare dacă produsul încrucişat este zero; în acest caz,vectorii sunt coliniari , orientaţi în aceeaşi direcţie sau în direcţii opuse.

Pentru a determina dacă un segment orientat−→p0p1 este în sensul acelor de ceasornic faţă de

segmentul orientat−→p0p2 în raport cu punctul lor comun p0, facem o simplă translaţie cu scopul

de a folosi p0 ca origine. Adică, notăm cu p1 − p0 vectorul p′1 = (x′1, y′1), unde x′1 = x1 − x0 şi

y′1 = y1 − y0. Definim în mod analog p2 − p0. Calculăm apoi produsul încrucişat

(p1 − p0)× (p2 − p0) = (x1 − x0)(y2 − y0)− (x2 − x0)(y1 − y0).1De fapt, produsul încrucişat este un concept tri-dimensional. Este un vector perpendicular pe p1 şi pe p2,

conform “regulii mâinii drepte”, şi al cărui modul este |x1y2 − x2y1|. În acest capitol. se va dovedi convenabilătratarea produsului încrucişat ca simpla valoare x1y2 − x2y1.

35.1. Proprietăţile segmentului de dreaptă 761

Figura 35.1 (a) Produsul încrucişat al vectorilor p1 şi p2 este aria cu semn a paralelogramului. (b)Regiunea albă conţine vectorii care sunt în sensul acelor de ceasornic faţă de p. Regiunea haşuratăconţine vectorii care sunt în sens trigonometric faţă de p.

Dacă acest produs încrucişat este pozitiv, atunci−→p0p1 este în sensul acelor de ceasornic faţă de−→

p0p2; dacă este negativ, atunci este în sens trigonometric.

Determinarea dacă segmente consecutive se întorc la stânga sau ladreapta

Următoarea întrebare este dacă două segmente de dreaptă consecutive p0p1 şi p1p2 se întorcla stânga sau la dreapta în punctul p1. Adică, dorim o metodă pentru determinarea direcţieiîn care se întoarce un unghi dat ∠p0p1p2. Produsul încrucişat ne permite să răspundem laaceastă întrebare fără să calculăm unghiul. Aşa cum se poate vedea în figura 35.2, verificămdacă segmentul orientat

−→p0p2 este în sensul acelor de ceasornic sau în sens trigonometric, relativ

la segmentul orientat−→p0p1. Pentru această verificare, calculăm produsul încrucişat (p2−p0)×(p1−

p0). Dacă semnul acestui produs încrucişat este negativ, atunci−→p0p2 este în sens trigonometric

faţă de−→p0p1 şi, astfel, facem o întoarcere la stânga în p1. Un produs încrucişat pozitiv, indică o

orientare în sensul acelor de ceasornic şi o întoarcere la dreapta. Un produs încrucişat 0 înseamnăcă punctele p0, p1 şi p2 sunt coliniare.

Determinarea faptului dacă două segmente de dreaptă se intersectează

Pentru a determina dacă două segmente de dreaptă se intersectează, vom proceda în douăetape. Prima etapă este respingerea rapidă : segmentele de dreaptă nu se pot intersecta dacădreptunghiurile de mărginire nu se intersectează. Dreptunghiul de mărginire al unei figurigeometrice este cel mai mic dreptunghi care conţine figura şi ale cărui segmente sunt paralelecu axa-x şi axa-y. Dreptunghiul de mărginire al segmentului de dreaptă p1p2 este reprezentatprin dreptunghiul (p1, p2) cu punctul stânga jos p1 = (x1, y1) şi punctul dreapta sus p2 =(x2, y2), unde x1 = min(x1, x2), y1 = min(y1, y2), x2 = max(x1, x2) şi y2 = max(y1, y2). Douădreptunghiuri reprezentate prin punctele din stânga jos şi din dreapta sus (p1, p2) şi (p3, p4) se

762 Capitolul 35 Geometrie computaţională

Figura 35.2 Folosirea produsului încrucişat pentru a determina cum se întorc în punctul p1 segmentelede dreaptă consecutive p0p1 şi p1p2. Verificăm dacă segmentul orientat

−→p0p2 este în sensul acelor de

ceasornic sau în sens trigonometric relativ la segmentul orientat−→p0p1. (a) Dacă este în sens trigonometric,

punctele fac o întoarcere la stânga. (b) Dacă este în sensul acelor de ceasornic, ele fac o întoarcere ladreapta.

intersectează dacă, şi numai dacă, este adevărată conjuncţia:

(x2 ≥ x3) ∧ (x4 ≥ x1) ∧ (y2 ≥ y3) ∧ (y4 ≥ y1).

Dreptunghiurile trebuie să se intersecteze pe ambele laturi. Primele două comparaţii de mai susdetermină dacă dreptunghiurile se intersectează în x; ultimele două comparaţii determină dacădreptunghiurile se intersectează în y.

A doua etapă în determinarea faptului dacă două segmente de dreaptă se intersectează decidedacă fiecare segment “întretaie” dreapta care conţine celălalt segment. Un segment p1p2 întretaieo dreaptă dacă punctul p1 se află de o parte a dreptei, iar p2 se află de cealaltă parte a ei. Dacăp1 şi p2 se află pe dreaptă, atunci spunem că segmentul întretaie dreapta. Două segmente dedreaptă se intersectează dacă, şi numai dacă, ele trec de testul de respingere rapidă şi fiecaresegment întretaie dreapta care conţine celălalt segment.

Putem folosi metoda produsului încrucişat pentru a determina dacă segmentul de dreaptăp3p4 întretaie dreapta care conţine punctele p1 şi p2. Ideea, aşa cum am arătat în figura 35.3(a)şi (b), este să determinăm dacă segmentele orientate

−→p1p3 şi

−→p1p4 au orientări opuse relativ

la−→p1p2. În acest caz, segmentul întretaie dreapta. Amintim că putem determina orientările

relative cu ajutorul produselor încrucişate, verificând doar dacă semnele produselor încrucişate(p3 − p1) × (p2 − p1) şi (p4 − p1) × (p2 − p1) sunt diferite. O condiţie limită apare dacă oricaredintre produsele încrucişate este zero. În acest caz, fie p3, fie p4 se află pe dreapta care conţinesegmentul p1p2. Deoarece cele două segmente au trecut deja testul de respingere rapidă, unuldintre punctele p3 sau p4 trebuie să se afle, de fapt, pe segmentul p1p2. Două astfel de situaţiisunt ilustrate în figura 35.3(c) şi (d). Cazul în care cele două segmente sunt coliniare, dar nuse intersectează, ilustrat în figura 35.3(e), este eliminat de testul de respingere rapidă. O ultimăcondiţie limită apare dacă unul dintre cele două segmente are lungimea zero, altfel spus, capetelesegmentului coincid. Dacă ambele segmente au lungimea zero, atunci testul de respingere rapidăeste suficient. Dacă doar un segment, să zicem p3p4, are lungimea zero, atunci segmentele seintersectează dacă, şi numai dacă, produsul încrucişat (p3 − p1)× (p2 − p1) este zero.

Alte aplicaţii ale produselor încrucişateÎn ultima secţiune a acestui capitol se vor prezenta alte utilizări ale produselor încrucişate.

În secţiunea 35.3 vom avea nevoie să ordonăm o mulţime de puncte în raport cu unghiurile lor

35.1. Proprietăţile segmentului de dreaptă 763

Figura 35.3 Determinarea faptului dacă segmentul de dreaptă p3p4 întretaie dreapta ce conţinesegmentul p1p2. (a) Dacă acesta întretaie dreapta, atunci semnele produselor încrucişate (p3−p1)×(p2−p1) şi (p4− p1)× (p2− p1) diferă. (b) Dacă acesta nu întretaie dreapta, atunci produsele sunt de acelaşisemn. (c)-(d) Cazurile limită în care cel puţin unul dintre produsele încrucişate este zero şi segmentulîntretaie dreapta. (e) Cazul limită în care segmentele sunt coliniare, dar nu se intersectează. Ambeleproduse încrucişate sunt zero, dar ele nu pot fi calculate prin algoritmul nostru deoarece segmentele nutrec testul de respingere rapidă – dreptunghiurile lor de mărginire nu se intersectează.

polare şi o origine dată. Aşa cum se cere să arătaţi în exerciţiul 35.1-2, produsele încrucişatepot fi folosite pentru comparările din procedura de sortare. În secţiunea 35.2, vom folosi arboriroşu-negru pentru a păstra ordonarea verticală a unei mulţimi de segmente de dreaptă care nu seintersectează. Decât să păstrăm valorile cheie explicit, preferăm să înlocuim fiecare comparaţiede cheie, din codul arborilor roşu-negru, cu un calcul de produs încrucişat pentru a determinacare dintre două segmente, care intersectează o dreaptă verticală dată, este mai sus.

Exerciţii

35.1-1 Demonstraţi că, dacă p1 × p2 este pozitiv, atunci vectorul p1 este în sensul acelor deceasornic faţă de vectorul p2 în raport cu originea (0, 0) şi că, dacă acest produs este negativ,atunci vectorul p1 este în sens trigonometric faţă de vectorul p2.

35.1-2 Scrieţi, în pseudocod, o procedură pentru sortarea unei secvenţe 〈p1, p2, ..., pn〉 de npuncte specificate prin unghiurile lor polare, în raport cu un punct de origine p0 dat. Proceduratrebuie să se execute într-un timp O(n lg n) şi să folosească produse încrucişate pentru a comparaunghiuri.

35.1-3 Arătaţi cum se determină, într-un timp O(n2 lg n), dacă oricare trei puncte dintr-o mul-ţime de n puncte sunt coliniare.

764 Capitolul 35 Geometrie computaţională

35.1-4 Profesorul Amundsen propune următoarea metodă pentru a determina dacă secvenţa den puncte 〈p0, p1, ..., pn−1〉 reprezintă vârfurile consecutive ale unui poligon convex. (Vezi secţiunea16.4 pentru definiţiile relative la poligoane.) Dacă mulţimea ∠pipi+1pi+2 : i = 0, 1, ..., n− 1,unde adunarea de indici se face modulo n, nu conţine nici întoarceri la stânga, şi nici întoarcerila dreapta, atunci ieşirea este “da”; altfel ieşirea este “nu”. Arătaţi că, deşi această metodă areun timp de execuţie liniar, ea nu conduce întotdeauna la rezultatul corect. Modificaţi metodaprofesorului astfel încât să producă, întotdeauna, răspunsul corect într-un timp liniar.

35.1-5 Fiind dat un punct p0 = (x0, y0), raza orizontală spre dreapta , din punctul p0, estemulţimea punctelor pi = (xi, yi) : xi ≥ x0 şi yi = y0, adică mulţimea punctelor din dreapta luip0 inclusiv p0. Fiind dată o rază orizontală spre dreapta din p0, arătaţi cum se determină într-un timp O(1), dacă aceasta se intersectează cu un segment de dreaptă p1p2. Realizaţi aceastareducând problema la a determina dacă două segemente de dreaptă se intersectează.

35.1-6 O metodă pentru a determina dacă un punct p0 se află în interiorul unui poligon P ,nu neapărat convex, este să verificăm dacă fiecare rază din p0 intersectează frontiera lui P deun număr impar de ori, iar punctul p0 nu este pe frontiera lui P . Arătaţi cum se calculează,într-un timp Θ(n), dacă un punct p0 este în interiorul unui poligon P cu n vârfuri. (Indicaţie:Folosiţi exerciţiul 35.1-5. Asiguraţi-vă că algoritmul este corect când raza intersectează frontierapoligonului într-un vârf şi când raza se suprapune peste o latură a poligonului.)

35.1-7 Arătaţi cum se calculează aria unui poligon cu n vârfuri, nu neapărat convex, într-untimp Θ(n).

35.2. Determinarea cazului în care oricare două segmente seintersectează

Această secţiune prezintă un algoritm pentru a determina dacă oricare două segmente dedreaptă, dintr-o mulţime de segmente, se intersectează. Algoritmul foloseşte o tehnică cunoscutăsub numele de “baleiere” care este comună multor algoritmi de geometrie computaţională. Maimult, aşa cum este arătat în exerciţiile de la sfârşitul secţiunii, acest algoritm sau simple variaţiuniale lui pot fi folosite pentru a rezolva şi alte probleme de geometrie computaţională.

Timpul de execuţie al algoritmului este O(n lgn), unde n este numărul de segmente date.Algoritmul determină numai dacă două drepte se intersectează sau nu; nu afişează toateintersecţiile. (În exerciţiul 35.2-1, pentru a găsi toate intersecţiile într-o mulţime de n segmentede dreaptă, timpul de execuţie, în cel mai defavorabil caz, este Ω(n2).

În baleiere , o dreaptă de baleiere verticală, imaginară, traversează mulţimea de obiectegeometrice dată, de obicei, de la stânga la dreapta. Dimensiunea x a spaţiului în care dreaptade baleiere se deplasează, este tratată ca dimensiunea timpului. Baleierea oferă o metodă pentruordonarea obiectelor geometrice, de obicei, plasându-le într-o structură de date dinamică, şipentru obţinerea relaţiilor dintre ele. În această secţiune, algoritmul intersecţie-segment-de-dreaptă consideră toate capetele segmentelor de dreaptă ordonate de la stânga la dreapta şiverifică dacă există o intersecţie de fiecare dată când întâlneşte un capăt de segment.

35.2. Determinarea cazului în care oricare două segmente se intersectează 765

Figura 35.4 Ordinea segmentelor de dreaptă pentru diferite drepte de baleiere verticale. (a) Avema >r c, a >t b, b >t c, a >t c şi b >u c. Segmentul d nu este comparabil cu segmentele din figură.(b) La momentul intersecţiei segmentului e cu segmentul f , ordinea lor se inversează: avem e >v f , darf >w e. Orice dreaptă de baleiere (de exemplu z) care traversează regiunea haşurată are în ordinea eitotală segmentele e şi f consecutive.

Ordonarea segmentelor

Dacă presupunem că nu există segmente verticale, atunci orice segment de intrare care inter-sectează o dreaptă de baleiere verticală dată, o face într-un singur punct. Astfel, putem ordonasegmentele care intersectează o dreaptă de baleiere verticală după coordonatele y ale punctelorde intersecţie.

Mai exact, considerăm două segmente s1 şi s2 care nu se intersectează. Spunem că acestesegmente sunt comparabile după x dacă dreapta de baleiere verticală cu coordonata orizontalăx le intersectează pe amândouă. Spunem că s1 este deasupra lui s2 după x şi scriem s1 >x s2,dacă s1 şi s2 sunt comparabile după x şi intersecţia lui s1 cu dreapta de baleiere din x se aflădeasupra intersecţiei lui s2 cu aceeaşi dreaptă de baleiere. De exemplu, în figura 35.4(a) avemrelaţiile a >r c, a >t b, b >t c, a >t c şi b >u c. Segmentul d nu este comparabil cu nici un altsegment.

Pentru orice x dat, relaţia “>x” este o ordine totală (vezi secţiunea 5.2) de segmente careintersectează dreapta de baleiere din x. Pentru valori diferite ale lui x, ordinea poate fi diferită,deşi segmentele intră şi ies din ordonare. Un segment intră în ordonare când capătul stâng esteîntâlnit de baleiere şi iese din ordonare când este întâlnit capătul drept.

Ce se întâmplă atunci când dreapta de baleiere trece prin intersecţia a două segmente? Aşacum se vede în figura 35.4(b) este inversată poziţia lor în ordinea totală. Dreptele de baleiere vşi w sunt în dreapta, respectiv, stânga punctului de intersecţie a segmentelor e şi f , şi aveme >v f dar f >w e. Subliniem aceasta pentru că presupunem că nu există trei segmentecare să se intersecteze în acelaşi punct, trebuie să existe vreo dreaptă de baleiere verticală xcare intersectează segmentele e şi f şi pentru care ele sunt consecutive în ordinea totală >x.Orice dreaptă de baleiere care trece prin regiunea haşurată din figura 35.4(b), cum ar fi z, aresegmentele e şi f consecutive în ordinea totală.

766 Capitolul 35 Geometrie computaţională

Deplasarea dreptei de baleiere

Algoritmii de baleiere, de obicei, gestionează două mulţimi de date:

1. Starea liniei de baleiere dă relaţia dintre obiectele intersectate de linia de baleiere.

2. Lista punct-eveniment este o secvenţă de coordonate-x, ordonate de la stânga ladreapta, care definesc poziţiile de oprire ale dreptei de baleiere. Numim fiecare astfel depoziţie de oprire punct eveniment . Numai în punctele eveniment, se întâlnesc modificăriale stării liniei de baleiere.

Pentru unii algoritmi (de exemplu, algoritmul cerut în exerciţiul 35.2-7), lista punct-eveni-ment este determinată dinamic în timpul execuţiei algoritmului. Cu toate acestea, algoritmulpe care îl avem la îndemână determină, static, punctele eveniment, bazându-se doar pe simpleproprietăţi ale datelor de intrare. În particular, fiecare capăt de segment este un punct eveniment.Sortăm capetele de segment prin creşterea coordonatei-x şi procedăm de la stânga la dreapta.Când întâlnim un capăt stâng de segment, inserăm segmentul în stările dreptei de baleiere şi,când întâlnim un capăt drept de segment, ştergem segmentul din stările dreptei de baleiere.De fiecare dată când două segmente devin consecutive în ordinea totală, verificăm dacă ele seintersectează.

Stările dreptei de baleiere sunt o ordine totală T , pentru care avem nevoie de următoareleoperaţii:

• Inserează(T ,s): inserează segmentul s în T .

• Şterge(T ,s): şterge segmentul s din T .

• Deasupra(T ,s): returnează segmentul care este imediat deasupra lui s în T .

• Dedesubt(T ,s): returnează segmentul care este imediat dedesubtul lui s în T .

Dacă există n segmente în mulţimea de intrare, folosind arborii roşu-negru, putem realizafiecare dintre operaţiile deasupra în timpul O(lg n). Reamintim că, în capitolul 14, operaţiilearbore-roşu-negru necesită compararea cheilor. Putem înlocui compararea cheilor cu comparareaprodus încrucişat care determină ordinea relativă a două segmente (vezi exerciţiul 35.2-2).

Algoritm pseudocod pentru intersecţia segmentelor

Algoritmul următor primeşte ca date de intrare o mulţime S de n segmente de dreaptă. Acestareturnează valoarea logică adevărat dacă orice pereche de segmente din S se intersectează, iaraltfel returnează fals. Ordinea totală T este implementată printr-un arbore-roşu-negru.

Execuţia algoritmului este ilustrată în figura 35.5. În linia 1 este iniţializată ordinea totalăcu mulţimea vidă. Linia 2 determină lista punctelor eveniment prin ordonarea de la stânga ladreapta a celor 2n capete de segment, eliminând egalităţile prin punerea capetelor din stângaînaintea capetelor din dreapta.

35.2. Determinarea cazului în care oricare două segmente se intersectează 767

Figura 35.5 Execuţia algoritmului Intersecţia-Oricăror-Segmente. Fiecare dreaptă punctatăreprezintă o dreaptă de baleiere într-un punct eveniment. Ordinea numelor de segment de sub fiecaredreaptă de baleiere este ordinea totală T la sfârşitul ciclului pentru în care este tratat punctul evenimentcorespunzător. Intersecţia segmentelor d şi b este găsită când este detectat segmentul c.

Intersecţia-Oricăror-Segmente(S)1: T ← ∅2: sortează capetele segmentelor din S de la stânga la dreapta eliminând egalităţile prin punerea

capetelor stânga înaintea capetelor dreapta3: pentru fiecare punct p din lista ordonată de capete execută4: dacă p este capătul stâng al segmentului s atunci5: Inserează(T ,s)6: dacă (Deasupra(T ,s) există şi intersectează pe s) sau (Dedesubt(T ,s) există şi

intersectează pe s) atunci7: returnează adevărat8: dacă p este capătul drept al segmentului s atunci9: dacă există ambele segmente Deasupra(T ,s) şi Dedesubt(T ,s) şi Deasupra(T ,s)

intersectează Dedesubt(T ,s) atunci10: returnează adevărat11: Şterge(T ,s)12: returnează fals

Fiecare iteraţie a ciclului pentru din liniile 3–11 tratează un punct eveniment p. Dacă peste capătul din stânga al segmentului s, atunci linia 5 adaugă s la ordinea totală şi liniile 6–7 returnează adevărat dacă s intersectează ambele segmente ce îi sunt consecutive în ordineatotală definită de linia de baleiere ce trece prin p. (O condiţie limită apare dacă p se află pe un altsegment s′. În acest caz, este necesar doar ca s şi s′ să fie consecutive în T .) Dacă p este capătuldin dreapta al segmentului s, atunci s este şters din ordinea totală. Liniile 9–10 returneazăadevărat dacă există o intersecţie între segmentele ce îi sunt consecutive lui s în ordinea totalădefinită de dreapta de baleiere ce trece prin p; aceste segmente vor deveni consecutive în ordineatotală, când s este şters. Dacă aceste segmente nu se intersectează, linia 11 şterge segmentul s

768 Capitolul 35 Geometrie computaţională

din ordinea totală. În final, dacă nu este găsită nici o intersecţie prin prelucrarea celor 2n puncteeveniment, atunci linia 12 returnează fals.

Corectitudinea

Următoarea teoremă arată că Intersecţia-Oricăror-Segmente este corect.

Teorema 35.1 Apelul funcţiei Intersecţia-Oricăror-Segmente(S) returnează adevăratdacă, şi numai dacă, există o intersecţie printre segmentele lui S.

Demonstraţie. Procedura poate fi incorectă dacă, şi numai dacă, returnează adevărat cândnu există intersecţie sau dacă returnează fals când există, cel puţin o intersecţie. Primul caznu poate să apară deoarece Intersecţia-Oricăror-Segmente returnează adevărat numaidacă găseşte o intersecţie între două segmente de intrare.

Pentru a arăta că ultimul caz nu poate să apară, să presupunem că există, cel puţin, o intersec-ţie şi algoritmul Intersecţia-Oricăror-Segmente returnează fals. Fie p cel mai din stângapunct de intersecţie, eliminând egalităţile prin alegerea unui punct cu cea mai mică coordonată-y, şi fie a şi b segmentele care se intersectează în p. Întrucât nu apare nici o intersecţie în stângalui p, ordinea dată de T este corectă pentru toate punctele din stânga lui p. Există un capăt desegment q pe dreapta de baleiere z care este punctul eveniment la care a şi b devin consecutiveîn ordinea totală. Dacă p este pe dreapta de baleiere z atunci q = p. Dacă p nu este pe dreaptade baleiere z atunci q este în stânga faţă de p. În ambele cazuri, ordinea dată de T este corectăînainte de procesarea lui q. (Aici suntem siguri că p este cel mai de jos dintre cele mai din stângapuncte de intersecţie. Datorită ordinii în care sunt procesate punctele eveniment, chiar dacă peste pe dreapta de baleiere z şi există un alt punct de intersecţie p′ pe z, punctul evenimentq = p, procesat înaintea celeilalte intersecţii p′ poate interfera cu ordinea totală T .) Există doardouă posibilităţi de a acţiona în punctul eveniment q:

1. Unul dintre a şi b este inserat în T şi celălalt segment este deasupra sau dedesubtul acestuiaîn ordinea totală. Liniile 4–7 detectează acest caz.

2. Segmentele a şi b sunt deja în T şi un segment aflat între ele în ordinea totală a fost şters,astfel a şi b devenind consecutive. Liniile 8–11 detectează acest caz.

În ambele cazuri, este găsită intersecţia p, contrazicând presupunerea că procedura returneazăfals.

Timpul de execuţie

Dacă există n segmente în mulţimea S, atunci Intersecţia-Oricăror-Segmente seexecută într-un timp O(n lg n). Linia 1 necesită un timp O(1). Linia 2 necesită un timp O(n lgn),folosind sortarea prin interclasare sau heapsort. Deoarece există 2n puncte eveniment, ciclulpentru din liniile 3–11 se execută de cel mult 2n ori. Fiecare iteraţie necesită un timp O(lg n)deoarece fiecare operaţie arbore-roşu-negru necesită un timp O(lg n) şi, folosind metoda dinsecţiunea 35.1, fiecare test de intersecţie necesită un timp O(1). Astfel, timpul total este O(n lgn).