mirel cosulschi - ucv

Algoritmi Geometrici - Laborator

Mirel Cosulschi

Cuprins

1 Elemente de reprezentare grafica ın limbajul C 31.1 Initializarea modului grafic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.2 Desenare pe ecran. Corespondenta ıntre ecranul grafic si ecranul virtual . . . . 51.3 Aplicatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.4 Exercitii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2 Transformari geometrice ın plan 122.1 Principalele transformari geometrice ın plan . . . . . . . . . . . . . . . . . . . 122.2 Desenarea graficului unei functii . . . . . . . . . . . . . . . . . . . . . . . . . . 182.3 Desenarea unei linii cu algoritmul lui Bresenham . . . . . . . . . . . . . . . . . 232.4 Exercitii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

3 Transformari geometrice ın spatiu 293.1 Principalele transformari geometrice ın plan . . . . . . . . . . . . . . . . . . . 293.2 Exercitii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

4 Curbe ın plan si spatiu. Reprezentare grafica 374.1 Curbe ın spatiu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374.2 Curbe Bezier. Algoritmul lui De Casteljau . . . . . . . . . . . . . . . . . . . . 404.3 Curbe spline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434.4 Exercitii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

5 Reprezentarea suprafetelor. Mascarea suprafetelor ascunse 485.1 Algoritmul lui Warnock . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 485.2 Metoda ZBuffer - TBD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 545.3 Exercitii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

6 Probleme elementare de Algoritmica geometrica 566.1 Intersectii de intervale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 566.2 Intersectii de segmente de dreapta . . . . . . . . . . . . . . . . . . . . . . . . . 566.3 Apartenenta la interiorul unui poligon . . . . . . . . . . . . . . . . . . . . . . 616.4 Verificarea daca un poligon este convex . . . . . . . . . . . . . . . . . . . . . . 65

7 Probleme de intersectii multiple de segmente 687.1 Problema ”Vanatorii de fantome” . . . . . . . . . . . . . . . . . . . . . . . . . 687.2 Un algoritm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

8 Acoperiri convexe ın plan. Algoritmii Graham si Jarvis 728.1 Un algoritm simplu de determinare a acoperirii convexe a unei multimi de puncte 738.2 Algoritmul lui Graham . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

1

8.3 Algoritmul lui Jarvis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 808.4 Un algoritm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

9 Determinarea nucleului unui poligon (Problema galeriei de arta) si trian-gularea unui poligon prin metoda taierii urechilor 849.1 Determinarea nucleului unui poligon . . . . . . . . . . . . . . . . . . . . . . . 849.2 Triangularea unui poligon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

9.2.1 Triangularea optima a unui poligon . . . . . . . . . . . . . . . . . . . . 92

A Algoritmi pentru calculul optimal al vizibilitatii unor puncte 94A.1 Descrierea problemei . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94A.2 Algoritmul Visibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94A.3 Algorithm VisibilityOpt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97A.4 Aplicatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

2

Laboratorul 1

Elemente de reprezentare grafica ınlimbajul C

Dezvoltarea programelor se va realiza folosind mediul integrat de dezvoltare (IDE) Blood-shed Dev-C++1. Acesta poate fi descarcat de la adresa http://www.bloodshed.net/dev/

devcpp.html.Pentru a putea sa lucram cu mediul grafic este nevoie sa configuram acest mediu de lucru.

Descrierea ıntregului proces de configurare poate fi urmarita ın [14] sau [15].Se vor descarca doua fisiere si se vor copia ın doua directoare, astfel:

1. Fisierul graphics.h2 se va copia ın folderul C:\Dev-Cpp\include (presupunem camediul Dev-C++ a fost instalat ın folderul C:\Dev-Cpp);

2. Fisierul libbgi.a3 se va copia ın folderul C:\Dev-Cpp\lib.

In cazul fiecarui proiect nou, se va alege ”Console Application” si ”C++ project” (cu ”Cproject” nu se compileaza programele) iar ın cadrul ferestrei ”Project options” se va selectatab-ul ”Parameters” pentru a se transmite urmatorii parametri link-editorului4:

-lbgi

-lgdi32

-lcomdlg32

-luuid

-loleaut32

-lole32

Prezentam un program ce poate fi utilizat pentru a testa daca mediul de dezvoltare siproiectul suporta mediul grafic (a se vedea [14])(initgraph.cpp):

#include <graphics.h> // biblioteca primitive grafice

#include <math.h>

#include <stdlib.h>

#include <dos.h>

#include <conio.h>

#define pi M_PI

1http://www.bloodshed.net/devcpp.html2http://www.cs.colorado.edu/~main/bgi/dev-c++/graphics.h3http://www.cs.colorado.edu/~main/bgi/dev-c++/libbgi.a4http://en.wikipedia.org/wiki/Linker_(computing)

3

int gd, gm;

int n, i, j;

double r, x, y, xp, yp, fi;

int main()

n = 16;

r = 150; // testare n= 17, 25, 30

gd = DETECT ;

// initializarea modului grafic

initgraph(&gd, &gm, ""); // initializare regim grafic

initwindow(900, 900, "Grafica"); //fereastra de desenare

settextstyle(1, 0, 2);

setcolor(4); // culoare desenare

// schimbare origine in mijlocul ecranului (fara clipping)

setviewport(getmaxx()/2, getmaxy()/2, getmaxx(), getmaxy(), 0);

// se genereaza coordonatele varfurilor

for (i = 0; i <= n-1; i++)

fi = (2 * pi * i) / n;

x = r * cos(fi);

y = r * sin(fi);

// se genereaza muchiile / laturile

for (j = i+1; j <= n; j++)

fi = (2 * pi * j) / n ;

xp = r * cos(fi);

yp = r * sin(fi);

// se traseaza segmentul [(x,y) (xp,yp)]

line(x, y, xp, yp);

getch(); // pastrarea imaginii pe ecran

closegraph();

return 0;

Primitivele grafice pe care le vom utiliza au antetul descris ın fisierul header graphics.hsi formeaza Borland Graphics Interface for Windows (aceste primitive reprezinta marea ma-joritate a primitivelor ce puteau fi utilizate ın cadrul compilatoarelor Borland sub mediulDOS - Borland Graphics Interface for DOS programs).

Lista acestor primitive poate fi consultata la adresa http://www.cs.colorado.edu/

~main/bgi/doc/.

1.1 Initializarea modului grafic

Pentru initializarea modului grafic se foloseste functia initgraph()5:

void initgraph(int *graphdriver, int *graphmode, char *pathtodriver);

5http://www.cs.colorado.edu/~main/bgi/doc/initgraph.html

4

acest lucru realizandu-se prin ıncarcarea unui driver grafic de pe o unitate de stocarenevolatila a datelor sau prin validarea unui driver deja ınregistrat, trecand apoi sistemul ınmodul grafic.

Un exemplu simplu de initializare a modului grafic si trasare a unui dreptunghi esteurmatorul:

#include <graphics.h> // biblioteca primitive grafice

#include <stdlib.h>

#include <conio.h>

int main()

int gd, gm;

gd = DETECT;

// initializarea modului grafic

initgraph(&gd, &gm, ""); // initializare regim grafic

setcolor(15); // culoare desenare

rectangle(10, 10, 100, 100);

getch(); // pastrarea imaginii pe ecran

closegraph();

return 0;

1.2 Desenare pe ecran. Corespondenta ıntre ecranul

grafic si ecranul virtual

1.3 Aplicatie

Vom prezenta un program ce poate fi utilizat ın cadrul tuturor aplicatiilor viitoare: acestprogram ne permite sa selectam ın mod vizual niste puncte pe ecran folosind un cursormanevrat cu ajutorul tastelor sageti.

Codul sursa al programului utildraw.cpp este urmatorul:

#include <stdio.h>

#include <stdlib.h>

#include <conio.h>

#include <dos.h>

#include <graphics.h>

#define N 40

#define TRUE 1

#define FALSE 0

#define INF_LIMIT 5

#define CURSOR_SIZE 20

void *p;

void init(void)

int gd, gm;

5

gd = DETECT;

initgraph(&gd, &gm, "");

if (graphresult()!= grOk)

printf("Eroare grafica: %s\n", grapherrormsg(graphresult()));

printf("Apasati o tasta!");

getch();

exit(1);

void createCursor(void)

int vertices[] = 0, 0, 9, 3, 7, 5, 17, 15, 15, 17, 5, 7, 3, 9, 0, 0;

unsigned size;

setcolor(WHITE);

setfillstyle(SOLID_FILL, WHITE);

drawpoly(8, vertices);

fillpoly(8, vertices);

size = imagesize(0, 0, CURSOR_SIZE, CURSOR_SIZE);

p = malloc(sizeof(char) * size);

getimage(0, 0, CURSOR_SIZE, CURSOR_SIZE, p);

cleardevice();

int readChar(void)

int c;

c = getch();

if (!c)

c = getch();

return c;

void saveVerticesCoord(int n, int x[], int y[])

char fname[12];

FILE *f;

int i;

printf("Numele fisierului: "); scanf("%s", fname);

if ((f = fopen(fname, "wt"))== NULL)

fprintf(stderr, "Nu se poate deschide fisierul de date.\n");

exit(1);

fprintf(f, "%d\n", n);

for (i = 0; i < n; i++)

fprintf(f, "%d %d\n", x[i], y[i]);

fclose(f);

void loop(void)

6

unsigned int n;

int x[N], y[N];

char ch;

int step, xp, yp, stopAddVertices;

xp = 10; yp = 10; step = 10;

stopAddVertices = FALSE;

n = 0;

putimage(xp, yp, p, XOR_PUT);

do

ch = readChar();


switch (ch)

case 72: if (yp > step)

yp = yp - step;

break;

case 80: if (yp < getmaxy() - step)

yp = yp + step;

break;

case 77: if (xp <= getmaxx() - step)

xp = xp + step;

break;

case 75: if (xp > step)

xp = xp - step;

break;

case ’+’: if (step < getmaxy()/2)

step += INF_LIMIT;

break;

case ’-’: if (step > INF_LIMIT)

step -= INF_LIMIT;

break;

case ’t’: line(x[n-1], y[n-1], x[0], y[0]);

stopAddVertices = TRUE;

break;

case 13: if (stopAddVertices)

break;

x[n] = xp; y[n] = yp;

n++;

if (n > 1)

line(x[n-1], y[n-1], x[n-2], y[n-2]);

rectangle(xp-3, yp-3, xp+3, yp+3);

break;

case ’s’: saveVerticesCoord(n, x, y);

cleardevice();

n = 0;


;


while(ch != 27);

int main()

7

init();

createCursor();

loop();

return 0;

In functia init() se ıncearca initializarea modului grafic. Daca acest lucru nu se poaterealiza (se testeaza valoarea returnata de functia graphresult()), se afiseaza un mesaj deeroare corespunzatorul codului de eroare grapherrormsg(graphresult()) si se parasesteprogramul.

void init(void)

int gd, gm;

gd = DETECT;





getch();

exit(1);

In functia createCursor() se initializeaza tabloul vertices cu coordonatele (x, y) a8 puncte care unite formeaza conturul unei sageti. Astfel vertices[0] reprezinta coor-donata pe axa Ox a primului punct iar vertices[1] reprezinta coordonata pe axa Oy aprimului punct; vertices[2] reprezinta coordonata pe axa Ox a celui de-al doilea punctetc. Se seteaza culoarea de desenare ca fiind alba (setcolor(WHITE);), se initializeazaculoarea de umplere ca fiind alba (setfillstyle(SOLID FILL, WHITE);) si se deseneazalinia poligonala ınchisa definita de coordonatele pastrate ın tabloul vertices, (drawpoly(8,vertices);). Se umple poligonul definit de aceleasi coordonate cu ajutorul instructiuniifillpoly(8, vertices);.

Se determina apoi dimensiunea unei zone rectangulare definita de coordonatele stanga-sussi dreapta-jos (size = imagesize(0, 0, CURSOR SIZE, CURSOR SIZE);) zona ce cuprindesageata desenata anterior. Se aloca un spatiu de memorie (p = malloc(sizeof(char) *

size);) unde se va pastra o imagine bit cu bit corespunzatoare zonei rectangulare definita decoordonatele stanga-sus si dreapta-jos getimage(0, 0, CURSOR SIZE, CURSOR SIZE, p);.Se sterge apoi ecranul curent aflat ın mod grafic (cleardevice();).


int vertices[] = 0, 0, 9, 3, 7, 5, 17, 15, 15, 17, 5, 7, 3, 9, 0, 0;

unsigned size;

setcolor(WHITE);






8


cleardevice();

In functia loop() se deplaseza cursorul, se selecteaza punctele unui desen si se salveaza. Sedeseneaza mai ıntai cursorul (putimage(xp, yp, p, XOR PUT);). Se asteapta apoi apasareaunei taste (ch = readChar();). Daca se apasa tastele sageti acestea vor genera un codextins : valoarea variabilei ch rezultata ın urma instructiunii ch = getch(); va fi 0, iarpentru a se obtine codul tastei apasate trebuie sa se mai citeasca o data: ch = getch();.Dupa apasarea unei taste se apeleaza din nou putimage(xp, yp, p, XOR PUT);. Aplicareasuccesiva a aceluiasi desen la aceleasi coordonate ın modul XOR PUT conduce la refacereafundalului existent ınainte de prima desenare. Ne ıncadram astfel ıntr-un sablon de realizarea unei animatii: se deseneaza ceva, se asteapta o perioada de timp, se reface fundalul, secalculeaza noile coordonate si se deseneaza la noile coordonate obiectul ce se doreste a fideplasat.

Astfel codul ’72’ corespunde tastei sageata-sus, codul ’80’ corespunde tastei sageata-jos,codul ’77’ corespunde tastei sageata-dreapta, iar codul ’75’ corespunde tastei sageata-stanga.In urma apasarii unei taste sageti se calculeaza noile coordonate ale cursorului, de exempluyp = yp - step;.

Atunci cand se apasa tasta ’Enter’ se genereaza codul ’13’: acest lucru va avea dreptrezultat memorarea coordonatelor curente ale cursorului xp si yp ın tablourile x si y, prin x[n]

= xp; y[n] = yp;. Se deseneaza cate o linie de la punctul curent (ultimul punct selectat)la penultimul punct ales: line(x[n-1], y[n-1], x[n-2], y[n-2]);. Pe pozitia ultimuluipunct selectat se deseneaza un mic patrat: rectangle(xp-3, yp-3, xp+3, yp+3);.

Daca se apasa tasta ’t’ atunci se ınchide linia poligonala si din acest moment nu se maipot selecta puncte noi pana aceste coordonate nu sunt salvate ıntr-un fisier.

...


do

ch = readChar();


switch (ch)

case 72: if (yp > step)

yp = yp - step;

break;

case 80: if (yp < getmaxy() - step)

yp = yp + step;

break;

case 77: if (xp <= getmaxx() - step)

xp = xp + step;

break;

case 75: if (xp > step)

xp = xp - step;

break;

...

case ’t’: line(x[n-1], y[n-1], x[0], y[0]);


break;

case 13: if (stopAddVertices)

break;

9

Fig. 1.1: Desenarea unei linii poligonale

x[n] = xp; y[n] = yp;

n++;

if (n > 1)

line(x[n-1], y[n-1], x[n-2], y[n-2]);


break;

...

;


while(ch != 27);

Prin apasarea tastei ’Esc’ programul se opreste.In figura 1.1 se poate observa desenul unei linii poligonale ınchise. Coordonatele punctelor

ce descriu conturul acestei figuri au fost salvate ın fisierul fig5.txt, ce va avea urmatorulcontinut:

10

110 60

290 20

380 130

340 230

450 330

450 180

270 180

170 340

60 230

190 120

1.4 Exercitii

1. Sa se realizeze un program care, cu ajutorul primitivelor grafice puse la dispozitie deBorland Graphics Interface for Windows, sa deseneze un ’tunel’ alcatuit din cercuri sau

10

patrate.

2. Sa se modifice programul initgraph.cpp astfel ıncat figura desenata sa poata fi rotitaın jurul unui punct oarecare.

3. Sa se realizeze un program care, cu ajutorul primitivelor grafice puse la dispozitie deBorland Graphics Interface for Windows, sa deseneze:

• un triunghi echilateral;

• un pentagon;

• un hexagon regulat;

• o linie poligonala oarecare ıchisa avand 8 puncte;

• o casuta simpla.

• o figura geometrica ce reprezinta desenul folosit pentru explicarea teoremei luiMenelaus6;

• o figura geometrica ce reprezinta desenul folosit pentru explicarea teoremei luiCeva7;

• o figura geometrica ce reprezinta desenul folosit pentru explicarea teoremei luiEuler8;

• o figura geometrica ce reprezinta cercul lui Euler9;

• o figura geometrica ce reprezinta desenul folosit pentru explicarea unei proprietatia ortocentrului unui triunghi10.

4. Sa se deseneze si sa se salveze cu ajutorul programului utildraw.cpp mai multe figurigeometrice:


• un dreptunghi;

• un pentagon;

• un hexagon regulat;

• o linie poligonala oarecare ıchisa avand 10 puncte.

6http://ro.wikipedia.org/wiki/Teorema_lui_Menelaus7http://ro.wikipedia.org/wiki/Teorema_lui_Ceva8http://geo-abc.blogspot.ro/2009/04/teorema-lui-euler.html9http://geo-abc.blogspot.ro/2009/04/cercul-lui-euler.html

10http://geo-abc.blogspot.ro/2009/03/despre-ortocentrul-unui-triunghi.html

11

Laboratorul 2

Transformari geometrice ın plan

