# 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. `}`

```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. 