문제해결 전략 - 15. 계산기하 정리

계산기하 알고리즘

점, 선, 다각형과 원 등 기하학 적 도형을 다루는 알고리즘

• 학부 선형 대수나 고등학교 수준의 기하학을 코드로 구현할 수 있는 능력
• 기초적인 수학 이론을 어떻게 간결하고 예외가 적은 형태로 구현하는지에 초점

---

계산기하 도구들

벡터의 구현

• 2차원 평면의 서로 다른 두 점의 상대적 위치
• 벡터는 방향과 거리의 쌍이므로 시작점이 중요하지 않다.
• 벡터의 시작점은 항상 좌표공간의 원점으로 둔다
• 벡터를 화살표 끝점의 위치 (x,y)로 표현할 수 있다.

const double PI = 2.0 * acos(0.0);
struct vector {
double x, y;
explicit vector(2double x_ = 0 double y_ =0)
등등 여러 operator

 

• x 좌표가 작은 벡터일수록, 끝점 x 좌표가 같을 경우 y좌표가 작은 벡터일 수록 작은 벡터라고 계산

점과 직선, 선분의 표현

• 벡터를 기준으로 생각하는 것이 코드를 간결하게 하고 문제를 푸는데 강력한 도구가 된다.
• 점 세게 p, a, b가 주어질 때 a가 b보다 p에 얼마나 가까운지 반환하는 함수 가정

double howMuchCloser(vector2 p, vector2 a, vector2 b){
   return (b-p).norm() - (a-p).norm();
}

 

• 사실 점 두개로 표현해도 되긴 한데 중요한 건 해당 표현 방식을 프로그램 내에서 일관적으로 사용해야함

벡터의 내적과 외적

• 벡터의 내적
  a*b = |a||b|cos
• 벡터의 외적(3차원 벡터)
  모든 2차원 벡터를 z가 0인 3차원 벡터로 생각해서 2차원 벡터에 대한 외적 가능
  외적에서 유용한 것은 반환되는 벡터의 길이와 방향
  |a||b|sin
• 외적의 절댓값은 a, b를 두변으로 하는 평행 사변형의 넓이
• 외적의 주된 사용처는 두 벡터의 방향성을 판단하는것
  a*b>0 이면 b가 a로 부터 반시계 방향으로 180도 이내에 있다
  음수라면 시계방향으로 180도 이내에 있다

직선과 직선의 교차

• 직선을 한 점과 방향벡터로 표현
  a+p*b형태로 표현
• a+pb 와 c+qd의 교점을 구하기 위해 a+pb = c + qd 방정식을 풀면됨
• 결과적으로 구한 p 값을 a+pb에 대입하면 원하는 점을 구할 수 있다.

bool lineTersection(vector2 a, vector2 b, vector2 c, vector2 d, vector2& x){
	double det = (b - a).across(d - c);
    //평행
    if(fabs(det) < EPSILON) return false;
    x = a+(b- a)*((c-a).across(d-c)/det);
    return true
}

선분과 선분의 교차

• 직선과 직선의 교차와 비슷하다
• 두 직선의 교차점을 계산한 뒤 교차점이 모두 두 선분 위에 있는지 확인한다.
• 한 직선위에 두 선분이 있을 때 관계는
  1. 두 선분잉 서로 겹치지 않음
  2. 두 선분이 한점에서 닿음
  3. 두 선분이 겹쳐짐
  4. 한 선분이 다른 선분 안에 포함됨
• 위 네가지의 경우 lineIntersection() 에서 모두 false를 return 한다. 그치만 선분은 교차하는걸
• 두 직선이 평행한 경웅 별도 처리를 해줘야 한다.

선분과 선분의 교차 : 교차점이 필요 없을 때

• 교차하는 두 선분 ab 와 cd를 생각해 보자
• a입장에서 c와 d중 한쪽은 b를 기준으로 시계방향에, 다른 한쪽은 시계방향 반대에 있어야 한다.
• c의 입장에선 반대로 동일하다.
• 이 두 조건과 선분의 교차 여부는 동치이다.

점과 선 사이의 거리

• 두 점의 벡터 a, b가 주어졌을 때 이 직선과 다른 점 p 사이의 거리를 계산할 때
• p가 직선 ab에 내리는 수선의 발을 계산 한 뒤 p와의 거리를 계산하는 것
• 벡터의 내적을 이용하면 쉽게 구할 수 있다.
• 점과 선 사이 거리 계산은 점과 선분 사이의 거리, 선분과 선분 사이의 거리를 계산하는데 유용하게 쓰인다.

다각형

• 볼록 다각형 : 모든 내각이 180도 미만인 다각형
• 오목 다각형 : 180도가 넘는 내각을 가진 다각형
• 단순 다각형 : 다각형의 경계가 스스로를 교차하지 않는 다각형

면적 구하기

• 벡터의 외적을 이용해 삼각형의 세 점이 주어질 때 그 면적을 구할 수 있다.
• 다각형을 삼각형들로 분리해서 구한다.
• 오복다각형의 경우는 절댓값 취하지 않고 합한다.

내부/외부 판별

• 단순 다각형과 이 다각형의 경계 위에 있지 않은 점 q가 주어질때 q가 다각형 내부에 있는지 판단
• q에서 시작해 오른쪽으로 뻗어나가는 반직선을 상상하고 이 다각형과 몇번 교차하는지 확인
• 내부점은 홀수번 교차, 외부 점은 짝수 번 교차
• 근데 이렇게 하면 예외가 생김(선분으로 겹친다던가)
• 한가지 방법으로는 엄청나게 작은 값만큼 살짝 올리는 것이다.

계산 기하 알고리즘 디자인 패턴

• 이미 다룬 기하 관련 코드들의 조합으로 풀 수 있다.
• 평면 스위핑 : 수평선 혹은 수직선으로 주어진 평면을 쓸고 지나가면서 문제를 해결
  • 직사각형 합집합의 면적 기본 풀이 
    
