Convex hull
Algorithm
Input Set S of points.
Output Set of points which form convex hull .
Complexity O(nlgn)
Convex hull(S: set of points {P = (P.x,P.y)}):
Select the rightmost lowest point P0 in S.
Sort S angularly about P0 as a center.
For ties, discard the closer points.
Let P[N] be the sorted array of points.
Push P[0]=P0 and P[1] onto a stack W.
WHILE < N DO
Let PT1 = the top point on W
Let PT2 = the second top point on W
IF (P[i] is strictly left of the line PT2 to PT1) THEN
Push P[i] onto W
i++ // increment i
ELSE
Pop the top point PT1 off the stack
ENDIF
END
RETURN W = the convex hull of S
Algorithm Description
C Code
// Fibonacci heap
#include<stdio.h>
#include<conio.h>
#define s 20
struct corr
{
int x;
int y;
}cor[s],st1[s],st[s],half[s],half1[s];
int lp=1,lp1=0;
int main()
{
int i,di,n,min,a=0,p,j,data,data1,m,z,w,ds,d1,d2,d3;
printf("Enter the total number of points");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("Enter the x coordinate than y\t");
scanf("%d%d",&cor[i].x,&cor[i].y);
}
for(i=0;i<n;i++) //insertion sort
{
for(j=0;j<n-1;j++)
{
if(cor[j].y>cor[j+1].y)
{
data=cor[j].y;
data1=cor[j].x ;
cor[j].y=cor[j+1].y;
cor[j].x=cor[j+1].x;
cor[j+1].y=data;
cor[j+1].x=data1;
}
}
}
printf("\nSorted coordinates\t "); //After sorting
for(i=0;i<n;i++)
{
printf("(%d %d)\t",cor[i].x,cor[i].y);
}
half[0].x=cor[0].x;
half[0].y=cor[0].y;
half1[0].x=cor[0].x;
half1[0].y=cor[0].y;
m=1,w=1;
for(i=1;i<n;i++) //store coordiante greater than x of lowest
{
if(cor[0].x<cor[i].x)
{
half[m].x=cor[i].x;
half[m].y=cor[i].y;
m++;
}
else
{
half1[w].x=cor[i].x; //store coordiante less than x of lowest
half1[w].y=cor[i].y;
w++;
}
}
printf("ist half is "); //printf ist half
for(i=0;i<m;i++)
{
printf("\t(%d %d)",half[i].x,half[i].y);
}
printf("2nd half is\n"); //printf 2nd half2
for(i=0;i<w;i++)
{
printf("\t(%d %d)",half1[i].x,half1[i].y);
}
printf("\n\n\nMission\t"); //print aur main output
printf("\t(%d %d)",half[0].x,half[0].y);
for(i=1;i<m;) //calculate determinant
{
d1=half[i-1].x*half[i].y-half[i-1].x*half[i+1].y ;
d2 =half[i-1].y*half[i].x-half[i-1].y*half[i+1].x ;
d3=half[i].x*half[i+1].y-half[i+1].x*half[i].y ;
di=d1+d3-d2;
if(di>0)
{
st[lp].x=half[i].x;
st[lp].y=half[i].y;
lp=lp+1;
i=i+1;
}
else
{
st[lp].x=half[i+1].x; //skip ist
st[lp].y=half[i+1].y;
lp=lp+1;
i=i+1;
}
}
for(i=1;i<w;) //calculate determinant for 2nd half
{
d1=half1[i-1].x*half1[i].y-half1[i-1].x*half1[i+1].y ;
d2 =half1[i-1].y*half1[i].x-half1[i-1].y*half1[i+1].x ;
d3=half1[i].x*half1[i+1].y-half1[i+1].x*half1[i].y ;
ds=d1+d3-d2 ;
if(ds<0)
{
st1[lp1].x=half1[i].x;
st1[lp1].y=half1[i].y;
lp1=lp1+1;
i=i+1;
}
else
{
st1[lp1].x=half1[i+1].x; //skip first
st1[lp1].y=half1[i+1].y;
lp1=lp1+1;
i=i+1;
}
}
for(i=1;i<m;i++)
{
if(st[i].x==st[i+1].x && st[i].y==st[i+1].y) //check for duplicate
printf(" ");
else
printf("\t(%d %d)",st[i].x,st[i].y);
}
printf("\tLeftmost");
for(i=0;i<w;i++) //check for duplicate 2nd half
{
if(st1[i].x==st1[i+1].x && st1[i].y==st1[i+1].y)
printf(" ");
else
printf("\t(%d %d)",st1[i].x,st1[i].y);
}
}
Java Code
import java.io.*;
class convex
{
float angle1(int a[][],int m,int n)
{
float angle=0;
float temp;
// angle less than 90
if(a[n][1]>a[m][1] && a[n][0]>a[m][0])
{
temp=(float)Math.sqrt(Math.pow((a[n][1]-a[m][1]),2)+Math.pow((a[n][0]-a[m][0]),2));
angle=(float)(a[n][1]-a[m][1])/temp;
}
//angle b/w 90 and 180
if(a[n][1]>a[m][1] && a[m][0]>a[n][0])
{
temp=(float)Math.sqrt(Math.pow((a[n][1]-a[m][1]),2)+Math.pow((a[m][0]-a[n][0]),2));
angle=(float)(a[m][0]-a[n][0])/temp;
angle=angle+1;
}
//angle b/w 180 and 270
if(a[m][1]>a[n][1] && a[m][0]>a[n][0])
{
temp=(float)Math.sqrt(Math.pow((a[m][1]-a[n][1]),2)+Math.pow((a[m][0]-a[n][0]),2));
angle=(float)(a[m][1]-a[n][1])/temp;
angle=angle+2;
}
//angle b/w 270 and 360
if(a[n][0]>a[m][0] && a[m][1]>a[n][1])
{
temp=(float)Math.sqrt(Math.pow((a[m][1]-a[n][1]),2)+Math.pow((a[n][0]-a[m][0]),2));
angle=(float)(a[n][0]-a[m][0])/temp;
angle=angle+3;
}
//angle 0
if(a[n][0]>=a[m][0] && a[m][1]==a[n][1])
{
angle=0;
}
//angle 90
if(a[n][0]==a[m][0] && a[n][1]>a[m][1])
{
angle=1;
}
// angle 180
if(a[n][1]==a[m][1] && a[n][0]<a[m][0])
{
angle=2;
}
//angle 270
if(a[n][0]==a[m][0] && a[n][1]<a[m][1])
{
angle=3;
}
return angle;
}
public static void main(String args[]) throws IOException
{
int n,i,j,k,temp1,temp2,fp=0,z;
float min=0,previous;
convex c = new convex();
System.out.println("Enter the number of points the hull");
BufferedReader br = new BufferedReader (new InputStreamReader(System.in));
n=Integer.parseInt(br.readLine());
int a[][] = new int[n][2];
int f[][] = new int[n][2];
System.out.println("Enter the coordinates of the points");
for(i=0;i<n;i++)
{
System.out.println("Enter the x-coordinate and y-coordinate of "+(i+1)+"th point");
a[i][0]=Integer.parseInt(br.readLine());
a[i][1]=Integer.parseInt(br.readLine());
}
i=0;
for(j=i+1;j<n;j++)
{
if(a[i][1]>=a[j][1])
{
if(((a[i][1]==a[j][1]) && (a[i][0]>a[j][0])) || (a[i][1]>a[j][1]))
{
temp1=a[i][0];
a[i][0]=a[j][0];
temp2=a[i][1];
a[i][1]=a[j][1];
a[j][0]=temp1;
a[j][1]=temp2;
}
}
}
f[fp][0]=a[0][0];
f[fp][1]=a[0][1];
fp++;
j=1;
k=0;
min=c.angle1(a,k,1);
for(i=2;i<n;i++)
{
if(c.angle1(a,k,i)<=min)
{
if(c.angle1(a,k,i)<min)
{
min=c.angle1(a,k,i);
j=i;
}
else
{
if(a[i][0]<a[j][0] || a[i][1]<a[j][1])
j=i;
}
}
}
f[fp][0]=a[j][0];
f[fp][1]=a[j][1];
fp++;
z=k;
do
{
previous=c.angle1(a,j,z);
z=j;
min=previous+4;
if(previous>=2)
previous=previous-4;
for(i=0;i<n;i++)
{
if(i!=j )
{
if(c.angle1(a,j,i)<=min && c.angle1(a,j,i)>previous)
{
if(c.angle1(a,j,i)<min)
{
min=c.angle1(a,j,i);
k=i;
}
else
{
if(min<2)
{
if(a[i][0]<a[k][0] || a[i][1]<a[k][1])
k=i;
}
if(min>2)
{
if(a[i][0]>a[k][0] || a[i][1]>a[k][1])
k=i;
}
}
}
}
}
f[fp][0]=a[k][0];
f[fp][1]=a[k][1];
fp++;
j=k;
}while(fp<=n && (f[fp-1][0]!=f[0][0] || f[fp-1][1]!=f[0][1]));
System.out.println("The sides of convex hull will be");
for(i=0;i<fp-1;i++)
{
System.out.println("\t("+f[i][0]+","+f[i][1]+") ("+f[i+1][0]+","+f[i+1][1]+")");
}
}
}
