Jarvis March Algorithm in Java

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.

```
/**
```

 ** Java Program to Implement Jarvis Algorithm

```
 **/
```
```
 
```
```
import java.util.Scanner;
```
```
import java.util.Arrays;
```
```
 
```
```
/** Class point **/
```
```
class Point
```
```
{
```
```
    int x, y;
```
```
}
```
```
 
```
```
/** Class Jarvis **/
```
```
public class Jarvis
```
```
{    
```

    private boolean CCW(Point p, Point q, Point r)

```
    {
```

        int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);

```
 
```
```
         if (val >= 0)
```
```
             return false;
```
```
         return true;
```
```
    }
```

    public void convexHull(Point[] points)

```
    {
```
```
        int n = points.length;
```

        /** if less than 3 points return **/

```
        if (n < 3) 
```
```
            return;     
```
```
        int[] next = new int[n];
```
```
        Arrays.fill(next, -1);
```
```
 
```
```
        /** find the leftmost point **/
```
```
        int leftMost = 0;
```
```
        for (int i = 1; i < n; i++)
```

            if (points[i].x < points[leftMost].x)

```
                leftMost = i;
```
```
        int p = leftMost, q;
```

        /** iterate till p becomes leftMost **/

```
        do
```
```
        {
```
```
            /** wrapping **/
```
```
            q = (p + 1) % n;
```
```
            for (int i = 0; i < n; i++)
```

              if (CCW(points[p], points[i], points[q]))

```
                 q = i;
```
```
 
```
```
            next[p] = q;  
```
```
            p = q; 
```
```
        } while (p != leftMost);
```
```
 
```
```
        /** Display result **/
```
```
        display(points, next);
```
```
    }
```

    public void display(Point[] points, int[] next)

```
    {
```

        System.out.println("\nConvex Hull points : ");

        for (int i = 0; i < next.length; i++)

```
            if (next[i] != -1)
```

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

```
    }
```
```
    /** Main function **/
```

    public static void main (String[] args)

```
    {
```

        Scanner scan = new Scanner(System.in);

        System.out.println("Jarvis Algorithm Test\n");

        /** Make an object of Jarvis class **/

        Jarvis j = new Jarvis();

```
 
```

        System.out.println("Enter number of points n :");

```
        int n = scan.nextInt();
```
```
        Point[] points = new Point[n];
```

        System.out.println("Enter "+ n +" x, y cordinates");

```
        for (int i = 0; i < n; i++)
```
```
        {
```
```
            points[i] = new Point();
```

            points[i].x = scan.nextInt();

            points[i].y = scan.nextInt();

```
        }        
```
```
        j.convexHull(points);        
```
```
    }
```
```
}
```

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.

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

« Prev - Java Program to Implement Manacher Algorithm

» Next - Java Program to Implement Cubic Convergence 1/pi Algorithm

Related Posts:

Recommended Articles: