컴퓨터 알고리즘 - 기하 알고리즘 (4/24)

최수환·2023년 4월 24일

기하 알고리즘 알고리즘

컴퓨터 알고리즘

목록 보기

8/14

기하 알고리즘

두 선분의 상대 위치확인

두 선분의 교차검사(방법1)

입력: 선분 AB, 선분 CD (4개의 점 A,B,C,D)
방법: A,B와 C,D 각 두 점으로부터 두 직선의 방정식을 찾고, 두 직선의 방정식으로부터 교점의 좌표를 찾는다. 그 뒤 교점이 선분 AB 또는 선분 CD에 포함되어 있는지를 확인
많은 단계의 계산들이 필요해 비효율적이다.

두 선분의 교차검사(방법2)

입력: 선분 AB, 선분 CD (4개의 점 A,B,C,D)
방법: 꺾은선 ABC와 꺾은선 ABD가 동일한 방향으로 꺾이는지 확인하고 동시에 꺾은선 CDA와 꺾은선 CDB도 동일한 방향으로 꺾이는지 확인
대량의 선분의 교차검사에 있어서 삼각함수의 적용은 비효율적일 수 있다.

두 선분의 교차검사(방법3: Intersection 함수)

A≠B and C≠D 이면 다음 두 조건이 만족될 때
두 선분이 교차한다.
(1) Direction(A,B,C) ⅹ Direction(A,B,D) ≤ 0
(2) Direction(C,D,A) ⅹ Direction(C,D,B) ≤ 0
즉, 모든 교차 상황에서는 조건이 만족, 모든 비교차 상황에서는 조건이 불만족 되도록 Direction 함수를 설계하고자 한다.

Direction 함수 설계 및 검증

위의 Direction함수의 전제조건을 이용하여 8가지 경우의 검증을 진행한다.

1 . 두 선분이 교차할 때

2 . 두 선분이 평행할 때

3 . 두 선분이 한 끝점 교차할 때

4 . 두 선분이 양 끝점 교차할 때

5 . 두 선분이 양 연장선 교차할 때

6 . 두 선분이 한 연장선 교차할 때

7 . 두 선분이 교차없는 일직선일 때

8 . 두 선분이 교차하는 일직선일 때

Direction 함수 구현

기울기를 이용하여 시계 방향인지 반시계 방향인지 판단한다. 나누기 대신 양변을 곱하여 곱셈으로 표현하였다.
기울기를 이용하여 일치함에 따라 A,B,C가 일직선상에 존재하는지 판단
길이를 이용하여 중간에 위치하는 점을 판단

Intersection 함수 구현

구현한 Direction함수를 이용하여 Intersection 함수를 구현한다.

단순 폐쇄 경로 찾기

우편배달부 문제

한 명의 배달부가 우편물을 배달하는 데 하루 동안 n개의 집을 방문하여야 한다. 우체국을 떠나서 이 n개 집을 모두 한 번씩 방문하고 다시 우체국으로 돌아오는 효율적인 경로는 무엇일까?

Idea: 배달부가 방문한 집들을 순서대로 직선으로 연결했을 때 그 선분들이 서로 교차하지 않도록 하는 방법
- 항상 최적 경로는 보장되지 않는다
- 한번 통과한 지점을 다시 통과하지 않아 효율적인 경로이다

단순 폐쇄 경로 설계

1. 기준점 D 선정
(Ex. Y좌표가 최소인 점들 중 X좌표 또한 최소점)
2. D 에서 나머지 점들 P 각각에 대한 반직선을 DP 라 할때, 반직선 Dx 와 DP 사이의 각도들을 계산
3. 이 각도들을 기준으로 P 점들을 오름차순으로 정렬
4. 기준점 D 부터 시작해 정렬된 점들을 순서대로 직선으로 연결

📒 기준점을 A로 선정하면 다른 단순 다각형이 생성된다.

효율적인 각도 비교 방법(상대 각도)

단순폐쇄경로를 생성할 때 tan-1(y/x) 등의 삼각함수를 사용할 경우 계산시간이 상대적으로 오래 걸림
실제각도를 찾지는 못하지만 보다 효율적인 각도 비교가 가능한 방법으로 상대각도 TA 도입
상대각도 요구조건
1 . A점의 실제각도가 B점의 실제각도보다 같거나 클 경우 TA ≥ TB
2 . A점의 실제각도가 B점의 실제각도보다 작을 경우 TA < TB
3 . 실제각도보다 계산이 용이해야 함

각 사분면에서의 상대 각도 계산법
좌표가 음수인 경우 절대값을 통해 양수로 바꾸어준다.

상대각도 생성함수 구현

조건문을 통해 상대각도를 계산 후 각도 조정을 위해
return Angle*90.0 을 수행한다.

점과 다각형의 상대위치 확인

어떤 점 P의 위치가 다각형 내부인지 외부인지를 결정하는 문제
아이디어: P점에서 그은 반직선(검사선)이 다각형의 변과 교차하는 교차점의 개수를 조사
- 교차점 수가 홀수 개이면 P점은 다각형 내부에 위치
- 교차점 수가 짝수 개이면 P점은 다각형 외부에 위치
- 검사선이 다각형의 꼭지점과 교차하는 경우 또는 검사선이 다각형의 한 변 전체를 지나는 경우는 별도 고려 필요