CONVEXHULL
Program Coding:
import java.io.*;
import java.lang.*;
class convexhull
{
int
a[][];
public
int n;
boolean
b[];
double
ndeg=0;
int
next=0;
void
nextfn(double deg,int i)
{
ndeg=deg;
next=i;
}
void
insertpts() throws Exception
{
DataInputStream
in=new DataInputStream(System.in);
System.out.println("enter
the size:");
n=Integer.parseInt(in.readLine());
a=new
int[2][n];
b=new
boolean[n];
for(int
i=0;i<n;i++)
{
System.out.println("enter
the "+(i+1)+" x:");
a[0][i]=Integer.parseInt(in.readLine());
System.out.println("enter
the "+(i+1)+" y:");
a[1][i]=Integer.parseInt(in.readLine());
b[i]=false;
for(int
j=0;j<i;j++)
{
if(a[0][i]<a[0][j])
swap(j,i);
if(a[0][i]==a[0][j]
&& a[1][i]<a[1][j])
swap(j,i);
}
}
display(false);
}
void
swap(int i,int j)
{
int
temp=a[0][i];
a[0][i]=a[0][j];
a[0][j]=temp;
temp=a[1][i];
a[1][i]=a[1][j];
a[1][j]=temp;
}
public
void display(boolean k)
{
if(k==true)
System.out.println("boundry
pt are");
for(int
i=0;i<n;i++)
{
if(k==true
&& b[i]==false)
continue;
System.out.println("pt:("+a[0][i]+","+a[1][i]+")");
}}
public
void traverse(int x,char c)
{
b[x]=true;
double
slope=0,deg=0;
int
i=0;
next=0;
ndeg=0;
for(i=x+1;i<n;i++)
{
try{
slope=(double)(a[0][i]-a[0][x]);
slope/=(double)(a[1][i]-a[1][x]);
deg=Math.toDegrees(Math.atan(slope));
if(deg
< 0)
deg=180+deg;
}
catch(Exception
ex)
{
deg=90;
}
if(i==x+1)
{
nextfn(deg,i);
}
else
{
if(c=='L')
{
if(ndeg>deg)
nextfn(deg,i);
}
else{
if(ndeg<deg)
nextfn(deg,i);
}
if(deg==ndeg)
{
if(deg==90
&& a[1][i]<a[1][i])
nextfn(deg,i);
else
if(a[0][i]<a[0][next])
nextfn(deg,i);
}}}
if(next!=0)
{
traverse(next,c);
}
}
public static void main(String arg[]) throws Exception
{
convexhull
c=new convexhull();
c.insertpts();
if
(c.n>0)
{
c.traverse(0,'L');
c.traverse(0,'H');
}
c.display(true);
}
}
Output:
CONVEXHULL
Enter thesize:
3
Enter the1x:
7
Enter the 1y:
5
Enter the2x:
9
Enter the 2y:
4
Enter the3x:
3
Enter the 3y:
8
Pt:(3,8)
Pt:(7,5)
Pt:(9,4)
Boundary Points are:
Pt:(3,8)
Pt:(7,5)
Pt:(9,4)
No comments:
Post a Comment