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