2.1 Principalele transformari geometrice ın plan

Prezentam ın continuare programul transf2D.cpp ce implementeaza principalele transformarigeometrice ın plan (translatie, scalare, simetrie fata de axele Ox si Oy si fata de origine, rotatiefata de origine):


#include <conio.h>

#include <stdlib.h>

#include <math.h>

typedef struct point2d

float x, y;

POINT2D;

typedef struct line

POINT2D *p1, *p2;

LINE;

typedef struct

float xRmin, xRmax, yRmin, yRmax;

float xEmin, xEmax, yEmin, yEmax;

float sx, sy;

LINE Ox, Oy;

SYSTEM;

typedef enumOX = 0, OY = 1, OO = 2 SIMETRIE;

void initGraphics(void)

int gd, gm;

gd = DETECT;





getch();

exit(1);

12

void init(SYSTEM* s)

s->xRmin = -100; s->xRmax = 100;

s->yRmin = -100; s->yRmax = 100;

s->xEmin = 0; s->xEmax = getmaxx();

s->yEmin = 0; s->yEmax = getmaxy();

s->sx = (s->xEmax - s->xEmin) / (float)(s->xRmax - s->xRmin);

s->sy = (s->yEmax - s->yEmin) / (float)(s->yRmax - s->yRmin);

s->Ox.p1 = (POINT2D*)malloc(sizeof(POINT2D));

s->Ox.p1->x = s->xRmin;

s->Ox.p1->y = 0.0;

s->Ox.p2 = (POINT2D*)malloc(sizeof(POINT2D));

s->Ox.p2->x = s->xRmax;

s->Ox.p2->y = 0.0;

s->Oy.p1 = (POINT2D*)malloc(sizeof(POINT2D));

s->Oy.p1->x = 0.0;

s->Oy.p1->y = s->yRmin;

s->Oy.p2 = (POINT2D*)malloc(sizeof(POINT2D));

s->Oy.p2->x = 0.0;

s->Oy.p2->y = s->yRmax;

float xreal2ecran(float xr, SYSTEM* s)

return (xr - s->xRmin) * s->sx + s->xEmin;

float yreal2ecran(float yr, SYSTEM* s)

return (yr - s->yRmin) * s->sy + s->yEmin;

void real2ecran(POINT2D* pe, POINT2D pr, SYSTEM* s)

pe->x = round(xreal2ecran(pr.x, s));

pe->y = round(yreal2ecran(pr.y, s));

/***************** Transformari geometrice punct ********************/

void translatie(POINT2D* p, float dx, float dy)

p->x = p->x + dx;

p->y = p->y + dy;

void scalare(POINT2D* p, float sx, float sy)

p->x = p->x * sx;

p->y = p->y * sy;

13

void simetrie(POINT2D* p, SIMETRIE tip)

switch(tip)

case OX: p->y = -p->y;

break;

case OY: p->x = -p->x;

break;

case OO: p->x = -p->x;

p->y = -p->y;

;

void rotatie(POINT2D* p, float alfa)

float x, y;

x = p->x * cos(alfa) - p->y * sin(alfa);

y = p->x * sin(alfa) + p->y * cos(alfa);

p->x = x; p->y = y;

/*****************************************************/

/***************** Transformari geometrice figura ********************/

void translatieFigura(int n, POINT2D* p, float dx, float dy)

int i;

for (i = 0; i < n; i++)

translatie(&p[i], dx, dy);

void scalareFigura(int n, POINT2D* p, float sx, float sy)

int i;

for (i = 0; i < n; i++)

scalare(&p[i], sx, sy);

void simetrieFigura(int n, POINT2D* p, SIMETRIE tip)

int i;

for (i = 0; i < n; i++)

simetrie(&p[i], tip);

void rotatieFigura(int n, POINT2D* p, float alfa)

int i;

for (i = 0; i < n; i++)

rotatie(&p[i], alfa);

/*****************************************************/

void drawAxe(SYSTEM* s)

14

POINT2D p1, p2;

real2ecran(&p1, *(s->Ox.p1), s);

real2ecran(&p2, *(s->Ox.p2), s);

line((int)p1.x, (int)p1.y, (int)p2.x, (int)p2.y);

real2ecran(&p1, *(s->Oy.p1), s);

real2ecran(&p2, *(s->Oy.p2), s);

line((int)p1.x, (int)p1.y, (int)p2.x, (int)p2.y);

void drawFigure(int m, LINE* fig, SYSTEM* s)

int i;

POINT2D pe1, pe2;

for (i = 0; i < m; i++)

real2ecran(&pe1, *(fig[i].p1), s);

real2ecran(&pe2, *(fig[i].p2), s);

line((int)pe1.x, (int)pe1.y, (int)pe2.x, (int)pe2.y);

/*****************************************************/

int readChar(void)

int c;

c = getch();

if (!c)

c = getch();

return c;

void loop(int n, POINT2D *p, int m, LINE *fig, SYSTEM* s)

char ch;

int step = 3;

float alfa = 0.1;

setwritemode(XOR_PUT);

drawAxe(s);

drawFigure(m, fig, s);

do

ch = readChar();


switch (ch)

case 72: translatieFigura(n, p, 0, -step);

break;

case 80: translatieFigura(n, p, 0, step);

break;

case 77: translatieFigura(n, p, step, 0);

break;

case 75: translatieFigura(n, p, -step, 0);

break;

15

case ’+’: scalareFigura(n, p, 1.1, 1.1);

break;

case ’-’: scalareFigura(n, p, 0.9, 0.9);

break;

case ’x’: simetrieFigura(n, p, OX);

break;

case ’y’: simetrieFigura(n, p, OY);

break;

case ’o’: simetrieFigura(n, p, OO);

break;

case ’q’: rotatieFigura(n, p, alfa);

break;

case ’w’: rotatieFigura(n, p, -alfa);

break;

;


while(ch != 27);

void readInput(int *n, POINT2D **p, int *m, LINE **fig, SYSTEM* s)

FILE *f;

int i, u, v;

if ((f = fopen("figura1.txt", "rt")) == NULL)

printf("Nu se poate deschide fisierul de date!\n");


getch();

exit(1);

// se citeste numarul de puncte

fscanf(f,"%d", n);

*p = (POINT2D*)malloc(sizeof(POINT2D) * (*n));

// se citesc coordonatele reale ale punctelor

for (i = 0; i < *n; i++)

fscanf(f, "%f %f", &((*p)[i].x), &((*p)[i].y));

printf("%.2f %.2f\n", (*p)[i].x, (*p)[i].y);

// se citeste numarul de segmente de dreapta ce compun figura

fscanf(f,"%d", m);

*fig = (LINE*)malloc(sizeof(LINE) * (*m));

// se citesc indicii punctelor capetelor segmentelor de dreapta

for (i = 0; i < *m; i++)

fscanf(f, "%d %d", &u, &v);

(*fig)[i].p1 = &(*p)[u-1];

(*fig)[i].p2 = &(*p)[v-1];

printf("%.2f %.2f\n", (*fig)[i].p1->x, (*fig)[i].p2->x);

16

fscanf(f, "%f %f %f %f", &s->xRmin, &s->xRmax, &s->yRmin, &s->yRmax);

printf("%.2f %.2f %.2f %.2f\n", s->xRmin, s->xRmax, s->yRmin, s->yRmax);

fscanf(f, "%f %f %f %f", &s->xEmin, &s->xEmax, &s->yEmin, &s->yEmax);



s->Ox.p1->x = s->xRmin;

s->Ox.p1->y = 0.0;

s->Ox.p2->x = s->xRmax;

s->Ox.p2->y = 0.0;

s->Oy.p1->x = 0.0;

s->Oy.p1->y = s->yRmin;

s->Oy.p2->x = 0.0;

s->Oy.p2->y = s->yRmax;

fclose(f);

int main()

SYSTEM s;

int n;

POINT2D *points;

int m;

LINE* figura;

initGraphics();

init(&s);

readInput(&n, &points, &m, &figura, &s);

loop(n, points, m, figura, &s);

return 0;

Un exemplu de continut pentru fisierul de intrare ’figura1.txt’ poate fi:

4

-50.0 -50.0

50.0 -50.0

50.0 50.0

-50.0 50.0

4

1 2

2 3

3 4

4 1

-100.0 100.0 -100.0 100.0

0.0 500.0 0.0 400.0

17

Fig. 2.1: Transformari geometrice ın spatiul 2D

In figura 2.1 este reprezentat patratul din fisierul de intrare, dupa ce a fost supus unoroperatii succesive de translatie, scalare si rotatie.

2.2 Desenarea graficului unei functii

Vom realiza o aplicatie ce deseneaza graficul unei functii matematice. Aceasta este introdusaprin intermediul unei functii definita ın limbajul de programare C:

float f(float x)

....

unde limitele domeniului de definitie si ale codomeniului sunt [xRmin, xRmax], respectiv[yRmin, yRmax].

Astfel ın exemplu vom desena graficul functiei sin(x), sin (x) : [−2π, 2π] ⇒ R undelimitele domeniului si codomeniului vor avea urmatoarele valori:

const float xRmin = -2 * M_PI;

const float xRmax = 2 * M_PI;

const float yRmin = -2;

const float yRmax = 2;

Fereastra de desenare, adica fereastra-ecran ın care se va realiza desenarea graficului uneifunctii matematice este aleasa prin intermediul unui cursor. Pentru activarea modului ’se-lectare zona’ se apasa tasta ’Enter’, aceeasi tasta fiind responsabila si de ıncheierea selectarii.

Programul pentru desenarea graficul este urmatorul:

#include <stdio.h>

#include <stdlib.h>

#include <conio.h>

#include <math.h>


18

#include <stack>

#define TRUE 1

#define FALSE 0

#define INF_LIMIT 5

#define CURSOR_SIZE 20

const float xRmin = -2 * M_PI;

const float xRmax = 2 * M_PI;

const float yRmin = -2;

const float yRmax = 2;

void far *p;


int gd = DETECT, gm;


if (graphresult() != grOk)

printf("Eroare grafica!\n");

exit(1);


int vertices[] = 0,0,9,3,7,5,17,15,15,17,5,7,3,9,0,0;

unsigned size;

setcolor(WHITE);







cleardevice();

int readChar(void)

int c;

c = getch();

if (!c)

c = getch();

return c;

float f(float x)

return sin(x);

19

float real2screen(float r, float Rmin, float Emin, float fs)

return (r - Rmin) * fs + Emin;

void setScreenCoord(int l, int r, float *Emin, float *Emax)

if (l < r)

*Emin = l;

*Emax = r;

else

*Emin = r;

*Emax = l;

float getAspectRatio(float Rmin, float Rmax, float Emin, float Emax)

return (Emax - Emin) / (Rmax - Rmin);

void graphFunction(int xl, int yl, int xr, int yr)


float rx, ry;

float xr1, xr2, yr1, yr2;

int xe1, xe2, ye1, ye2;

std::stack<std::pair<float, float> > xStack;

setScreenCoord(xl, xr, &xEmin, &xEmax);

setScreenCoord(yl, yr, &yEmin, &yEmax);

rx = getAspectRatio(xRmin, xRmax, xEmin, xEmax);

ry = getAspectRatio(yRmin, yRmax, yEmin, yEmax);

xr1 = xRmin; xr2 = xRmax;

xStack.push(std::make_pair(xr1, xr2));

while (!xStack.empty())

std::pair<float,float> pair = xStack.top();

xStack.pop();

xr1 = pair.first; xr2 = pair.second;

yr1 = f(xr1);

yr2 = f(xr2);

xe1 = ceil(real2screen(xr1, xRmin, xEmin, rx));


if (xe2 - xe1 > 2)

xStack.push(std::make_pair(xr1, (xr1 + xr2)/2));

xStack.push(std::make_pair((xr1 + xr2)/2, xr2));

else

ye1 = ceil(real2screen(yr1, yRmin, yEmin, ry));


line(xe1, ye1, xe2, ye2);

20

void showRect(int xl, int yl, int xr, int yr)

int color = getcolor();

setcolor(WHITE);

rectangle(xl, yl, xr, yr);

setcolor(color);

void hideRect(int xl, int yl, int xr, int yr)

int color = getcolor();

setcolor(getbkcolor());

rectangle(xl, yl, xr, yr);

setcolor(color);

void loop(void)

int ch;

int step = 10;

int x, y;

int active = 0;

int xl, yl, xr, yr;

x = 0; y = 0;


while (TRUE)

if (active)

showRect(xl, yl, xr, yr);

putimage(x, y, p, XOR_PUT);

ch = readChar();

if (active)


putimage(x, y, p, XOR_PUT);

switch (ch)

case 72: if (y > step) y -= step; break;

case 80: if (y < getmaxy() - step) y += step; break;

case 77: if (x < getmaxx() - step) x += step; break;

case 75: if (x > step) x -= step; break;

case ’a’: if (step < getmaxx()/2) step++; break;

case ’s’: if (step > 5) step--; break;

case 27: return;

case 13: if (active == 0)

active = 1;

xl = x; yl = y;

xr = x; yr = y;

else

active = 0;

xr = x; yr = y;

21

setwritemode(COPY_PUT);


graphFunction(xl, yl, xr, yr);


break;

xr = x; yr = y;

int main(void)

initGraphics();

createCursor();

loop();

return 0;

Practic un grafic se realizeaza ın urma apelului functiei graphFunction(int xl, int

yl, int xr, int yr) unde (xl, xr) reprezinta coordonatele coltului stanga-sus ale drep-tunghiului selectiei iar (xr, yr) reprezinta coordonatele coltului dreapta-jos.

void graphFunction(int xl, int yl, int xr, int yr)


float rx, ry;

float xr1, xr2, yr1, yr2;

int xe1, xe2, ye1, ye2;

std::stack<std::pair<float, float> > xStack;

setScreenCoord(xl, xr, &xEmin, &xEmax);

setScreenCoord(yl, yr, &yEmin, &yEmax);

rx = getAspectRatio(xRmin, xRmax, xEmin, xEmax);

ry = getAspectRatio(yRmin, yRmax, yEmin, yEmax);

xr1 = xRmin; xr2 = xRmax;

xStack.push(std::make_pair(xr1, xr2));

while (!xStack.empty())

std::pair<float,float> pair = xStack.top();

xStack.pop();

xr1 = pair.first; xr2 = pair.second;

yr1 = f(xr1);

yr2 = f(xr2);



if (xe2 - xe1 > 2)

xStack.push(std::make_pair(xr1, (xr1 + xr2)/2));

xStack.push(std::make_pair((xr1 + xr2)/2, xr2));

else


22

Fig. 2.2: Grafice corespunzatoare functiei sin (x)


line(xe1, ye1, xe2, ye2);

Graficele functiei sin (x) desenate pentru mai multe zone rectangulare-ecran se pot vedeaın figura 2.2.

Prin apasarea tastei ’Esc’ programul se opreste.

2.3 Desenarea unei linii cu algoritmul lui Bresenham

Vom prezenta algoritmul lui Bresenham pentru trasarea unei linii1.Functia RBresenham() avand lista de parametrii int x1, int y1, int x2, int y2,

traseaza un segment de dreapta ıntre punctele de coordonate (x1, y1) si (x2, y2). Calcu-lul erorii se face folosind operatii cu numere reale, aceste fiind reprezentate ın virgula mobila.Coordonatele punctelor trebuie date astfel ıncat x1 < x2 si y1 <= y2.

void RBresenham(int x1, int y1, int x2, int y2)

int x, y, dx, dy, i;

float e;

x = x1; y = y1;

dx = x2 - x1; dy = y2 - y1;

e = dy/(float)dx - 1./2.;

for (i = 0; i < dx; i++)

putpixel(x, y, WHITE);

while (e >= 0.)

1http://en.wikipedia.org/wiki/Bresenham’s_line_algorithm

23

y = y + 1;

e = e - 1;

x = x + 1;

e = e + dy/(float)dx;

Operatiile cu numere ıntregi sunt mult mai rapide decat operatiile cu numere reale.Functia IBresenham() reprezinta echivalentul functiei RBresenham() ın care operatiile cunumere reale pentru calculul erorii e au fost ınlocuite cu operatii cu numere ıntregi.

void IBresenham(int x1, int y1, int x2, int y2)

int x, y, dx, dy, e, i;

x = x1; y= y1;

dx = x2 - x1; dy = y2 - y1;

e = 2 * dy - dx ;

for (i = 0; i < dx; i++)


while (e >= 0)

y = y + 1;

e = e - 2 * dx;

x = x + 1;

e = e + 2 * dy;

Functia Bresenham() traseaza o linie folosing algoritmul lui Bresenham: pentru aceastacoordonatele punctelor (x1, y1) si (x2, y2) pot fi date oricum (x1 6= x2).

Programul C rezultat este urmatorul:

#include <stdio.h>

#include <stdlib.h>

#include <time.h>


int sign(int number)

if (number > 0)

return 1;

else

if (number < 0)

return -1;

else

return 0;


int gd = DETECT, gm;


if (graphresult() != grOk)

24

printf("Eroare grafica!\n");

exit(1);

void RBresenham(int x1, int y1, int x2, int y2)

int x, y, dx, dy, i;

float e;

x = x1; y = y1;

dx = x2 - x1; dy = y2 - y1;

e = dy/(float)dx - 1./2.;

for (i = 0; i < dx; i++)


while (e >= 0.)

y = y + 1;

e = e - 1;

x = x + 1;

e = e + dy/(float)dx;

void IBresenham(int x1, int y1, int x2, int y2)

int x, y, dx, dy, e, i;

x = x1; y= y1;

dx = x2 - x1; dy = y2 - y1;

