Computational Geometry(계산 기하학)

계산 기하학

• 컴퓨터 알고리즘의 한 분야
• 기하 물체를 대상으로 하는 문제를 조합론 및 알고리즘적인 해법으로 해결함
  • 컴퓨터 그래픽스, 로보틱스, VLSI 디자인, CAD 등에서 응용됨

기본 기하 연산

벡터의 외적

• 두 벡터 p = (px, py)와 q = (qx, qy)에 대해서, p X q = pxqy-pyqx = -q x p
• 외적 p x q는 점 (0,0), p, q, p + q를 꼭지점으로 하는 평행 사변형의 부호화된 면적을 나타냄
• 성질
  1. p x q > 0: q가 p로부터 반시계 방향으로 180도 이내에 존재
  2. p x q < 0: q가 p로부터 시계 방향으로 180도 이내에 존재
  3. p x q = 0: q는 p와 일직선 상에 존재
     
     

CCW 함수

• 벡터의 외적을 이용하여 정의

// 원점에서 벡터 q가 벡터 p에 반시계 방향이면 양수, 시계방향이면 음수 반환
// 평행이면 0 반환
typedef struct point { int x; int y; } Point;
// 원점에서 벡터 q가 벡터 p에 반시계 방향이면 양수, 시계방향이면 음수 반환
// 평행이면 0 반환
int ccw(Point p, Point q) {
	return p.x * q.y - p.y * q.x;
}

//점 r을 기준으로 벡터 rq가 벡터 rp에 반시계 방향이면 양수, 시계방향이면 음수 반환
// 평행이면 0 반환
int ccw(Point r, Point p, Point q) {
	return ccw(p - r, q - r);
}

CCW 활용

1. 세 점 a, b, c의 회전방향

   

• 위 그림에서 leftTrun은 ccw(a,b,c) > 0, righturn은 ccw(a,b,c) < 0

// 세 점 a, b, c의 회전 방향이 좌회전인지 검사
bool leftTurn(Point a, Point b, Point c) {
	return ccw(a, b, c) > 0;
}
// 세 점 a, b, c의 회전 방향이 우회전인지 검사
bool rightTurn(Point a, Point b, Point c) {
	return ccw(a, b, c) < 0;
}
// 세 점 a, b, c의 회전 방향이 일직선인지 검사
bool collinear(Point a, Point b, Point c) {
	return ccw(a, b, c) == 0;
}

1. 선분 교차 검사

// 세 점 a, b, c의 회전 방향 검사에서 좌회전이면 1,
// 우회전이면 -1, 일직선이면 0 반환
int direction(Point a, Point b, Point c) {
	if (ccw(a, b, c) < 0) return -1;
	if (ccw(a, b, c) > 0) return 1;
	return 0;
}

// 선분의 끝점이 교차점이 되는 경우를 제외
bool intersectProp(Point a, Point b, Point c, Point d) {
	return direction(a, b, c) * direction(a, b, d) < 0 &&
		direction(c, d, a) * direction(c, d, b) < 0;
}

// 선분의 끝점이 교차점이 되는 경우 허용
bool intersect(Point a, Point b, Point c, Point d) {
	return direction(a, b, c) * direction(a, b, d) <= 0 &&
		direction(c, d, a) * direction(c, d, b) <= 0;
}

• 만약, ccw(a, b, c)*ccw(a, b, d) == 0 (혹은 cda, cdb 연산이 0)이면 a, b, c 혹은 a, b, d가 일직선 상에 있는 것으로 이때는 a, b와 c, d의 상대적 위치를 비교해야 한다.
• 아래코드를 응용하여 검사

  bool between(Point a, Point b, Point c) {
    if (!collinear(a, b, c)) return false;
    if (a.x != b.x) { // 선분 ab가 수직선이 아니면
        return a.x <= c.x && c.x <= b.x ||
            b.x <= c.x && c.x <= a.x;
    }
    else {
        return a.y <= c.y && c.y <= b.y ||
            b.y <= c.y && c.y <= a.y;
    }
  }