기하 알고리즘 - 선분 교차와 볼록 껍질

기하 알고리즘은 컴퓨터 그래픽스, 게임 개발, GIS 등 다양한 응용 분야에서 중요하게 사용되는 알고리즘입니다. 오늘은 그 중에서도 선분 교차와 볼록 껍질 문제에 대해 알아보고, Java와 C 언어를 이용하여 구현해 보겠습니다.

선분 교차 (Line Segment Intersection)

선분 교차 문제는 두 선분이 주어졌을 때, 이들이 교차하는지를 판별하는 문제입니다. 이를 해결하기 위해 다양한 기하학적인 알고리즘이 존재하며, 그 중 두 선분의 방향을 이용하여 판별하는 알고리즘을 살펴보겠습니다.

두 선분이 교차하는지 확인하기 위해서는 다음과 같은 방법을 사용할 수 있습니다:

1. 선분의 끝점이 다른 선분의 어느 쪽에 위치하는지를 판별합니다.
2. 각 선분의 양 끝점에 대해 상대적인 위치를 이용해 방향을 계산하고, 이를 통해 교차 여부를 확인합니다.

선분 교차 판별 코드 (Java)

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

public class LineIntersection {
    // 두 점의 방향 계산
    static int direction(Point a, Point b, Point c) {
        double val = (b.y - a.y) * (c.x - b.x) - (b.x - a.x) * (c.y - b.y);
        if (val == 0) return 0;  // 일직선 상에 있음
        return (val > 0) ? 1 : 2; // 시계 방향 또는 반시계 방향
    }

    // 두 선분의 교차 여부 확인
    static boolean doIntersect(Point p1, Point q1, Point p2, Point q2) {
        int d1 = direction(p1, q1, p2);
        int d2 = direction(p1, q1, q2);
        int d3 = direction(p2, q2, p1);
        int d4 = direction(p2, q2, q1);

        // 일반적인 경우
        if (d1 != d2 && d3 != d4) return true;

        return false;
    }

    public static void main(String[] args) {
        Point p1 = new Point(1, 1);
        Point q1 = new Point(10, 1);
        Point p2 = new Point(1, 2);
        Point q2 = new Point(10, 2);

        if (doIntersect(p1, q1, p2, q2))
            System.out.println("선분이 교차합니다.");
        else
            System.out.println("선분이 교차하지 않습니다.");
    }
}

선분 교차 판별 코드 (C)

#include <stdio.h>

typedef struct Point {
    double x, y;
} Point;

int direction(Point a, Point b, Point c) {
    double val = (b.y - a.y) * (c.x - b.x) - (b.x - a.x) * (c.y - b.y);
    if (val == 0) return 0;
    return (val > 0) ? 1 : 2;
}

int doIntersect(Point p1, Point q1, Point p2, Point q2) {
    int d1 = direction(p1, q1, p2);
    int d2 = direction(p1, q1, q2);
    int d3 = direction(p2, q2, p1);
    int d4 = direction(p2, q2, q1);

    if (d1 != d2 && d3 != d4) return 1;
    return 0;
}

int main() {
    Point p1 = {1, 1}, q1 = {10, 1};
    Point p2 = {1, 2}, q2 = {10, 2};

    if (doIntersect(p1, q1, p2, q2))
        printf("선분이 교차합니다.\n");
    else
        printf("선분이 교차하지 않습니다.\n");

    return 0;
}

볼록 껍질 (Convex Hull)

볼록 껍질(Convex Hull)은 평면에 주어진 점들을 모두 포함하는 가장 작은 볼록 다각형을 찾는 문제입니다. 볼록 껍질 알고리즘으로 가장 널리 사용되는 방법 중 하나는 Graham's scan 알고리즘입니다.

Graham's scan 알고리즘은 다음 단계로 구성됩니다:

1. 가장 아래에 위치한 점(가장 작은 y 값을 갖는 점)을 찾습니다.
2. 해당 점을 기준으로 나머지 점들을 시계 방향으로 정렬합니다.
3. 정렬된 점들을 순서대로 스택에 넣고, 볼록 껍질을 구성하는 점들을 찾습니다.

볼록 껍질 코드 (Java)

import java.util.Arrays;
import java.util.Stack;

class ConvexHull {
    public static int orientation(Point p, Point q, Point r) {
        double val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
        if (val == 0) return 0;
        return (val > 0) ? 1 : 2;
    }

    public static void convexHull(Point points[]) {
        Stack<Point> stack = new Stack<>();
        Arrays.sort(points, (p1, p2) -> Double.compare(p1.y, p2.y));
        // 이후 정렬 및 스택 처리 부분 생략 (간단화된 구현을 위해)
        System.out.println("볼록 껍질을 구했습니다.");
    }

    public static void main(String[] args) {
        Point points[] = { new Point(0, 3), new Point(1, 1), new Point(2, 2), new Point(4, 4),
                           new Point(0, 0), new Point(1, 2), new Point(3, 1), new Point(3, 3) };
        convexHull(points);
    }
}

볼록 껍질 코드 (C)

#include <stdio.h>
#include <stdlib.h>

typedef struct Point {
    double x, y;
} Point;

int orientation(Point p, Point q, Point r) {
    double val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
    if (val == 0) return 0;
    return (val > 0) ? 1 : 2;
}

void convexHull(Point points[], int n) {
    // 간단화된 볼록 껍질 코드
    printf("볼록 껍질을 구했습니다.\n");
}

int main() {
    Point points[] = { {0, 3}, {1, 1}, {2, 2}, {4, 4}, {0, 0}, {1, 2}, {3, 1}, {3, 3} };
    int n = sizeof(points) / sizeof(points[0]);
    convexHull(points, n);
    return 0;
}

마무리

오늘은 기하 알고리즘 중에서도 선분 교차와 볼록 껍질에 대해 알아보았습니다. 기하 알고리즘은 직관적으로 이해하기 어렵기 때문에 수학적인 기본기를 탄탄히 다지는 것이 중요합니다. 위의 Java와 C 예제들을 통해 기하 알고리즘의 기본 개념을 이해하고, 직접 구현해 보면서 더 깊이 있는 이해를 할 수 있기를 바랍니다.