Quick Hull

Quick Hull

볼록 껍질(Convex Hull)

볼록 껍질이란 주어진 점들을 모두 포함하는 가장 작은 볼록 집합이다.

위의 그림과 같이 주어진 점들 이어 볼록 집합을 만들 수 있다.

'볼록'껍질인 이유는 위와 같이 움푹 들어간 모양이 나오지 않아야 하기 때문이다. 볼록 껍질의 내각은 항상 180도 보다 작아야 한다.

볼록함을 만족시키지 않는 점은 볼록 껍질을 만드는 점들의 집합에 포함시키지 않는다.

Quick Hull

Quick Hull은 볼록 껍질을 만드는 점들의 집합을 구하는 알고리즘 중 하나다.

위의 애니메이션이 Quick Hull Algorithm의 과정을 보여주고 있다. (출처: https://en.wikipedia.org/wiki/Quickhull)

우선 Quick Hull은 두 점을 이어 직선을 하나 만드는 것으로 시작한다. 시작하는 두 점은 반드시 볼록껍질에 포함되는 점이여야 한다.

일반적으로 2차원 공간에서 두 점은 x값이 가장 작은 점과 가장 큰 점을 사용한다.(x값이 같은 점들이 있는 경우, y값이 가장 작은 점과 가장 큰 점을 사용한다, x, y값에 대해서 점들을 정렬하고 첫 점과 끝 점을 사용하면 된다)

위의 기준이 유일한 것은 아니고 두 점이 볼록껍질에 반드시 포함된다는 것을 보장하는 기준 중 하나다.

이제 직선을 기준으로 점들을 집합 S1, S2로 나누어 준다.

직선 위 점들의 집합을 S1이라고 할 때, S1의 점들 중 직선과의 거리가 가장 먼 점을 찾는다.

해당 점을 볼록 껍질을 구성하는 점들의 집합에 포함시키고 새로 추가된 점과 직선이 이루는 삼각형 내부에 있는 점들은 볼록 껍질을 구성하는 점이 될 수 없기 때문에 후보에서 제외한다.

이제 새로 생성된 직선들에 대해 재귀적으로 다음 점을 찾는 과정을 반복한다. S2에 대해서도 똑같은 과정을 해줘야 하고 더 이상 직선 너머의 점이 없을 때 까지 반복한다.

이 과정을 이해하고 다시 위의 애니메이션을 보면 이제 애니메이션의 과정이 눈에 더 잘 들어올 것이다.

구현

Quick Hull을 구현하기 위해서는 세가지 함수가 필요하다.

1. 직선을 기준으로 S1, S2를 나누는 기준을 계산하는 함수.
2. 점이 삼각형 내부에 있는지 확인하는 함수.
3. 가장 거리가 먼 점을 찾기위해 점과 직선 사이의 거리를 계산하는 함수.

1. CW(Clock Wise), CCW(Counter Clock Wise)

CW, CCW는 두 벡터가 이루는 각을 시계방향 또는 반시계방향으로 계산했을 때, 예각이면 양수 둔각이면 음수 0, 180도를 이루면 0이 되는 함수를 말한다.

이를 이용하면 직선을 기준으로 양쪽 방향으로 점들을 S1과 S2로 나누어 담을 수 있다. 0값이 나오는 경우는 직선 위에 점이 존재하는 경우인데 볼록껍질을 이루는 점이 될 수 없으니 제외한다.

def CCW(a, b, c):
    return (b[0] - a[0]) * (c[1]-a[1]) - (c[0] - a[0]) * (b[1] - a[1])

벡터의 외적을 이해하고 있다면 원리를 쉽게 이해할 수 있을것이다.

결과에서 벡터의 방향이 매우 중요하기 때문에 a, b, c 값을 넣을 때 주의해서 넣어야 한다.

2. 점이 삼각형 내부에 있는지 확인하는 함수

점이 삼각형 내부에 있는지 확인할 수 있는 방법은 여러가지가 있다.

1. 삼각형의 세 변을 기준으로 점이 모두 변 안쪽에 있을 때, 점은 삼각형 내부에 있다.

CCW를 사용해 세번의 CCW값의 부호가 모두 같은지 확인하면 된다.

2. 삼각형의 두 변을 단위벡터로 사용하고 한 점을 기준점으로 사용해 점의 위치를 정의하고 내부에 있는지 확인한다.

점 b를 기준으로 v1, v2 벡터를 단위벡터로 사용해 벡터 k를 표현 할 수 있다.

$$k.x = α\cdot v_{1}.x+β\cdot v_{2}.x$$ $$k.y = α\cdot v_{1}.y+β\cdot v_{2}.y$$

벡터를 x성분과 y성분으로 분해하면 연립방정식으로 α, β 값을 구할 수 있다. 그리고 α, β 값이 다음과 같은 조건을 만족하면 삼각형 내부에 존재한다.

$$0 \leq α \leq 1$$ $$0 \leq β \leq 1$$ $$α + β \leq 1$$

등호를 붙이면 삼각형의 선분 위에 존재하는 경우도 내부로 포함하게 된다. 문제의 조건에 의해 해당 경우도 삼각형 내부에 존재하는 것으로 판단한다.

조건들을 이해하기 쉽게 그림으로 표현해 봤다. 삼각형 외부의 점을 b를 기준으로 k벡터로 표현했을 때, k = v1 + v3가 된다.

$$v_{3} = x\cdot v_{1} + y\cdot v_{2}$$ $$k = v_{1} + v_{3} = (1+x)\cdot v_{1} + y\cdot v_{2}$$

즉, α 또는 β 값이 1보다 크면 점이 삼각형 외부에 있다는 것을 알 수 있다.

점 c에서 a로 가는 벡터를 v1 - v2로 표현할 수 있다. 이를 이용하면

$$k = v_{1} + x\cdot (v_{1} - v_{2}) = (1+x)\cdot v_{1} +(-x)\cdot v_{2}$$ $$α = 1+x,\ β = -x$$ $$α+β = 1$$

위의 논리와 마찬가지로 선분에서 삼각형 바깥쪽 방향으로 더 나아간다면 α+β 값이 1보다 커질 수 밖에 없다.

def isInTriangle(v2, v3, v1, point):
    v1 = [v2[0] - v1[0], v2[1] - v1[1]]
    v2 = [v3[0] - v1[0], v3[1] - v1[1]]
    k = [point[0] - v1[0], point[1] - v1[1]]

    alpha = (v2[0] * k[1] - v2[1] * k[0]) / (v2[0] * v1[1] - v2[1] * v1[0])
    beta = (v1[0] * k[1] - v1[1] * k[0]) / (v1[0] * v2[1] - v2[0] * v1[1])

    if(0 <= alpha and alpha <= 1 and 0 <= beta and beta <= 1 and alpha + beta <= 1): return True

3. 점과 직선 사이의 거리

직선 ax+by+c와 점 (x1, y2)사이의 거리를 구하는 공식을 사용하여 거리를 구한다.

$$ d = \frac{|ax_{1} + by_{1} + c|}{\sqrt{a^{2}+b^{2}}} $$

ax+by+c 직선을 구하는 과정도 추가해줘야 한다.(점 p와 q가 이루는 직선)

$$y - p.y = \frac{q.y - p.y}{q.x - p.x}(x - p.x)$$ $$a = p.y - q.y,$$ $$b = q.x - p.x,$$ $$c = p.x \cdot (q.y - p.y) - p.y \cdot (q.x - p.x)$$

def getDistance(p, q, r):
    a = p[1] - q[1]
    b = q[0] - p[0]
    c = p[0] * (q[1] - p[1]) - p[1] * (q[0] - p[0])
    return abs(a*r[0] + b*r[1] + c) / sqrt(a**2 + b**2)

1707번 - 볼록 껍질

1708번 - 볼록 껍질 문제를 해결하기 위해 python으로 작성한 코드다. 볼록 껍질을 구성하는 점의 개수를 세는것으로 구현했지만 변형하여 구성하는 점들의 좌표를 구할 수도 있다.

from sys import stdin
from math import sqrt
n = int(stdin.readline())
points = [[]] * n
for i in range(n): points[i] = list(map(int, stdin.readline().split()))

def CCW(a, b, c):
    return (b[0] - a[0]) * (c[1]-a[1]) - (c[0] - a[0]) * (b[1] - a[1])

def isInTriangle(v2, v3, v1, point):
    d1 = [v2[0] - v1[0], v2[1] - v1[1]]
    d2 = [v3[0] - v1[0], v3[1] - v1[1]]
    k = [point[0] - v1[0], point[1] - v1[1]]

    alpha = (d2[0] * k[1] - d2[1] * k[0]) / (d2[0] * d1[1] - d2[1] * d1[0])
    beta = (d1[0] * k[1] - d1[1] * k[0]) / (d1[0] * d2[1] - d2[0] * d1[1])

    if(0 <= alpha and alpha <= 1 and 0 <= beta and beta <= 1 and alpha + beta <= 1): return True
    else: return False

def getDistance(p, q, r):
    a = p[1] - q[1]
    b = q[0] - p[0]
    c = p[0] * (q[1] - p[1]) - p[1] * (q[0] - p[0])
    return abs(a*r[0] + b*r[1] + c) / sqrt(a**2 + b**2)

def QuickHull(points):
    points.sort()
    a = points[0]
    b = points[-1]
    points = points[1:-1]
    S1 = []
    S2 = []
    for point in points:
        ccw = CCW(a, b, point)
        if(ccw > 0): S2.append(point)
        elif(ccw < 0): S1.append(point)
    result = 2
    result += FindHull(S1, a, b)
    result += FindHull(S2, b, a)
    return result

def FindHull(S, a, b):
    if(len(S) == 0): return 0
    if(len(S) == 1): return 1
    dist = 0
    C = [0,0]
    for point in S:
        d = getDistance(a, b, point)
        if(d > dist):
            dist = d
            C = point
    result = 1
    S1 = []
    S2 = []

    for point in S:
        if(point[0] == C[0] and point[1] == C[1]): continue
        if(isInTriangle(C, a, b, point)): continue
        ccw = CCW(a, C, point)
        if(ccw < 0): S1.append(point)
        elif(ccw > 0): S2.append(point)

    result += FindHull(S1, a, C)
    result += FindHull(S2, C, b)

    return result

if(n == 3): print(3)
else: print(QuickHull(points))