[Algorithm] 선분교차(Line-segment intersection) 판정 알고리즘

! 본 글은 다크모드에서 수식이 제대로 나타나지 않습니다. 

 

• Line-segment intersection 판별 알고리즘의 필요성

Line-segment의 교차 판정은 PS에서 흔히 다뤄지는 문제이다. 예컨대 네 점

이 주어졌다고 하자. 이 때 다음과 같은 두 선분을 생각할 수 있다.

이때 두 선분의 교차 관계를 판단하는 가장 직관적인 방법은 역시 slope를 구해서 일차 함수로 표현한 뒤 교점을 구하여 범위를 인식하는 방법이다.

위의 두 line-segment의 intersection을 일차 함수를 이용하여 파악해 보자.

위와 같은 두 선형 함수를 만들 수 있고, 두 함수의 교점을 쉽게 구할 수 있다. 구한 교점에 대하여 x값과 y값의 범위를 계산하면 선분의 교차 관계를 매우 직관적으로 얻을 수 있다.

다만 이 방법엔 문제가 있다. 다음 문제들을 떠올릴 수 있겠다.

---

• 선형 함수의 교점을 이용한 선분 교차 판단 알고리즘의 문제

1. 기울기가 매우 크거나 기울기가 매우 작을 경우 자료형으로 표현이 불가능하다.

기울기가 매우 큰 경우를 생각해 보자. 수직에 근접하여 기울기가 long long int 자료형이 표현할 수 있는 값보다 커진다면, 표현하기가 곤란해질 것이다. 수직이 된다면 예외 처리로 뺴면 되겠지만, 수직에 수렴하는 무한히 큰 기울기는 사실상 프로그램 내에서 표현이 불가능하다.

 

또한, 기울기가 0에 수렴하는 매우 작은 숫자라면, 이 역시도 부동소수점으로 표현할 수 있는 범위를 벗어나 0으로 근사되어 정밀한 교차 판정이 불가능하다.

 

2. 부동소수점 표현으로 인한 round-off error가 발생한다.

1번의 기울기가 0에 수렴하는 경우에 발생하는 문제와 같은 맥락이다. 대부분의 slope는 정수형으로 표현이 되지 않아 실수형으로 표현해야 하는데, 부동소수점을 이용하여 실수형을 표현하는 프로그램의 특성 상 완전히 같은 값의 slope를 표현하는 것이 아니라 매우 근사한 값으로 대신 표현하게 된다.

 

일반적인 프로그램에서는 이러한 점이 큰 불편을 주지는 않지만, 매우 정밀하게 교점의 위치를 판단해야 하는 경우에는 오답을 반환할 수 밖에 없다.

 

3. division을 사용하는 경우 computationally expensive하다.

컴퓨터에서 division 연산은 multiplication 연산보다 훨씬 느리다. 따라서 division 연산이 수 차례 포함되는 이 방식은 compuationally expensive할 수 밖에 없다.

 

따라서 새로운 방법이 요구된다. polar angle을 이용한 방법을 비롯한 여러 방법이 있겠지만, 이번에 내가 다룰 것은 cross product를 이용한 line-segment intersection의 determination이다.

 

---

• Cross Product (벡터곱, 가위곱)

일반적으로 cross product라고 함은 외적으로 번역되곤 하는데, 이는 오해의 소지가 많다. 외적이라는 하나의 한글 단어에 outer product와 cross product 두 개의 개념이 대응되기 때문이다.

 

outer product는 두 벡터를 곱해 행렬을 만드는 연산이고, cross product는 3차원의 두 벡터를 곱해 법선벡터 방향을 갖는 새로운 벡터를 만드는 연산이다. 내가 사용할 것은 cross product이다.

다음과 같은 두 벡터를 정의해 보자.

이 두 벡터의 cross product 값은 다음과 같이 정의된다.

이때 theta는 두 벡터의 사잇각이고, n은 법선벡터를 의미하는데 정확한 방향은 오른손 법칙을 이용해 알 수 있다.

출처 :https://en.wikipedia.org/wiki/Right-hand_rule

