종만북 15장 계산 기하
이 포스팅은 <프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략>, 구종만, 인사이트(2012)을 읽고 개인 학습용으로 정리한 글입니다.
➖ 21-06-16
벡터 구현
#include <math.h>
//cos(PI/2) = 0
const double PI = 2.0 * acos(0.0);
struct vector2{
//벡터 시작점 항상 원점으로 고정 -> 벡터를 끝점의 위치(x,y)로만 표현할 수 있다
double x, y;
//생성자 explicit으로 구현
explicit vector2(double x_ = 0, double y_ = 0) : x(x_), y(y_){}
//벡터 비교 연산
//rhs: right hand side 매개변수
bool operator == (const vector2& rhs) const{
return x == rhs.x && y == rhs.y;
}
bool operator < (const vector2& rhs) const{
return x != rhs.x ? x < rhs.x : y < rhs.y;
}
//벡터 덧셈/뺄셈
vector2 operator + (const vector2& rhs) const{
return vector2(x + rhs.x, y + rhs.y);
}
vector2 operator - (const vector2& rhs) const{
return vector2(x - rhs.x, y - rhs.y);
}
//벡터 실수로 곱셈
vector2 operator * (double rhs) const{
return vector2(x * rhs, y * rhs);
}
//벡터 길이 반환
double norm() const{
return hypot(x,y);
//표준 라이브러리 함수 -> 두 변의 길이가 각각 x, y인 직각삼각형의 빗변의 길이 계산
}
//방향이 같은 단위벡터(unit vector)반환
//영벡터에 의해 호출된 경우 반환값은 정의되지 않음 (분모 norm() = 0이 되기 때문)
vector2 normalize() const{
return vector2(x / norm(), y / norm());
}
//x축의 양의 방향으로부터 이 벡터까지의 반시계방향으로 잰 각도 = 극각도 (polar angle)
double polar() const{
return fmod( atan2(y,x) + 2 * PI, 2*PI);
//atan(y,x): 각 좌표의 부호를 이용해 자동으로 극각도 계산, 반환값 [-PI, PI]
//fmod(): 실수를 다른 실수로 나눴을 때 나머지를 구하는 함수 (float modular)
//반환 각도에 2*PI를 더하고 2*PI로 나눈 나머지 구함 -> 결과 [0, 2*PI) 가 되도록 함
}
/*
벡터 내적의 계산:
a dot b = ax*bx + ay*by = a크기 * b크기 *cos세타
벡터 내적의 사용:
1. 벡터의 사이각 구하기
세타 = acos( (a dot b) / (a크기 * b크기) )
2. 벡터의 직각 여부 확인
길이가 0이 아닌 두 벡터의 내적 = 0 -> 두 벡터 직각
3. 벡터의 사영
*/
//벡터 내적
double dot (const vector2& rhs) const{
return x * rhs.x + y * rhs.y;
}
//벡터 rhs에 사영
vector2 project(const vector2& rhs) const{
vector2 r = rhs.normalize();
return r * r.dot(*this);
}
/* 벡터 외적의 계산:
벡터 a, b가 주어졌을 때 이 두 벡터에 모두 수직인 다른 벡터 반환
a cross b = ax * by - ay * bx = a크기 * b크기 * sin세타
벡터 외적의 사용:
1. 면적 계산하기
외적의 절댓값 = a, b를 두변으로 하는 평행사변형의 넓이
2. 두 방향 벡터의 판별
외적이 음수인지 양수인지 알면 세타가 양수인지 음수인지 알 수 있다
*/
//벡터 외적
double cross (const vector2& rhs) const{
return x * rhs.y - y * rhs.x;
}
};
CCW
//ccw: counter clockwise
//polar() 사용하는 것보다 벡터의 외적 이용하는 것이 더 효율적
double ccw(vector2 a, vector2 b){
return a.cross(b);
//원점에서 벡터b가 벡터a의 반시계방향에 있으면 양수, 시계방향에 있으면 음수, 평행이면 0 반환
}
double ccw(vector2 p, vector2 a, vector2 b){
return (a-p).cross(b-p);
//점p를 기준으로 벡터b가 벡터a의 반시계방향에 있으면 양수, 시계방향에 있으면 음수, 평행이면 0 반환
}📌참고 자료
- 생성자 멤버 초기화 리스트
https://boycoding.tistory.com/246
- 값을 할당하지 않고 멤버 변수를 초기화할 수 있다
- 생성자 본문에서 값을 할당하는 것보다 성능이 우수하다
- const 또는 reference 변수와 같이 초기값이 필요한 멤버를 초기화할 수 있는 유일한 방법이다
- 멤버 초기화 리스트는 기본 자료형 변수와 클래스 자체인 멤버 모두에서 잘 작동한다
- expilict 키워드: 컴파일러가 알아서 형변환 하는것을 막을 수 있다
- explicit 키워드 없이 사용한다면 사용자가 원치 않은 형변환이 일어나는 등 예기치 않은 버그가 발생할 수 있기 때문에 사용해 주는 것이 좋다
➖ 21-06-17
직선의 벡터 방정식
- 벡터a를 포함하는 직선의 벡터 방정식 = 벡터a + p * 방향벡터 (p는 실수)
- 두 직선 사이의 관계: 두 직선의 방향 벡터의 관계를 이용하여 풀이
직선과 직선의 교차
//두 직선의 교차점 계산
//벡터 a, b를 포함하는 직선 l1 과 벡터 c, d를 포함하는 직선 l2의 교점을 x에 저장
//두 직선이 평행하면 false, 아니면 true반환
bool lineIntersection(vector2 a, vector2 b, vector2 c, vector2 d, vector2& x){
//l1 벡터 = 벡터a + p * (벡터b - 벡터a)
//l2 벡터 = 벡터c + q* (벡터d - 벡터c)
//두 직선 평행한지 검사 -> 두 방향 벡터를 외적(cross)했을 때 0 이면 평행한다
double det = (b-a).cross(d-c);
if(fabs(det) < FLT_EPSILON) return false;
//epsilon : the difference between 1.0 and the next value representable by the floating type
x = a + (b - a) * ((c-a).cross(d-c) / det);
return true;
}
선분과 선분의 교차
- 두 선분 ab, cd이 평행할 때, 교차하는지 검사
bool parallelSegments(vector2 a, vector2 b, vector2 c, vector2 d, vector2& p){
if(b < a) swap(a, b);
if(d < c) swap(c, d);
//한 직선 위에 없는 경우
if(ccw(a, b, c) != 0) return false;
//한 직선 위에 있지만 두 선분 겹치지 않는 경우
if(b < c || d < a) return false;
//한 직선 위에 있고 두 선분 겹치는 경우 -> 교차점 찾기
if(a < c) p = c;
else p = a;
return true;
}
- 벡터p가 벡터a와 벡터b를 잇는 선분ab 위에 있는지 검사
(세 벡터는 일직선 상에 있음)
//p가 (a, b)를 감싸면서 각 변이 x,y축에 평행한 최소 사각형 내부에 있는지 확인
bool inBoundingRectangle(vector2 p, vector2 a, vector2 b){
if(b<a) swap(a, b);
return (a == p || b == p || a < p && p < b);
}bool segmentIntersection (vector2 a, vector2 b, vector2 c, vector2 d, vector2& p){
//두 직선이 평행한 경우 처리
if(!lineIntersection(a,b,c,d,p))
return parallelSegments(a,b,c,d,p);
//교차점 p가 두 선분에 포함되어 있는 경우 true
return inBoundingRectangle(p,a,b) && inBoundingRectangle(p,c,d);
}선분과 선분의 교차 (교차점 필요 없는 경우)
bool segmentIntersects(vector2 a, vector2 b, vector2 c, vector2 d){
double ab = ccw(a, b, c) * ccw(a, b, d);
double cd = ccw(c, d, a) * ccw(c, d, b);
//ab와 cd 둘 다 0인 경우 : 두 선분이 한 직선 위에 있거나 끝점이 겹치는 경우
if(ab == 0 && cd == 0){
if(b<a) swap(a, b);
if(d<c) swap(c ,d);
return !(b<c || d < a);
}
//ab와 cd 둘 중 하나 0인 경우에도 참 반환
return ab<= 0 && cd <= 0;
}-
ab와 cd 둘 다 0인 경우 : 두 선분이 한 직선 위에 있거나 끝점이 겹치는 경우
-
ab와 cd 둘 중 하나 0인 경우에도 참 반환
점과 선 사이의 거리
//점p에서 벡터a,b를 포함하는 직선에 내린 수선의 발q
vector2 perpendicularFoot(vector2 p, vector2 a, vector2 b){
return a + (p-a).project(b-a);
}
//점p와 벡터a,b를 포함하는 직선 사이의 거리 = 점p과 점q 사이의 거리
double pointToLine(vector2 p, vector2 a, vector2 b){
return (p - perpendicularFoot(p,a,b)).norm();
}점과 선분 사이의 거리
- 선분을 포함하는 직선에 내린 수선의 발q가 선분 위에 떨어질 경우
d = 점p와 점q 사이의 거리 - 선분을 포함하는 직선에 내린 수선의 발q가 선분 밖에 떨어질 경우
d = 점p와 (선분 중 점q와 가까운 끝점) 사이의 거리
➖ 21-06-26
다각형(polygon)의 종류
-
볼록 다각형 (convex polygon): 모든 내각이 180도 미만인 다각형
-> 두 볼록 다각형의 교집합은 항상 볼록 다각형이다
-> 볼록 다각형 내부의 두 점을 연결하는 선분은 볼록 다각형의 경계를 절대 교차하지 않는다 -
오목 다각형 (concave polygon): 180도를 넘는 내각을 갖는 다각형
-
단순 다각형 (simple polygon): 다각형의 경계가 스스로를 교차하지 않는 다각형
면적 구하기
-
다각형의 점들 p0, p1, p2, ... , pn-1이 반시계 순서대로 배열되어있을 때
- 한 점 q을 잡는다
- 다각형의 인접한 두 점 pi, p(i+1)%n과 q를 꼭짓점으로 하는 삼각형의 넓이
(pi - q) X (p(i+1)%n - q)/2 - 삼각형들의 넓이를 각각 계산하여 더한다
이때, 외적의 값을 절대값을 취하지 않음 -> 삼각형의 넓이 중 음수가 있을 수 있다
-
q의 위치와 상관 없이 다각형이 단순 다각형이기만 하면 항상 성립한다
-> q를 원점으로 두면 이 방법을 공식으로 표현할 수 있다
//주어진 단순 다각형 p의 넓이를 구한다
//p는 각 꼭지점의 위치 벡터의 집합(vector<T>)으로 주어진다
double area(const vector<vector2>& p){
double ret = 0;
for(int i = 0; i<p.size; ++i){
int j = (i+1) % p.size;
ret += p[i].x * p[j].y - p[j].x * p[i].y;
}
return fabs(ret)/2.0;
}⚡내부/외부 판별
- 단순 다각형과 이 다각형의 경계 위에 있지 않은 점 q가 주어질 때
q에서 시작해 오른쪽으로 쭉 뻗어나가는 반직선을 상상하고 이 반직선이 다각형과 몇번 교차하는지 확인
-> 내부에 있는 점에서 시작하는 반직선: 항상 홀수 번 교차
-> 외부에 있는 점에서 시작하는 반직선: 항상 짝수 번 교차
-
발생할 수 있는 예외 사항
-> a에서 시작하는 반직선: 다각형의 점을 지난다
-> b에서 시작하는 반직선: 다각형의 두 변과 접촉한다 -
올바르게 작동하는 알고리즘 작성을 위해 반직선을 마음속으로 '엄청나게 작은 값'만큼 위로 올린다
-> 어떤 변이 반직선의 끝점과 겹칠 경우, 다른 한 점이 위에 있느냐 아래에 있느냐에 따라 결과 달라지게 된다
-> 반직선과 수평인 다각형의 변들은 완전히 무시된다
//점 q가 다각형p 안에 포함되어 있을 경우 참, 아닌 경우 거짓 반환
//q가 다각형의 경계 위에 있는 경우의 반환값은 정의되어 있지 않다
bool isInside(vector2 q, const vector<vector2>& p){
int crosses = 0;
for(int i = 0; i < p.size(); ++i){
int j = (i+1) % p.size();
if(p[i].y > q.y != p[j].y > q.y){
double atX = (p[j].x - p[i].x)*(q.y - p[i].y) / (p[j].y - p[i].y) + p[i].x;
if(q.x < atX){
++crosses;
}
}
}
return crosses%2 > 0;
} 
➖ 21-08-30
너드인가, 너드가 아닌가? (NERDS)
기하 문제로의 변환
- 각 사람의 신발 사이즈와 타이핑 속도를 각각 x, y 좌표로 하면, 입력 데이터를 N개의 점으로 표시할 수 있다
-
입력 데이터를 N개의 점으로 표시한 그림에서, 너드와 너드가 아닌 사람을 갈라놓을 수 있는 직선이 있다면, 너드인 사람에 대해 성립하는 식 Ax + >= T이 반드시 존재한다
-
따라서 이 문제는 평면 상에 두 종류의 점이 주어질 때 이들을 구분할 수 있는 직선이 존재하는지 여부를 구하는 문제로 바꿀 수 있다
볼록 껍질 모델링
-
볼록 껍질(convex hull): 2차원 평면에서 주어진 점들을 모두 포함하는 최소 크기의 다각형
-> 크기가 최소가 되기 위해, 볼록 껍질의 꼭짓점은 모두 원래 주어진 점이다 -
두 종류의 점에 대해 각각 볼록 껍질을 구한 후, 두 다각형이 서로 겹치거나 닿아 있는지만을 확인해서 문제를 해결할 수 있다
-> 두 개의 다각형이 서로 겹치거나 닿아 있지 않은 경우: 이들을 구분하는 직선 존재
-> 두 개의 다각형이 서로 겹치거나 닿아 있는 경우: 이들을 구분하는 직선 존재 X
⚡볼록 껍질 찾기
- 선물 포장 알고리즘(Gift wrapping algorithm):
- 우선 항상 볼록 껍질에 포함될 수 밖에 없는 점을 하나 찾는다
- 그 점에 가상의 '포장지'인 반직선을 붙인 뒤, 이 반직선을 시계 방향으로 돌리며 다른 점을 감싸 나간다
- 선물 포장 알고리즘의 구현 방법:
- 마지막으로 포장지가 닿은 점 p가 주어질 때 모든 점을 검사한다
- 이때 p에서 각 점으로 가는 벡터 중 가장 왼쪽에 있는 벡터에 대응되는 점이 다음으로 포장지에 닿을 점이 된다
- 이렇게 찾은 다음 점을 볼록 껍질에 포함시키고, 시작점으로 돌아올 때까지 반복한다
//블록 껍질을 찾는 선물 포장 알고리즘의 구현
typedef vector<vector2> polygon;
//points에 있는 점들을 모두 포함하는 최소의 볼록 다각형(볼록 껍질)을 찾는다
polygon giftWrap(const vector<vector2>& points){
int n = points.size();
polygon hull;
//가장 왼쪽 아래 점을 찾는다 (STL min_element 함수 이용)
//이 점은 볼록 껍질에 반드시 포함된다
vector2 pivot = *min_element(points.begin(), points.end());
hull.push_back(pivot);
while(true){
//ph에서 시작하는 벡터가 가장 왼쪽인 점 next를 찾는다 (ccw 이용)
//평행인 점이 여러 개 있으면 가장 먼 것을 선택한다
vector2 ph = hull.back();
vector2 next = points[0];
for(int i = 1; i <n; ++i){
double cross = ccw(ph, next, points[i]);
double dist = (next - ph).norm - (points[i]-ph).norm;
//조건 1) cross > 0 : points[i]가 next보다 왼쪽인 점일 경우
//조건 2) corss == 0 && dist < 0: points[i]와 next가 평행하고, points[i]가 더 멀리 떨어진 점일 경우
if(cross > 0 || (cross == 0 && dist < 0))
next = points[i];
}
//시작점으로 돌아온 경우 종료
if(next == pivot) break;
//next를 볼록 껍질에 포함시킨다
hull.push_back(next);
}
return hull;
}-
선물 포장의 while문은 볼록 껍질에 점이 하나 추가될 때 마다 반복 수행되고, while문 수행 시간은 O(N)이다
-> 볼록 껍질에 포함된 점의 수가 H일 때 전체 시간 복잡도: O(NH)
-> N개의 점이 모두 볼록 껍질에 포함될 때(최악의 경우) 전체 시간 복잡도: O(N^2) -
⚡더 많은 점에 대해 볼록 껍질을 구해야할 경우, 그라함 스캔(Graham's Scan) 알고리즘을 사용하면 O(NlgN) 시간에 볼록 껍질을 구할 수 있다
다각형 교차 판정
-
giftWrap()을 이용해 두 종류의 점에 대해 각각 볼록 껍질을 구한 뒤, 두 볼록 다각형이 서로 닿는지 판단해야 한다
-
가장 단순한 방법으로 다각형 교차를 판정하는 polygonIntersects()의 구현:
-> 처음에 한 다각형이 다른 다각형에 완전히 포함되어 있는 경우 예외로 처리한다
-> 이 경우를 제외하고 나면 두 다각형이 겹치기 위해서는 서로 겹치거나 닿는 두 변이 반드시 존재해야 한다
//두 볼록 다각형의 교차 여부를 확인하는 polygonIntersects()의 구현
//두 다각형이 서로 닿거나 겹치는지 여부를 반환한다
//한 점이라도 겹친다면 true
bool polygonIntersects(const polygon& p, const polygon& q){
int n = p.size();
int m = q.size();
//처음에 한 다각형이 다른 다각형에 완전히 포함되어 있는 경우 예외 처리
if(isInside(p[0], q) || isInside(q[0], p)) return true;
//이 외의 경우, 두 다각형이 서로 겹친다면 서로 닿는 두 변이 반드시 존재한다
for(int i = 0; i<n; ++i)
for(int j = 0; j<m; ++j)
if(segmentIntersects(p[i], p[(i+1)%n], q[j], q[(j+1)%m]))
return true;
return false;
} - polygonIntersects()의 시간 복잡도: 두 다각형의 점의 수 A, B에 대해 O(AB)가 된다
-> 볼록 껍질을 구하는 데 이미 O(N^2) 시간이 걸리므로 프로그램의 전체 시간 복잡도 달라지지 않는다
선형 분리
- 이와 같이 2차원 공간 상에 주어진 두 종류의 점들을 구분하는 직선이 존재하는지 여부를 찾는 문제 = 선형 분리(linear separability)문제이다
전체 풀이
#include <iostream>
#include <vector>
#include <math.h>
#include <utility>
#include <algorithm>
using namespace std;
typedef pair<int, int> dot;
typedef vector<dot> polygon;
double norm(dot a){
return hypot(a.first, a.second);
}
int ccw(dot a, dot b) {
int cross = a.first * b.second - a.second * b.first;
if (cross > 0) return 1;
else if (cross < 0) return -1;
else return 0;
}
int ccw(dot p, dot a, dot b) {
a.first -= p.first; a.second -= p.second;
b.first -= p.first; b.second -= p.second;
return ccw(a, b);
}
int segmentIntersects(dot a, dot b, dot c, dot d) {
int ab = ccw(a, b, c) * ccw(a, b, d);
int cd = ccw(c, d, a) * ccw(c, d, b);
if (ab == 0 && cd == 0) {
if (b < a) swap(a, b);
if (d < c) swap(c, d);
return !(b < c || d < a);
}
return ab <= 0 && cd <= 0;
}
polygon giftWrap(const vector<dot>& points) {
int n = points.size();
polygon hull;
dot pivot = *min_element(points.begin(), points.end());
hull.push_back(pivot);
while (true) {
dot ph = hull.back();
dot next = points[0];
for (int i = 1; i < n; ++i) {
int cross = ccw(ph, next, points[i]);
double dist = norm(make_pair(next.first - ph.first, next.second - ph.second)) - norm(make_pair(points[i].first - ph.first, points[i].second - ph.second));
if (cross > 0 || (cross == 0 && dist < 0))
next = points[i];
}
if (next == pivot) break;
hull.push_back(next);
}
return hull;
}
bool isInside(dot q, const polygon& p) {
int crosses = 0;
for (int i = 0; i < p.size(); ++i) {
int j = (i + 1) % p.size();
if (p[i].second > q.second != p[j].second > q.second) {
double atX = (p[j].first - p[i].first)*(q.second - p[i].second) / (p[j].second - p[i].second) + p[i].first;
if (q.first < atX) {
++crosses;
}
}
}
return crosses % 2 > 0;
}
bool polygonIntersects(const polygon& p, const polygon& q) {
int n = p.size();
int m = q.size();
if (isInside(p[0], q) || isInside(q[0], p)) return true;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (segmentIntersects(p[i], p[(i + 1) % n], q[j], q[(j + 1) % m]))
return true;
}
}
return false;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int T;
cin >> T;
while (T--) {
vector<dot> nerds;
vector<dot> not_nerds;
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
int a, b, c;
cin >> a >> b >> c;
if (a == 1) nerds.push_back(make_pair(b, c));
else not_nerds.push_back(make_pair(b, c));
}
polygon convex_hull1 = giftWrap(nerds);
polygon convex_hull2 = giftWrap(not_nerds);
if (polygonIntersects(convex_hull1, convex_hull2))
cout << "THEORY IS INVALID\n";
else
cout << "THEORY HOLDS\n";
}
return 0;
}➖ 21-09-01
계산 기하 알고리즘 디자인 패턴
- 기하 알고라즘 디자인 패턴
- 평면 스위핑
- 회전하는 캘리퍼스
평면 스위핑
- 평면 스위핑(plane sweeping):
수평선 혹은 수직선으로 주어진 평면을 쓸고 지나가며 문제를 해결하는 방법
직사각형 합집합의 면적
-
문제:
x축과 y축에 각 변이 평행한 직사각형들이 여러 개 주어질 때 이들의 합집합의 면적을 구하라 -
문제를 푸는 방법 중 하나: 포함-배제 원칙(inclusion-exclusion principle) 이용하기
- 각 직사각형의 면적을 모두 구해 더한다
- 두 개의 직사각형의 pair에 대한 교집합 -> 이들의 면적은 두번 더해졌으니 결과에서 빼준다
- 세 개의 직사각형의 tuple에 대한 교집합 -> 이들의 면적은 세번 더해지고 세번 빠졌으니 결과에 다시 더한다
- 이 과정을 반복한다
- 이 방법의 문제점:
사각형이 n개 있을 때 모든 2^n 개의 교집합을 방문해야 한다
평면 스위핑 알고리즘 설계
- 이 그림을 왼쪽에서 오른쪽으로 훑고 지나가는 수직선이 있다고 가정하기
-> 수직선의 좌표 x가 주어질 때, 사각형들을 수직선으로 잘랐을 때 단면(사각형들과 수직선이 겹치는 부분)의 길이를 반환하는 함수 cutLength()가 있다면
-> 합집합의 넒이 = 이 함수를 x에 대해 정적분한 결과
-> 그림 (a)
- 실제로 cutLength()함수를 정적분할 필요는 없다
-> 단면의 길이가 변하는 지점은 직사각형의 왼쪽 끝이거나 오른쪽 끝 뿐이기 때문이다
-> 이와 같이 단면의 길이가 변하는 지점을 이벤트(event)라고 부르자
-> 이벤트들의 위치를 미리 계산해 정렬해 두면 각 이벤트 사이에서는 cutLength()의 값이 변하지 않는다
-> 그림 (b)
- 두 이벤트 사이에서의 합집합의 넓이 = 한 이벤트 위치에서 cutLength 다음 이벤트까지의 거리
-> 그림 (c)
- ⚡알고리즘 구현
-> 한 이벤트 위치에서 cutLength를 계산하기 위해 모든 사각형을 순회하는 방법 대신,
-> 모든 사각형들의 y좌표를 모아 정렬해두어 수직선을 이 좌표들로 쪼갠다
-> 수직선의 각 쪼개진 구간이 사각형에 겹쳐 있는지를 표시하는 배열 count를 이용하여 cutLength를 계산한다
-> 그림 (d)
//직사각형 합집합의 면적을 구하는 unionArea()의 구현
struct Rectangle{
int x1, y1, x2, y2;
};
int unionArea(const vector<Rectangle>& recs){
if(recs.empty()) return 0;
//이벤트 <x좌표, <delta, 사각형의 번호>>
//delta: 사각형의 왼쪽 x좌표라면 1, 오른쪽 x좌표라면 -1
typeof pair<int, pair<int, int>> Event;
vector<Event> events;
//모든 사각형의 y좌표의 집합
vector<int> ys;
//각 사각형을 순회하며 이벤트 집합와 y좌표 집합을 만든다
for(int i = 0; i<recs.size(); ++i){
events.push_Back( {recs[i].x1, {1, i}} );
events.push_Back( {recs[i].x2, {-1, i}} );
ys.push_back(recs[i].y1);
ys.push_back(recs[i].y2);
}
//이벤트 집합 정렬
sort(events.begin(), events.end());
//y좌표 집합 정렬 & 중복 제거
sort(ys.begin(), ys.end());
ys.erase(unique(ys.begin(), ys.end()), ys,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){
//이벤트의 x좌표 & delta & 사각형의 번호
int x = events[i].first;
int delta = events[i].second.first;
int rectangle = events[i].second.second;
//count[] 갱신
int y1 = recs[rectangle].y1;
int y2 = recs[rectangle].y2;
for(int j = 0; j < ys.size(); ++j){
//수직선의 쪼개진 구간이 사각형에 겹쳐있는 경우
if(y1 <= ys[j] && ys[j] < y2){
//이벤트의 x좌표가 사각형의 왼쪽 좌표인 경우 count 1 증가
//이벤트의 x좌표가 사각형의 오른쪽 좌표인 경우 count 1 감소
count[j] += delta;
}
}
//cutLength 계산
int cutLength = 0;
for(int j = 0; j < ys.size(); ++j){
//수직선의 쪼개진 구간에 겹쳐있는 사각형 존재
if(count[j] > 0){
//cutLength에 쪼개진 구간의 길이만큼 더한다
cutLength += (ys[j+1] - ys[j]);
}
}
//두 이벤트 사이에서의 합집합의 넓이
//= 한 이벤트 위치에서 cutLength * 다음 이벤트까지의 거리
if(i+1 < events.size())
ret += (cutLength * (events[i+1].first - x));
}
return ret;
}다각형 교집합의 넓이 구하기
- 문제: 보물섬(TREASURE)
N개의 점을 갖는 다각형과 (x1, y1), (x2, y2)를 서로 대칭인 꼭짓점으로 갖고 네 변이 모두 x축 혹은 y축에 평행한 직사각형의 내부와의 교집합의 넓이를 구하라
https://algospot.com/judge/problem/read/TREASURE
- 두 다각형의 꼭짓점과 변들의 교차점들의 x좌표를 모두 이벤트로 두면,
두 이벤트 사이에서 두 다각형의 교집합은 항상 사다리꼴 형태이다
-> 교집합의 넓이 = 수직선을 움직이면서 각 사다리꼴들의 면접을 모두 더한 값
- 이 방법은 교집합을 직접 구하지 않지만, 두 오목 다각형이 주어질 경우에도 교집합의 넓이를 쉽게 계산할 수 있다
교차하는 선분들
-
문제:
평면 위 선분들의 집합이 주어질 때 이들 중 서로 교차하는 것이 있는지 찾아라 -
모든 선분의 쌍에 대해 이들이 교차하는지 확인하는 방법: O(N^2)
평면 스위핑 알고리즘을 이용하는 방법: O(NlgN) -
평면을 왼쪽에서부터 오른쪽까지 쭉 훑어가는 수직선이 있다고 가정하자
-> 이벤트: 이 수직선이 어떤 선분의 왼쪽 끝점 혹은 오른쪽 끝점과 만나는 경우 -
두 선분이 교차하는 지점 바로 이전 이벤트에서 교차하는 두 선분 사이에는 어떤 선분도 없다
-> 샤모스-호이(Shamos-Hoey) 알고리즘은 이 점을 이용한다
⚡샤모스-호이 알고리즘
-
왼쪽에서부터 각 이벤트를 방문하며, 현재 수직선과 겹쳐져 있는 선분들의 집합을 수직선을 만나는 y좌표가 증가하는 순으로 정렬하여 유지한다
-
선분 집합:
수직선이 선분의 왼쪽 끝 점을 만나는 경우: 집합에 선분 추가
수직선이 선분의 오른쪽 끝점을 만나는 경우: 집합에서 선분 삭제 -
선분 교차 확인:
집합에 선분이 추가된 경우: 집합 상에서 새 선분과 인접한 두 선분과의 교차 여부 확인
집합에서 선분이 삭제된 경우: 집합 상에서 이 선분과 인접해있던 두 선분의 교차 여부 확인 -
이 알고리즘은 교차하는 선분이 한 쌍이라도 나오는 시점에서 종료된다
-> 선분 교차가 일어나지 않으면 각 선분의 수직선과 만나는 y좌표의 상대적인 순서가 유지된다
-> 선분이 추가/삭제될 때마다 집합을 재정렬하지 않아도 된다 -
이 알고리즘을 O(NlgN)에 구현하기 위해서는 효율적인 자료 구조의 선택이 필요하다
-> 이진 검색 트리를 이용해 구현해야 한다 -
⚡이 알고리즘의 확장판인 벤틀리-오트만(Bently-Ottman) 알고리즘을 이용하면, 교차의 존재 여부 뿐만 아니라 모든 교차점을 O((N+K)lgN)에 구할 수 있다
(N: 선분의 개수, K: 교차점의 개수)➖ 21-09-05
⚡회전하는 캘리퍼스(rotating calipers)
볼록 다각형의 지름
-
볼록 다각형의 지름: 볼록 다각형에 완전히 포함되는 가장 긴 선분의 길이
-
가장 단순한 방법: 모든 꼭짓점의 쌍을 순회하며 가장 멀리 떨어져 있는 쌍을 찾는다
-> N개의 꼭짓점이 있을 때 시간 복잡도 O(N^2) -
회전하는 캘리퍼스 알고리즘을 이용한 방법:
- 다각형을 평행한 두 직선 사이에 끼운다
- 다각형을 따라 직선을 한 바퀴 돌리면서 직선에 닿는 꼭짓점들 간의 거리를 잰다
- 이 과정에서 얻을 수 있는 최대 거리가 다각형의 지름이 된다
- 회전하는 캘리퍼스 알고리즘 구현:
- 가장 왼쪽과 오른쪽 점을 찾아낸 뒤, 각각에 두 개의 수직선을 붙인다
-> 이 두 벡터의 방향은 항상 반대이다 - 두 직선을 시계 반대 방향으로 돌렸을 때 어느 쪽이 먼저 다각형의 다른 점을 만나는지 계산한다
-> 이를 위해 현재 수직선의 방향과 다음 점 까지의 방향 사이의 각도 계산 - 이 두 각도 중 더 작은 쪽을 택해 두 직선을 회전한다
-> 직선의 회전: 직선의 방향 갱신하고, 회전의 축이 되는 점을 다음 점으로 옮긴다
//볼록 다각형의 지름을 재는 회전하는 캘리퍼스 알고리즘
//시계 반대 방향으로 주어진 볼록 다각형에서 가장 먼 꼭짓점 쌍 사이의 거리 반환
double diameter(const polygon& p){
int n = p.size();
//가장 왼쪽과 오른쪽 점 찾기
//min_element: pair.first를 기준으로 가장 작은 값을 가진 pair의 iterator
//-> x좌표가 가장 작은 좌표 = 가장 왼쪽에 있는 점
int left = min_element(p.begin(), p.end()) - p.begin();
//max_element: pair.first를 기준으로 가장 큰 값을 가진 pair의 iterator
//-> x좌표가 가장 큰 좌표 = 가장 오른쪽에 있는 점
int right = max_element(p.begin(), p.end()) - p.begin();
// p[left], p[right]각각에 두 개의 수직선 붙이기
//두 수직선은 서로 반대 방향 -> A의 방향만을 표현 (y축과 평행하여 위 방향)
vector2 calipersA(0,1);
//꼭짓점 쌍 사이의 거리: p[left] ~ p[right] 거리로 초기화
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는 각각 두 선분 calipersA, calipersB가 어디에 붙은 채로 회전하고 있는지를 나타낸다
int a = left, b = right;
//반 바퀴 돌아서 두 선분이 서로 위치를 바꿀 때까지 계속한다
while(a != right || b != left){
//a에서 다음 점까지의 각도와 b에서 다음 점까지의 각도 중 어느 쪽이 작은지 확인한다
//두 벡터 사이의 각 -> 내적값 이용
//선분 calipersA와 p[a]에서 다음 점까지의 방향을 나타내는 단위 벡터 내적
double cosThetaA = calipersA.dot(toNext[a]);
//선분 calipersB와 p[b]에서 다음 점까지의 방향을 나타내는 단위 벡터 내적
//calipersB는 calipersA와 반대 방향이므로 -calipersA로 표현 가능
double cosThetaB = -calipersA.dot(toNext[b]);
//직선 방향 갱신 & 회전의 축이 되는 점 다음 점으로 옮기기
if(cosThetaA > cosThetaB){
//thetaA < thetaB
//calipersA의 방향 = toNext[a]로 갱신
calipersA = toNext[a];
a = (a+1) % n;
}
else{
//thetaA >= thetaB
//calipersA의 방향 = toNext[b]로 갱신된 calipersB의 방향과 반대
calipersA = -toNext[b];
b = (b+1) % n;
}
//꼭짓점 쌍 사이의 거리 갱신
ret = max(ret, (p[a] - p[b]).norm());
}
return ret;
}📌참고자료
- 회전하는 캘리퍼스
https://stonejjun.tistory.com/42
Be able to be vulnerable, in search of truth