[알고리즘] 기본 개념 정리 (8) - Python을 이용한 기하 알고리즘 입문

직선에 대한 점의 좌우 판별

Q. 세 점이 있을 때, 두 점을 연결한 반직선을 기준으로 좌우를 판별할 수 있는가?

→ 벡터의 외적을 이용한 직선에 대한 점의 좌우 판별 가능

def LP(A,B,C):
    result1 = (A[0]*B[1]) + (B[0]*C[1]) + (C[0]*A[1])
    result2 = (B[0]*A[1]) + (C[0]*B[1]) + (A[0]*C[1])
    result = result1 - result2
    if (result > 0):
        return 'LEFT'
    elif (result < 0):
        return 'RIGHT'
    else:
        return 'S'

볼록 껍질 문제에 대한 해법

그레이엄 스캔 - 볼록 다각형, 오목 다각형 구분

• 주어진 모든 점들 중, 가장 왼쪽의 점을 기준점으로 설정 (x좌표가 같은 경우, 가장 아래쪽 점을 기준점으로 설정)
• 기준점에서 시계 반대 방향으로 돌며 순회 순서를 결정 (각도가 같은 경우 기준점에 더 가까운 점을 먼저 방문

Q. 가장 왼쪽에 있는 점을 기준점으로 하는 이유는?

1. 시작점의 명확성
2. 정렬 및 비교의 용이성
3. 계산 단순화
4. 일관된 시작점 보장

순서

• 스택에 기준점과 1번 점을 push하는 것으로 시작
• 사전에 부여한 순서대로 점을 스택에 push
  • 단, 점이 반직선 오른쪽에 존재할 경우, pop 후 재시도
• 마지막 점까지 push를 완료 → 스택은 볼록 껍질을 보장함

def LR(A,B,C):
    result1 = (A[0]*B[1]) + (B[0]*C[1]) + (C[0]*A[1])
    result2 = (B[0]*A[1]) + (C[0]*B[1]) + (A[0]*C[1])
    result = result1 - result2
    if (result > 0):
        return 'LEFT'
    elif (result < 0):
        return 'RIGHT'
    else:
        return 'S'

def slope(A,B):
    if (A[0] == B[0]):
        return float('inf')
    else:
        return (B[1]-A[1])/(B[0]-A[0])
    
def dist(A,B):
    return ((B[0]-A[0])**2 + (B[1]-A[1])**2)**(1/2)

p = [[1, 3], [0, 7], [0, 3], [-9, 3], [-3, -8], [2, 4], [8, 8], [7, 7]]

i = p.index(min(p))
p[0], p[i] = p[i], p[0]

for round in range(len(p)):
    for i in range(1, len(p)-1):
        if slope(p[0], p[i]) > slope(p[0], p[i+1]):
            p[i], p[i+1] = p[i+1], p[i]
        elif slope(p[0], p[i]) == slope(p[0], p[i+1]):
            if dist(p[0], p[i]) > dist(p[0], p[i+1]):
                p[i], p[i+1] = p[i+1], p[i]

stack = [p[0], p[1]]

for i in range(2, len(p)):
    while(1):
        if (LR(stack[-2], stack[-1], p[i]) == 'RIGHT'):
            stack.pop()
        else:
            stack.append(p[i])
            break

print(stack)

다각형의 내,외부 구분 문제

Q. 임의의 점에서 한쪽 방향으로 그었을 때, 다각형과 만나는 횟수가 짝수이냐, 홀수이냐에 따라, 다각형의 내-외부를 결정할 수 있는가?

→ 꼭짓점을 지나냐, 아니냐도 관련 있음. (영상 보기 전에는, 아니라고 생각함)

따라서, ‘위쪽 선분과 아랫쪽 선분 중 하나만을 센다!’

→ 선분과 반직선이 겹치는 경우는 무시

def LR(A,B,C):
    result1 = (A[0]*B[1]) + (B[0]*C[1]) + (C[0]*A[1])
    result2 = (B[0]*A[1]) + (C[0]*B[1]) + (A[0]*C[1])
    result = result1 - result2
    if (result > 0):
        return 'LEFT'
    elif (result < 0):
        return 'RIGHT'
    else:
        return 'S'

def Cross(A,B,C,D):
    if (LR(A,B,C) != LR(A,B,D) and LR(C,D,A) != LR(C,D,B)):
        return True
    else:
        return False

p = [[-4, 4], [-7, 2], [-3, 1], [-5, -2], [-2, -1], [1, -4], [1, 1], [2, 2]]
x = -6
y = 2

p.append(p[0])
count = 0

for i in range(0, len(p) - 1) :
    if (p[i][1] == p[i + 1][1]) :
        continue
    elif ((p[i][1] == y) and (x < p[i][0])) :
        if (p[i + 1][1] > p[i][1]) :
            count = count + 1
    elif ((p[i + 1][1] == y) and (x < p[i + 1][0])) :
        if (p[i][1] > p[i + 1][1]) :
            count = count + 1
    else :
        if Cross(p[i], p[i + 1], [x, y], [100000000, y]) == True :
            count = count + 1

if (count % 2 == 0) :
    print("OUT")
else :
    print("IN")