e = 2 * dy - dx ;

for (i = 0; i < dx; i++)


while (e >= 0)

y = y + 1;

e = e - 2 * dx;

x = x + 1;

e = e + 2 * dy;

void Bresenham(int x1, int y1, int x2, int y2)

int x, y, dx, dy, e, i, schimb;

int s1, s2;

int temp;

x = x1; y = y1;

dx = abs(x2 - x1); dy = abs(y2 - y1);

s1 = sign(x2 - x1);

s2 = sign(y2 - y1);

if (dy > dx)

temp = dx; dx = dy; dy = temp;

schimb = 1;

25

else

schimb = 0;

e = 2 * dy - dx;

for (i = 0; i < dx; i++)


while (e >= 0)

if (schimb)

x = x + s1;

else

y = y + s2;

e = e - 2 * dx;

if (schimb)

y = y + s2;

else

x = x + s1;

e = e + 2 * dy;

int random(int n)

return rand() % n;

int main(void)

int j;

int x, y;

initGraphics();

srand(time(NULL));

/*for (j = 0; j < 1000; j++)

x = random(getmaxx());

y = random(getmaxy());

RBresenham(x, y, x + random(getmaxx() - x), y + random(getmaxy() - y));

*/

for (j = 0; j < 1000; j++)

Bresenham(random(getmaxx()), random(getmaxy()), random(getmaxx()), random(getmaxy()));

return 0;

In figura 2.3 se pot vedea un numar de 100 de segmente de dreapta desenate ın fereastracurenta folosind functia ce implementeaza algoritmul lui Bersenham pentru trasarea uneilinii.

2.4 Exercitii

1. Sa se modifice programul pentru desenarea graficului functiei sin (x) astfel ıncat sa sepoata reprezenta graficele altor functii matematice:

26

Fig. 2.3: Segmente de dreapta desenate cu algoritmul lui Bresenham

(a) f(x) = x2 − 7x + 2, f : R→ R;

(b) f(x) = 5x3 − x2 + 9x− 1, f : R → R;

(c) f(x) = 12 log2 (x), f : (0,∞)→ R;

(d) f(x) = xln (x)

, f : (0,∞)→R;

(e) f(x) = ex, f : R→ R;

(f) f(x) = ex, f : R∗ →R;

(g) f(x) = 3x − x3, f : R→ R;

(h) f(x) = ln (x + 2)/ ln (2)− 2x + 2, f : (0,∞)→ R;

(i) f(x) = −2 ∗ x/(1 + x2)2 + (2 ∗ (1 + x4)− 2 ∗ x ∗ 4 ∗ x3)/(1 + x4)2, f : R→ R;

2. Sa se modifice programul transf2D.cpp pentru a permite salvarea coordonatelor punctelor(coordonate reale sau coordonate ecran) la un moment dat (dupa aplicarea mai multortransformari geometrice).

3. Sa se efectueze mai multe teste cu programul transf2D.cpp astfel ıncat figura ce secitete din fisierul de intrare sa fie:


• un hexagon;

• o linie poligonala ıchisa avand 10 puncte.

4. Sa se calculeze de cate ori opereaza mai repede functia IBresenham() fata de RBresenham().Sa se compare timpul de lucru al functiei Bresenham() fata de timpii de rulare core-spunzatori celorlalte doua functii, respectiv cu functia de biblioteca line().

5. Se considera un segment de dreapta determinat de punctele P1(0, 0) si P2(50, 50). Scrietiun program ce realizeaza urmatoarele:

27

(a) rotette segmentul ın jurul originii cu 30 de grade si apoi ıl translateaza cu 25 deunitati pe cele doua directii OX, respectiv OY .

(b) translateaza segmentul cu 25 de unitati pe cele doua directii OX si OY si apoi ılrotette cu 30 de grade ın jurul originii.

6. Sa se realizeze un program ce deseneaza un cerc prin aproximarea lui cu un poligonregulat cu n = 50 laturi.

28

Laboratorul 3

Transformari geometrice ın spatiu

3.1 Principalele transformari geometrice ın plan

Prezentam ın continuare programul transf3D.cpp ce implementeaza principalele transformarigeometrice ın spatiu (translatie, scalare, rotatie fata de axele Ox, Oy si Oz):


#include <conio.h>

#include <stdlib.h>

#include <math.h>

#define ZOOMIN_FACTOR 1.1

#define ZOOMOUT_FACTOR 0.9


float x, y, z;

POINT3D;


float x, y;

POINT2D;

typedef struct line

int p1, p2;

LINE;

typedef struct



float sx, sy;

POINT3D ps[4];

LINE Ox, Oy, Oz;

SYSTEM;

typedef enumOX = 0, OY = 1, OZ = 2 AXE;


int gd, gm;

gd = DETECT;

29





getch();

exit(1);

void init(SYSTEM* s)

s->xRmin = -100; s->xRmax = 100;

s->yRmin = -100; s->yRmax = 100;

s->xEmin = 0; s->xEmax = getmaxx();

s->yEmin = 0; s->yEmax = getmaxy();



s->ps[0].x = 0; s->ps[0].y = 0; s->ps[0].z = 0;

s->ps[1].x = 100; s->ps[1].y = 0; s->ps[1].z = 0;

s->ps[2].x = 0; s->ps[2].y = 100; s->ps[2].z = 0;

s->ps[3].x = 0; s->ps[3].y = 0; s->ps[3].z = 100;

s->Ox.p1 = 0; s->Ox.p2 = 1;

s->Oy.p1 = 0; s->Oy.p2 = 2;

s->Oz.p1 = 0; s->Oz.p2 = 3;

/**/void proiectie3D_2D(POINT3D p3d, POINT2D &p2d)

p2d.x = p3d.x - p3d.z * sqrt(2)/2;

p2d.y = p3d.y - p3d.z * sqrt(2)/2;

/**/

// proiectia perspectiva

/**void proiectie3D_2D(POINT3D p3d, POINT2D &p2d)

const int L = -1000;

p2d.x = L* p3d.x / (p3d.z + L);

p2d.y = L* p3d.y / (p3d.z + L);

**/

// proiectia ortografica



p2d.x = p3d.x;

p2d.y = p3d.y;

**/

// proiectia cabinet


30


const float xp = 0.433;

const float yp = 0.25;

const float zp = -1;

p2d.x = p3d.x - p3d.z/zp*xp;

p2d.y = p3d.y - p3d.z/zp*yp;

**/




//return (yr - s->yRmin) * s->sy + s->yEmin;

return s->yEmax - (yr - s->yRmin) * s->sy;




/***************** Transformari geometrice punct ********************/

void translatie(POINT3D* p, float dx, float dy, float dz)

p->x = p->x + dx;

p->y = p->y + dy;

p->z = p->z + dz;

void scalare(POINT3D* p, float sx, float sy, float sz)

p->x = p->x * sx;

p->y = p->y * sy;

p->z = p->z * sz;

float rad2grade(float alfa)

return alfa * 90 / M_PI;

void rotatie(POINT3D* p, float alfa, AXE axa)

float x, y, z;

switch(axa)

case OX: y = p->y * cos(alfa) + p->z * sin(alfa);

z = -p->y * sin(alfa) + p->z * cos(alfa);

p->y = y; p->z = z;

break;

case OY: x = p->x * cos(alfa) - p->z * sin(alfa);

z = p->x * sin(alfa) + p->z * cos(alfa);

p->x = x; p->z = z;

break;

31

case OZ: x = p->x * cos(alfa) + p->y * sin(alfa);

y = -p->x * sin(alfa) + p->y * cos(alfa);

p->x = x; p->y = y;

break;

;

/*****************************************************/

/***************** Transformari geometrice figura ********************/

void translatieFigura(int n, POINT3D* p, float dx, float dy, float dz)

int i;

for (i = 0; i < n; i++)

translatie(&p[i], dx, dy, dz);

void scalareFigura(int n, POINT3D* p, float sx, float sy, float sz)

int i;

for (i = 0; i < n; i++)

scalare(&p[i], sx, sy, sz);

void rotatieFigura(int n, POINT3D* p, float alfa, AXE axa)

int i;

for (i = 0; i < n; i++)

rotatie(&p[i], alfa, axa);

/*****************************************************/

void trans3Dto2D(int n, POINT3D* points3d, POINT2D* points2d)

int i;

for (i = 0; i < n; i++)

proiectie3D_2D(points3d[i], points2d[i]);

void real2ecran(int n, POINT2D* points, SYSTEM* s)

int i;

for (i = 0; i < n; i++)

real2ecran(&points[i], points[i], s);

void drawAxe(SYSTEM* s)

POINT2D p2d[4];

trans3Dto2D(4, s->ps, p2d);

real2ecran(4, p2d, s);

POINT2D pe1 = p2d[s->Ox.p1];

32

POINT2D pe2 = p2d[s->Ox.p2];


pe1 = p2d[s->Oy.p1];

pe2 = p2d[s->Oy.p2];


pe1 = p2d[s->Oz.p1];

pe2 = p2d[s->Oz.p2];


void drawFigure(POINT2D* points, int m, LINE* fig, SYSTEM* s)

int i;

POINT2D pe1, pe2;

for (i = 0; i < m; i++)

pe1 = points[fig[i].p1];

pe2 = points[fig[i].p2];


/*****************************************************/

int readChar(void)

int c;

c = getch();

if (!c)

c = getch();

return c;

void loop(int n, POINT3D *points3d, int m, LINE *fig, SYSTEM* s)

char ch;

int step = 3;

float alfa = 0.1;

AXE axac = OX;;

POINT2D *points2d;

points2d = (POINT2D*)malloc(sizeof(POINT2D) * n);


drawAxe(s);

trans3Dto2D(n, points3d, points2d);

real2ecran(n, points2d, s);

drawFigure(points2d, m, fig, s);

do

ch = readChar();


switch (ch)

33

case 72: if (axac == OZ)

translatieFigura(n, points3d, 0, 0, -step);

else

translatieFigura(n, points3d, 0, step, 0);

break;

case 80: if (axac == OZ)

translatieFigura(n, points3d, 0, 0, step);

else

translatieFigura(n, points3d, 0, -step, 0);

break;

case 77: translatieFigura(n, points3d, step, 0, 0);

break;

case 75: translatieFigura(n, points3d, -step, 0, 0);

break;

case ’+’: scalareFigura(n, points3d, ZOOMIN_FACTOR, ZOOMIN_FACTOR, ZOOMIN_FACTOR);

break;

case ’-’: scalareFigura(n, points3d, ZOOMOUT_FACTOR, ZOOMOUT_FACTOR, ZOOMOUT_FACTOR);

break;

case ’x’: axac = OX;

break;

case ’y’: axac = OY;

break;

case ’z’: axac = OZ;

break;

case ’q’: rotatieFigura(n, points3d, alfa, axac);

break;

case ’w’: rotatieFigura(n, points3d, -alfa, axac);

break;

;

trans3Dto2D(n, points3d, points2d);

real2ecran(n, points2d, s);


while(ch != 27);

void readInput(int *n, POINT3D **p, int *m, LINE **fig, SYSTEM* s)

FILE *f;

int i, u, v;

if ((f = fopen("fig3dA1.txt", "rt")) == NULL)



getch();

exit(1);

// se citeste numarul de puncte

fscanf(f,"%d", n);


// se citesc coordonatele reale ale punctelor

34

for (i = 0; i < *n; i++)

fscanf(f, "%f %f %f", &((*p)[i].x), &((*p)[i].y), &((*p)[i].z));

printf("%.2f %.2f %.2f\n", (*p)[i].x, (*p)[i].y, (*p)[i].z);

// se citeste numarul de segmente de dreapta ce compun figura

fscanf(f,"%d", m);

*fig = (LINE*)malloc(sizeof(LINE) * (*m));

// se citesc indicii punctelor capetelor segmentelor de dreapta

for (i = 0; i < *m; i++)

fscanf(f, "%d %d", &u, &v);

(*fig)[i].p1 = u-1;

(*fig)[i].p2 = v-1;

printf("%d %d\n", (*fig)[i].p1, (*fig)[i].p2);

fscanf(f, "%f %f %f %f", &s->xRmin, &s->xRmax, &s->yRmin, &s->yRmax);

printf("%.2f %.2f %.2f %.2f\n", s->xRmin, s->xRmax, s->yRmin, s->yRmax);

fscanf(f, "%f %f %f %f", &s->xEmin, &s->xEmax, &s->yEmin, &s->yEmax);



s->ps[1].x = s->xRmax; s->ps[1].y = 0; s->ps[1].z = 0;

s->ps[2].x = 0; s->ps[2].y = s->yRmax; s->ps[2].z = 0;

s->ps[3].x = 0; s->ps[3].y = 0; s->ps[3].z = s->xRmax;

fclose(f);

int main()

SYSTEM s;

int n;

POINT3D *points;

int m;

LINE* figura;

initGraphics();

init(&s);

readInput(&n, &points, &m, &figura, &s);

loop(n, points, m, figura, &s);

return 0;

Un exemplu de continut pentru fisierul de intrare ’fig3dA1.txt’ poate fi:

8

0 0 0

50 0 0

35

Fig. 3.1: Transformari geometrice ın spatiul 3D

50 50 0

0 50 0

0 0 50

50 0 50

50 50 50

0 50 50

12

1 2

2 3

3 4

4 1

5 6

6 7

7 8

8 5

1 5

2 6

3 7

4 8

-100.0 100.0 -100.0 100.0

0.0 500.0 0.0 400.0

In figura 3.1 este reprezentat cubul din fisierul de intrare, dupa ce a fost supus unoroperatii succesive de translatie, scalare si rotatie.

3.2 Exercitii

1. Desenati un poligon regulat cu n laturi, avand raza cercului circumscris r si centrul ınpunctul de coordonate C(x, y).

2. Desenati un poligon regulat stelat cu n laturi, avand raza cercului circumscris r sicentrul ın punctul de coordonate C(x, y).

36

Laboratorul 4

Curbe ın plan si spatiu. Reprezentaregrafica

4.1 Curbe ın spatiu

Vom prezenta ın continuare o aplic⁀ie ce deseneaza ın spatiu o suprafata generata de o functie[13].

Programul surfaces.cpp deseneaza o suprafata corespunzatoare functiei f(x, y) = sin√

x2 + y2,f : R× R→ R restrictionata la un domeniu de definitie.

#include <stdio.h>

#include <stdlib.h>

#include <conio.h>


#include <math.h>

#define NX 30

#define NY 30

#define ALFA 18

#define BETA -80

#define GAMA 0

const int a = -12;

const int b = 13;

const int c = -12;

const int d = 13;


float x, y;

POINT2D;

typedef struct



float sx, sy;

SYSTEM;


37

int gd, gm;

gd = DETECT;





getch();

exit(1);

/**********************************************/




return s->yEmax - (yr - s->yRmin) * s->sy;




//pe->y = round(getmaxy() - yreal2ecran(pr.y, s));

/**********************************************/

float f(float x, float y)

return sin(sqrt(x*x + y*y));

float grade2rad(int u)

return (u * M_PI / 180);

void update(float& min, float& max, float v, int flag)

if (flag)

min = v; max = v;

else

if (min > v)

min = v;

if (max < v)

max = v;

void computePoints(POINT2D points[][NY], SYSTEM& s)

float alfa, beta, gama;

float c1, c2, c3, s1, s2, s3;

float ux, uy;

38

float x, y, z;

int i, j;

alfa = grade2rad(ALFA); beta = grade2rad(BETA); gama = grade2rad(GAMA);

c1 = cos(alfa); c2 = cos(beta); c3 = cos(gama);

s1 = sin(alfa); s2 = sin(beta); s3 = sin(gama);

ux = abs(b-a)/(NX-1.0); uy = abs(d-c)/(NY-1.0);

x = a;

for (i = 0; i < NX; i++)

y = c;

for (j = 0; j < NY; j++)

z = f(x, y);

//proiectie punct 3D -> 2D

points[i][j].x = x * c1 + y * c2 + z * c3;

points[i][j].y = x * s1 + y * s2 + z * s3;

//actualizare bounding box

update(s.xRmin, s.xRmax, points[i][j].x, (i+j == 0));

update(s.yRmin, s.yRmax, points[i][j].y, (i+j == 0));

y = y + uy;

x = x + ux;

s.xEmin = 0; s.xEmax = getmaxx() - 100;

s.yEmin = 0; s.yEmax = getmaxy() - 100;

s.sx = (s.xEmax - s.xEmin) / (float)(s.xRmax - s.xRmin);

s.sy = (s.yEmax - s.yEmin) / (float)(s.yRmax - s.yRmin);

void drawPoints(POINT2D points[][NY], SYSTEM& s)

int i, j;

for (i = 0; i < NX; i++)

POINT2D pe;

real2ecran(&pe, points[i][0], &s);

moveto((int)pe.x, (int)pe.y);

for (j = 1; j < NY; j++)

real2ecran(&pe, points[i][j], &s);

lineto((int)pe.x, (int)pe.y);

for (j = 0; j < NY; j++)

POINT2D pe;

real2ecran(&pe, points[0][j], &s);

moveto((int)pe.x, (int)pe.y);

for (i = 1; i < NX; i++)

real2ecran(&pe, points[i][j], &s);

lineto((int)pe.x, (int)pe.y);

39

Fig. 4.1: Suprafata tridimensionala corespunzatoare functiei f(x, y)

int main()

POINT2D points[NX][NY];

SYSTEM s;

initGraphics();

computePoints(points, s);

drawPoints(points, s);

getch();

return 0;

Desenul proiectiei bidimensionale corespunzatoare suprafetei punctelor (x, y, z) unde z =f(x, y) este reprezentat ın figura 4.1.

4.2 Curbe Bezier. Algoritmul lui De Casteljau

O prezentare animata a constructiei acestor curbe poate fi urmarita la adresa https://www.

jasondavies.com/animated-bezier/.Programul castejau.cpp prezinta un program care construieste curbe Bezier 1 pentru o

multime de puncte folosind atat cat si algoritmul lui De’Casteljau2:

#include <stdio.h>

#include <conio.h>

#include <math.h>

1http://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/spline/Bezier/bezier-construct.html2http://pomax.github.io/bezierinfo/

40


#include <stack>

#define N 40

#define TRUE 1

#define FALSE 0

unsigned int n;

int pointsX[N];

int pointsY[N];

int stopAddVertices;


int gd, gm;

gd = DETECT;





getch();

exit(1);

/********************************************************************/

//Formula standard pentru curbele Bezier.

float bezier(int m, int* a, float t)

int i;

long comb;

float aux, powt;

powt = 1.0; comb = 1; aux = powt * comb * a[0];

for (i = 1; i <= m; i++)

powt = powt * t;

comb = comb * (m - i + 1) / i;

aux = aux * (1-t) + powt * comb * a[i];

return aux;

//Algoritmul lui De’Casteljau

float decastejau(int m, int* a, float t)

float ca[N];

int i, k;

for (i = 0; i <= m; i++)

ca[i] = a[i];

for (k = 1; k <= m; k++)

41

for (i = 0; i <= (m - k); i++)

ca[i] = (1 - t) * ca[i] + t * ca[i + 1];

return ca[0];

void drawCurve(int n, int ptx[], int pty[], float (*f)(int, int*, float))

float left, right;

int ixl, iyl, ixr, iyr;

int q;

std::stack<float> s;

left = 0; right = 1;

ixl = (int)round(f(n, ptx, left));

iyl = (int)round(f(n, pty, left));

while (TRUE)

putpixel(ixl, iyl, WHITE);

q = TRUE;

while (q)

ixr = (int)round(f(n, ptx, right));

iyr = (int)round(f(n, pty, right));

if ((abs(ixl - ixr) <= 1) && (abs(iyl - iyr) <= 1))

q = FALSE;

else

s.push(right);

right = (left + right) / 2;

q = TRUE;

left = right;

ixl = ixr; iyl = iyr;

if (s.empty())

break;

else

right = s.top();

s.pop();

putpixel(ixl, iyl, WHITE);

/********************************************************************/

void click_handler(int xp, int yp)

char text[3];

int err;

if (stopAddVertices)

return;

pointsX[n] = xp; pointsY[n] = yp;

n++;

rectangle(xp - 5, yp - 5, xp + 5, yp + 5);

42

itoa(n, text, err);

outtextxy(xp - 10, yp - 10, text);

int readChar(void)

int c;

c = getch();

if (!c)

c = getch();

return c;

void loop(void)

char ch;


n = 0;

registermousehandler(WM_LBUTTONDOWN, click_handler);

do

ch = readChar();

switch (ch)

case ’c’: n = 0;

cleardevice();


break;

case ’s’: stopAddVertices = TRUE;

drawCurve(n - 1, pointsX, pointsY, decastejau);

drawCurve(n - 1, pointsX, pointsY, bezier);

break;

;

while(ch != 27);

int main()

initGraphics();

loop();

return 0;

Rezultatul rularii programului de mai sus, desenul unei curbe Bezier generata de 9 puncte,este ilustrat ın figura 4.2.

4.3 Curbe spline

#include <stdio.h>

#include <stdlib.h>

#include <conio.h>


#include <math.h>

43

Fig. 4.2: Curba Bezier generata de n puncte

#define N 40

#define TRUE 1

#define FALSE 0

typedef struct coeficienti

float *a, *b, *c, *d;

COEFICIENTI;

int n;

float x[N], y[N];



int gd, gm;

gd = DETECT;





getch();

exit(1);

int readChar(void)

int c;

c = getch();

if (!c)

c = getch();

return c;

44


char text[3];


return;

n++;

x[n] = xp; y[n] = yp;


itoa(n, text, 10);


/*************************************************************/

float* alocare(int n, float* x)

if (x != NULL)

free(x);

x = (float*) malloc(sizeof(float) * (n+1));

return x;

void spline(int n, COEFICIENTI& cc, float *x)

int i, j;

float *h, *alfa, *miu, *l, * z;

h = alocare(n, NULL);

alfa = alocare(n, NULL);

miu = alocare(n, NULL);

l = alocare(n, NULL);

z = alocare(n, NULL);

cc.a = alocare(n, cc.a);

cc.b = alocare(n, cc.b);

cc.c = alocare(n, cc.c);

cc.d = alocare(n, cc.d);

for (i = 0; i <= n; i++)

cc.a[i] = x[i];

for (i = 0; i < n; i++)

h[i] = x[i+1] - x[i];

for (i = 1; i < n; i++)

alfa[i] = 3 * (cc.a[i+1] - cc.a[i] * 2 + cc.a[i-1]);

l[0] = 1; z[0] = 0; miu[0] = 0;

for (i = 1; i < n; i++)

l[i] = 4 - miu[i-1];

miu[i] = 1 / l[i];

z[i] = (alfa[i] - z[i-1]) / l[i];

l[n] = 1; z[n] = 0; cc.c[n] = 0;

for (i = n-1; i >= 0; i--)

45

cc.c[i] = z[i] - miu[i]*cc.c[i+1];

cc.b[i] = (cc.a[i+1] - cc.a[i]) - (cc.c[i+1] + 2* cc.c[i]) / 3;

cc.d[i] = (cc.c[i+1] - cc.c[i]) / 3;

free(z); free(l);

free(miu); free(alfa); free(h);

float f(COEFICIENTI* cc, int k, float x)

float x2, x3;

x2 = (x - k) * (x - k);

x3 = x2 * (x - k);

return cc->a[k] + cc->b[k] * (x - k) + cc->c[k] * x2 + cc->d[k] * x3;

void drawSpline(int n, COEFICIENTI* cx, COEFICIENTI* cy)

int i, j;

float xold, yold, xt, yt;

for (i = 0; i < n; i++)

xold = f(cx, i, i); yold = f(cy, i, i);

for (j = 1; j <= 50; j++)

xt = f(cx, i, i + (float)j/50);

yt = f(cy, i, i + (float)j/50);

line((int)round(xold), (int)round(yold), (int)round(xt), (int)round(yt));

xold = xt; yold = yt;

/*************************************************************/

void loop(void)

char ch;

COEFICIENTI cx, cy;



cx.a = NULL; cx.b = NULL; cx.c = NULL; cx.d = NULL;

cy.a = NULL; cy.b = NULL; cy.c = NULL; cy.d = NULL;

n = -1;

do

ch = readChar();

switch (ch)

case ’c’: cleardevice();

n = -1;


break;


spline(n, cx, x);

46

spline(n, cy, y);

drawSpline(n, &cx, &cy);

break;

;

while(ch != 27);

int main()

initGraphics();

loop();

return 0;

Un exemplu de curba spline poate fi urmarit ın figura 4.3.

Fig. 4.3: Curba spline generata de n puncte

4.4 Exercitii

1. Sa se realize cate un program pentru generarea urmatoarelor curbe:

(a) elipsa:

x(t) = a ∗ cos(t)

y(t) = b ∗ sin(t), 0 ≤ t ≤ 2 ∗ π, a, b ∈ R

(b) astroida:

x(t) = a ∗ cos3(t),

y(t) = b ∗ sin3(t), 0 ≤ t ≤ 2 ∗ π, a, b ∈ R;

(c) curbe spirografice

x(t) = a ∗ cos(t) + b ∗ cos(c ∗ t),

y(t) = a ∗ sin(t) + b ∗ sin(c ∗ t), 0 ≤ t ≤ 5 ∗ π, a, b, c ∈ R.

47

Laboratorul 5

Reprezentarea suprafetelor. Mascareasuprafetelor ascunse

5.1 Algoritmul lui Warnock

Programul warnock.cpp implementeaza algoritmul lui Warnock 1:


#include <conio.h>

#include <stdlib.h>

#include <math.h>

#include <stack>

#define TRUE 1

#define FALSE 0


float x, y, z;

POINT3D;

typedef struct poligon

int firstPointIndex;

int pointsNo;

int color;


float a, b, c, d;

POLIGON;

typedef struct patrat

int x, y;

int width;

PATRAT;

const int FMAX = 512;//256;


int gd, gm;

1http://labs.cs.upt.ro/labs/Graphics/html/SPG/Download/C2_Z-buffer_Warnock.pdf

48

gd = DETECT;





getch();

exit(1);

/*****************************************************/

//actualizeaza coordonatele bounding box-ului corespunzator poligonului poly

void updatePoligonBoundingBox(POLIGON& poly, POINT3D& p, int first)

if (first)

poly.xRmin = p.x; poly.xRmax = p.x;

poly.yRmin = p.y; poly.yRmax = p.y;

else

if (p.x < poly.xRmin)

poly.xRmin = p.x;

if (p.x > poly.xRmax)

poly.xRmax = p.x;

if (p.y < poly.yRmin)

poly.yRmin = p.y;

if (p.y > poly.yRmax)

poly.yRmax = p.y;

/* calculeaza parametrii a, b, c, d corespunzatori ecuatiei generale

a planului, ax + by + cz + d = 0, determinat de punctele poligonului poly */

void parameters(POLIGON& poly, POINT3D *points)

float fa, fb, fc;

int i, j;

int n = poly.pointsNo;

int first = poly.firstPointIndex;

fa = 0.0; fb = 0.0; fc = 0.0;

for (i = first; i < first + n; i++)

j = first + ((i + 1 - first) % n);

fa = fa + (points[i].y - points[j].y) * (points[i].z + points[j].z);

fb = fb + (points[i].z - points[j].z) * (points[i].x + points[j].x);

fc = fc + (points[i].x - points[j].x) * (points[i].y + points[j].y);

poly.a = fa; poly.b = fb; poly.c = fc;

poly.d = -(fa * points[first].x + fb * points[first].y + fc * points[first].z);

void readInput(int *n, POINT3D **p, int *m, POLIGON **fig)

FILE *f;

int i, j;

49

int currentPointIndex = 0;

if ((f = fopen("warnock3.txt", "rt")) == NULL)



getch();

exit(1);

// se citeste numarul total de puncte si numarul de poligoane

fscanf(f,"%d %d", n, m);


*fig = (POLIGON*)malloc(sizeof(POLIGON) * (*m));

// se citesc coordonatele reale ale punctelor din cadrul fiecarui poligon

for (i = 0; i < *m; i++)

// se citesc numarul de puncte al poligonului si culoarea poligonului

fscanf(f, "%d %d", &((*fig)[i].pointsNo), &((*fig)[i].color));

(*fig)[i].firstPointIndex = currentPointIndex;

for (j = 0; j < (*fig)[i].pointsNo; j++)

// se citesc coordonatele x, y, z ale unui punct

fscanf(f, "%f %f %f", &((*p)[currentPointIndex + j].x),

&((*p)[currentPointIndex + j].y),

&((*p)[currentPointIndex + j].z));

//se actualizeaza coordonatele bounding box-ului poligonului

updatePoligonBoundingBox((*fig)[i], (*p)[currentPointIndex + j], (j == 0));

printf("%.2f %.2f %.2f \n", ((*p)[currentPointIndex + j].x),

((*p)[currentPointIndex + j].y),

((*p)[currentPointIndex + j].z));

//se calculeaza val parametrilor planului poligonului

parameters((*fig)[i], *p);

currentPointIndex += (*fig)[i].pointsNo;

fclose(f);

/* testare rapida - se verifica daca dreptunghiul de coordonate (p.x, p.y),

(p.x + p.z - 1, p.y + p.z - 1) intersecteaza bounding box-ul

corespunzator unui poligon */

int testRectIntersection(POLIGON& poly, PATRAT& p)

float xst, xdr, ydown, yup;

xst = p.x; xdr = p.x + p.width - 1;

ydown = p.y; yup = p.y + p.width - 1;

if (poly.xRmin > xdr)

return FALSE;

if (poly.xRmax < xst)

return FALSE;

if (poly.yRmin > yup)

return FALSE;

50

if (poly.yRmax < ydown)

return FALSE;

return TRUE;

// se deseneaza patratul de coordonate stanga-sus si dreapta-jos (p.x, p.y),

//(p.x + p.width - 1, p.y + p.width - 1)

void drawRect(PATRAT p, int color)

if (p.width > 1)

setfillstyle(SOLID_FILL, color);

bar(p.x, p.y, (p.x + p.width - 1), (p.y + p.width - 1));

else

putpixel(p.x, p.y, color);

// se salveaza pe stiva trei valori reale a, b, c

void push(std::stack<PATRAT>& s, int a, int b, int c)

PATRAT p;

p.x = a; p.y = b; p.width = c;

s.push(p);

/* se calculeaza valoarea adancimii z, pentru un punct (xc, yc, z)

ce apartine planului corespunzator poligonului poly */

float computeDepth(float xc, float yc, POLIGON& poly)

return round(-(xc * poly.a + yc * poly.b + poly.d) / poly.c);

float scalarProduct(float p1x, float p1y, float p2x, float p2y, float p3x, float p3y)

return (p2x - p1x)*(p3y - p1y) - (p2y - p1y)*(p3x - p1x);

/* se determina poligonul cel mai apropiat de punctul de vedere; poligonul

al carui plan intersectat cu dreapta x = xc, y = yc, corespunde punctului

de coordonata z maxima */

int findClosestPoligon(PATRAT p, int m, POLIGON* fig, POINT3D* points)

float p1x, p1y, p2x, p2y;

float x, y, z, zmax;

int poligonNo, i, j, k;

int isPointInside;

zmax = 0; poligonNo = -1;

x = p.x + p.width / 2.0; y = p.y + p.width / 2.0;

for (i = 0; i < m; i++)

j = fig[i].firstPointIndex;

int limit = fig[i].firstPointIndex + fig[i].pointsNo - 1;

//se verifica daca centrul patratului se afla in interiorul poligonului fig[i]

isPointInside = TRUE;

while ((j <= limit) && (isPointInside))

k = (j < limit) ? j+1 : fig[i].firstPointIndex;

p1x = points[j].x; p1y = points[j].y;

51

p2x = points[k].x; p2y = points[k].y;

if (scalarProduct(p1x, p1y, p2x, p2y, x, y) > 0)

isPointInside = FALSE;

else

j++;

if (isPointInside)

z = computeDepth(x, y, fig[i]);

if (z > zmax)

zmax = z; poligonNo = i;

return poligonNo;

void warnock(int n, POINT3D *p, int m, POLIGON *fig)

std::stack<PATRAT> pStack;

int i, disjunct;

int bkColor = BLACK;

push(pStack, 0, 0, FMAX);

while (!pStack.empty())

PATRAT tmp = pStack.top();

pStack.pop();

i = 0; disjunct = TRUE;

while ((i < m) && (disjunct == TRUE))

disjunct = !testRectIntersection(fig[i], tmp);

i++;

if (disjunct == FALSE)

if (tmp.width > 1)

int cota = tmp.width / 2;

push(pStack, tmp.x + cota, tmp.y + cota, cota);

push(pStack, tmp.x, tmp.y + cota, cota);

push(pStack, tmp.x + cota, tmp.y, cota);

push(pStack, tmp.x, tmp.y, cota);

else

i = findClosestPoligon(tmp, m, fig, p);

if (i < 0)

drawRect(tmp, bkColor);

else

drawRect(tmp, fig[i].color);

else

drawRect(tmp, bkColor);

52

/*****************************************************/

int main()

int n;

POINT3D *points;

int m;

POLIGON *figura;

initGraphics();

readInput(&n, &points, &m, &figura);

warnock(n, points, m, figura);

getch();

return 0;

Structura fisierului ce contine datele de intrare este urmatoarea:

n m

k1 c1

x11 y11 z11

x12 y12 z12

...

x1k1 x1k1 y1k1

k2 c2

x21 y21 z21

x22 y22 z22

...

x2k2 y2k2 z2k2

...

unde n - numarul de puncte total al scenei, m - numarul de suprafete ce formeaza scena,k1 - numarul de puncte al primului poligon, c1 - culoarea de umplere a primului poligon,x1 y1 z1 coordonatele ın spatiu 3D ale celor k1 puncte ce formeaza poligonul primeisuprafete, k2 - numarul de puncte al celui de-al doilea poligon, c2 - culoarea de umplerea celui de-al doilea poligon, x2 y2 z2 coordonatele ın spatiu 3D ale celor k2 puncte ceformeaza poligonul celei de-a doua suprafete etc.

Observatia 5.1 Punctele reprezentand varfurile unui poligon ce determina o suprafata tre-buie alese astfel ıncat sa fie coplanare.

Punctele reprezentand varfurile unui poligon ce determina o suprafata trebuie specificateın ordine invers trigonometrica.

Un exemplu de fisier pentru datele de intrare este prezentat ın continuare:

11 3

4 1

80 30 20

80 250 20

200 250 20

200 30 20

4 15

50 120 10

53

Fig. 5.1: Algoritmul lui Warnock

50 200 10

240 200 10

240 120 10

3 8

150 150 25

200 250 5

250 100 5

Rezultatul obtinut ın urma rularii programului anterior poate fi observat ın figura 5.1.

5.2 Metoda ZBuffer - TBD

5.3 Exercitii

1.

54

Fig. 5.2: Algoritmul lui Warnock

55

Laboratorul 6

Probleme elementare de Algoritmicageometrica