법선벡터가 위와 같이 변하는 것은 theta가 단순한 사잇각이 아닌 p1벡터에서 p2벡터로 반시계방향으로 계산한 각도를 의미하고, 사잇각이 pi를 넘어갈 경우 sin은 음수 값을 갖기 때문이다. 위와 같이 법선벡터는 두 벡터 p1과 p2가 만드는 평면에 수직으로 통과하는 벡터를 의미한다.

---

• Cross product의 행렬식을 이용한 계산

cross product는 그 정의에 의하여 행렬식으로도 구할 수 있다. 원래 cross product는 3차원 벡터로 정의되지만, 2차원 벡터의 연산으로도 바꾸어 사용할 수 있다.

다음과 같은 두 벡터가 있다고 하자.

이 두 벡터의 크기는 다음과 같은 법선벡터 n

이 있다고 할때, 다음과 같이 법선방향 단위벡터의 성분들을 1행, p1을 2행, p3을 3행에 넣은 행렬식으로 계산할 수 있다.

이를 계산하면 다음과 같다.

이를 성분에 따라 정리하면 다음과 같은 벡터가 된다.

만약 p1과 p2가 2차원 벡터라면 z좌표의 값은 0이고, 법선벡터의 성분 또한 i=j=0이다. 따라서

이 되고, 평면에 수직한 방향으로의 성분만 남는다. 이 수직성분의 부호에 따라서 theta의 크기를 알 수 있다. 이는 사실 이차원 벡터의 determinant값과도 같다.

따라서 간단하게 이차원 벡터의 cross product만을 계산하여 theta의 크기를 알 수 있다.

---

• Cross product 값에 따른 위치관계

---

• Clockwise와 Counterclockwise

위에서 결론내린 방식으로 두 이차원 벡터의 cross product를 계산함으로써 두 번째 벡터가 첫 번째 벡터에 비해 clockwise에 있는지, counterclockwise에 있는지 알 수 있다. 이해를 돕기 위해 그림을 직접 그려보았다.

p와 같은 origin을 공유하는 임의의 벡터 p'이 있다고 했을 때, p'의 끝 지점에 따라서 위의 경계처럼 나뉘게 된다. 끝 지점에 핑크색 영역에 있다면 p'는 p에 대해 clockwise에 있는 것이고, 남색 영역에 있다면 counterclockwise에 있는 것이다. p'의 끝 지점이 하늘색 직선 위에 있다면 두 벡터는 colinear한 것이고, cross product의 값은 0이다.

그럼 모든 준비가 끝났으니 두 선분의 위치관계를 cross product를 이용하여 파악해 보자.

---

• Cross product를 이용한 두 선분의 교차 판별

먼저 처음과 같이, 평면 위에 두 개의 선분이 다음과 같이 있다고 가정하자.

이 선분의 양 끝 점은 다음과 같다.

이를 이용해 cross product의 값을 나타내는 변수인 d_n을 정의하자.

이 네 개의 값은 한 선분의 양 끝 점에서 다른 선분의 양 끝점을 종점으로 하는 두 벡터의 cross product라는 의미를 갖는다. 이 값을 이용하여 선분의 교차를 판정해 보자.

---

1. 두 선분이 교차(straddle)하는 경우

이와 같은 경우 d1과 d2의 부호가 다르고, d3와 d4의 부호가 다르게 된다. 교차하기 때문에 clockwise-counterclockwise 관계가 뒤바뀌기 때문이다.

따라서 다음과 같은 경우로 정리할 수 있다.

위 값이 true인 경우, 두 line-segment는 straddle한다.

---

2. 두 선분이 교차하지 않는 경우

이런 경우에는 d_3와 d_4의 부호는 다르지만 d_1과 d_2의 부호가 같다.

이 경우에는 d_1과 d_2의 부호가 같고, d_3와 d_4의 부호도 같다.

따라서 1의 조건이 성립하지 않는 경우 boundary condition을 제외하면 straddle한 경우가 아니라고 판단할 수 있다. 이 경우는 두 선분이 평행한 경우도 포함된다.

---

3. 세 점 이상이 한 직선 위에 있는 경우

이 경우 d_3의 값이 0이 된다. 네 값 중 하나의 d값이 0인 경우 한 직선 위에 세 개의 점이 위치하는 것이고, 네 개의 d값 모두 0인 경우 한 직선 위에 네 점 모두 위치하는 경우이다.

