CONVEX HULL

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;

                 }

                 catch(Exception e)

                 {

                   degree=90;

                 }

                 if(i==p+1)

                 {

                  deg=degree;

                  next=i;

                 }

                 else

                 {

                  if((c=='L' && deg>degree)||(c!='L' && deg<degree)

                           ||(degree==deg && x[i]<x[next]))                                         

                  {

                   deg=degree;

                   next=i;

                  }

                 }

                }

                if(next!=0)

                   check(next,c);

        }

}

class convexhull

{

        public static void main(String arg[]) throws IOException

        {

                convexhullalg c=new convexhullalg();

                c.insert();

        }

 OUTPUT:

--------

Enter number of points:

4

Enter x and y coordinates for

point 1

2

6

point 2

7

8

point 3

1

4

point 4

2

10

Boundary points are

(1, 4)

(2, 10)

(7, 8)

 RESULT:

                        Thus the program for convex hull has been implemented using Java and the output is verified.