Dynamic Convex hull | Adding Points to an Existing Convex Hull

// Java program to add given a point p to a given // convex hull. The program assumes that the // point of given convex hull are in anti-clockwise // order. import java.io.*; import java.util.*; class GFG  {  // checks whether the point crosses the convex hull  // or not  static int orientation(ArrayList<Integer> a,  ArrayList<Integer> b,  ArrayList<Integer> c)  {  int res = (b.get(1) - a.get(1)) * (c.get(0) - b.get(0)) -  (c.get(1) - b.get(1)) * (b.get(0)-a.get(0));  if (res == 0)  return 0;  if (res > 0)  return 1;  return -1;  }  // Returns the square of distance between two input points  static int sqDist(ArrayList<Integer>p1, ArrayList<Integer>p2)  {  return (p1.get(0) - p2.get(0)) * (p1.get(0) - p2.get(0)) +   (p1.get(1) - p2.get(1)) * (p1.get(1) - p2.get(1));  }  // Checks whether the point is inside the convex hull or not  static boolean inside(ArrayList<ArrayList<Integer>> A,ArrayList<Integer>p)  {  // Initialize the centroid of the convex hull  ArrayList<Integer> mid = new ArrayList<Integer>(Arrays.asList(0,0));  int n = A.size();  for (int i = 0; i < n; i++)  {  mid.set(0,mid.get(0) + A.get(i).get(0));  mid.set(1,mid.get(1) + A.get(i).get(1));  }  // if the mid and the given point lies always  // on the same side w.r.t every edge of the  // convex hull, then the point lies inside  // the convex hull  for (int i = 0, j; i < n; i++)  {  j = (i + 1) % n;  int x1 = A.get(i).get(0)*n, x2 = A.get(j).get(0)*n;  int y1 = A.get(i).get(1)*n, y2 = A.get(j).get(1)*n;  int a1 = y1 - y2;  int b1 = x2 - x1;  int c1 = x1 * y2 - y1 * x2;  int for_mid = a1 * mid.get(0) + b1 * mid.get(1) + c1;  int for_p = a1 * p.get(0) * n + b1 * p.get(1) * n + c1;  if (for_mid*for_p < 0)  return false;  }  return true;  }  // Adds a point p to given convex hull a[]  static void addPoint(ArrayList<ArrayList<Integer>> a,ArrayList<Integer> p)  {  // If point is inside p  if (inside(a, p))  return;  // point having minimum distance from the point p  int ind = 0;  int n = a.size();  for (int i = 1; i < n; i++)  {  if (sqDist(p, a.get(i)) < sqDist(p, a.get(ind)))  {  ind = i;  }  }  // Find the upper tangent  int up = ind;  while (orientation(p, a.get(up), a.get((up+1)%n))>=0)  up = (up + 1) % n;  // Find the lower tangent  int low = ind;  while (orientation(p, a.get(low), a.get((n+low-1)%n))<=0)  low = (n+low - 1) % n;  // Initialize result  ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();  // making the final hull by traversing points  // from up to low of given convex hull.  int curr = up;  ret.add(a.get(curr));  while (curr != low)  {  curr = (curr + 1) % n;  ret.add(a.get(curr));  }  // Modify the original vector  ret.add(p);  a.clear();  for (int i = 0; i < ret.size(); i++)  {  a.add(ret.get(i));  }  }  // Driver code  public static void main (String[] args)   {  // the set of points in the convex hull  ArrayList<ArrayList<Integer>> a = new ArrayList<ArrayList<Integer>>();  a.add(new ArrayList<Integer>(Arrays.asList(0, 0)));  a.add(new ArrayList<Integer>(Arrays.asList(3, -1)));  a.add(new ArrayList<Integer>(Arrays.asList(4, 5)));  a.add(new ArrayList<Integer>(Arrays.asList(-1, 4)));  int n = a.size();  ArrayList<Integer> p = new ArrayList<Integer>(Arrays.asList(100,100));  addPoint(a, p);  // Print the modified Convex Hull  for(ArrayList<Integer> e:a )  {  System.out.print("(" + e.get(0) + ", " + e.get(1) + ") ");  }  } } // This code is contributed by rag2127