[알고리즘] CCW ( CounterClockWise )

 

◇  설명, 코드

 

세 점 P1, P2, P3 이 있을 때,  P1-> P2 -> P3 차례로 이은 선분이 어떤 방향으로 이어지는지 판단

P1( x1, y1 )
P2( x2, y2 )
P3( x3, y3 )

• value  <  0  :  시계
• value  ==  0  :  일직선
• value  >  0  :  반시계

private int ccw(int x1, int y1, int x2, int y2, int x3, int y3) { // CounterClockWise 
	int value = (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1); 
	return value < 0 ? -1 : value > 0 ? 1 : 0; 
}

 

 

+  두 선분의 교차 여부

 

네 점 P1, P2, P3, P4 이 있을 때, P1-P2 를 이은 선분과 P3-P4 를 이은 선분의 교차 여부

P1( x1, y1 )
P2( x2, y2 )
P3( x3, y3 )
P4( x4, y4 )

 

P1-P2, P3-P4 두 선분에 대해 다른 선분의 두 점 각각의 방향 

• d123 = ccw( x1, y1, x2, y2, x3, y3 )  =  -1
• d124 = ccw( x1, y1, x2, y2, x4, y4 )  =  1
• d341 = ccw( x3, y3, x4, y4, x1, y1 )  =  -1
• d342 = ccw( x3, y3, x4, y4, x2, y2 )  =  1

 

P1-P2, P3-P4 두 선분에 대해 다른 선분의 두 점의 방향이 반대( -1 )인지 판단

• v12 = d123 * d124  =  -1
• v34 = d341 * d342  =  -1

 

• v12 < 0  &&  v34 < 0  :  두 선분이 서로 교차  ①
• (v12 == 0 && v34 < 0) || (v12 < 0 && v34 == 0)  :  세 점이 일직선 상에 있는데 한 점이 다른 두 점 사이에 있음  ②
• v12 == 0 && v34 == 0  :  세 점 이상이 일직선 상에 있음
• d123 == 0 && d124 == 0 && d341 == 0 && d342 == 0  :  네 점이 일직선 상에 있음  ③
  • ( p1 & p2, p3 & p4 를 좌표 위치에 따라 pA & pB, pC & pD 라고 할 때 )
  • pC < pB  &&  pA < pD  :  선분이 일직선으로 서로 겹침  ( 무수히 많은 점 )
  • pC == pB  ||  pA == pD  :  두 점이 같고 일직선으로 이어짐  ( 한 점에서 만남 )
  • (나머지)  :  교차하지 않음 ( 만나지 않음  )
• (나머지)  :  세 점이 일직선 상에 있는데 그 중 두 점이 같음  ④

각 경우의 예

네 점이 일직선 상에 있는 경우

 

▶  세 점이 일직선에 있는 경우는 제외 

private boolean isIntersect(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) {
	int d123 = ccw(x1, y1, x2, y2, x3, y3), d124 = ccw(x1, y1, x2, y2, x4, y4),
		d341 = ccw(x3, y3, x4, y4, x1, y1), d342 = ccw(x3, y3, x4, y4, x2, y2);
	int v12 = d123 * d124, v34 = d341 * d342;
	return v12 < 0 && v34 < 0;
}

▶  세 점 이상이 일직선 위에 있는 경우 포함

private boolean isIntersect(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) {
	int v12 = ccw(x1, y1, x2, y2, x3, y3) * ccw(x1, y1, x2, y2, x4, y4), 
	    v34 = ccw(x3, y3, x4, y4, x1, y1) * ccw(x3, y3, x4, y4, x2, y2);
	if (v12 == 0 && v34 == 0) // 네 점이 일직선 / 세 점이 일직선인데 그 중 두 점이 겹침
		return Math.min(x1, x2) <= Math.max(x3, x4)
			&& Math.min(x3, x4) <= Math.max(x1, x2)
			&& Math.min(y1, y2) <= Math.max(y3, y4)
			&& Math.min(y3, y4) <= Math.max(y1, y2); // 두 선분이 겹치거나 이어져 있는지
	return v12 <= 0 && v34 <= 0; // 세 점이 일직선인데 두 점 사이에 있거나 / 두 선분이 교차하는지
}

private boolean isIntersect(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) {
	int d123 = ccw(x1, y1, x2, y2, x3, y3), d124 = ccw(x1, y1, x2, y2, x4, y4),
	    d341 = ccw(x3, y3, x4, y4, x1, y1), d342 = ccw(x3, y3, x4, y4, x2, y2); // direction
	int v12 = d123 * d124, v34 = d341 * d342;
	if (v12 == 0 && v34 == 0) {
		if (d123 == 0 && d124 == 0 && d341 == 0 && d342 == 0) { // 네 점이 일직선
			int pA, pB, pC, pD;
			if (x1 == x2) { pA = Math.min(y1, y2); pB = Math.max(y1, y2); }
			else		   { pA = Math.min(x1, x2); pB = Math.max(x1, x2); }
			if (x3 == x4) { pC = Math.min(y3, y4); pD = Math.max(y3, y4); }
			else	 	   { pC = Math.min(x3, x4); pD = Math.max(x3, x4); }
			if (pC < pB && pA < pD)	return true; // 두 선분이 서로 겹침 (무수히 많은 점과 만남)
			if (pC == pB || pA == pD)	return true; // 두 선분 각각의 한 점이 같아 이어짐 (한 점에서 만남)
			return false; // 만나지 않음
			//return pC <= pB && pA <= pD; // 두 선분이 겹치거나 이어지는지
		}
		return true; // 세 점이 일직선인데 그 중 두 점이 겹침
	}
	return v12 <= 0 && v34 <= 0; // 세 점이 일직선인데 두 점 사이에 있거나 / 두 선분이 서로 교차하는지
}

 

◇  참고

  https://www.acmicpc.net/blog/view/27

 

◇  예제

  https://hyunjiishailey.tistory.com/476 

[백준(Baekjoon)][자바(java)] 11758 : CCW / 기하

  https://hyunjiishailey.tistory.com/481

[백준(Baekjoon)][자바(java)] 20149 : 선분 교차 3 / 기하