    • 각 직사각형들의 면적을 모두 구해 더한 뒤
    • 각 직사각형의 쌍에 대해 이들의 교집합을 구한다.
    • 결과에서 교집합을 빼준다.
    • 세개의 사각형이 겹치는 부분은 다시 더해준다.
    • 문제점은 모든 조합의 교집합을 한번씩 다 확인해야 되기 때문에 사각형이 n개 있을 때 2^n개의 교집합을 방문해야 한다.
  • 직사각형 합집합의 면적 평면 스위핑
    • 왼쪽에서 오른쪽으로 그림을 훓고 지나가는 수직성 상상
    • 사각형들을 수직선으로 잘랐을 떄 단ㅁ면의 길이를 반환하는 함수
    • 이 함수를 x에 대해 정적분한 결과가 답
  • 다각형의 교집합의 넓이 구하기
    • 입력을 특정 축으로 자르면 풀기 쉬워진다.
    • 수직선을 움직이면서 각 사다리꼴들의 면적을 모두 더하면 교집합의 넓이를 찾을 수 있다.
  • 교차하는 선분들
    • 왼쪽부터 방문하면서 현재 수직선과 겹쳐져 있는 선분들의 집합응ㄹ 유지한다.
    • 수직선이 선분의 왼쪽 끝 점을 만나면 선분이 이 집합에 추가되고 오른쪽 끝 점을 만나면 집합에서 빠지게 된다.
    • 집합은 항상 각 선분이 수직선을 만나는 y좌표가 증가하는 순으로 정렬한다.
    • 집합에 새로운 선분이 추가될 떄 마다 집합 상에서 새 선분과 인접한 두 선분의 교차 여부를 확인한다.
    • 집합에서 선분이 삭제될 때마다 집합 상에서 이 선분과 인접해 잇던 두 선분의 교차 여부를 확인한다.
    • 교차하는 선분들이 한 쌍이라도 나오는 시점에 종료한다.
• 회전하는 캘리퍼스 : 무언가를 재는 과정을 알고리즘응로 옮기는데 효율적이다.
  • 볼록 다각형의 지름
    • 단순하게는 모든 꼭지점의 쌍을 순회하며 이중 서로 가장 멀리 떨어져 있는 쌍을 찾는다.
    • 캘리퍼스를 이용한 알고리즘은 다각형을 평행한 두 직선 사이에 끼우고, 다각형을 다라 직선을 한 바퀴 돌리면서 직선에 닿는 꼭지점들 간의 사이 거리를 잰다.
    • 꼭지점들 간의 사이 거리가 최대값이면 지름이다.

자주 히는 실수와 유의점

• 계산기하 문제에 본질적으로 예외가 아주 많다.
  • 퇴화도형 : 도형의 일반 위치가 아닌 반대가 되는 예외
    • 일직선 상에 있는 세개 이상의 점들
    • 서로 평행이거나 겹치는 직선/선분들
    • 넓이가 0인 다각형들
    • 다각형의 변들이 서로 겹치는 경우
  • 직교 좌표계와 스크린 좌표계
    • 대개 위로 갈수록 y좌표가 증가하고 오른쪽으로 갈 수록 x 좌표가 증가하는 형태
    • 배열에서 각 원소의 위치를 표현하거나 스크린의 픽셀의 위치를 표현할 땐 맨 윗줄의 y좌표가 0이고 아래로 갈 수록 y좌표가 증가한다.

---