Java Program to Find the Convex Hull using Graham Scan Algorithm

This is a Java Program to implement Graham Scan Algorithm. Graham’s scan is a method of computing the convex hull of a finite set of points in the plane with time complexity O(n log n).

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

  1. //This is a java program to implement Graham Scan Algorithm
  2. import java.util.Arrays;
  3. import java.util.Comparator;
  4. import java.util.Scanner;
  5. import java.util.Stack;
  6.  
  7. class Point2D implements Comparable<Point2D>
  8. {
  9.     public static final Comparator<Point2D> X_ORDER = new XOrder();
  10.     public static final Comparator<Point2D> Y_ORDER = new YOrder();
  11.     public static final Comparator<Point2D> R_ORDER = new ROrder();
  12.     public final Comparator<Point2D> POLAR_ORDER = new PolarOrder();
  13.     public final Comparator<Point2D> ATAN2_ORDER = new Atan2Order();
  14.     public final Comparator<Point2D> DISTANCE_TO_ORDER = new DistanceToOrder();
  15.  
  16.     private final double x; // x coordinate
  17.     private final double y; // y coordinate
  18.  
  19.     public Point2D(double x, double y)
  20.     {
  21.         if (Double.isInfinite(x) || Double.isInfinite(y))
  22.             throw new IllegalArgumentException("Coordinates must be finite");
  23.         if (Double.isNaN(x) || Double.isNaN(y))
  24.             throw new IllegalArgumentException("Coordinates cannot be NaN");
  25.         if (x == 0.0)
  26.             x = 0.0; // convert -0.0 to +0.0
  27.         if (y == 0.0)
  28.             y = 0.0; // convert -0.0 to +0.0
  29.         this.x = x;
  30.         this.y = y;
  31.     }
  32.  
  33.     public double x()
  34.     {
  35.         return x;
  36.     }
  37.  
  38.     public double y()
  39.     {
  40.         return y;
  41.     }
  42.  
  43.     public double r()
  44.     {
  45.         return Math.sqrt(x * x + y * y);
  46.     }
  47.  
  48.     public double theta()
  49.     {
  50.         return Math.atan2(y, x);
  51.     }
  52.  
  53.     private double angleTo(Point2D that)
  54.     {
  55.         double dx = that.x - this.x;
  56.         double dy = that.y - this.y;
  57.         return Math.atan2(dy, dx);
  58.     }
  59.  
  60.     public static int ccw(Point2D a, Point2D b, Point2D c)
  61.     {
  62.         double area2 = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
  63.         if (area2 < 0)
  64.             return -1;
  65.         else if (area2 > 0)
  66.             return +1;
  67.         else
  68.             return 0;
  69.     }
  70.  
  71.     public static double area2(Point2D a, Point2D b, Point2D c)
  72.     {
  73.         return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
  74.     }
  75.  
  76.     public double distanceTo(Point2D that)
  77.     {
  78.         double dx = this.x - that.x;
  79.         double dy = this.y - that.y;
  80.         return Math.sqrt(dx * dx + dy * dy);
  81.     }
  82.  
  83.     public double distanceSquaredTo(Point2D that)
  84.     {
  85.         double dx = this.x - that.x;
  86.         double dy = this.y - that.y;
  87.         return dx * dx + dy * dy;
  88.     }
  89.  
  90.     public int compareTo(Point2D that)
  91.     {
  92.         if (this.y < that.y)
  93.             return -1;
  94.         if (this.y > that.y)
  95.             return +1;
  96.         if (this.x < that.x)
  97.             return -1;
  98.         if (this.x > that.x)
  99.             return +1;
  100.         return 0;
  101.     }
  102.  
  103.     private static class XOrder implements Comparator<Point2D>
  104.     {
  105.         public int compare(Point2D p, Point2D q)
  106.         {
  107.             if (p.x < q.x)
  108.                 return -1;
  109.             if (p.x > q.x)
  110.                 return +1;
  111.             return 0;
  112.         }
  113.     }
  114.  
  115.     private static class YOrder implements Comparator<Point2D>
  116.     {
  117.         public int compare(Point2D p, Point2D q)
  118.         {
  119.             if (p.y < q.y)
  120.                 return -1;
  121.             if (p.y > q.y)
  122.                 return +1;
  123.             return 0;
  124.         }
  125.     }
  126.  
  127.     private static class ROrder implements Comparator<Point2D>
  128.     {
  129.         public int compare(Point2D p, Point2D q)
  130.         {
  131.             double delta = (p.x * p.x + p.y * p.y) - (q.x * q.x + q.y * q.y);
  132.             if (delta < 0)
  133.                 return -1;
  134.             if (delta > 0)
  135.                 return +1;
  136.             return 0;
  137.         }
  138.     }
  139.  
  140.     private class Atan2Order implements Comparator<Point2D>
  141.     {
  142.         public int compare(Point2D q1, Point2D q2)
  143.         {
  144.             double angle1 = angleTo(q1);
  145.             double angle2 = angleTo(q2);
  146.             if (angle1 < angle2)
  147.                 return -1;
  148.             else if (angle1 > angle2)
  149.                 return +1;
  150.             else
  151.                 return 0;
  152.         }
  153.     }
  154.  
  155.     private class PolarOrder implements Comparator<Point2D>
  156.     {
  157.         public int compare(Point2D q1, Point2D q2)
  158.         {
  159.             double dx1 = q1.x - x;
  160.             double dy1 = q1.y - y;
  161.             double dx2 = q2.x - x;
  162.             double dy2 = q2.y - y;
  163.  
  164.             if (dy1 >= 0 && dy2 < 0)
  165.                 return -1; // q1 above; q2 below
  166.             else if (dy2 >= 0 && dy1 < 0)
  167.                 return +1; // q1 below; q2 above
  168.             else if (dy1 == 0 && dy2 == 0)
  169.             { // 3-collinear and horizontal
  170.                 if (dx1 >= 0 && dx2 < 0)
  171.                     return -1;
  172.                 else if (dx2 >= 0 && dx1 < 0)
  173.                     return +1;
  174.                 else
  175.                     return 0;
  176.             } else
  177.                 return -ccw(Point2D.this, q1, q2); // both above or below
  178.         }
  179.     }
  180.  
  181.     private class DistanceToOrder implements Comparator<Point2D>
  182.     {
  183.         public int compare(Point2D p, Point2D q)
  184.         {
  185.             double dist1 = distanceSquaredTo(p);
  186.             double dist2 = distanceSquaredTo(q);
  187.             if (dist1 < dist2)
  188.                 return -1;
  189.             else if (dist1 > dist2)
  190.                 return +1;
  191.             else
  192.                 return 0;
  193.         }
  194.     }
  195.  
  196.     public boolean equals(Object other)
  197.     {
  198.         if (other == this)
  199.             return true;
  200.         if (other == null)
  201.             return false;
  202.         if (other.getClass() != this.getClass())
  203.             return false;
  204.         Point2D that = (Point2D) other;
  205.         return this.x == that.x && this.y == that.y;
  206.     }
  207.  
  208.     public String toString()
  209.     {
  210.         return "(" + x + ", " + y + ")";
  211.     }
  212.  
  213.     public int hashCode()
  214.     {
  215.         int hashX = ((Double) x).hashCode();
  216.         int hashY = ((Double) y).hashCode();
  217.         return 31 * hashX + hashY;
  218.     }
  219.  
  220. }
  221.  
  222. public class GrahamScan
  223. {
  224.     private Stack<Point2D> hull = new Stack<Point2D>();
  225.  
  226.     public GrahamScan(Point2D[] pts)
  227.     {
  228.  
  229.         // defensive copy
  230.         int N = pts.length;
  231.         Point2D[] points = new Point2D[N];
  232.         for (int i = 0; i < N; i++)
  233.             points[i] = pts[i];
  234.         Arrays.sort(points);
  235.  
  236.         Arrays.sort(points, 1, N, points[0].POLAR_ORDER);
  237.  
  238.         hull.push(points[0]); // p[0] is first extreme point
  239.         int k1;
  240.         for (k1 = 1; k1 < N; k1++)
  241.             if (!points[0].equals(points[k1]))
  242.                 break;
  243.         if (k1 == N)
  244.             return; // all points equal
  245.  
  246.         int k2;
  247.         for (k2 = k1 + 1; k2 < N; k2++)
  248.             if (Point2D.ccw(points[0], points[k1], points[k2]) != 0)
  249.                 break;
  250.         hull.push(points[k2 - 1]); // points[k2-1] is second extreme point
  251.  
  252.         for (int i = k2; i < N; i++)
  253.         {
  254.             Point2D top = hull.pop();
  255.             while (Point2D.ccw(hull.peek(), top, points[i]) <= 0)
  256.             {
  257.                 top = hull.pop();
  258.             }
  259.             hull.push(top);
  260.             hull.push(points[i]);
  261.         }
  262.  
  263.         assert isConvex();
  264.     }
  265.  
  266.     public Iterable<Point2D> hull()
  267.     {
  268.         Stack<Point2D> s = new Stack<Point2D>();
  269.         for (Point2D p : hull)
  270.             s.push(p);
  271.         return s;
  272.     }
  273.  
  274.     private boolean isConvex()
  275.     {
  276.         int N = hull.size();
  277.         if (N <= 2)
  278.             return true;
  279.  
  280.         Point2D[] points = new Point2D[N];
  281.         int n = 0;
  282.         for (Point2D p : hull())
  283.         {
  284.             points[n++] = p;
  285.         }
  286.  
  287.         for (int i = 0; i < N; i++)
  288.         {
  289.             if (Point2D
  290.                     .ccw(points[i], points[(i + 1) % N], points[(i + 2) % N]) <= 0)
  291.             {
  292.                 return false;
  293.             }
  294.         }
  295.         return true;
  296.     }
  297.  
  298.     // test client
  299.     public static void main(String[] args)
  300.     {
  301.         System.out.println("Graham Scan Test");
  302.         Scanner sc = new Scanner(System.in);
  303.         System.out.println("Enter the number of points");
  304.         int N = sc.nextInt();
  305.  
  306.         Point2D[] points = new Point2D[N];
  307.         System.out.println("Enter the coordinates of each points: <x> <y>");
  308.         for (int i = 0; i < N; i++)
  309.         {
  310.             int x = sc.nextInt();
  311.             int y = sc.nextInt();
  312.             points[i] = new Point2D(x, y);
  313.         }
  314.         GrahamScan graham = new GrahamScan(points);
  315.         System.out.println("The convex hull consists of following points: ");
  316.         for (Point2D p : graham.hull())
  317.             System.out.println(p);
  318.  
  319.         sc.close();
  320.     }
  321.  
  322. }

Output:

$ javac GrahamScan.java
$ java GrahamScan
 
Graham Scan Test
Enter the number of points
5
Enter the coordinates of each points: <x> <y>
1 2
2 3
4 5
20 10
6 4 
The convex hull consists of following points: 
(1.0, 2.0)
(6.0, 4.0)
(20.0, 10.0)
(4.0, 5.0)
 
Graham Scan Test
Enter the number of points
5
Enter the coordinates of each points: <x> <y>
1 2
2 3
3 4
4 5
5 6
The convex hull consists of following points: 
(1.0, 2.0)
(5.0, 6.0)

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement

Here’s the list of Best Books in Java Programming, Data Structures and Algorithms.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.