6.1 Intersectii de intervale

6.2 Intersectii de segmente de dreapta

Fig. 6.1: Intersectia a doua segmente de dreapta [AB] si [CD]

Sa notam cu d1 si d2 cele doua drepte existente ın figura 6.1. Ecuatiile generale ale celordoua drepte sunt:

d1 : a1 · x + b1 · y + c1 = 0 (6.1)

d2 : a2 · x + b2 · y + c2 = 0, a1, a2, b1, b2, c1, c2 ∈ R (6.2)

Definitia 6.1 Fie trei puncte distincte oarecare ın plan A(x1, y1), B(x2, y2), C(x3, y3) ∈ R2.

Notam cu ∆(A, B, C) urmatorul determinant:

∆(A, B, C) =

∣

∣

∣

∣

∣

∣

1 1 1x1 x2 x3

y1 y2 y3

∣

∣

∣

∣

∣

∣

= (x2 − x1) · (y3 − y1)− (x3 − x1) · (y2 − y1) (6.3)

Pozitia punctului C fata de segmentul [AB] poate fi caracterizata cu ajutorul valorii ∆(A, B, C)astfel:

1. punctul C este situat pe dreapta AB ⇔ ∆(A, B, C) = 0;

56

2. punctul C este situat ın dreapta segmentului orientat−→AB ⇔ ∆(A, B, C) < 0;

3. punctul C este situat ın stanga segmentului orientat−→AB ⇔ ∆(A, B, C) > 0.

Altfel spus, semnul valorii rezultate ın urma evaluarii expresiei ∆(A, B, C) poate fi utilizatpentru a determina orientarea varfurilor ce formeaza triunghiul ABC.

Definitia 6.2 Punctele A, B, C se spune ca sunt orientate ın sens trigonometric dacasign(A, B, C) > 0 si sunt orientate ın sens invers trigonometric daca sign(A, B, C) < 0.

Punctele A, B, C sunt coliniare daca si numai daca sign(A, B, C) = 0.

Conditia pentru ca segmentele de dreapta [AB] si [CD] sa se intersecteze ıntr-un punctaflat ın interiorul lor, poate fi dedusa utilizand orientarea varfurilor. Astfel segmentul [AB]intersecteaza segmentul [CD] daca dreapta AB (dreapta ce trece prin punctele A si B)separa punctele C si D, iar dreapta CD separa punctele A si B. Aceasta conditie se traduceın urmatoarea expresie:

sign(A, B, C) · sign(A, B, D) < 0 ∧ sign(C, D, A) · sign(C, D, B) < 0 (6.4)

Pentru un segment de dreapta [AB] avem ecuatia parametrica:

p(t) = (1− t) · P A + t · P B, t ∈ [0, 1]. (6.5)

Aceasta ecuatie se poate scrie, pentru fiecare dintre coordonatele x si y, astfel:

px(t) = (1− t) · P Ax + t · P B

x , t ∈ [0, 1]

py(t) = (1− t) · P Ay + t · P B

y .

Intersectia a doua segmente [AB] si [CD] se poate determina ca solutie a sistemului deecuatii:

p(t) = q(s), unde

p(t) = (1− t) · P A + t · P B,

q(s) = (1− s) · P C + s · P D, s ∈ [0, 1].

sau

(1− t) · x1 + t · x2 = (1− s) · x3 + s · x4,

(1− t) · y1 + t · y2 = (1− s) · y3 + s · y4,

unde avem A(x1, y1), B(x2, y2), C(x3, y3) si D(x4, y4).Segmentele [AB] si [CD] se intersecteaza daca sistemul are solutia (t′, s′) iar t′ ∈ [0, 1] si

s′ ∈ [0, 1].Ecuatiile anterioare se mai pot scrie sub forma:

x1 + t · (x2 − x1) = x3 + s · (x4 − x3),

y1 + t · (y2 − y1) = y3 + s · (y4 − y3),

sau

t · (x2 − x1)− s · (x4 − x3) = x3 − x1,

t · (y2 − y1)− s · (y4 − y3) = y3 − y1.

57

Vom folosi relatiile lui Cramer pentru rezolvarea sistemului de mai sus. Astfel solutiilesunt

t =∆t

∆si s =

∆s

∆

unde

∆ =

∣

∣

∣

∣

(x2 − x1) (x3 − x4)(y2 − y1) (y3 − y4)

∣

∣

∣

∣

, ∆t =

∣

∣

∣

∣

(x3 − x1) (x3 − x4)(y3 − y1) (y3 − y4)

∣

∣

∣

∣

, ∆s =

∣

∣

∣

∣

(x2 − x1) (x3 − x1)(y2 − y1) (y3 − y1)

∣

∣

∣

∣

.

Programul urmator implementeaza doua functii: una ce determina intersectia dintredoua segmente de dreapta, daca exista, (int segmentIntersection(POINT2D, POINT2D,

POINT2D, POINT2D, POINT2D&)) iar cealalta pentru a determina intersectia dintre douadrepte (int lineIntersection(POINT2D, POINT2D, POINT2D, POINT2D, POINT2D&)).

#include <stdio.h>

#include <stdlib.h>

#include <conio.h>

#include <dos.h>


#define N 100

#define TRUE 1

#define FALSE 0


float x, y;

POINT2D;

unsigned int n;

POINT2D points[N];



int gd, gm;

gd = DETECT;





getch();

exit(1);

/**************************************************/

int segmentIntersection(POINT2D p1, POINT2D p2,

POINT2D p3, POINT2D p4, POINT2D& pi)

float c21x, c21y, c43x, c43y, c13x, c13y;

float det, dets, dett, t;

c21x = p2.x - p1.x;

c21y = p2.y - p1.y;

c43x = p4.x - p3.x;

58

c43y = p4.y - p3.y;

det = c21x * c43y - c43x * c21y;

if (det == 0)

return 0;

c13x = p1.x - p3.x;

c13y = p1.y - p3.y;

dets = c21x * c13y - c21y * c13x;

if ((dets < 0) == (det > 0))

return -1;

dett = c43x * c13y - c43y * c13x;

if ((dett < 0) == (det > 0))

return -1;

if (((dets > det) == (det > 0)) || ((dett > det) == (det > 0)))

return -1;

t = dett / det;

pi.x = p1.x + t * c21x;

pi.y = p1.y + t * c21y;

return 1;

int lineIntersection(POINT2D p1, POINT2D p2,

POINT2D p3, POINT2D p4, POINT2D& pi)

float c21x, c21y, c43x, c43y, c13x, c13y;

float det, dett, t;

c21x = p2.x - p1.x;

c21y = p2.y - p1.y;

c43x = p4.x - p3.x;

c43y = p4.y - p3.y;

det = c21x * c43y - c43x * c21y;

if (det == 0)

return 0;

c13x = p1.x - p3.x;

c13y = p1.y - p3.y;

dett = c43x * c13y - c43y * c13x;

t = dett / det;

pi.x = p1.x + t * c21x;

pi.y = p1.y + t * c21y;

return 1;

/**************************************************/


59

char text[3];


return;

points[n].x = xp; points[n].y = yp;

n++;


itoa(n, text, 10);


if (n % 2 == 0)

line((int)points[n-2].x, (int)points[n-2].y,

(int)points[n-1].x, (int)points[n-1].y);

if (n == 4)

POINT2D pi;

stopAddVertices = true;

if (segmentIntersection(points[0], points[1], points[2], points[3], pi) == 1)

rectangle((int)pi.x - 5, (int)pi.y - 5, (int)pi.x + 5, (int)pi.y + 5);

//draw lines

/*line((int)pi.x, (int)pi.y, (int)points[0].x, (int)points[0].y);

line((int)pi.x, (int)pi.y, (int)points[2].x, (int)points[2].y);*/

int readChar(void)

int c;

c = getch();

if (!c)

c = getch();

return c;

void loop(void)

char ch;

//schimba culoarea de fundal si culoarea de desenare

setbkcolor(WHITE);

setcolor(BLACK);

cleardevice();


n = 0;


do

ch = readChar();

switch (ch)

case ’c’: n = 0;

cleardevice();

60


break;

;

while(ch != 27);

int main()

initGraphics();

loop();

return 0;

6.3 Apartenenta la interiorul unui poligon

Programul urmator prezinta implementarea algoritmului de verificare a apartenentei unuipunct la interiorul unui poligon:

#include <stdio.h>

#include <stdlib.h>

#include <conio.h>

#include <dos.h>

#include <math.h>


#define N 100

#define TRUE 1

#define FALSE 0


double x, y;

POINT2D;

unsigned int n;

POINT2D points[N];



int gd, gm;

gd = DETECT;





getch();

exit(1);

/*************************************************************/

61

int testInPoligon(int n, POINT2D* points, double xc, double yc)

double minX = points[0].x;

double maxX = points[0].x;

double minY = points[0].y;

double maxY = points[0].y;

int i, j;

for (i = 1; i < n; i++)

minX = std::min(minX, points[i].x);

maxX = std::max(maxX, points[i].x);

minY = std::min(minY, points[i].y);

maxY = std::max(maxY, points[i].y);

if (xc < minX || xc > maxX || yc < minY || yc > maxY)

return FALSE;

// http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html

int inside = FALSE;

for (i = 0, j = n-1; i < n; j = i++)

if ((points[i].y > yc) != (points[j].y > yc) &&

(xc < (points[j].x - points[i].x) * (yc - points[i].y) / (points[j].y - points[i].y)

+ points[i].x))

inside = !inside;

return inside;

/*************************************************************/

int readChar(void)

int c;

c = getch();

if (!c)

c = getch();

return c;




if (testInPoligon(n, points, xp, yp) > 0)

outtextxy (10, 10, "Punctul se afla in interiorul poligonului.");

else

outtextxy (10, 10, "Punctul se afla in exteriorul poligonului.");

else


n++;

if (n > 1)

62

line(xp, yp, (int)points[n-2].x, (int)points[n-2].y);


void loop(void)

char ch;


setbkcolor(WHITE);

setcolor(BLACK);

cleardevice();



n = 0;

do

ch = readChar();

switch (ch)

case ’t’: line((int)points[n-1].x, (int)points[n-1].y,

(int)points[0].x, (int)points[0].y);


break;


n = 0;


;

while(ch != 27);

int main()

initGraphics();

loop();

return 0;

In figura 6.2 este prezentat un exemplu de verificare a apartenentei unui punct la interiorulunui poligon oarecare.

O alta varianta de verificare daca un punct se afla ın interiorul unui poligon este data demetoda urmatoare1:

#define TWOPI 6.283185307179586476925287


double x, y;

POINT2D;

/*

* Calculeaza unghiul dintre doi vectori din plan: unghiul calculat este cel

* dintre vectorul 1 si vectorul 2, in sens trigonometric pozitiv.

1http://paulbourke.net/geometry/polygonmesh/

63

Fig. 6.2: Verificarea apartenentei unui punct la interiorul unui poligon

* Rezultatul calculat are valoarea cuprinsa intre -PI si PI.

*/

double Angle2D(double x1, double y1, double x2, double y2)

double dtheta, theta1, theta2;

theta1 = atan2(y1, x1);

theta2 = atan2(y2, x2);

dtheta = theta2 - theta1;

while (dtheta > M_PI)

dtheta -= TWOPI;

while (dtheta < -M_PI)

dtheta += TWOPI;

return (dtheta);

int next(int u, int m)

return (u + 1) % m;

int testInPoligon(int n, POINT2D* points, double xc, double yc)

int i;

double angle = 0;

double x1, y1, x2, y2;

for (i = 0; i < n; i++)

x1 = points[i].x - xc;

y1 = points[i].y - yc;

x2 = points[next(i, n)].x - xc;

y2 = points[next(i, n)].y - yc;

64

angle += Angle2D(x1, y1, x2, y2);

if (fabs(angle) < M_PI)

return FALSE;

else

return TRUE;

6.4 Verificarea daca un poligon este convex

In programul urmator este implementat un algoritm de verificare daca un poligon este concavsau convex:

#include <stdio.h>

#include <stdlib.h>

#include <conio.h>

#include <dos.h>


#define N 100

#define TRUE 1

#define FALSE 0


float x, y;

POINT2D;

unsigned int n;

POINT2D points[N];



int gd, gm;

gd = DETECT;





getch();

exit(1);

/*****************************************************/

// semnul unei valori reale

int sign(float x)

if (x < 0)

return -1;

65

else

return 1;

float scalarProduct(POINT2D p1, POINT2D p2, POINT2D p3)

return (p2.x - p1.x)*(p3.y - p2.y) - (p2.y - p1.y)*(p3.x - p2.x);

int next(int u, int m)

return (u + 1) % m;

int testPoligonConvexity(int n, POINT2D* p)

int test = TRUE;

int i, j, k;

int initSign, cSign;

for (i = 0, initSign = 0; i < n; i++)

j = next(i, n);

k = next(j, n);

cSign = sign(scalarProduct(points[i], points[j], points[k]));

if (initSign == 0)

initSign = cSign;

else

if (initSign != cSign)

return FALSE;

return TRUE;

/*****************************************************/

int readChar(void)

int c;

c = getch();

if (!c)

c = getch();

return c;



return;


n++;

if (n > 1)

line(xp, yp, (int)points[n-2].x, (int)points[n-2].y);


66

Fig. 6.3: Un poligon concav

void loop(void)

char ch;



n = 0;

do

ch = readChar();

switch (ch)

case ’t’: line((int)points[n-1].x, (int)points[n-1].y,

(int)points[0].x, (int)points[0].y);


if (testPoligonConvexity(n, points) > 0)

outtextxy (10, 10, "Poligon convex!");

else

outtextxy (10, 10, "Poligon concav!");

break;


n = 0;


;

while(ch != 27);

int main()

initGraphics();

loop();

return 0;

In figura 6.3 este reprezentat un poligon concav.

67

Laboratorul 7

Probleme de intersectii multiple desegmente

7.1 Problema ”Vanatorii de fantome”

Un grup de n vanatori de fantome se lupta cu n fantome. Fiecare vanator de fantome(Ghostbuster) este ınarmat cu pusca cu protoni, care trage cu un flux catre o fantoma,conducand la eliminarea acesteia. Un flux merge ın linie dreapta si se termina atunci candloveste o fantoma.

Vanatorii de fantome decid sa aplice o strategie de lupta. La ınceput fiecare vanator ısiva alege cate o fantoma, formand n perechi vanator - fantoma. Simultan, fiecare vanatorde fantome va trage un jet catre fantoma lui. Deoarece este foarte periculos atunci canddoua fluxuri se intersecteaza, vanatorii de fantome trebuie sa ısi aleaga asocierile astfel ıncatatunci cand ıncep sa traga sa nu existe fluxuri ce se intersecteaza.

Cu alte cuvinte, cunoscandu-se pozitiile vanatorilor de fantome si ale fantomelor, sa seidentifice o modalitate de a asocia fiecare vanator de fantome cu cate o fantoma, astfelıncat segmentele de linii care unesc fiecare vanator de fantome cu fantoma asociata sa nu seintersecteze.

Presupunem ca pozitia fiecarui vanator de fantome si a fiecarei fantome este un punct ınplan si ca nu exista trei pozitii coliniare.

Se va prezenta o aplicatie care gaseste o solutie pentru cerinta acestei probleme. Se vorgenera ın mod aleator (pseudo-aleator atata timp cat vom folosi un generator de numerepseudo-aleatoare implementat ın librariile limbajului C/C++) coordonatele punctelor undese afla cate un vanator de fantome sau o fantoma.

Strategia aleasa pentru a fi implementata aici este similara, de exemplu, cu modul de lucrula metoda de sortare prin interschimbare: atata timp cat se ıntampla un eveniment (ın catzulde fata atata timp cat mai exista doua perechi vanator - fantoma astfel ıncat linia trasoare dela primul vanator de fantome se intersecteaza cu linia trasoare de la cel de-al doilea vanatorde fantome) se produce interschimbarea acelor elemente (se interschimba fantomele ın cadrulcelor doua perechi: astfel daca consideram perechile V1 − F1 si V2 − F2 dupa interschimbarevom avea perechile V1 − F2 si V2 − F1).

//http://courses.csail.mit.edu/6.006/spring11/psets/ps7_sol.pdf

//http://www.cs.umd.edu/Outreach/hsContest97/questions/node8.html


#include <stdio.h>

68

#define NMAX 55

#define EPS 3


int x, y;

POINT2D;

typedef struct segment

int p1, p2;

SEGMENT;


int gd, gm;

gd = DETECT;





getch();

exit(1);

int exists(int m, POINT2D a[], int x, int y)

int i;

for (i = 0; i < m; i++)

if ((abs(a[i].x - x) <= EPS) || (abs(a[i].y - y) <= EPS))

return 1;

return 0;

void generate(int n, POINT2D ghosts[], POINT2D busters[])

int x, y;

int maxx = getmaxx();

int maxy = getmaxy();

int nghosts = 0;

int nbusters = 0;

srand(time(NULL));

while (nghosts < n || nbusters < n)

do

x = rand() % maxx;

y = rand() % maxy;

while (exists(nghosts, ghosts, x, y) || exists(nbusters, busters, x, y));

ghosts[nghosts].x = x;

ghosts[nghosts].y = y;

nghosts++;

do

69

x = rand() % maxx;

y = rand() % maxy;

while (exists(nghosts, ghosts, x, y) || exists(nbusters, busters, x, y));

busters[nbusters].x = x;

busters[nbusters].y = y;

nbusters++;

void init(int m, SEGMENT pairs[])

int i;

for (i = 0; i < m; i++)

pairs[i].p1 = i;

pairs[i].p2 = i;

float sign(POINT2D a, POINT2D b, POINT2D c)

float value = (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);

return (value >= 0) ? ((value > 0)? 1:0) : -1;

bool hasIntersection(POINT2D a, POINT2D b, POINT2D c, POINT2D d)

if ((sign(a, b, c) * sign(a, b, d) <= 0) && (sign(c, d, a) * sign(c, d, b) < 0) ||

(sign(a, b, c) * sign(a, b, d) < 0) && (sign(c, d, a) * sign(c, d, b) <= 0))

return true;

else

return false;

void solution(int n, POINT2D ghosts[], POINT2D busters[], SEGMENT pairs[])

int i, j, k;

bool swap;

init(n, pairs);

for(i = 0; i < n; i++)

setcolor(BLUE);

rectangle(ghosts[pairs[i].p1].x-3, ghosts[pairs[i].p1].y-3,

ghosts[pairs[i].p1].x+3, ghosts[pairs[i].p1].y+3);

setcolor(YELLOW);

rectangle(busters[pairs[i].p2].x-3, busters[pairs[i].p2].y-3,

busters[pairs[i].p2].x+3, busters[pairs[i].p2].y+3);

setcolor(WHITE);

line(ghosts[pairs[i].p1].x, ghosts[pairs[i].p1].y,

busters[pairs[i].p2].x, busters[pairs[i].p2].y);


do

swap = false;

70

for (i = 0; i < n-1; i++)

for (j = i+1; j < n; j++)

if (hasIntersection(ghosts[pairs[i].p1], busters[pairs[i].p2],

ghosts[pairs[j].p1], busters[pairs[j].p2]))



line(ghosts[pairs[j].p1].x, ghosts[pairs[j].p1].y,

busters[pairs[j].p2].x, busters[pairs[j].p2].y);

swap = true;

k = pairs[i].p1; pairs[i].p1 = pairs[j].p1; pairs[j].p1 = k;

delay(100);



line(ghosts[pairs[j].p1].x, ghosts[pairs[j].p1].y,

busters[pairs[j].p2].x, busters[pairs[j].p2].y);

getch();

while (swap);

int main()

int n;

POINT2D ghosts[NMAX], busters[NMAX];

SEGMENT pairs[NMAX];

printf("Dati numarul de perechi (1-50):"); scanf("%d", &n);

initGraphics();

generate(n, ghosts, busters);

solution(n, ghosts, busters, pairs);

getch();

return 0;

7.2 Un algoritm

71

Laboratorul 8

Acoperiri convexe ın plan. AlgoritmiiGraham si Jarvis

Definitia 8.1 Fie A, B ∈ Rn. Se numeste segment ınchis [AB] multimea combinatiilor

convexe dintre A si B:

[AB] = (1− t)A + tB|t ∈ [0, 1] = αA + βB|α, β ∈ [0, 1], α + β = 1. (8.1)

t = 0 ⇒ (1− t)A + tB = (1− 0) ·A + 0 ·B = A

t = 1 ⇒ (1− 1)A + 1B = (1− 1) · A + 1 · B = B

t =1

2⇒ (1− t)A + tB = (1−

1

2) ·A +

1

2· B =

1

2(A + B)mijlocul segmentului [AB].

Definitia 8.2 O multime M ⊂ Rn este convexa daca oricare ar fi A, B ∈ M, segmentul

[AB] este inclus ın M.

M⊂ Rn convexa ⇔ ∀A, B ∈M, ∀t ∈ [0, 1] avem (1− t)A + tB ∈M (8.2)

Observatia 8.1 Intersectia mai multor multimi convexe este o multime convexa.

Fie X o multime oarecare de puncte din Rn, finita sau infinita. O combinatie convexa de

puncte din X este un punct:

P = α1A1 + α2A2 + . . . + αmAm, α1, α2, . . . , αn ∈ [0, 1],

n∑

i=1

αi = 1, Ai ∈ Rn. (8.3)

Multimea tuturor combinatiilor convexe din X este o multime convexa numita acoperireaconvexa a multimii finite X.

Acoperirea convexa a unei multimi finite X, notata conv(X), este:

• intersectia tuturor multimilor convexe ce contin X;

• cea mai mica multime convexa (ın sensul incluziunii) ce contine multimea X.

Conv(X) este un politop convex:

• n = 1⇒ Conv(X) este un segment ;

72

• n = 2⇒ Conv(X) este un poligon;

• n = 3⇒ Conv(X) este un poliedru.

Poliedrul reprezinta o generalizare a poligonului din spatiul bidimensional ın spatiul tridi-mensional: o regiune din spatiu marginita de un numar finit de suprafete poligonale undeaceste suprafete poligonale sunt fie disjuncte, fie au ın comun muchii si varfuri.

Problema: fiind dat un numar n de puncte ın plan, Ai ∈ R2, sa se determine acoperirea

convexa a multimii X = A1, A2, . . . , An. Din ceea ce am prezentat avem ca acoperireaconvexa a multimii X este un poligon convex P.

8.1 Un algoritm simplu de determinare a acoperirii

convexe a unei multimi de puncte

In continuare se prezinta implementarea unui algoritm simplu de determinare a acopeririiconvexe a unei multimi de puncte oarecare din plan:

#include <stdio.h>

#include <stdlib.h>

#include <conio.h>

#include <dos.h>


#define N 40

#define TRUE 1

#define FALSE 0


float x, y;

POINT2D;

unsigned int n;

POINT2D points[N];



int gd, gm;

gd = DETECT;





getch();

exit(1);


char text[3];

73


return;


n++;


itoa(n, text, 10);


int readChar(void)

int c;

c = getch();

if (!c)

c = getch();

return c;

/*******************************************************/

/* Se calculeaza centrul de greutate al multimii de puncte. */

void computeCenter(int n, POINT2D points[], float& xc, float& yc)

int i;

xc = 0.0f; yc = 0.0f;

for (i = 0; i < n; i++)

xc += points[i].x;

yc += points[i].y;

xc = xc/n;

yc = yc/n;

int sign(float x)

if (x < 0)

return -1;

else

if (x > 0)

return 1;

else

return 0;



/* Se verifica daca segmentul de dreapta [pi, pj] apartine acoperirii convexe.

Un segment de dreapta se spune ca apartine acoperirii convexe daca toate

celelalte puncte se afla in acelasi semiplan cu centrul de greutate (xc, yc)

al multimii de puncte. */

int lineofconvexhull(int n, POINT2D points[], float xc, float yc, int pi, int pj)

74

float a, b;

float db, dk, di, dj;

int k;

POINT2D pc;

pc.x = xc; pc.y = yc;

db = sign(scalarProduct(points[pi], points[pj], pc));

if (db == 0)

return 0;

else

for (k = 0; k < n; k++)

if (k != pi && k != pj)

dk = sign(scalarProduct(points[pi], points[pj], points[k]));

if (db * dk < 0)

return 0;

else

if (dk == 0)

di = sign(scalarProduct(pc, points[k], points[pi]));

dj = sign(scalarProduct(pc, points[k], points[pj]));

if (di * dj > 0)

return 0;

return 1;

/* Se construieste acoperirea convexa a unei multimi de puncte. */

void simpleConvexHull(int n, POINT2D points[])

float xc, yc;

int i, j;

computeCenter(n, points, xc, yc);

for (i = 0; i < n-1; i++)

for (j = i + 1; j < n; j++)

if (lineofconvexhull(n, points, xc, yc, i, j))

line((int)points[i].x, (int)points[i].y,

(int)points[j].x, (int)points[j].y);

/*******************************************************/

void loop(void)

char ch;


setbkcolor(WHITE);

setcolor(BLACK);

cleardevice();


75

Fig. 8.1: Acoperirea convexa a unei multimi de puncte

n = 0;


do

ch = readChar();

switch (ch)

case ’c’: n = 0;

cleardevice();


break;

case ’t’: stopAddVertices = TRUE;

simpleConvexHull(n, points);

break;

;

while(ch != 27);

int main()

initGraphics();

loop();

return 0;

In figura 8.1 este reprezentat rezultatul rularii programului anterior asupra unei multimide puncte oarecare din plan.

8.2 Algoritmul lui Graham

Algoritmul lui Graham1 este un algoritm destul de simplu de implementat. Punctele suntmai ıntai ordonate, ın mod lexicografic, dupa unghiul polar si distanta.

1http://www.geeksforgeeks.org/convex-hull-set-2-graham-scan/

76

Se parcurge multimea de puncte ın ordinea data de sortarea initiala. Punctele suntadaugate unul cate unul la frontiera acoperirii convexe. Aceasta frontiera (punctele sale) estepastrata ıntr–o stiva (ca structura de date). Pe parcurs, unele puncte candidat adaugate pestiva sunt eliminate: daca ultimele doua puncte adaugate, aflate ın stiva, si punctul curent ceeste inspectat, sunt orientate ın sens invers trigonometric (∆(A, B, C) < 0) atunci se eliminapunctul aflat ın varful stivei (ultimul punct adaugat la frontiera), si se continua procedurade calcul.

Programul grahamscan.cpp implementeaza algoritmul lui Graham:

#include <stdio.h>

#include <stdlib.h>

#include <conio.h>

#include <dos.h>


#include <stack>

#define N 100

#define TRUE 1

#define FALSE 0


int x, y;

POINT2D;

unsigned int n;

POINT2D points[N];



int gd, gm;

gd = DETECT;





getch();

exit(1);

/*******************************************************/

int sign(float x)

if (x < 0)

return -1;

else

if (x > 0)

return 1;

else

return 0;

77

int scalarProduct(POINT2D p1, POINT2D p2, POINT2D p3)


int dist(POINT2D p1, POINT2D p2)

return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);

int compare(const void *pc1, const void *pc2)

POINT2D p1 = *(POINT2D*)pc1;

POINT2D p2 = *(POINT2D*)pc2;

int d = scalarProduct(points[0], p1, p2);

if (d == 0)

if (dist(points[0], p1) <= dist(points[0], p2))

return -1;

else

return 1;

else

return -d;

int lowestPoint(int n, POINT2D p[])

int min = 0;

int i;

for (i = 1 ; i < n; i++)

if ((p[i].y < p[min].y) || ((p[i].y == p[min].y) && (p[i].x < p[min].x)))

min = i;

return min;

void graham(int n, POINT2D p[])

int k = lowestPoint(n, p);

POINT2D first, currentPoint;

first = p[0]; p[0] = p[k]; p[k] = first;

qsort(&p[1], n-1, sizeof(POINT2D), compare);

std::stack<POINT2D> s;

s.push(p[0]);

s.push(p[1]);

currentPoint = p[2];

k = 3;

while (k < n)

while (sign(scalarProduct(s.top(), currentPoint, p[k])) <= 0)

currentPoint = s.top();

s.pop();

78

s.push(currentPoint);

currentPoint = p[k];

k++;

first = currentPoint;

while (!s.empty())

POINT2D p1 = s.top();

s.pop();

line(currentPoint.x, currentPoint.y, p1.x, p1.y);

currentPoint = p1;

line(currentPoint.x, currentPoint.y, first.x, first.y);

/*******************************************************/


char text[3];


return;


n++;


itoa(n, text, 10);


int readChar(void)

int c;

c = getch();

if (!c)

c = getch();

return c;

void loop(void)

char ch;


n = 0;


do

ch = readChar();

switch (ch)

case ’c’: n = 0;

cleardevice();


break;


79

graham(n, points);

break;

;

while(ch != 27);

int main()

initGraphics();

loop();

return 0;

8.3 Algoritmul lui Jarvis

Algoritmul lui Jarvis2 mai este cunoscut sub numele de algoritmul gift wrapping, sau marsullui Jarvis : se pleaca de la un punct aflat pe ınfasuratoarea convexa si se traseaza o semidreaptamobila ce pleaca de la orizontala si se poate roti ın sens trigonometric, primul punct ıntalnitde aceasta trebuie sa fie pe ınfasuratoarea convexa. Se retine acel punct si se continua proce-dura pana cand un alt punct este atins, astfel pana cand pachetul este ın ıntregime ınfasurat(punctul de ınceput este inclus din nou).

Mai ıntai se determina un punct ce apartine acoperirii convexe ın mod sigur: punctul ceprezinta cea mai mica coordonata pe Ox si pe Oy - punctul cel mai din stanga-jos.

Apoi se inspecteaza toate punctele multimii initiale. Se determina punctul succesor alpunctului curent, adica cel mai la dreapta punct fata de ultimele doua puncte alese. Inmomentul ın care se revine la punctul de unde s-a plecat, algoritmul se ıncheie.

Programul jarvis.cpp implementeaza algoritmul lui Jarvis:

#include <stdio.h>

#include <stdlib.h>

#include <conio.h>

#include <dos.h>


#define N 100

#define TRUE 1

#define FALSE 0


int x, y;

POINT2D;

unsigned int n;

POINT2D points[N];



int gd, gm;

2http://www.geeksforgeeks.org/convex-hull-set-1-jarviss-algorithm-or-wrapping/

80

gd = DETECT;





getch();

exit(1);

/*****************************************************/

int lowestPoint(int n, POINT2D p[])

int min = 0;

int i;

for (i = 1 ; i < n; i++)

if ((p[i].x < p[min].x) || ((p[i].x == p[min].x) && (p[i].y < p[min].y)))

min = i;

return min;

int sign(float x)

if (x < 0)

return -1;

else

if (x > 0)

return 1;

else

return 0;



void jarvis(int n, POINT2D p[])

int v1, v2, v3, i;

v1 = lowestPoint(n, points);

v2 = v1;

do

v3 = (v2 + 1) % n;

for (i = 0; i < n; i++)

if (sign(scalarProduct(points[v2], points[i], points[v3])) < 0)

v3 = i;

line(p[v2].x, p[v2].y, p[v3].x, p[v3].y);

v2 = v3;

while (v2 != v1);

/*****************************************************/

81


char text[3];


return;


n++;


itoa(n, text, 10);


int readChar(void)

int c;

c = getch();

if (!c)

c = getch();

return c;

void loop(void)

char ch;


setbkcolor(WHITE);

setcolor(BLACK);

cleardevice();


n = 0;


do

ch = readChar();

switch (ch)

case ’c’: n = 0;

cleardevice();


break;


jarvis(n, points);

break;

;

while(ch != 27);

int main()

initGraphics();

loop();

return 0;

82

Fig. 8.2: Determinarea acoperirii convexe a unei multimi de puncte cu algoritmul lui Jarvis

In figura 8.2 este reprezentat rezultatul aplicarii algoritmului lui Jarvis asupra uneimultimi de puncte oarecare din plan.

O comparatie a celor doi algoritmi poate fi urmarita la adresa http://www.chrisharrison.net/index.php/Research/ConvexHull.

8.4 Un algoritm

83

Laboratorul 9

Determinarea nucleului unui poligon(Problema galeriei de arta) sitriangularea unui poligon prin metodataierii urechilor

Sa consideram o galerie de arta, compusa dintr-un numar de camere ınvecinate. Se poate trecedintr-o camera intr-alta prin intermediul usilor existente. Fiecare camera este supravegheatade o camera video ce poate vedea ın toate directiile. Se pune problema de a determina numarulminim de camere si locatiile lor de amplasare astfel ıncat acestea sa aiba sub supravegheretoata galeria.

O galerie de arta poate fi interpretata ca un poligon simplu P avand n varfuri.O camera video (vizibilitate 3600) poate fi identificata cu un punct din interiorul lui

