convexHull_grahamScan_java

ConvexHull.java

package ssw;

import java.util.*;

/**
 * Created by sunu.park on 2018. 11. 10.
 */

    class Point{
        int x, y;

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

        // 세 점으로 이루어진 삼각형의 면적을 구하는 방법을 이용해서 방향성을 구할수 있다
        // 0 라면 --> p,q,r 은 선형
        // 1 라면(양수) --> 반시계방향
        // 2 라면(음수) --> 시계방향
        public static int ccw(Point p, Point q, Point r){
            int val = (q.y -p.y) * (r.x - p.x) - (q.x - p.x) * (r.y - p.y);
            if (val == 0) return 0;
            return (val > 0)? 1: 2;
        }

        public static List<Point> convexHull_grahamScan(List<Point> pointList, int n)
        {

            //if(n < 3) return;

            // 가장 아래에 있는 점으로부터 시작한다 y좌표동일시 x좌표 최소값
            int l = 0;
            for( int i = 1; i <n; i++) {
                if (pointList.get(i).y < pointList.get(l).y) {
                    l = i;
                } else if (pointList.get(i).y == pointList.get(l).y) {
                    if (pointList.get(i).x < pointList.get(l).x) {
                        l = i;
                    }
                }
            }

            List<Point> sorted = new ArrayList<Point>(getSortedPointSet(pointList, l));

            // 스택에 첫 2 좌표를 집어넣는다
            Stack<Point> stack = new Stack<Point>();
            stack.push(sorted.get(0));
            stack.push(sorted.get(1));

            Point second = null, first = null, next = null;
            for(int i =2; i < n; i++)
            {
                while(stack.size() >= 2){

                    // 정렬된 좌표기준으로 다음값을 불러와서 next에 설정
                    // first 는 시작점 second는 다음점,
                    // 그리고 앞 두점이 만드는 직선보다 세번째 점이 반시계반향에 위치하면 스택에 넣는다
                    next = sorted.get(i);
                    second = stack.pop();
                    first = stack.peek();

                    if(ccw(first, second, next) == 1){
                        stack.add(second);
                        break;
                    }
                }
                stack.add(next);
            }

            return new ArrayList<Point>(stack);
        }

        private static Set<Point> getSortedPointSet(List<Point> pointList, int low) {
            final Point lowest = pointList.get(low);

            TreeSet<Point> set = new TreeSet<Point>(new Comparator<Point>() {
                @Override
                public int compare(Point p1, Point p2) {
                    // ccw 결과값 기준으로 작은 순서에서 큰 순서로 정렬하기
                    long ret = ccw(lowest, p1, p2);

                    if(ret == 1) return -1;
                    else if(ret == 2) return 1;

                    // ccw 결과값 동일시 거리기준으로 정렬
                    long disA = ((lowest.x - p1.x) * (lowest.x - p1.x)) + ((lowest.y - p1.y) * (lowest.y - p1.y));
                    long disB = ((lowest.x - p2.x) * (lowest.x - p2.x)) + ((lowest.y - p2.y) * (lowest.y - p2.y));

                    if( disA < disB) return -1;
                    else if( disA > disB) return 1;
                    return 0;
                }
            });

            set.addAll(pointList);
            return set;
        }

        public static void main(String[] args) {

            List<Point> pointList = new ArrayList<Point>();
            pointList.add(new Point(1, 1));
            pointList.add(new Point(1, 2));
            pointList.add(new Point(1, 3));
            pointList.add(new Point(2, 1));
            pointList.add(new Point(2, 2));
            pointList.add(new Point(2, 3));
            pointList.add(new Point(3, 1));
            pointList.add(new Point(3, 2));

            List<Point> hull = convexHull_grahamScan(pointList, pointList.size());

            for (Point temp : hull)
                System.out.println("(" + temp.x + ", " + temp.y + ")");

//            샘플데이터 결과값
//            (1, 1)
//            (1, 3)
//            (2, 3)
//            (3, 2)
//            (3, 1)

            Point testPoint = new Point(100, 100);  // 외부
            Point testPoint2 = new Point(2, 2);     // 내부
            for(int i =1; i< hull.size()-1; i++){
                // 모든 ccw 값이 동일하다면 내부, ccw 값이 다르다면 외부!
                if(ccw(hull.get(0), hull.get(1), testPoint) != ccw(hull.get(i), hull.get(i+1), testPoint)){
                    System.out.print("주어진 좌표는 기존 볼록껍질의 외부에 있다!");
                }
            }
        }
    }