
One hour of coding within the European Project EURO INFORMATICA  March 19, 2017

Graham – algorithm  January 16, 2017

Fibonacci – recursive algorithm  December 13, 2016

Graphs – related components(algorithm)  December 12, 2016

JavaScript Comments  December 9, 2016

CSS Introduction  December 9, 2016

Java – Modifier Types and Basic Operators  December 8, 2016

Polinom – derivate(algorithm in C)  December 8, 2016

Euclid algorithm  December 8, 2016

Queue – algorithm (Sample 1)  December 8, 2016
Graham – algorithm
Graham’s scan is a method of finding the convex hull of a finite set of points in the plane with time complexity O(n log n). It is named after Ronald Graham, who published the original algorithm in 1972.^{[1]} The algorithm finds all vertices of the convex hull ordered along its boundary. It uses a stack to detect and remove concavities in the boundary efficiently.
The first step in this algorithm is to find the point with the lowest ycoordinate. If the lowest ycoordinate exists in more than one point in the set, the point with the lowest xcoordinate out of the candidates should be chosen. Call this point P. This step takes O(n), where n is the number of points in question.
Next, the set of points must be sorted in increasing order of the angle they and the point P make with the xaxis. Any generalpurpose sorting algorithm is appropriate for this, for example heapsort (which is O(n log n)).
Sorting in order of angle does not require computing the angle. It is possible to use any function of the angle which is monotonic in the interval [ 0 , π ] {\displaystyle [0,\pi ]} . The cosine is easily computed using the dot product, or the slope of the line may be used. If numeric precision is at a stake, the comparison function used by the sorting algorithm can use the sign of the cross product to determine relative angles.
The algorithm proceeds by considering each of the points in the sorted array in sequence. For each point, it is first determined whether traveling from the two points immediately preceding this point constitutes making a left turn or a right turn. If a right turn, the secondtolast point is not part of the convex hull, and lies ‘inside’ it. The same determination is then made for the set of the latest point and the two points that immediately precede the point found to have been inside the hull, and is repeated until a “left turn” set is encountered, at which point the algorithm moves on to the next point in the set of points in the sorted array minus any points that were found to be inside the hull; there is no need to consider these points again. (If at any stage the three points are collinear, one may opt either to discard or to report it, since in some applications it is required to find all points on the boundary of the convex hull.)
Again, determining whether three points constitute a “left turn” or a “right turn” does not require computing the actual angle between the two line segments, and can actually be achieved with simple arithmetic only. For three points P 1 = ( x 1 , y 1 ) {\displaystyle P_{1}=(x_{1},y_{1})} , P 2 = ( x 2 , y 2 ) {\displaystyle P_{2}=(x_{2},y_{2})} and P 3 = ( x 3 , y 3 ) {\displaystyle P_{3}=(x_{3},y_{3})} , compute the zcoordinate of the cross product of the two vectors P 1 P 2 → {\displaystyle {\overrightarrow {P_{1}P_{2}}}} and P 1 P 3 → {\displaystyle {\overrightarrow {P_{1}P_{3}}}} , which is given by the expression ( x 2 − x 1 ) ( y 3 − y 1 ) − ( y 2 − y 1 ) ( x 3 − x 1 ) {\displaystyle (x_{2}x_{1})(y_{3}y_{1})(y_{2}y_{1})(x_{3}x_{1})} . If the result is 0, the points are collinear; if it is positive, the three points constitute a “left turn” or counterclockwise orientation, otherwise a “right turn” or clockwise orientation (for counterclockwise numbered points).
This process will eventually return to the point at which it started, at which point the algorithm is completed and the stack now contains the points on the convex hull in counterclockwise order.
//acoperirea convexa (algoritmul Graham) #include <string.h> #include <math.h> #include <stdio.h> #include <stdlib.h> #include <conio.h> #include <dos.h> #include <graphics.h> typedef struct point { float x,y; }point; point p[1000]; int n; int s[1000];//stiva in care la final vor fi punctele acoperirii convexe int t;//cate elemente sunt in stiva s int q[1000];//in q vom avea indicii punctelor sortate int i,j,temp; void initg() { int gdriver = DETECT, gmode, errorcode; initgraph(&gdriver, &gmode, "c:\\borlandc\\bgi"); errorcode = graphresult(); if (errorcode != grOk) /* an error occurred */ printf("Graphics not initialised !!!"); } float aria(point a,point b,point c) { float ar; ar=((b.xa.x)*(c.ya.y)(b.ya.y)*(c.xa.x))/2.; return ar; } int compare(int i,int j) { float r; if (i==j) return 0; r=aria(p[q[0]], p[q[i]], p[q[j]]); if (r>0) return 1; else if (r<0) return 1; } void graham() { for (i=0;i<n;i++) q[i]=i;//in q vom avea indicii punctelor sortate //acum vom calcula temp=indicele punctului cel mai de jos, dreapta: temp=0; for (i=0;i<n;i++) if ( (p[i].y < p[temp].y)  (p[i].y==p[temp].y && p[i].x > p[temp].x) ) temp=i; //acum schimb pe p0 cu 0: q[0]=temp; q[temp]=0; //acum ordonam punctele: for (i=0;i<n;i++) for (j=i+1;j<n;j++) if (compare(i,j)<0){ temp=q[i]; q[i]=q[j]; q[j]=temp; } s[0]=0;//punctul 0 este extrem s[1]=1;//punctul 1 este extrem t=2;//cate elemente am in stiva s i=1; while(i!=0){ ++i%=n;//adica i=(i+1)%n sau {i++;i=i%n;} if (aria(p[q[s[t2]]], p[q[s[t1]]], p[q[i]])>0) s[t++]=i;//punem punctul i in stiva else { t; i; }//scoatem ultimul punct din stiva } //afisam punctele convexe: for (i=0;i<t;i++) printf(" %d,",q[s[i]]); } void citire() { float var, *p_var=&var; char c[3]; //citire de la tastatura /*printf("\nDati numarul de puncte:"); scanf("%d",&n); for(i=0;i<n;i++) { printf("Coord. pentru vf %d:",i); scanf("%f%f",&p[i].x,&p[i].y); }*/ //citire randomize printf("n="); scanf("%d",&n); randomize(); for (i=0;i<n;i++) { p[i].x=100+random(300); p[i].y=100+random(300); } //desenare puncte for(i=0;i<n;i++) { itoa(i,c,10); setcolor(YELLOW); circle(p[i].x,p[i].y,1); setcolor(RED); outtextxy(p[i].x+3,p[i].y+3,c); } } void desenez() { char c[3]; for(i=0;i<n;i++) { setcolor(YELLOW); lineto(p[i].x,p[i].y); } } void main() { initg(); citire(); printf("\nAcoperirea convexa:"); graham(); getch(); //cleardevice(); //setbkcolor(BLUE); desenez(); getch(); }
68,694 total views, 464 views today