컨벡스 헐 (Convex Hull)

Convex Hull 이란?

 

2차원 평면에 좌표들이 주어졌을때 가장 바깥쪽의 좌표들만 연결하여 다각형을 만드는 알고리즘

결과적으로는 컨벡스 헐을 구성하는 점들의 좌표를 얻을 수 있다.

모든 좌표들은 구해진 경계선 안에 존재한다. 그렇기에 점들이 차지하는 최소 영역을 구할 수 있다.

 

 

Graham Scan Algorithm

 

- 먼저 점들을 y좌표 기준, 같으면 x좌표 기준으로 정렬한다. (오름차순) -> 어디에서 시작(가장 아래)하는지

- 가장 아래에 있는 점을 기준으로, 나머지 점들을 각도 기준으로 정렬한다.

  (각도는 기준점에서 반시계방향(각도 높음)인지 확인. CCW(Counter Clock Wise) 사용)

    CCW 판별: p->q->r의 회전 알고싶을때 (q.x - p.x) * (r.y - p.y) - (q.y - p.y) * (r.x - p.x)

    => 결과가 음수면 시계방향, 양수면 반시계방향. 절댓값은 꺾이는 정도 나타냄.

 

- 기준점부터 순서대로 점을 보면서 스택에 넣되, 스택의 상위 두 점과 현재 점이 시계 방향을 이루면 pop 한다.

- 이 과정을 반복하여, 반시계 방향(CCW)만 유지하도록 한다.

- 모든 점을 확인했을때 스택에 남아있는 값이 컨벡스헐이 된다.

 

 

import java.util.*;
 
// 점을 표현하는 클래스
class Point {
    int x, y;
 
    Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
 
    // 두 점의 방향을 계산하는 메서드 (교차 곱)
    static int crossProduct(Point p, Point q, Point r) {
        return (q.x - p.x) * (r.y - p.y) - (q.y - p.y) * (r.x - p.x);
    }
}
 
public class ConvexHull {
 
    // 그라함 스캔 알고리즘
    public static List<Point> grahamScan(List<Point> points) {
        if (points.size() < 3) {
            return points;
        }
 
        // 기준점 찾기
        points.sort((p1, p2) -> (p1.y == p2.y) ? Integer.compare(p1.x, p2.x) : Integer.compare(p1.y, p2.y));
        Point start = points.remove(0);
 
        // 각도기준 정렬
        points.sort((p1, p2) -> {
            int cp = Point.crossProduct(start, p1, p2);
            if (cp == 0) {
                return Integer.compare(distance(start, p1), distance(start, p2));
            }
            return cp > 0 ? -1 : 1;
        });
 
        // CCW 판별로 컨벡스헐 구성하는지 확인
        Stack<Point> stack = new Stack<>();
        stack.push(start);
      stack.push(points.get(0));
 
        for (int i = 1; i < points.size(); i++) {
            while (stack.size() > 1 && Point.crossProduct(stack.get(stack.size() - 2), stack.peek(), points.get(i)) <= 0) {
                stack.pop();
            }
            stack.push(points.get(i));
        }
 
        // 스택에 남은 점들이 컨벡스 헐을 구성하는 점들
        return new ArrayList<>(stack);
    }
 
    // 두 점 간의 거리
    public static int distance(Point p1, Point p2) {
        return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
    }
 
    // 최종 출력
    public static void printConvexHull(List<Point> convexHull) {
        for (Point p : convexHull) {
            System.out.println("(" + p.x + ", " + p.y + ")");
        }
    }
 
    public static void main(String[] args) {
        List<Point> points = new ArrayList<>();
        points.add(new Point(0, 0));
        points.add(new Point(1, 1));
        points.add(new Point(2, 2));
        points.add(new Point(4, 4));
        points.add(new Point(0, 4));
        points.add(new Point(1, 3));
        points.add(new Point(3, 0));
 
        List<Point> convexHull = grahamScan(points);
        System.out.println("컨벡스 헐을 구성하는 점들:");
        printConvexHull(convexHull);
    }
}