convexhull.java

A Convex Hull is the smallest convex polygon that contains every point of the set S. A polygon P is

import java.io.*;
public class convexhull
{
public float isLeft( Point P0, Point P1, Point P2 )
{
    return (P1.x - P0.x)*(P2.y - P0.y) - (P2.x - P0.x)*(P1.y - P0.y);
}
public int hull_2D( Point P[], int n, Point H[] )
{
    
    int    bot=0, top=(-1); 
    int    i;               

    
    int minmin = 0, minmax;
    float xmin = P[0].x;
    for (i=1; i<n; i++)
        if (P[i].x != xmin) break;
    minmax = i-1;
    if (minmax == n-1) {       
        H[++top] = P[minmin];
        if (P[minmax].y != P[minmin].y) 
            H[++top] = P[minmax];
        H[++top] = P[minmin];         
        return top+1;
    }

   
    int maxmin, maxmax = n-1;
    float xmax = P[n-1].x;
    for (i=n-2; i>=0; i--)
        if (P[i].x != xmax) break;
    maxmin = i+1;

   
    H[++top] = P[minmin];      
    i = minmax;
    while (++i <= maxmin)
    {
    
        if (isLeft( P[minmin], P[maxmin], P[i]) >= 0 && i < maxmin)
            continue;     

        while (top > 0)   
        {
            
            if (isLeft( H[top-1], H[top], P[i]) > 0)
                break;         
            else
                top--;         
        }
        H[++top] = P[i];       
    }

    
    if (maxmax != maxmin)      
        H[++top] = P[maxmax];  
    bot = top;                 
    i = maxmin;
    while (--i >= minmax)
    {
        
        if (isLeft( P[maxmax], P[minmax], P[i]) >= 0 && i > minmax)
            continue;       
        while (top > bot)   
        {
            
            if (isLeft( H[top-1], H[top], P[i]) > 0)
                break;         
            else
                top--;         
        }
        H[++top] = P[i];       
    }
    if (minmax != minmin)
        H[++top] = P[minmin];  

    return top+1;
}


public static void main(String args[])throws IOException {try{

System.out.println("Enter the number of point you want to Enter :--");
BufferedReader pp=new BufferedReader(new InputStreamReader(System.in));
String no=pp.readLine();
int n=0;
n=(new Integer(no)).intValue();

Point p[]=new Point[n];
Point h[]=new Point[n];

System.out.println("Enter the points lexographic sorted order :--");


int i=0;
while(i<n)
{

System.out.println("Enter the x coordinate for point "+i+"   :----");
BufferedReader  bpl=new BufferedReader(new InputStreamReader(System.in));
String slot=bpl.readLine();
float x = Float.valueOf(slot).floatValue(); 
System.out.println("Enter the y coordinate for point "+i+"   :----");
BufferedReader  kbpl=new BufferedReader(new InputStreamReader(System.in));
String in=kbpl.readLine();
float y = Float.valueOf(in).floatValue(); 

Point pt=new Point();
pt.x=x;
pt.y=y;
p[i]=pt;
i++;

}
convexhull c=new convexhull();

int k= c.hull_2D(p,n,h);
i=0;
System.out.println("Points of Planar convex hull   :----");
while(i<k)
{

System.out.println("( "+h[i].x+" , "+h[i].y+" )");
i++;} 

}
catch(Exception e){
System.out.println();
System.out.println("              Error             ");
System.out.println("-----Plese check your input-----");System.out.println();}
}

}