[기하] 두 선분 교차 (Intersection)

주어진 선분 AB, CD 가 서로 교차하는지 확인해보자

 

꺾은선 ABC 와 ABD 가 서로 다른 방향 ( 시계 와 반시계 ) 이며

 

CDA 와 CDB 가 서로 다른 방향일때 두 선분은 교차한다고 말할 수 있다.

 

이 때 꺾은선의 방향을 알려주는 함수를 정의하자.

 

함수 Direction 은 시계방향일 때  1, 반시계일 때 -1, 한 직선위에 세 점이 존재할 때 0 이라고 한다면

 

교차하기 위해서는 아래 식을 만족해야한다.

 

이 때 Direction 함수를 코드로 나타내 보자

 

int direction(struct point A, struct point B, struct point C) {
	int dxAB, dxAC, dyAB, dyAC, Dir;
	dxAB = B.x - A.x; dxAC = C.x - A.x;
	dyAB = B.y - A.y; dyAC = C.y - A.y;

	if (dxAB * dyAC < dyAB * dxAC) Dir = -1;
	if (dxAB * dyAC > dyAB * dxAC) Dir = 1;
	if (dxAB * dyAC == dyAB * dxAC) {
		if (dxAB == 0 && dyAB == 0) Dir = 0;
		if ((dxAB * dxAC < 0) || (dyAB * dyAC < 0)) Dir = 1;
		else if ((dxAB * dxAB + dyAB * dyAB) >= (dxAC * dxAC + dyAC * dyAC)) Dir = 0;
		else Dir = -1;

	}
	return Dir;
}

 

이 때 A, B, C 가 일직선 상에 있을 때 어떤 점이 중점이 되는지 파악해 줘야한다.

 

이 부분을 코드로 다시 나타내보면

 

if (dxAB * dyAC == dyAB * dxAC) {// AC, AB 기울기가 동일한 경우
		if (dxAB == 0 && dyAB == 0) Dir = 0; // A,B,C 중 동일점이 존재하는 경우
		if ((dxAB * dxAC < 0) || (dyAB * dyAC < 0)) Dir = -1; // AB 와 AC가 반대방향 확인
        // 맞으면 A 가 사이점
		else if ((dxAB * dxAB + dyAB * dyAB) >= (dxAC * dxAC + dyAC * dyAC)) Dir = 0;
        // AB, AC 같은방향이면서 |AB| >= |AC| 인지 확인
        // 맞으면 C 가 사이점
		else Dir = 1; // B가 사이점
	}

 

위의 Direction 함수를 이용해 Intersection 함수를 만들자

 

int intersection (strcut line AB, struct line CD){
	int LineCrossing;
    if((Direction(AB.A,AB.B,CD.C) * Direction(AB.A,AB.B,CD.D) <= 0) &&
    	(Direction(CD.C,CD.D,AB.A) * Direction(CD.C,CD.D,AB.B) <= 0))
        LineCrossing = true;
    else LineCrossing = false;
    return LineCrossing;
}