[알고리즘] 10. 기하 알고리즘

KOCW에서 제공하는 고려대학교 유용재 교수 알고리즘 강의를 듣고 정리한 글 입니다.

10주차. Python을 이용한 기하 알고리즘 입문

 

---

10주차. Python을 이용한 기하 알고리즘 입문

 

1.  직선에 대한 점의 좌우 판별

1) 벡터의 외적을 이용한 직선에 대한 점의 좌우 판별

• 점 A(x1, y1), B(x2, y2), C(x3, y3) 이 좌표평면 위에 주어져 있을 때, 
• 반직선 AB-> 에 대한 점 C의 상대적 위치는 아래와 같이 판단할 수 있다.
• (x1y2 - x2y1) + (x2y3 - x3y2) + (x3y1 - x1y3) 이 양수면 왼쪽, 음수면 오른쪽, 0이면 나란하게 있다. 

# Week 10

# LR

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 'L'
    elif result < 0:
        return 'R'
    else:
        return 'S'
        
A = [-1, -1]
B = [1, 4]
C = [3, 0]
print(LR(A, B, C))

'''
Output
R
'''

 

 

2) 관련 예제. 철도 공사

좌표평면위에 A, B, C, D 네 지점이 존재하는 상황에서 A, B를, C와 D를 이으려고한다. 철길끼리 만나게 되는 경우 공사를 진행할 수 없다고한다. 네 좌표를 받아 철길끼리 만나게 되는지 여부를 반환하는 Cross함수를 Python에서 작성하면?
(단 네 지점은 한 직선위에 있지 않는다)

철길이 교차하려면 AB-> 에대해 C, D의 위치는 반대이다. 같은 원리로 CD-> 에 대해 A, B의 위치는 정반대이다.

# Week 10

# isCross

def LR(A, B, C):
    # 위와 동일
        

def isCross(A, B, C, D):
    # AB에 대해 C, D 방향 반대
    if (LR(A, B, C) != LR(A, B, D)):
        # CD에 대해 A, B 방향 반대
        if (LR(C, D, A) != LR(C, D, B)):
            return True
    return False

A = [0, 0]
B = [2, 2]
C = [2, 0]
D = [0, 2]
print(isCross (A, B, C, D))

'''
Output
R
'''

 

2.  볼록 껍질 문제에 대한 해법

1) 관련 개념 : 볼록, 오목 다각형

좌) 볼록 다각형, 우) 오목 다각형

• 볼록다각형 : 다각형 경계 위의 어떤 두 점을 잇더라도, 그 선분은 다각형 내에 존재
  다각형을 구성하는 모든 강의 크기가 180도 이하
• 오목 다각형 : 볼록다각형이 아닌 다각형
  다각형을 구성하는 각 중 180도가 넘는 것이 하나 이상 존재

 

2) 볼록다각형 문제 Convex hull

임의의 위치에 점 여러 개가 존재하는 상황에서 모든 점을 포함하는 볼록 다각형을 찾는 문제
(점들이 선이나 도형 내부에 존재) 

여러가지 해법 존재

(1) 그레이엄 스캔 Graham Scan

https://www.youtube.com/watch?v=Ps1idzOx6LA&t=6s

그레이엄 스캔 시뮬레이션 영상

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

 

Q. 가장 왼쪽 점을 기준 점으로 설정하는 이유? 
-> 오른쪽만 돌면서 점들의 기울기 계산하면 된다.

 

그레이엄 스캔 구현

• 스택에 기준점과 1번 점을 push 
• 사전에 부여한 순서대(기울기)로 점을 스택에 push
  단, 점이 최근에 그은 반직선 오른쪽에 점이 존재할 경우 방금 넣은 원소 pop 후 재시도 (기울기 가장 크게 되는 점 찾기)
  -> 기울기, 거리 계산 필요
• 마지막 점까지 push 완료 -> 볼록 껍질 완성

# Week 10

# Graham Scan

def LR(A, B, C):
    # 위와 동일
        

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)) **0.5

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

# i = x값이 가장 작은 원소의 인덱스
i = p.index(min(p))
# 맨 앞 원소와 p[i] 자리 바꾸기 
p[0], p[i] = p[i], p[0]

# Buuble sort. 기울기 오름차순
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]
                
stk = [p[0], p[1]]

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

'''
Output
[[-9, 3], [-3, -8], [8, 8], [0, 7]]
'''

 

 

3.  다각형 내/외부 구분 문제

1) 다각형 내부/외부 구분 문제 

• 점에서 출발해 오른쪽으로 끊임없이 뻗어가는 반직선이 주어진 다각형과 만나는 횟수가 홀수면 내부, 짝수면 외부에 위치
• 예외1 ) 꼭지점을 지나는 경우 외부에 존재해도 횟수가 1인데, 꼭짓점을 지난다는 것은 두 선분을 지나는 경우이다.
  선분 1개만 고려해야한다.
• 예외 2) 내부에 존재해도 도형의 선분과 겹치는 경우, 횟수가 2회가 되는데(겹치는 선분의 시작과 끝점 2), 겹치는 경우는 세지 않는다.

# Week 10

# Graham Scan

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 'L'
    elif result < 0:
        return 'R'
    else:
        return 'S'


def isCross(A, B, C, D):
    # AB에 대해 C, D 방향 반대
    if (LR(A, B, C) != LR(A, B, D)):
        # CD에 대해 A, B 방향 반대
        if (LR(C, D, A) != LR(C, D, B)):
            return True
    return False
    




def inout(p, x, y):
    cnt = 0
    for i in range(len(p)-1):
        # 예외 2) 점과 다음 점 y좌표 동일하면 (x축과 평행한 직선)
        if p[i][1] == p[i+1][1]:
            cnt = cnt
        # 예외 1) * < 이렇게 생긴 경우
        elif (p[i][1] == y) and (x < p[i][0]):
            # 위에 선분인 경우
            if p[i+1][1] > p[i][1]:
                cnt = cnt + 1
        # 예외 1) * > 이렇게 생긴 경우
        elif (p[i+1][1] == y) and (x < p[i+1][0]):
            # 위에 선분인 경우
            if p[i][1] > p[i+1][1]:
                cnt = cnt + 1
        else:
            if isCross(p[i], p[i+1], [x, y], [10000000, y]) == True:
                cnt = cnt + 1
    if cnt%2 == 0:
        print('외부')
    else:
        print('내부')

p = [[-4, 4], [-7, 2], [-3, 1], [-5, -2], [-2, -1], [1, 4], [1, 1], [2, 2]]
# 마지막 점과 첫 점 잇기
p.append(p[0])

dot = [-6, 2]
inout(p, dot[0], dot[1])


'''
Output
내부
'''