July 18, 2016

Convex Hull in Java

Convex Hull 이라는 것은 points set의 외곽면을 찾는 것인데, 기하학이나 이미지 처리에서도 쓰인다. 알고리즘 문제에서는 흔히 가장 distance가 길거나 하는 형태로 출현하는데, Java로 한번 짜보자.

참고로 Apache Hama를 가지고 distributed convex optimization 구현도 찾아볼 수 있다 :)
http://www.slideshare.net/rogerz1234567/distributed-convex-optimization-thesis-behroz-sikander 

import java.util.Scanner;

public class Main {

  private static Stack hull;
  private static Point first;

  public static void solve(Point[] pts) {
    int N = pts.length;
    Point[] points = new Point[N];
    for (int i = 0; i < N; i++)
      points[i] = pts[i];

    Point[] tmp = new Point[points.length];
    mergeSort(0, points.length - 1, points, tmp, false);

    first = points[0];

    mergeSort(1, points.length - 1, points, tmp, true);

    hull.push(points[0]);
    hull.push(points[1]);
    
    for(int i = 2; i < N; i++) {
      Point head = points[i];
      Point middle = hull.pop();
      Point tail = hull.peek();

      int turn = ccw(tail, middle, head);
      
      switch(turn) {
          case 1:
              hull.push(middle);
              hull.push(head);
              break;
          case -1:
              i--;
              break;
          case 0:
              hull.push(head);
              break;
      }
    }
  }

  public static void mergeSort(int low, int high, Point[] a, Point[] tmp,
      boolean isFirst) {
    if (low < high) {
      int mid = low + (high - low) / 2;

      mergeSort(low, mid, a, tmp, isFirst);
      mergeSort(mid + 1, high, a, tmp, isFirst);
      merge(low, mid, high, a, tmp, isFirst);
    }
  }

  private static void merge(int low, int mid, int high, Point[] a, Point[] tmp,
      boolean isFirst) {
    for (int i = low; i <= high; ++i) {
      tmp[i] = a[i];
    }

    int i = low;
    int j = mid + 1;
    int k = low;

    while (i <= mid && j <= high) {
      boolean comp;
      if (isFirst) {
        comp = tmp[i].compareTo2(tmp[j]) <= 0;
      } else {
        comp = tmp[i].compareTo(tmp[j]) <= 0;
      }

      if (comp) {
        a[k] = tmp[i];
        i++;
      } else {
        a[k] = tmp[j];
        j++;
      }
      k++;
    }

    while (i <= mid) {
      a[k] = tmp[i];
      k++;
      i++;
    }
  }

  static Point[] stack = new Point[1000000];
  public static class Stack {
    private int top;
    int size;

    public Stack(int size) {
      this.size = size;
      top = -1;
    }

    public void push(Point v) {
      if (top == size - 1) {
        System.out.println("stack is full");
      } else {
        size++;
        top++;
        stack[top] = v;
      }
    }

    public Point pop() {
      if (!isEmpty()) {
        size--;
        return stack[top--];
      } else {
        return null;
      }
    }

    public Point peek() {
      if (isEmpty())
        return null;

      return stack[top];
    }

    public boolean isEmpty() {
      return top == -1;
    }

    public int size() {
      return top + 1;
    }

    public Point[] getArray() {
      Point[] tmp = new Point[this.size()];
      for (int i = 0; i < this.size(); i++) {
        tmp[i] = stack[i];
      }
      return tmp;
    }
  }

  public static int ccw(Point p1, Point p2, Point p3) {
    double area2 = (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x);
    if (area2 < 0)
      return -1;
    else if (area2 > 0)
      return +1;
    else
      return 0;
  }

  public static class Point implements Comparable {
    double x, y;

    public Point(int x, int y) {
      this.x = x;
      this.y = y;
    }

    public String toString() {
      return "(" + x + ", " + y + ")";
    }

    public int compareTo(Point that) {
      if (this.y < that.y)
        return -1;
      if (this.y > that.y)
        return +1;
      if (this.x < that.x)
        return -1;
      if (this.x > that.x)
        return +1;
      return 0;
    }

    public int compareTo2(Point q2) {
      double dx1 = this.x - first.x;
      double dy1 = this.y - first.y;
      double dx2 = q2.x - first.x;
      double dy2 = q2.y - first.y;

      if (dy1 >= 0 && dy2 < 0)
        return -1;
      else if (dy2 >= 0 && dy1 < 0)
        return +1;
      else if (dy1 == 0 && dy2 == 0) {
        if (dx1 >= 0 && dx2 < 0)
          return -1;
        else if (dx2 >= 0 && dx1 < 0)
          return +1;
        else
          return 0;
      } else {
        return -ccw(first, this, q2);
      }
    }

  }

  public static void main(String[] args) throws Exception {
    Scanner sc = new Scanner(System.in);
   
    int N = sc.nextInt();
    Point[] points = new Point[N];
    hull = new Stack(N + 1);
      
    for (int i = 0; i < N; i++) {
      int x = sc.nextInt();
      int y = sc.nextInt();
      points[i] = new Point(x, y);
    }
    solve(points);

    System.out.println(hull.size());
   
    sc.close();
  }

}