---

• 참고문헌

• Cormen, T. H., & Cormen, T. H. (2001). Introduction to algorithms. Cambridge, Mass: MIT Press.

---

• 관련 예제

BOJ에 관련 문제들이 많으므로 implementation된 예를 살펴보면 이해에 도움이 될 것이다.

---

BOJ 17386 : 선분 교차

https://www.acmicpc.net/problem/17386

17386번: 선분 교차 1

 

이 문제는 다음과 같이 해결할 수 있다 :

#include <iostream>
#include <algorithm>

using namespace std;

typedef struct {
    int x, y;
}Vector;

typedef long long int ll;

ll crossProduct(Vector a, Vector b) {
    return (((ll)a.x*b.y)-((ll)a.y*b.x));
}

int direction(Vector a, Vector b, Vector c) {
    Vector ca, cb;
    ca.x= a.x-c.x, ca.y= a.y-c.y;
    cb.x= b.x-c.x, cb.y= b.y-c.y;
    return (crossProduct(ca, cb)>0)? 1: -1;
}

bool lineSegIntersect(Vector* p) {
    if(direction(p[1],p[2],p[3])*direction(p[1],p[2],p[4]) < 0 && direction(p[3],p[4],p[1]) * direction(p[3],p[4],p[2]) <0) return true;
    return false;
}

int main( void ) {
    //freopen("/workspace/PS_Git/BOJ/17386/input.txt","r", stdin);
    Vector p[5];

    for(int i = 1; i <= 4; i++) scanf("%d %d", &p[i].x, &p[i].y);

    printf("%d", lineSegIntersect(p));
    return 0;

}

 

https://github.com/Jordano-Jackson/PS/blob/main/BOJ/17386/17386.cpp 에서도 이 코드를 확인할 수 있다.

GitHub - Jordano-Jackson/PS: Problem solving

 

---

BOJ 17387 : 선분 교차 2

https://www.acmicpc.net/problem/17387

17387번: 선분 교차 2

 

#include <iostream>
#include <algorithm>

using namespace std;

typedef struct {
	int x, y;
}Vector;

typedef long long int ll;

ll crossProduct(Vector a, Vector b) {
	return (((ll)a.x*b.y)-((ll)a.y*b.x));
}

int direction(Vector a, Vector b, Vector c) {
	Vector ca, cb;
	ll value;
	ca.x= a.x-c.x, ca.y= a.y-c.y;
	cb.x= b.x-c.x, cb.y= b.y-c.y;
	value = crossProduct(ca, cb);
	return (value >0)? 1 : (value<0? -1 : 0);
}

bool onSegment(Vector a, Vector b, Vector c) {
	if(c.x >= min(a.x, b.x) && c.x <= max(a.x,b.x) && c.y >= min(a.y,b.y) && c.y <= max(a.y,b.y)) return true;
	return false;
}

bool segmentIntersect(Vector* p) {
	int d1, d2, d3, d4;
	d1 = direction(p[3],p[4],p[1]);
	d2 = direction(p[3],p[4],p[2]);
	d3 = direction(p[1],p[2],p[3]);
	d4 = direction(p[1],p[2],p[4]);
	if(d1*d2<0 && d3*d4<0) return true;
	else if(d1==0 && onSegment(p[3],p[4],p[1])) return true;
	else if(d2==0 && onSegment(p[3],p[4],p[2])) return true;
	else if(d3==0 && onSegment(p[1],p[2],p[3])) return true;
	else if(d4==0 && onSegment(p[1],p[2],p[4])) return true;
	return false;
}

int main( void ) {
	//freopen("/workspace/PS_Git/BOJ/17386/input.txt","r", stdin);
	Vector p[5];
	
	for(int i = 1; i <= 4; i++) scanf("%d %d", &p[i].x, &p[i].y);
	
	printf("%d", segmentIntersect(p));
	return 0;
	
}

 

이 코드도 내 github에서 확인할 수 있다 : https://github.com/Jordano-Jackson/PS/blob/main/BOJ/17387/17387.cpp

GitHub - Jordano-Jackson/PS: Problem solving