P; aceasta poate supraveghea acele puncte cu care are vizibilitate directa (poate fi unitaprintr-un segment inclus ın interiorul poligonului.

Problema galeriei de arta Sa se determine numarul de camere video necesare pentrua supraveghea o galerie de arta si locatiile lor de amplasament.

Daca spatiul galeriei de arta are forma unui poligon convex este suficienta o singuracamera video pentru supraveghere.

Numarul de camere depinde de numarul de varfuri cat si de forma poligonului: cu catacesta are o forma mai complexa, cu atat numarul de camere va fi mai mare.

Pentru a simplifica problema se poate pleca de la o triangulare a poligonului ce reprezintagaleria de arta.

O prima restrictie se refera la locatiile camerelor: acestea nu pot fi amplasate decat ınvarfurile poligonului.

9.1 Determinarea nucleului unui poligon

Vom prezenta ın continuare o problema, asa cum poate fi ıntalnita la concursurile de progra-mare ale elevilor sau studentilor.

Problema 9.1 O galerie de arta are forma unui poligon. Datorita bugetului redus, directorulgaleriei de arta doreste sa angajeze un singur paznic. Supraveghetorul trebuie sa patrulezeıntr-un perimetru astfel ıncat, ın orice moment, sa poata observa fiecare latura a ıncaperii.

Spre exemplu pentru galeria specificata ın figura de mai jos (vezi figura 9.1), zona hasurataeste suprafata ın care paznicul poate patrula.

84

Fig. 9.1: Un exemplu de galerie de arta

Se cere sa se realizeze un program care sa determine aceasta suprafata.Intrare: galerie.inPe prima linie se afla numarul n (n < 101) de colturi ale ıncaperii. Urmatoarele n

linii contin coordonatele colturilor, cate unul pe fiecare linie. Coordonatele unui colt k sunto pereche de numere ıntregi (xk, yk) (−32000 < xk, yk < 32000) separate printr-un spatiu.Colturile sunt date ın ordine trigonometrica.

Iesire: galerie.outFisierul de iesire va contine pe prima linie numarul m de colturi al suprafetei cerute.

Pe urmatoarele m linii se gasesc coordonatele acestora sub forma unor perechi xk yk undexk, yk sunt doua numere reale afisate cu doua zecimale dupa virgula si separate printr-unspatiu. Colturile vor fi afisate ın ordinea crescatoare a coordonatei xk iar pentru valori egaleale acesteia, ın ordinea crescatoare a coordonatei yk.

Daca zona de supraveghere este vida, atunci fisierul de iesire va contine doar numarul 0.Timp de executie / test: 1 sec.

Exemplul 9.1 Datele de intrare si de iesire pentru figura 9.1 sunt:Intrare Iesire

4 4100 0 40.00 24.0075 80 50.00 40.0050 40 87.50 40.000 40 100.00 0.00

Un alt exemplu de fisier de intrare este urmatorul

6

0 0

500 0

300 200

85

300 300

200 300

0 500

al carui rezultatul corespunzator specificat ın fisierul de iesiere este:

5

0.00 -0.00

0.00 300.00

200.00 300.00

300.00 0.00

300.00 200.00

O solutie este prezentata ın continuare:

#include <stdio.h>

#include <stdlib.h>

#include <math.h>

#include <conio.h>

typedef struct point

float x, y;

POINT2D;

typedef struct line

int first, second;

double a, b, c;

LINE;

typedef struct nod

POINT2D *inf;

struct nod *left, *right;

NOD;

POINT2D *vertices;

LINE *lines;

NOD *rad;

int n;

int intNumber = 0;

/** Functie de comparare utilizata pentru aranjarea (ordonarea) punctelor

* @param p1 - adresa zonei de memorie unde se afla pastrate coord primului punct

* @param p2 - adresa zonei de memorie unde se afla pastrate coord celui de-al

* doilea punct

* @return - -1 daca (p1.y < p2.y) sau (p1.y = p2.y) si (p1.x < p2.x)

* 0 daca coordonatele celor doua puncte coincid

* 1 daca (p1.y > p2.y) sau (p1.y = p2.y) si (p1.x > p2.x)

*/

int compare(POINT2D* p1, POINT2D *p2)

if (p1->x == p2->x)

if (p1->y < p2->y)

return -1;

else

if (p1->y > p2->y)

86

return 1;

else

return 0;

else

if (p1->x < p2->x)

return -1;

else

if (p1->x > p2->x)

return 1;

return 0;

/** Creaza si initializeaza un nod intr-n arbore binar de cautare.

* @param key - adresa zonei de memorie unde se afla pastrate coord unui punct

* @return - adresa zonei de memorie unde a fost creat nodul arborelui

*/

NOD* CreateNode(POINT2D *key)

NOD *p;

intNumber++;

p = (NOD*)malloc(sizeof(NOD));

if (p == NULL)

printf("Eroare: memorie insuficienta! %d \n", intNumber);

exit(1);

p->left = p->right = NULL;

p->inf = (POINT2D*)malloc(sizeof(POINT2D));

p->inf->x = key->x;

p->inf->y = key->y;

return p;

/** Inserarea unui element (chei) intr-un arbore binar de cautare.

* @param p - adresa radacinii subarborelui curent in care se doreste inserarea

* @param key - adresa zonei de memorie unde se afla pastrate coord unui punct

*/

NOD* InsertNode(NOD *p, POINT2D *key)

int ind;

if (p == NULL)

p = CreateNode(key);

else

ind = compare(p->inf, key);

if (ind < 0)

p->right = InsertNode(p->right, key);

else

if (ind > 0)

p->left = InsertNode(p->left, key);

87

return p;

/** Parcurgerea (vizitarea) in inordine a unui arbore binar.

* @param p - adresa zonei de memorie unde se afla un nod al arborelui

*/

void VisitInord(NOD *p)

if (p != NULL)

VisitInord(p->left);

printf("[%5.2f %5.2f] ", p->inf->x, p->inf->y);

VisitInord(p->right);

/** Elibereaza zona de memorie alocata unui nod dintr-un arbore binar.


*/

NOD* FreeNode(NOD *p)

free(p->inf);

free(p);

return NULL;

/** Elibereaza zona de memorie alocata unui arbore binar.

* @param p - adresa zonei de memorie unde se afla radacina subarborelui

* pentru ale carui noduri se doreste sa se elibereze memoria ocupata.

*/

void freeTree(NOD *p)

if (p->left != NULL)

freeTree(p->left);

if (p->right != NULL)

freeTree(p->right);

FreeNode(p);

/** Se citesc datele de intrare dintr-un fisier: coordonatele punctelor

* ce determina o linie poligonala simplu inchisa. Se aloca dinamic spatiu

* pentru punctele poligonului, pentru segmentele de dreapta ale acestuia

* si se initializeaza.

*/

void readInput(void)

FILE *f;

int i;

float vx, vy;

if ((f = fopen("galerie.in", "rt")) == NULL)



88

getch();

exit(1);

fscanf(f, "%d", &n);

vertices = (POINT2D*)malloc(sizeof(POINT2D) * (n + 1));

for (i = 0; i < n; i++)

fscanf(f,"%f %f", &vertices[i].x, &vertices[i].y);

//vertices[i].x *= 100;

//vertices[i].y *= 100;

vertices[n].x = vertices[0].x;

vertices[n].y = vertices[0].y;

lines = (LINE*)malloc(sizeof(LINE) * n);

for (i = 0; i < n; i++)

lines[i].first = i;

lines[i].second = i+1;

vy = vertices[i+1].y - vertices[i].y;

vx = vertices[i+1].x - vertices[i].x;

lines[i].a = -vy;

lines[i].b = vx;

lines[i].c = vertices[i].x*vy - vertices[i].y*vx;

fclose(f);

/** Determina semiplanul determinat de linia l in care se afla punctul p.

* @param line - parametrii dreptei

* @param p - adresa zonei de memorie unde se afla pastrate coord punctului

* @return - valoarea functiei corespunzatoare liniei l calculata in punctul p

*/

float function(LINE l, POINT2D p)

return (p.x * l.a + p.y * l.b + l.c);

/** Determina punctul de intersectie dintre doua drepte.

* @param l1 - parametrii primei drepte

* @param l1 - parametrii celei de-a doua drepte

* @param p - adresa punctului de intersectie, daca exista

* @return - 1 daca cele doua drepte se intersecteaza

* 0 in caz contrar

*/

int lineSegmentIntersection(LINE l1, LINE l2, POINT2D* p)

double det = (l1.a * l2.b - l1.b * l2.a);

if (det == 0)

return 0;

else

p->x = (l1.b * l2.c - l2.b * l1.c) / det;

p->y = (l2.a * l1.c - l1.a * l2.c) / det;

89

return 1;

/** Se parcurge in inordine arborele binar a carui radacina este nodul p, si se

* pastreaza intr-un vector coordonatele punctelor din plan, pe masura ce sunt

* intalnite.


* @param vec - adresa zonei de memorie unde se afla un tablou de puncte

*/

void arb2vec(NOD *p, POINT2D* vec[])

if (p != NULL)

arb2vec(p->left, vec);

vec[intNumber++] = p->inf;

arb2vec(p->right, vec);

void run(void)

POINT2D p;

int i, j, k;

POINT2D **points;

FILE *f;

/* se calculeaza punctele de intersectie intre oricare doua drepte

ce apartin liniei poligonale simplu inchisa si se insereaza intr-un arbore

binar de sortare. */

for (i = 0; i < n - 1; i++)

for (j = i + 1; j < n; j++)

if (lineSegmentIntersection(lines[i], lines[j], &p))

rad = InsertNode(rad, &p);

//VisitInord(rad);

points = (POINT2D**)malloc(sizeof(POINT2D*) * intNumber);

if (points == NULL)

printf("Eroare: memorie insuficienta! %d \n", sizeof(POINT2D*) * intNumber);

exit(1);

intNumber = 0;

//se copiaza cheile arborelui in tabloul points, in ordinea in care acestea

//sunt intalnite in urma vizitarii in inordine a arborelui

arb2vec(rad, points);

for (i = 0; i < n; i++)

j = 0;

for (k = 0; k < intNumber; k++)

if (function(lines[i], *points[k]) >= 0)

points[j] = points[k];

j++;

90

intNumber = j;

//printf("\n");

f = fopen("galerie.out", "wt");

if ((f = fopen("galerie.out", "wt")) == NULL)

printf("Nu se poate deschide fisierul de iesire!\n");


getch();

exit(1);

//se salveaza multimea de puncte ale tabloului points

fprintf(f, "%d\n", intNumber);

for (i = 0; i < intNumber; i++)

fprintf(f, "%.2lf %.2lf\n", points[i]->x, points[i]->y);

//printf("%.2lf %.2lf\n", points[i]->x, points[i]->y);

fclose(f);

free(points);

freeTree(rad);

free(vertices);

free(lines);

int main(void)

readInput();

run();

return 0;

9.2 Triangularea unui poligon

Definitia 9.1 Fie o multime de n puncte ın planul euclidian, An = Ai = (xi, yi)|i = 1, n.Multimea P = [A1A2] ∪ [A2A3] ∪ . . . ∪ [An−1An] se numeste linie poligonala. Daca A1 = An

avem o linie poligonala ınchisa, iar daca Ai 6= Aj , ∀i 6= j linia poligonala se numeste linie

poligonala simpla.Ai se numesc varfuri, [AiAi+1] laturi iar ∠AiAi+1Ai+2 sunt unghiuri ale liniei poligonale.

Definitia 9.2 Un poligon P este o linie poligonala simpla ınchisa, cu toate unghiurile proprii.

Definitia 9.3 O diagonala a lui P este un segment ce uneste doua varfuri ale acestuia si careeste situat ın interiorul lui P.

De exemplu [AiAj ] cu i < j − 1 reprezinta o diagonala a poligonului P.

Definitia 9.4 O triangulare TP a poligonului P este o descompunere a lui P ın triunghiuri, datade o multime maximala de diagonale ce nu se intersecteaza.

Prin urmare o triangulare a unui poligon P este o descompunere finita a acestui poligon ıntriunghiuri astfel ıncat:

91

Fig. 9.2: Linii poligonale

• laturile oricarui triunghi sunt fie diagonale ale poligonului P, fie laturi ale acestuia;

• varfurile oricarui triunghi sunt dintre varfurile poligonului P;

• oricare doua triunghiuri au cel mult un varf comun sau o latura comuna (vezi figura 9.3 a)).

Fig. 9.3: Triangularea unui poligon convex

Orice triangulare a unui poligon cu n varfuri este formata din n−3 diagonale si n−2 triunghiuri.

Teorema 9.2 (Euler) Pentru orice triangulare a unui poligon cu n varfuri are loc urmatoarearelatie

n−m + f = 1 (9.1)

unde m este numarul de laturi ale triunghiurilor, iar f este numarul de triunghiuri.

Observatia 9.3 Se poate demonstra faptul ca numarul de posibilitati de a ımparti un poligon cu n

laturi ın n − 2 triunghiuri formate numai din diagonale ce nu se intersecteaza, este al (n − 1)-leanumar Catalan, T (n− 1), unde

T (1) = 1

T (n) =∑n−1

i=1 T (i)T (n − i).(9.2)

9.2.1 Triangularea optima a unui poligon

Lungimea unei triangulari TP a unui poligon P se defineste ca fiind suma lungimilor perimetrelortriunghiurilor ce o compun.

Enuntul problemei: Se da un poligon convex cu n laturi. Se cunosc coordonatele (xi, yi) alefiecarui varf al poligonului. Sa se traseze segmente de dreapta ıntre varfuri neadiacente astfel ıncataceste linii sa nu se intersecteze, ıntreaga suprafata a poligonului sa fie ımpartita ın n−2 triunghiuri,iar suma lungimilor tuturor acestor segmente sa fie minima (triangulare de valoare minima).

92

Rezolvare: Notam cu (i, j, k) perimetrul triunghiului format din varfurile Ai, Aj , Ak:

(i, j, k) = d(Ai, Aj) + d(Aj , Ak) + d(Ak, Ai) (9.3)

unde d(Ai, Aj) reprezinta distanta euclidiana ıntre varfurile Ai si Aj (d(Ai, Aj) = |AiAj |).Pentru doua puncte A,B ∈ R

2 avem:

d(A,B) =√

(Ax −Bx)2 + (Ay −By)2. (9.4)

Vom presupune ca varfurile poligonului P (P =< A1A2 . . . An >) sunt date ıntr-o anumitaordine de parcurgere (ın sensul acelor de ceas – sens invers trigonometric).

Vom utiliza o matrice T ∈ Mn×n(R), unde Ti,j = valoarea triangularii optime (de lungimeminima) a poligonului format din varfurile < Ai, Ai+1, . . . , Aj >. Costul triangularii optime apoligonului P ıl vom obtine ın T1,n.

Avem urmatoarele formule:

1. Ti,i+1 = 0 - costul triangularii optime a unui poligon convex format din doua puncte este 0;

2. Ti,j = mini<k<jTi,k + Tk,j +(i, k, j), i < j − 1 – costul triangularii optime a unui poligon< Ai, Ai+1, . . . , Aj > este dat de valoarea minima a descompunerii acestuia ın alte douapoligoane, < Ai, Ai+1, . . . , Ak > si < Ak, Ak+1, . . . , Aj > la care se adauga si triunghiul(Ai, Ak, Aj) (vezi figura 9.3 b)).

In matricea T ∈Mn×n(R) numai elementele aflate deasupra diagonalei principale sunt utilizate(Ti,j cu i ≤ j). Pentru o utilizare optima a spatiului vom pastra ın Tj,i valoarea k pentru care seobtine triangularea optima Ti,j (vezi algoritmul 1).

Algoritm 1 Algoritm pentru triangularea optima a unui poligon

1: Input n,A1, A2, . . . , An2: for i← 1, n− 1 do3: Ti,i+1 ← 04: end for5: for l← 2, n − 1 do6: for i← 1, n − l do7: j ← i + l

8: Ti,j ←∞9: for k ← i + 1, j − 1 do

10: value←(i, j, k) + Ti,k + Tk,j

11: if (ti,j > value) then12: Ti,j ← value

13: Tj,i ← k

14: end if15: end for16: end for17: end for18: Output T1,n

93

Appendix A

Algoritmi pentru calculul optimal alvizibilitatii unor puncte

A.1 Descrierea problemei

Vom considera urmatoarea problema:Enuntul problemei: Fie Oxy un sistem de coordonate ortogonal din plan. Vom considera omultime formata din n segmente de dreapta, paralele cu axa Oy si avand o extremitate pe axa Ox.Un astfel de segment se numeste obstacol. In acest mod, un obstacol este complet determinat deo pereche de numere (Xi,Hi), unde Xi reprezinta coordonata pe axa absciselor iar Hi ınaltimeaacestuia. Vom nota cu W = (X1,H1), (X2,H2), ..., (Xn,Hn) o multime compusa din n obiectedenumite obstacole. Elementele multimii W se considera ordonate dupa valorile coordonatelorcorespunzatoare axei Ox. Se cere sa se determine perechile de obstacole ce sunt vizibile ıntre ele.

Definitia A.1 Doua obstacole se spune ca sunt vizibile daca cel putin ıntre extremitatile lor su-perioare exista vizibilitate directa: adica ın raza vizuala ce uneste cele doua varfuri nu se gasestenici un alt obstacol.

Exemplul A.1 In figura A.1 se pot observa cinci obstacole numerotate de la 1 la 5. Obstacolulnumarul 1 nu este vizibil cu obstacolul numarul 3, deoarece ıntre ele se afla obstacolul numarul2 ce ımpiedica vizibilitatea ıntre cele doua, pe cand obstacolul numarul 3 este vizibil cu obstacolulnumarul 5, dupa cum se poate observa.

A.2 Algoritmul Visibility

Vom reaminti cateva elemente de baza din geometria computationala, esentiale pentru prezentareametodei si ıntelegerea algoritmilor prezentati.

Fig. A.1: Reprezentarea a mai multor obstacole si diverse cazuri de vizibilitate

94

Fig. A.2: Intersectia a doua segmente de dreapta [AB] si [CD]

Cele doua drepte existente ın figura A.2 sunt notate cu d1 si d2. Ecuatiile generale ale celordoua drepte sunt:

d1 : a1 · x + b1 · y + c1 = 0 (A.1)

d2 : a2 · x + b2 · y + c2 = 0 (A.2)

Fiind date trei puncte A(x1, y1), B(x2, y2) si A(x3, y3), vom nota cu sign(A,B,C) urmatoruldeterminant:

sign(A,B,C) =

∣

∣

∣

∣

∣

∣

1 1 1x1 x2 x3

y1 y2 y3

∣

∣

∣

∣

∣

∣

= (x2 − x1) · (y3 − y1)− (x3 − x1) · (y2 − y1) (A.3)

Semnul expresiei anterioare poate fi utilizat pentru a determina orientarea varfurilor ce formeazatriunghiul ABC.

Definitia A.2 Punctele A, B, C se spune ca sunt orientate ın sens trigonometric daca sign(A,B,C) >

0 si sunt orientate ın sens invers trigonometric daca sign(A,B,C) < 0.Punctele A, B, C sunt coliniare daca si numai daca sign(A,B,C) = 0.

Conditia pentru ca segmentele de dreapta [AB] si [CD] sa se intersecteze ıntr-un punct aflat ıninteriorul lor, poate fi dedusa utilizand orientarea varfurilor. Astfel segmentul [AB] intersecteazasegmentul [CD] daca dreapta AB (dreapta ce trece prin punctele A si B) separa punctele C si D,iar dreapta CD separa punctele A si B, ceea ce se poate scrie astfel:

sign(A,B,C) · sign(A,B,D) < 0 ∧ sign(C,D,A) · sign(C,D,B) < 0 (A.4)

