선분 교차 알고리즘 <CCW 이용>

http://jason9319.tistory.com/358

위의 블로그에서 보고 배웠습니다.

CCW : CounterClockWise의 약자로 뜻은 '시계 반대 방향'을 의미한다.

세 가지 점 (a, b, c)가 주어졌을 때, a->b->c 가

1. 시계방향

2. 반시계방향

3. 평행

중 어떤 경우인지를 분별해주는 알고리즘이다.

(x2 - x1)(y3 - y1) - (y2 - y1)(x3 - x1)의 값이

0보다 큰 경우 : 반 시계 방향

0인 경우 : 평행

0보다 작은 경우 : 시계 방향

* 위의 굵은 색 식의 값을 2로 나누면 삼각형의 넓이가 나온다고 한다.

굵은 색의 식을 나열하면 x1y2 + x2y3 + x3y1 - x1y3 - x2y1 - x3y2 가 된다.

이 식을 코드로 나타내면 아래 op와 관련된 코드가 나온다,

CCW 알고리즘 내용은 아래와 같다.

int CCW(pair<int, int> &p1, pair<int, int> &p2, pair<int, int> &p3)
{
	int op = p1.first * p2.second + p2.first*p3.second + p3.first*p1.second;
	op -= (p1.first*p3.second + p2.first*p1.second + p3.first*p2.second);

	if (op > 0) return 1;
	else if (op == 0) return 0;
	else return -1;
}

A

 l

C -------D

 l

B

위와 같이 AB 선분과 CD선분이 있었을 때, A->C->B는 반시계, A->D->B는  시계방향을 가리키면서 서로 다른 방향을 나타낸다.

따라서 CCW(A, B, C) * CCW(A, B, D)의 값이 음수인 경우에 '교차 가능성'이 존재한다. 

음수가 나와도 교차하지 않는 경우는 아래와 같다.

A

C------D       l

B

이러한 경우를 대비하여 CCW(C,D,A) * CCW(C,D,B) 값도 구해주면 된다.

CCW(A, B, C) * CCW(A, B, D)와 CCW(C,D,A) * CCW(C,D,B) 둘 다 <= 0 인 경우에 교차 가능성이 존재한다.

아직 교차 확정이 아닌 교차 가능성이라고 표현한 이유는 두 개의 값이 모두 0인 가능성이 있기 때문이다.

두 개의 값이 0이라는 것은 두 선분이 같은 선상에 평행하게 놓여져 있음을 뜻한다.

AㅡㅡB     Cㅡㅡ D 인 경우가 있을 수 있고 AㅡCㅡBㅡD 처럼 AB선분과 CD선분이 교차할 수도 있다.

이를 예외처리해주면, 선분이 교차되어 있는 지 판별할 수 있는 알고리즘을 구현할 수 있다.

bool CheckIntersect(int line1, int line2)
{
	pair<int, int> p1 = v[line1].first;
	pair<int, int> p2 = v[line1].second;
	pair<int, int> p3 = v[line2].first;
	pair<int, int> p4 = v[line2].second;

	int line1_2 = CCW(p1, p2, p3) * CCW(p1, p2, p4);
	int line2_1 = CCW(p3, p4, p1) * CCW(p3, p4, p2);

	if (line1_2 == 0 && line2_1 == 0)
	{
		if (p1 > p2) swap(p1, p2);
		if (p3 > p4) swap(p3, p4);

		return p1 <= p4 && p3 <= p2;
	}
	return line1_2 <= 0 && line2_1 <= 0;
}

위의 코드에 swap 해주는 두 부분은, 선분의 양 끝점 중 상대적으로 큰 점을 두 번째로 지정해주는 코드이다.

위의 코드를 통해 보자면 p1, p2 선분은 p2 점이 상대적으로 크고, p3, p4 선분은 p4점이 상대적으로 크게 설정해둔다.

pair<int, int> 에서 대소 비교는,먼저 .first를 비교한 뒤에 first가 같은 경우 .second를 비교하는 형태로 이루어진다.

p1 < p2  ,  p3 < p4 인 상태에서,   p1 <= p4 && p3 <= p2 가 되는 조건 하에 선분 교차가 이루어진다.