Java Program to Implement Jarvis Algorithm

«
»
This is a Java Program to Implement Jarvis Algorithm. Jarvis algorithm or the gift wrapping algorithm is an algorithm for computing the convex hull of a given set of points.

Here is the source code of the Java Program to Implement Jarvis Algorithm. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1. /**
  2.  ** Java Program to Implement Jarvis Algorithm
  3.  **/
  4.  
  5. import java.util.Scanner;
  6. import java.util.Arrays;
  7.  
  8. /** Class point **/
  9. class Point
  10. {
  11.     int x, y;
  12. }
  13.  
  14. /** Class Jarvis **/
  15. public class Jarvis
  16. {    
  17.     private boolean CCW(Point p, Point q, Point r)
  18.     {
  19.         int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
  20.  
  21.          if (val >= 0)
  22.              return false;
  23.          return true;
  24.     }
  25.     public void convexHull(Point[] points)
  26.     {
  27.         int n = points.length;
  28.         /** if less than 3 points return **/        
  29.         if (n < 3) 
  30.             return;     
  31.         int[] next = new int[n];
  32.         Arrays.fill(next, -1);
  33.  
  34.         /** find the leftmost point **/
  35.         int leftMost = 0;
  36.         for (int i = 1; i < n; i++)
  37.             if (points[i].x < points[leftMost].x)
  38.                 leftMost = i;
  39.         int p = leftMost, q;
  40.         /** iterate till p becomes leftMost **/
  41.         do
  42.         {
  43.             /** wrapping **/
  44.             q = (p + 1) % n;
  45.             for (int i = 0; i < n; i++)
  46.               if (CCW(points[p], points[i], points[q]))
  47.                  q = i;
  48.  
  49.             next[p] = q;  
  50.             p = q; 
  51.         } while (p != leftMost);
  52.  
  53.         /** Display result **/
  54.         display(points, next);
  55.     }
  56.     public void display(Point[] points, int[] next)
  57.     {
  58.         System.out.println("\nConvex Hull points : ");
  59.         for (int i = 0; i < next.length; i++)
  60.             if (next[i] != -1)
  61.                System.out.println("("+ points[i].x +", "+ points[i].y +")");
  62.     }
  63.     /** Main function **/
  64.     public static void main (String[] args) 
  65.     {
  66.         Scanner scan = new Scanner(System.in);
  67.         System.out.println("Jarvis Algorithm Test\n");
  68.         /** Make an object of Jarvis class **/
  69.         Jarvis j = new Jarvis();        
  70.  
  71.         System.out.println("Enter number of points n :");
  72.         int n = scan.nextInt();
  73.         Point[] points = new Point[n];
  74.         System.out.println("Enter "+ n +" x, y cordinates");
  75.         for (int i = 0; i < n; i++)
  76.         {
  77.             points[i] = new Point();
  78.             points[i].x = scan.nextInt();
  79.             points[i].y = scan.nextInt();
  80.         }        
  81.         j.convexHull(points);        
  82.     }
  83. }

advertisement
Jarvis Algorithm Test
 
Enter number of points n :
8
Enter 8 x, y cordinates
0 3
4 2
3 5
5 3
3 0
1 1
1 2
2 2
 
Convex Hull points :
(0, 3)
(3, 5)
(5, 3)
(3, 0)
(1, 1)

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn