계산 기하 Part2

다각형

• 다각형(Polygon): 현실 세계를 계산 기하로 표현하는 데 필수적인 요소
• 다각형의 종류
• 볼록 다각형(Convex Polygon): 모든 내각이 180도 미만인 다각형
• 오목 다각형(concave polygon): 180도가 넘는 내각을 가진 다각형
• 단순 다각형(simple polygon): 다각형의 경계가 스스로를 교차하지 않는 다각형
• 면적 구하기
• 벡터의 외적을 이용시 삼각형 세 점이 주어지면 그 면적을 구하는 것이 가능
• 볼록 다각형의 경우
• P0, P1, Pn-1의 점을 가질 때
• 다각형 내부에 한점 q를 잡고 그 q를 중심으로 하는 삼각형을 여러개를 만들어 각각의 삼각형의 넓이들을 더하면 가능
• 세 점 좌표 (x1,y1), (x2,y2), (x3,y3)가 있을 때 세 점을 꼭지점으로 하는 삼각형의 넓이
• 벡터의 외적은 3차원 벡터에서 정의되기 때문에 z=0이라고 생각하고 문제를 적용
• 즉 3차원 공간에서는 (x1,y1,0), (x2,y2,0), (x3,y3,0)이 이루는 삼각형의 면적을 구하는 문제로 생각
• 두변을 이루는 벡터
• 
• 삼각형의 면적: |a x b| / 2와 동일
• a x b = (0, 0, (x2-x1)(y3-y1) - (x3 - x1)(y2-y1))
• 삼각형의 넓이 = |(x2-x1)(y3-y1) - (x3 - x1)(y2-y1)| / 2
• 이런식으로 모든 삼각형을 구한 후 전부 더해서 계산
• 
• 볼록 다각형이 아닌 경우 판단
• 벡터의 외적을 이용하여 각도를 조사하여 180도 보다 큰 각이 존재하는 경우 이는 볼록 다각형이 아님을 판단할 수 있음
• a x b > 0인 경우 각도가 180도 보다 작은 볼록한 경우
• a x b < 0인 경우 각도가 180도보다 큰 오목한 경우
  
• z x b = 0인 경우 각도는 180도 또는 0인 경우
• 오목한 n각형의 면적 구하기
• 오목점이 1개인 경우 오목점을 중심으로 볼록다각형의 경우와 동일하게 삼각형으로 나누어 면적을 구하면 됨
• 
• 오목점이 여러개인 경우 위 방법 사용 불가능
  
• 
• S = -P1P2P3 + P1P3P4 + ... + P1Pn-1Pn 
  
• 
• sign은 부호함수, area는 삼각형 면적 구하는 함수
• S=(p0xp1 + p1xp2 + … pn-2 x pn-1 + pn-1 x p0) /2

• 다각형 내부/외부 판별
• 
• 점 A와 점 B가 다각형 내부인지 외부인지 판별하는 것
• 일반적으로 점에서 오른쪽으로 반직선을 그엇을 대 내부에 있는 점은 홀수개의 교점, 외부에 있는 점은 짝수개의 교점을 지남
  
• 
• 반직선은 항상 x축에  평행한 선이어야 한다.
  
• 반직선과 선분 사이에 교점이 있기 위한 조건
• 점B의 y좌표가 두 선분 꼭지점의 y좌표 사이에 있다.
• 점B를 지나는 수평선과 선분 사이의 교점의 x좌표가 점B의 x좌표보다 크다.
• 아래 코드는 동일한 수평에 선분이 존재하는 경우는 무시

