Posts

Showing posts from July, 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) {…