AIM
To write a Java program for the
implementation of convex hull
ALGORITHM
Step1: Start the program
Step2: Create a class convexhullalg
Step3: Read the number of points
Step4: Get the x and y co-ordinate values
Step5: Sort the values using sort function
Step6: To sort two values swap the values of i and j
Step7: Call the function display to display the
boundary points
Step8: The function check id used to check whether
the point is angular or not(180▫)
Step9: End of the program
PROGRAM
CONVEX HULL
import java.io.*;
class convexhullalg
{
int
x[],y[],n;
boolean
status[];
void
insert()
{
try
{
DataInputStream in=new DataInputStream(System.in);
System.out.println("Enter number of points:");
n=Integer.parseInt(in.readLine());
x=new int[n];
y=new int[n];
status=new boolean[n];
System.out.println("Enter x and y coordinates for ");
for(int i=0;i<n;i++)
{
System.out.println("point "+(i+1));
x[i]=Integer.parseInt(in.readLine());
y[i]=Integer.parseInt(in.readLine());
status[i]=false;
}
}
catch(Exception e){}
sort();
check(0,'L');
check(0,'H');
display();
}
void sort()
{
for(int i=0;i<n-1;i++)
{
for(int j=i+1;j<n;j++)
if((x[i]>x[j]) || ((x[i]==x[j]) && (y[i]>y[j])))
swap(i, j);
}
}
void
swap(int i,int j)
{
int
temp=x[i];
x[i]=x[j];
x[j]=temp;
temp=y[i];
y[i]=y[j];
y[j]=temp;
}
void
display()
{
System.out.println("Boundary points are");
for(int i=0;i<n;i++)
if(status[i]==true)
System.out.println("("+x[i]+",
"+y[i]+")");
}
void check(int p,char c)
{
double slope=0,degree=0,deg=0;
int
next=0;
status[p]=true;
for(int i=p+1;i<n;i++)
{
try
{
slope=(double)(x[i]-x[p])/(double)(y[i]-y[p]);
degree=Math.toDegrees(Math.atan(slope));
if(degree < 0)
degree+=180;
}