/* 점을 구조체로 정의 함 */ strcut vector2{ int x, y; } /* STL vector를 이용해서 다각형 자료형을 정의 함 */ typedef vector<vector2> polygon; bool isInside(vector2 B, const polygon& p){ //crosses는 점q와 오른쪽 반직선과 다각형과의 교점의 개수 int crosses = 0; for(int i = 0 ; i < p.size() ; i++){ int j = (i+1)%p.size(); //점 B가 선분 (p[i], p[j])의 y좌표 사이에 있음 if((p[i].y > B.y) != (p[j].y > B.y) ){ //atX는 점 B를 지나는 수평선과 선분 (p[i], p[j])의 교점 double atX = (p[j].x- p[i].x)*(q.y-p[i].y)/(p[j].y-p[i].y)+p[i].x; //atX가 오른쪽 반직선과의 교점이 맞으면 교점의 개수를 증가시킨다. if(B.x < atX) crosses++; } } return crosses % 2 > 0; }

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

• 평면 스위핑
• 수평선 또는 수직선으로 주어진 평면을 쓸고 지나가면서 해결
• 정렬 혹은 bst를 이용

• 직사각형 합집합의 면적

• 포함 배제 이용

• 모든 조합의 교집합을 한번 씩 다 더해야 하기 때문에 사각형이 n개 있을 때 2^n개의 교집합을 방문해야 한다.

• 매우 비효율적
• 각 직사각형들의 면적을 모두 구해 더한 뒤, 각 직사각형의 쌍에 대해 이들의 교집합을 구함
• 이때 면적이 두번 구해진 경우 결과에서 빼줌
• 세 개의 사각형이 겹치면 세번 빼고 한번을 더해주는 방식을 이용
• 평면 스위핑 방식 이용
• 왼쪽에서 오른쪽으로 훑고 지나가는 수직선이 있음.
• 수직선의 좌표 x가 주어질 때, 사각형들을 수직선으로 잘랐을 때 단면의 길이를 반환하는 함수 cutLength()가 있다고 가정.
• 그러면 우리가 원하는 합집합의 넓이는 이 함수를 x에 대해 정적분한 결과가 된다.
• 물론 실제로 적분할 필요는 없다.
• 
• 그어진 4개의 수직선을 보면 각 위치에서 단면의 길이는 항상 동일
• 원하는 값이 변하는 위치들을 event 라고 칭함.
• .
• 이벤트들의 위치를 미리 계산해 정렬해 두면각 이벤트 사이에서는 cutLength()의 값이 변하지 않는다.
• 따라서 한 event 위치에서 cutLength()를 계산한 뒤 다음 event까지의 거리를 곱하면두 event 사이에서 합집합의 면적을 손쉽게 계산할 수 있다.
• 
• 
• 위 그림은 수직선을 쪼개는 가로 선들과 한 구간에서 count값이 얼마나 되는지의 예를 보여준다.
• 각 event 위치마다 count를 갱신해 두면 간단하게 cutLength를 계산할 수 있다.

#include <iostream> #include <vector> #include <cstring> #include <algorithm> using namespace std; //x1<x2, y1<y2 struct Rectangle{ int x1, y1, x2, y2; Rectangle(){} Rectangle(int _x1, int _y1, int _x2, int _y2) : x1(_x1), y1(_y1), x2(_x2), y2(_y2){} }; //직사각형들의 면적을 계산한다. int unionArea(const vector<Rectangle>& rects){ if(rects.empty()) return 0; //이벤트 정보 : (x좌표, 왼쪽인가 오른쪽인가, 사각형의 번호) typedef pair<int, pair<int, int> > Event; vector<Event> events; vector<int> ys; //각 사각형을 순회하면서 y좌표의 모음과 이벤트의 집합을 찾는다. for(int i=0; i<rects.size(); ++i){ ys.push_back(rects[i].y1); ys.push_back(rects[i].y2); events.push_back(Event(rects[i].x1, make_pair(1,i))); events.push_back(Event(rects[i].x2, make_pair(-1,i))); } //y좌표의 집합을 정렬하고 중복을 제거 sort(ys.begin(), ys.end()); ys.erase(unique(ys.begin(), ys.end()), ys.end()); //이벤트 목록을 정렬 sort(events.begin(), events.end()); int ret=0; //count[i]=ys[i]~ys[i+1]구간에 겹쳐진 사각형의 수 vector<int> count(ys.size()-1, 0); for(int i=0; i<events.size(); ++i){ int x=events[i].first, delta = events[i].second.first; int rectangle=events[i].second.second; //count[]를 갱신 int y1=rects[rectangle].y1, y2=rects[rectangle].y2; for(int j=0; j<ys.size(); ++j) if(y1<=ys[j] && ys[j]<y2) count[j]+=delta; //cutlengt()값을 계산한다. int cutLength=0; for(int j=0; j<ys.size()-1; ++j) if(count[j]>0) cutLength+=ys[j+1]-ys[j]; //다음 이벤트까지의 거리에 cutLength를 곱한 값을 ret에 더한다. if(i+1 < events.size()) ret+=cutLength*(events[i+1].first-x); } return ret; }

• evnt와 ys의 원소수는 각각 O(N)이기 때문에 이 알고리즘의 전체 시간 복잡도는 O(N2)

• 다각형 교집합의 넓이 구하기
• 다각형의 교집합은 항상 사다리꼴 형태를 보인다.

• 수직선을 움직이면서 각 사다리꼴들의 면적을 모두 더하면 교집합의 넓이를 쉽게 찾을 수 있음
• 오목 다각형이 주여져도 쉽게 계산이 가능
• 교차하는 선분들
• 모든 선분의 쌍에 대해 이 선분들이 교차하는지 확인하는 것이 기초적인 방법
• 시간적 복잡도 O(N2)
• 평면 스위핑 알고리즘 이용시 O(NlgN)까지 가능
• 평면을 왼쪽에서부터 오른쪽까지 쭉 훑어가는 수직선 설정
• 이 수직선이 어떤 선분의 왼쪽 끝 점과 오른쪽 끝 점을 만나는 이벤트를 모음
• 수직선이 선분의 왼쪽 끝점을 만나면 선분이 이 집합에 추가되고 오른쪽 끝 점을 만나면 집합에서 빠지게 된다.
• 항상 각 선분이 수직선을 만나는 y 좌표가 증가하는 순으로 정렬
• 교차 여부 판단
• 새로운 선분이 추가될 때마다 집합 상에서 새 선분과 인전합 두 선분의 교차 여부를 확인
• 선분이 삭제될 때마다 집합 상에서 이 선분과 인접해 있던 두 선분의 교차 여부 판단
• 교차하는 선분이 한 쌍이라도 나오는 시점에서 바로 종료
• 교차가 아직 이루어지지 않았기 때문에 선분들의 상대적인 순서가 여전히 유지되기 때문에 정렬을 안함
• 회전하는 캘리퍼스
• 캘리퍼스
• 작은 물건의 지름, 너비들을 측정할 때 쓰는 공구
• 두 개의 평행한 변 사이에 물체를 끼우고 변 사이의 길이를 잼
• 볼록 다각형의 지름
• 볼록 다각형의 지름은 볼록 다각형에 완전히 포함되는 가장 긴 선분의 길이
• O(N2)
• 모든 꼭지점의 쌍을 순회하면서 이중 가장 멀리 떨어져 있는 쌍을 찾음
• 가장 왼쪽과 오른쪽 점을 찾아낸 뒤, 각각 두 개의 수직선을 붙임
• 두 벡터의 방향은 항상 반대이기 때문에 첫 번째 직선의 방향 벡터만을 저장하는 것으로 가능
• 직선을 시계방향으로 돌렸을 때 어느 쪽이 다각형의 다른 점을 만나는지 계산
• calipers와 다각형 변이 이루는 두 각 중 작은 각 만큼 두 calipers를 시계 반대 방향으로 평행을 유지하도록 돌려준다.
• 

//시계 반대 방향으로 주어진 볼록 다각형에서 가장 먼 꼭지점 쌍 사이의 거리를 반환한다. double diameter(const polygon& p) { int n = p.size(); //우선 가장 왼쪽에 있는 점과 오른쪽에 있는 점을 찾는다. int left = min_element(p.begin(), p.end()) - p.begin(); int right = max_element(p.begin(), p.end()) - p.begin(); //p[left]와 p[right]에 각각 수직선을 붙인다. 두 수직선은 서로 정반대 방향을 가리키므로 //A의 방향만을 표현하면 된다 vector2 calipersA(0, 1); double ret = (p[right] - p[left]).norm(); //toNext[i] = p[i]에서 다음 점까지의 방향을 나타내는 단위 벡터 vector<vector2> toNext(n); for (int i = 0; i < n; ++i) toNext[i] = p[(i + 1) % n] - p[i]).normalize(); //a와 b는 각각 두 선분이 어디에 붙은 채로 회전하고 있는지를 나타낸다. int a = left, b = right; //반 바퀴 돌아서 두 선분이 서로 위치를 바꿀 때까지 계속 진행 while (a != right || b != left) { //a에서 다음 점까지의 각도와 b에서 다음 점까지의 각도 중 어느 쪽이 작은지 확인 double cosThetaA = calipersA.dot(toNext[a]); double costThetaB = -calipersA.dot(toNext[b]); if (cosThetaA > costThetaB) { //thetaA < thetaB calipersA = toNext[a]; a = (a + 1) % n; } else { calipersA = -toNext[b]; b = (b + 1) % n; } ret = max(ret, (p[a] - p[b]).norm()); } return ret; }

자주 하는 실수와 유의점들

• 퇴화 도형
• 기하 알고리즘을 만들 때 도형들의 일반 위치만 고려하는 문제
• 일반 위치: 도형들의 상대적 위치의 일반적인 경우
• 퇴화 도형: 반대가 되는 경우
• 일직선 상에 있는 세 개 이상의 점들
• 서로 평행이거나 겹치는 직선/선분들
• 넓이가 0인 다각형들
• 다각형의 변들이 서로 겹치는 경우
• 이런 경우들에 대해 예외 처리를 해주어야 함.
• 직교 좌표계와 스크린 좌표계
• 좌표계를 착각하는 문제
• 직교 좌표계
• 위로 갈수록 y좌표가 증가하고 오른쪽으로 증가살 수록 x좌표가 증가
• 스크린 좌표계
• 맨 윗줄의 y좌표가 0, 아래로 갈수록 y좌표가 증가
• 좌표를 입력받아 익숙한 좌표계로 변환하여 해결
• 다른 실수들
• 알고리즘이 수치적으로 불안정한 경우 정수나 분수 연산만으로 정확하게 해결하는 방법을 모색해야 함.
• acos(), asin(), atan2() 등의 함수는 느리고 수치적으로 불안정하므로 가능한 사용을 자제
• acos(), asin()은 입력으로 +-1 범위의 실수만을 받아들임
• 따라서 범위 제한이 필요
• sqrt()함수의 입력에 0 대신에 아주 작은 음수가 들어가는 실수도 흔함
• 따라서 sqrt 함수 호출시에도 sqrt(max(0.0, x))와 같은 범위 제한이 필요

보물섬(TREASURE, 난이도: 상)

• 문제 링크: https://algospot.com/judge/problem/read/TREASURE

•