Acoperire convexa rapida

“ Quick Hull ”

Definitie : Acoperirea convexa a unei multimi de puncte S din spatiu reprezinta cea mai mica multime convexa care contine multimea S.

Paricularizind definitia pt o multime de puncte S din plan, acoperirea convexa este cel mai mic poligon convex care contine multimea S.

Pentru multimea punctelor S din plan pentru care punctele A, B determina o latura extrema, se determina un punct C al multimii si conform lemei care defineste multimea QH(A,B,S) reprezentind acoperirea convexa determinata de punctele multimii date ca fiind suma :

QH(A,B,S) = QH(A,C,SA) + ( C ) + QH(C,B,SB) unde :

SA este multimea punctelor situate la dreapta dreptei AC apartinind multimii date

SB este multimea punctelor situate la stinga dreptei CB apartinind multimii date

C este multimea convexa determinata de punctele A,B,C

Determinam multimea QH(A,B,S) a multimii date observind ca acoperirea convexa a multimii formata din punctele A,B,C corespunde cu triunghiul determinat de aceste puncte si aria acestuia este maxima fata aria determinata de punctele A,B si unul din punctele interioare triunghiului ABC apartinind multimii initiale de puncte.

1

Punctele A,B cele mai de jos ale multimii date se determina raportind multimea de puncte data la la un sistem de coordonate XOY pentru care obtinem dreapta extrema determinata de punctele A,B de coordonate (Xmax,Ymin ) pentru A si (Xmin,Ymin ) pt punctul B. Punctele multimii S se afla deasupra dreptei determinata de punctele A,B. In program acest lucru se realizeaza prin urmatorul set de instructiuni,

for(i=2;i<=n;i++){ if (a[i].p.x >a[X].p.x) {X=i;} if((a[i].p.x==a[X].p.x) &&(a[i].p.y<a[X].p.y)){X=i;} if(a[i].p.x < a[Y].p.x){Y=i;} if((a[i].p.x ==a[Y].p.x) &&(a[i].p.y<a[Y].p.y)){Y=i;} }

n reprezentind numarul de puncte al multimii date

Punctul C are proprietatea ca este situat la cea mai mare distanta fata de dreapta AB si este totodata si punct extrem pt multimea data

Determinind pe fiecare din multimile QH(A,C,SA), QH(C,B,SB), respectiv C, fiind multimea convexa a punctelor A,B,C . Pe primele doua determinindule

2

repetind rationamentul pt dreapta AC si multimea de puncte SA si pt dreapta CB si multimea SB , raportata la multimea de puncte initiala data.

Insumind multimile astfel determinate , se obtine acoperirea convexa a multimii de puncte data initial

Observatie: Algoritmul furnizeaza puncte extreme ale multimii S in ordinea direct trigonometrica de traversare a poligonului convex care include multimea S pornind din punctul X.

Algoritmul are o solutie de ordin n patrat si poate fi considerat un algoritm performant .

Program realizat in TC:#include <stdio.h>#include <conio.h>#include <graphics.h>

#define nmax 50

typedef enum { FALSE,TRUE }bool;

typedef struct point{ float x,y;

}point;typedef struct varf{

point p; }varf;

varf a[nmax];int extrem;point p[50];int n;int X,Y,n1,n2;int s1[nmax],s2[nmax];

void init(){ int gdriver = DETECT, gmode; initgraph(&gdriver, &gmode, "c:\\tc\\bgi");}

3

void desen(){int i; init(); setcolor(GREEN);setfillstyle(XHATCH_FILL,BLUE); moveto(p[0].x,p[0].y);circle(p[0].x,p[0].y,20);

for (i=1;i<=n-1;i++){ putpixel(p[i].x,p[i].y,RED); line(p[i-1].x,p[i-1].y,p[i].x,p[i].y);

} line(p[n-1].x,p[n-1].y,p[0].x,p[0].y); floodfill(p[0].x+21,p[0].y+21,GREEN);

for (i=1;i<=n-1;i++){ circle(p[i].x,p[i].y,20); } getch();}

float suprafata(point a,point b,point c){ float ar; ar=((b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x))/2.; return ar;}

void cit(){int k,i; clrscr(); printf("\nNr. de puncte?:"); scanf("%d",&n); for(i=0;i<n;i++){ printf("Coord punctului %d sunt:\n",i); printf("P[%d].X=",i); scanf("%f",&p[i].x); printf("P[%d].Y=",i); scanf("%f",&p[i].y);}}

4

void QH(int A,int B,int k, double s[nmax]){int C,j;double sup,na,nb;double max=0;double sa[nmax],sb[nmax];na=0;nb=0;if(k==0) {return;}else { for(j=1;j<=k;j++){ sup=-suprafata(a[A].p,a[B].p,a[s[j]].p); if (sup>max) { C=s[j];

max=sup;

} if(suprafata(a[A].p,a[C].p, a[s[j]].p)<0){ na++; sa[na]=s[j]; } if(suprafata(a[C].p,a[B].p,a[s[j]].p)<0) { nb++; sb[nb]=s[j]; }}}QH(A,C,na,sa);desen(C);QH(C,B,nb,sb);}

void main(){int i,j,k,l,extrem[50],n1,n2;double u;X=1;Y=1;cit();for(i=2;i<=n;i++){ if (a[i].p.x >a[X].p.x) {X=i;} if((a[i].p.x==a[X].p.x) &&(a[i].p.y<a[X].p.y)){X=i;}

5

if(a[i].p.x < a[Y].p.x){Y=i;} if((a[i].p.x ==a[Y].p.x) &&(a[i].p.y<a[Y].p.y)){Y=i;} }for(i=1;i<=n;i++){u=suprafata(a[X].p,a[Y].p,a[i].p);if(u<0){ n1++;

s1[n1]=i; }

if(u>0){ n2++; s2[n2]=i; }

//a[X].extrem=1;desen(X);QH(X,Y,n1,s1);//a[Y].extrem=1;desen(Y);QH(Y,X,n2,s2);} printf("\n Acoperirea convex† este:");}

6

7