Pe baza definitiei A.1, se poate descrie un algoritm simplu (vezi algoritmul 2) pentru a determinatoate perechile de obstacole vizibile.

Functia Intersect(A,B,C,D) primeste drept parametri de intrare coordonatele a patru punctedin plan ce desemneaza punctele de extremitate a doua segmente de dreapta, si returneaza rezultatulcalculat. Valoarea true returnata semnifica faptul ca cele doua segmente se intersecteaza unul cucelalalt, inclusiv situatia cand una dintre extremitatile celui de-al doilea segment se afla pozitionataın interiorul primului segment.

Procedura V isibility(X[N ],H[N ];V isible[N ][N ]) are drept parametri de intrare coordonatelepe axa Ox ale celor n obstacole ımpreuna cu ınaltimile lor. Matricea V isible va pastra situatia devizibilitate ıntre toate perechile de obstacole (i, j): V isiblei,j = 1 daca si numai daca obstacolul i seafla ın raza vizuala cu obstacolul j, sau V isiblei,j = 0 altfel.

Observatia A.2 Matricea V isible este simetrica. Prin urmare, pentru a reduce numarul operatiilorefectuate, este suficient sa calculam numai triunghiul superior al acesteia.

95

Algoritm 2 Algorithm Visibility

Input: X[N ] - vector ce contine coordonate pe Ox ale obstacolelor.H [N ] - vector ce contine coordonate pe Oy ale extremitatilor superioare ale obsta-

colelor.Output: V isible[N ][N ] - matricea de vizibilitate.1: function Sign(A, B, C)2: value← (B.x−A.x) · (C.y −A.y)− (C.x− A.x) · (B.y − A.y)3: return value4: end function

5: function Intersect(A, B, C, D)6: if (((sign(A, B, C) · sign(A, B, D) ≤ 0) ∧ (sign(C, D, A) · sign(C, D, B) < 0))) ∨

(((sign(A, B, C) · sign(A, B, D) < 0) ∧ (sign(C, D, A) · sign(C, D, B) ≤ 0))) then7: return true8: else9: return false

10: end if11: end function

12: procedure Visibility(X[N ], H [N ]; V isible[N ][N ])13: for i← 1, N − 1 do14: for j ← i + 1, N do15: intersection← false16: k ← i + 117: while ((k < j) ∧ (intersection = false)) do18: intersection← Intersect(A(Xi, Hi), B(Xj, Hj), C(Xk, 0), D(Xk, Hk))19: if (intersection 6= true) then20: k ← k + 121: end if22: end while23: if (intersection 6= true) then24: visiblei,j ← 025: else26: visiblei,j ← 127: end if28: end for29: end for30: end procedure

Analiza algoritmului

Pentru a determina complexitatea timp a acestui algoritm este nevoie sa cunoastem numarul deinstructiuni realizate la fiecare apel al subrutinei Intersect(), numarul de instructiuni realizate ıntimpul instructiunilor repetitive while (linia 17), si for (liniile 13 si 14) [8], [1].

Numarul instructiunilor realizate ın timpul apelului functiei Intersect() este constant si nudepinde de dimensiunea datelor de intrare. Din aceasta cauza putem aproxima complexitatea sa cafiind de ordinul O(1).

Blocul de instructiuni determinat de liniile 18-22, ın cazul cel mai defavorabil, este repetat dej− i− 1 ori, astfel complexitatea secventei determinata de instructiunea repetitiva while (linia 17)

96

Fig. A.3: Exemplu pentru conditia de orientare a punctelor

este O(j − i− 1).Pentru secventa determinata de instructiunea for (linia 14) numarul de operatii realizate este

urmatorul:

(i+1− i−1)+(i+2− i−1)+ ...+(n− i−1) = 0+1+2+ ...+(n− i−1) =

n∑

j=i+1

(j − i− 1) (A.5)

Dupa evaluarea sumei, se obtine:

n∑

j=i+1

(j − i− 1) =

n∑

j=1

j −

i∑

j=1

j − (n− i) · (i + 1) =n · (n + 1)

2−

i · (i + 1)

2− (n− i) · (i + 1) (A.6)

Corpul celei de-a doua instructiuni de ciclare for (linia 13) foloseste un timp constant, prinurmare timpul de executie este O(n2).

In final, dupa introducerea ın calculul nostru si a instructiunii for (linia 13), numarul de operatiiefectuate de catre algoritmul 2 [Visibility ] ın cazul cel mai defavorabil este:

n−1∑

i=1

n∑

j=i+1(j − i− 1) =

n−1∑

i=1(n·(n+1)

2 − i·(i+1)2 − (n− i) · (i + 1))

= n·(n+1)·(n−1)2 +

n−1∑

i=1

i2

2 +n−1∑

i=1

i2 − n ·

n−1∑

i=1i− n · (n− 1)

= 2·n3−6·n2+4·n

12

(A.7)

Din ecuatia (A.7) rezulta complexitatea algoritmului ın cazul cel mai defavorabil ca fiind deordinul O(n3).

A.3 Algorithm VisibilityOpt

Vom descrie ın continuare un alt algoritm VisibilityOpt (vezi algoritmul 3) a carui complexitateın cazul cel mai defavorabil este O(n2), mult mai buna decat complexitatea procedurii Visibility(algoritmul 2).

Algoritmul se bazeaza pe urmatoarea observatie:

97

Observatia A.3 Fie A limita superioara a obstacolului cu numarul i si B limita superioara aultimului obstacol k vizibil din A (k ≥ i + 1). Dupa cum se poate vedea din figura A.3, varful C

nu este vizibil din punctul A daca C se afla la dreapta sau chiar pe linia ce uneste punctele A siB, adica daca sign(A,B,C) ≤ 0. Punctul D este vizibil din punctul A daca este situat la stangasegmentului orientat AB, ceea ce conduce la conditia sign(A,B,D) > 0.

Descriem ın continuare algoritmul implementat ın cadrul procedurii V isibilityOpt: pentrufiecare punct Pi se determina daca varful candidat Pj se afla situat la dreapta sau chiar pe segmen-tul orientat determinat de punctul curent Pi si de ultimul punct vizibil din Pi, notat cu Plast visible

(la ınceput last visible ia valoarea i + 1). In momentul ın care conditia sign(i, last visible, j) > 0devine adevarata, punctul Pj este vizibil din punctul Pi, iar valoarea curenta a variabilei last visible

devine j.

Algoritm 3 Algorithm VisibilityOpt

Input: X[N ] - vector ce contine coordonate pe Ox ale obstacolelor.H [N ] - vector ce contine coordonate pe Oy ale extremitatilor superioare ale obsta-

colelor.Output: V isible[N ][N ] - matricea de vizibilitate.1: function Sign(I, J, K)2: value← (xJ − xI) · (hK − hI)− (xK − xI) · (hJ − hI)3: return value4: end function

5: procedure VisibilityOpt(X[N ], H [N ]; V isible[N ][N ])6: for i← 1, N − 1 do7: visiblei,i+1 ← 18: last visible← i + 19: j ← last visible + 1

10: while j ≤ N do11: v ← sign(i, last visible, j)12: if v > 0 then13: visiblei,j ← 114: last visible← j15: else16: visiblei,j ← 017: end if18: j ← j + 119: end while20: end for21: end procedure

Instructiunile 11-18 (vezi algoritmul 3) se vor executa de

n− last visible− 1 + 1 = n− last visible ori.

Secventa de instructiuni 7-19 va fi apelata den−1∑

i=1(n− i− 1) ori:

n−1∑

i=1

(n− i− 1) = n− 2 + n− 3 + ... + 1 =

n−2∑

i=1

i =(n− 1) · (n− 2)

2(A.8)

Astfel complexitatea algoritmului 3 implementat ın cadrul procedurii VisibilityOpt este O(n2).

98

A.4 Aplicatie

Urmatoarea problema ([6]) poate fi rezolvata ıntr-un mod optim utilizandu-se procedura Visibility-Opt. Prezentam ın continuare enuntul simplificat al acestei problemei:

Problema A.1 Intr-o zona montana se gasesc n munti. Acestia sunt dati ın ordine de la stangala dreapta si numerotati de la 1 la n, fiecare varf i fiind precizat prin coordonata Xi pe axa Ox siprin ınaltimea sa Hi.

Se doreste deschiderea unui lant de telecabine care va asigura legatura ıntre primul varf (varful1) si ultimul varf (varful n). Statiile de telecabine pot fi ınfiintate pe oricare dintre cele n varfuriale zonei montane. Vor fi amplasate exact k statii de telecabine. Statia de telecabine i (2 ≤ i < k)va fi conectata cu statiile i− 1 si i +1; prima statie (statia 1) va fi conectata numai cu statia 2, iarultima statie, k, doar cu statia k − 1.

Lungimea totala a cablurilor folosite pentru conectare trebuie sa fie minima. Lungimea cabluluifolosit pentru a conecta doua statii consecutive este egala cu distanta dintre ele, iar aceasta lungimenu poate fi mai mare decat o valoare L. Doua varfuri i si j nu pot fi conectate direct daca ıntre elenu avem vizibilitate.

Pentru amplasarea optima a celor k statii de telecabine, vom construi mai ıntai matricea V isible,unde:

V isiblei,j =

true , daca exista vizibilitate directa ıntre varful i si varful j

false , ın caz contrarOptimizarea lungimii cablului necesar pentru interconectarea tuturor celor k statii amplasate,

se va realiza folosind metoda programarii dinamice[1].Notam cu best costi,j costul cablului pentru amplasarea optima a j statii ıntre varfurile 1 si i.Matricea best cost va avea n linii si k coloane. Valoarea rezultatului cerut ın cadrul problemei,

va fi calculat ın best costn, k.Pentru ınceput, avem: best cost1,1 = 0 si best costi,j = +∞, i 6= 1 sau j 6= 1.Relatia de recurenta necesara pentru a putea sa aplicam metoda programarii dinamice este:

best costi,j = mink:k<j∧visiblek.i=true

best costk,i−1 + dist(k, i).

Cu alte cuvinte, costul optim pentru amplasarea a j statii ıntre varfurile 1 si i este dat devaloarea minima a costului amplasarii a j − 1 statii ıntre varfurile 1 si k la care se adauga costullegaturii directe, daca este posibil, a varfului k cu varful i.

Construirea grafului de vizibilitate fiecare-cu-fiecare ıntr-un mod optim conduce la ımbunatatireatimpului general de rulare al ıntregului program. Utilizarea primului algoritm de determinare aperechilor de puncte vizibile, a carui complexitate este de ordinul O(n3), conduce la un timp O(n3)pentru ıntregul algoritm.

Prezentam ın continuare o solutie pentru problema enuntata, solutie implementata ın limbajulC:

#include <stdio.h>

#include <math.h>

#define MAX_OBSTACOLE 100

#define MAX_STATII 30

#define LIMIT 2000000

#define TRUE 1

#define FALSE 0

typedef unsigned char byte;

99

int n; //numarul de obstacole

int k; //numarul de statii

long l; //distanta maxima dintre doua statii consecutive

long x[MAX_OBSTACOLE]; //coordonatele pe Ox ale obstacolelor

long h[MAX_OBSTACOLE]; //inaltimile obstacolelor

float best_cost[MAX_OBSTACOLE][MAX_STATII]; //matricea costurilor optimale

//matricea in care se pastreaza valoarea lui k

//ce minimizeaza formula de recurenta

byte optim[MAX_OBSTACOLE][MAX_STATII];

//matricea de vizibilitate directa intre obstacole

byte visible[MAX_OBSTACOLE][MAX_OBSTACOLE];

/** Citeste datele de intrare dintr-un fisier. */

int citDate(void)

FILE *f;

int i;

if ((f = fopen("input.dat", "rt")) == NULL)

fprintf(stderr, "Nu putem deschide fisierul cu date.\n");

return 0;

fscanf(f, "%d %d %ld", n, k, l);

for (i = 1; i <= n; i++)

fscanf(f, "%ld %ld", &x[i], &h[i]);

fclose(f);

return 1;

/** Calculeaza si returneaza valoarea minima dintre doua numere intregi. */

int min(int a, int b)

return (a < b) ? a : b;

/*

* Calculeaza distanta Euclidiana dintre

* punctele de coordonate (x1,y1) si (x2, y2).

*/

float distance(long x1, long y1, long x2, long y2)

float dx, dy;

dx = x2 - x1;

dy = y2 - y1;

return sqrt(dx * dx + dy * dy);

/** Calculeaza tipul orientatii a trei puncte */

float sign(long x1, long y1, long x2, long y2, long x3, long y3)

return (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1);

100

/** Calculeaza matricea de vizibilitate Visible conform algoritmului prezentat. */

void visibility(void)

int i, j, k;

int last_visible;

for (i = 1; i < n; i++)

visible[i][i + 1] = TRUE;

last_visible = i + 1;

j = last_visible + 1;

while (j <= n)

if (sign(x[i], h[i], x[last_v], h[last_v], x[j], h[j]) > 0)

visible[i][j] = TRUE;

last_visible = j;

j = last_visible + 1;

else

visible[i][j] = FALSE;

j = j + 1;

/** Functie recursiva utilizata pentru reconstituirea solutiei optimale. */

void drum(int varf, int nrs)

if (varf > 0)

drum(optim[varf][nrs], nrs - 1);

printf("%.4d", varf);

/** Calculeaza valorile matricii best_cost folosind metoda programarii dinamice. */

void run(void)

int i, j, nrs;

float d;

/* calculeaza matricea de vizibilitate */

visibility();

/* se initializeaza valorile matricilor best_cost si optim */

for (i = 1; i <= n; i++)

for (j = 1; j <= k; j++)

best_cost[i][j] = -1;

optim[i][j] = 0;

best_cost[1][1] = 0;

/* metoda programarii dinamice */

for (i = 2; i <= n; i++)

for (nrs = 2; nrs <= min(i,k); nrs++)

101

for (j = min(i - 1, nrs - 1); j <= i - 1; j++)

if (visible[j][i] == TRUE && best_cost[j][nrs - 1] != -1)

d = distance(x[j], h[j], x[i], h[i]);

if ((d <= l) && ((best_cost[i][nrs] == -1)

|| (best_cost[j][nrs - 1] + d < best_cost[i][nrs])))

best_cost[i][nrs] = best_cost[j][nrs - 1] + d;

optim[i][nrs] = j;

/* se afiseaza valoarea optima calculata */

printf("%ld", ceil(best_cost[n][k]));

/* se reconstituie pozitiile statiilor pentru sol optima */

drum(n, k);

printf("\n");

void main(void)

if (citDate())

run();

Consideratii finale

In aceasta sectiune, efortul s-a ındreptat spre studiul unui algoritm optimizat pentru calculareavizibilitatii dintre doua sau mai multe puncte, ın anumite conditii. O ıntrebare normala este aceeadaca algoritmul propus are complexitatea cea mai buna, sau daca nu s-a atins limita inferioara ın ceeace o priveste. Matricea V isible contine n2 elemente, astfel determinarea tuturor valorilor V isiblei,j

are o complexitate Ω(n2). Singurele ımbunatatiri ce se pot efectua sunt legate de constanteleimplicate ın formula generala.

102

Bibliografie

[1] T. H. Cormen, C. E. Leiserson, R. L. Rivest, Introducere ın Algoritmi, Computer Libris Agora,Cluj–Napoca, 1999.

[2] M. Cosulschi, M. Gabroveanu, Algoritmi o abordare pragmatica, Editia a 2-a, Universitaria,Craiova, 2004.

[3] M. de Berg, O. Cheong, M. van Kreveld, M. Overmars, Computational Geometry: Algorithmsand Applications, Springer, 3rd edition, 2008.

[4] S. Devadoss, J. O’Rourke, Discrete and Computational Geometry, Princeton University Press,2011.

[5] G. Farin, Curves and Surfaces for CAGD - A practical guide, 5th ed., Academic Press, 2002.http://www.farinhansford.com/books/cagd/materials.html

http://www.vis.uni-stuttgart.de/~kraus/LiveGraphics3D/cagd/

[6] Colectia Gazeta de Informatica - GInfo. Problema P050321, vol 13/5, 2003.

[7] B. W. Kernigham, D. M. Ritchie, The C Programming Language, 2nd Edition, Prentice Hall,1988.

[8] D. C. Kozen, The Design and Analysis of Algorithms. Texts and Monographs in ComputerScience, Springer, 1993.

[9] J. O’Rourke, Computational Geometry in C, Cambridge University Press, 2nd Ed, 1998.

[10] E. Petrisor, Modelare geometrica algoritmica, Ed. Tehnica, Bucuresti, 2001.

[11] H. Prautzsch, W. Boehm, M. Paluszny, Bezier and B-Spline Techniques, Springer, 2002.

http://i33www.ira.uka.de/applets/mocca/html/noplugin/inhalt.html

[12] F. P. Preparata, M. I. Shamos, Computational Geometry. Monographs in Computer Science,Springer-Verlag, (1985, revised ed., 1991).

[13] M. Vlada, I. Nistor, A. Posea, C. Constantinescu, Grafica pe calculator ın limbajele Pascal siC, vol. I-II, Ed. Tehnica, 1992.

[14] M. Vlada, Indicatii utilizare Dev C++ folosind graphics.h si libbgi.a, http://www.unibuc.ro/prof/vlada_m/docs/2012/mar/28_22_48_47Indicatii_dev-cpp.pdf

[15] How to add graphics.h header file in dev c++, http://innamhunzai.blogspot.ro/2013/03/how-to-add-graphicsh-header-file-in-dev.html

103

mirel cosulschi - ucv

Documents