CAPITOLUL I. INTRODUCERE ÎN ALGORITMICA

CAPITOLUL I. INTRODUCERE ÎN ALGORITMICA

GEOMETRICĂ ...................................................................................... 9

1.1 CE ESTE ALGORITMICA GEOMETRICĂ? .............................................. 9

1.2 LIMITELE GEOMETRIEI COMPUTAŢIONALE ...................................... 11

1.3 EXEMPLE TIPICE DE PROBLEME ALE GEOMETRIEI COMPUTAŢIONALE 13

1.4 TEME LABORATOR/SEMINAR ......................................................... 15

CAPITOLUL II. GRAFICA ÎN LIMBAJULUI C ............................... 16

2.1 CONFIGURAREA MODULUI GRAFIC ÎN DEV C++ ............................... 16

2.2 FUNCŢIILE MODULUI GRAFIC ÎN DEV C++ ....................................... 22

2.2.1. Iniţializarea ecranului grafic în Dev C++ ............................. 22

2.2.2. Culorile modului grafic în Dev C++ ..................................... 23

2.2.3. Coordonate-ecran ale pixelilor în Dev C++ ......................... 25

2.2.4. Funcţiile elementare de desenare .......................................... 27

2.2.5. Ecran virtual si ecran grafic ................................................. 30

2.3 TEME LABORATOR/SEMINAR ......................................................... 33

CAPITOLUL III. NOŢIUNI GEOMETRICE ELEMENTARE ......... 34

3.1 PUNCTE ŞI VECTORI ....................................................................... 34

3.2 GEOMETRIE AFINĂ ŞI EUCLIDIANĂ .................................................. 37

3.2.1 Operaţii afine cu puncte, vectori şi scalari ............................. 37

3.2.2. Produsul scalar .................................................................... 39

3.3 DREPTE ŞI CERCURI ÎN PLAN ........................................................... 40

3.4 REPREZENTAREA SPAŢIULUI 3D ..................................................... 42

3.4.1 Sistemul obiect şi observator ................................................. 42

3.4.2 Sisteme de coordonate 3D ..................................................... 43

3.5 DREPTE, PLANURI ŞI SFERE ÎN SPAŢIU ............................................. 45

3.6. REPREZENTAREA SPAŢIULUI 3D PE ECRAN ..................................... 46

3.7. TEME DE LABORATOR ................................................................... 49

CAPITOLUL IV. TRANSFORMĂRI GEOMETRICE....................... 51

4.1 TRANSFORMĂRI GEOMETRICE ELEMENTARE ÎN PLAN ....................... 51

4.1.1 Translaţia.............................................................................. 52

4.1.2 Scalarea ................................................................................ 52

4.1.3 Simetria ................................................................................ 53

4.1.4 Rotaţia .................................................................................. 54

4.2 TRANSFORMĂRI GEOMETRICE ELEMENTARE ÎN SPAŢIU .................... 55

4.2.1 Translaţia.............................................................................. 55

4.2.2 Scalarea ................................................................................ 56

4.2.3 Rotaţia .................................................................................. 57

4.2.4 Concatenarea şi transformarea inversă ................................. 58

4.3. TRANSFORMAREA DE PERSPECTIVĂ ............................................... 60

3.7. MODELUL CAMEREI DE LUAT VEDERI............................................. 64

4.4. TEME DE LABORATOR ................................................................... 66

CAPITOLUL V. ALGORITMI ELEMENTARI DE GEOMETRIE

COMPUTAŢIONALĂ .......................................................................... 71

5.1 PUNCTE, LINII ŞI POLIGOANE .......................................................... 71

5.2 ORIENTAREA TRIUNGIURILOR ŞI TESTUL DE COLINIARITATE ............ 74

5.2.1 Orientarea punctelor ............................................................. 74

5.2.2 Suprafeţe şi unghiuri ............................................................. 76

5.3 INTERSECŢII PROPRII ŞI IMPROPRII DE SEGMENTE ............................. 77

5.4 PROBLEMA DRUMULUI SIMPLU ÎNCHIS ............................................ 80

5.5 APARTENENŢA LA INTERIORUL UNUI POLIGON ................................ 82

5.6. TEME DE LABORATOR ................................................................... 86

CAPITOLUL VI. PROBLEME DE INTERSECŢII ............................ 93

6.1. INTERSECŢII GEOMETRICE ............................................................. 93

6.2. INTERSECŢII DE SEGMENTE DE DREAPTĂ ........................................ 94

6.2.1 Intersecţia brută a segmentelor de dreaptǎ ............................ 95

6.2.2 Linii orizontale si verticale .................................................... 96

6.2.3 Intersecţii de segmente arbitrare............................................ 99

6.3. TEME DE LABORATOR ................................................................. 100

CAPITOLUL VII. ÎNFĂŞURĂTOAREA CONVEXĂ ...................... 105

7.1 PROBLEMA DETERMINĂRII ACOPERIRII CONVEXE ŞI ALGORITMUL NAIV

........................................................................................................ 105

7.2 METODA ÎMPACHETĂRII (WRAPPING) ........................................... 108

7.3 SCANAREA GRAHAM ................................................................... 113

7.4 METODA RAPIDĂ PRIN SELECŢIE (QUICKHULL) ............................. 119

7.5. TEME DE LABORATOR ................................................................. 121

CAPITOLUL VII. SUBDOMENII ALE UNUI POLIGON ............... 127

8.1. PROBLEMA NUCLEULUI ............................................................... 127

8.2. TRIANGULAREA POLIGOANELOR.................................................. 130

8.2.1 Triangularea poligoanelor convexe ..................................... 132

8.2.2 Triangularea poligoanelor simple arbitrare ......................... 135

8.3. TEME DE LABORATOR ................................................................. 140

CAPITOLUL IX. DIAGRAME VORONOI ŞI TRIANGULĂRI

DELAUNAY ....................................................................................... 141

9.1. PROBLEMA DIAGRAMELOR VORONOI........................................... 141

9.2. CONSTRUCŢIA ALGORITMICĂ A DIAGRAMELOR VORONOI ............. 143

9.3. TRIANGULAREA DELAUNAY A UNUI ANSAMBLU DE PUNCTE ......... 144

9.4. ALGORITM DE DETERMINARE A TRIANGULĂRII DELAUNAY ŞI A

DIAGRAMEI VORONOI ........................................................................ 146

9.6. TEME DE LABORATOR ................................................................. 152

CAPITOLUL X. PROBLEMA CELUI MAI SCURT DRUM ÎNTR-UN

CÂMP CU OBSTACOLE ŞI GRAFUL DE VIZIBILITATE ........... 154

10.1. PROBLEMA CELUI MAI SCURT DRUM ÎNTR-UN CÂMP CU OBSTACOLE

........................................................................................................ 154

10.2. GRAFUL DE VIZIBILITATE .......................................................... 155

10.3. TEMĂ DE LABORATOR ............................................................... 159