기하[2] - 2차원 선분 교차 판별

  두 선분이 있을 때 두 선분이 교차하는지는 한 선분을 기준으로 나머지 선분의 끝 각 두 점에 대해서 세 점을 만든 뒤 이 세 점이 이루는 두 선분이 평행 또는 시계, 반시계인지를 판별하여 알 수 있다.

  기준 선분과 다른 선분의 점과 관계를 그림으로 나타내면 아래와 같다.

교차 선분	비교차 선분
교차 하는 경우	교차하지 않는 경우

  보다시피 교차하는 경우엔 시계 방향이 하나, 반시계 방향이 하나 존재하지만 교차하지 않는 경우엔 둘 다 시계 방향이거나 둘 다 반시계 방향이거나다. 따라서 판별할 때 세 점에 대해서 방향성을 조사할 때 시계 방향과 반시계 방향 하나씩 존재함을 확인하면 된다.

  하지만 평행일 경우엔 각별한 주의가 필요하다. 한 선분이 다른 선분을 포함할 수도, 다른 선분의 한 점만 포함할 수도 있기 때문에 기준을 두 선분 모두 둬야한다. 기준 선분에 다른 선분의 점이 들어있는지 판별하여 확인한다.

평행인데 교차하는 경우

평행하는데 교차하지 않는 경우

 

  교차 판별을 코드로 작성하면 아래와 같다.

struct pt { double x, y; };
// check overflow
int orient(pt& p1, pt& p2, pt& p3) {
	double d = (p2.y - p1.y) * (p3.x - p2.x) - (p3.y - p2.y) * (p2.x - p1.x);
	return d < 0 ? -1 : (d ? 1 : 0);
}

// 두 점 s,e 가 잇는 선분에 p점이 있는지 확인하는 함수
bool in(pt& s, pt& e, pt& p) {
	if (s.x != e.x && s.y != e.y) {
		double d = (e.y - s.y) / ((double)e.x - s.x), y;
		y = d * (p.x - s.x) + s.y;
		return s.x <= p.x && p.x <= e.x && y == p.y;
	}
	if (s.x == e.x)
		return p.x == s.x && s.y <= p.y && p.y <= e.y;
	else return p.y == s.y && s.x <= p.x && p.x <= e.x;
}

bool intersected(pt& s1, pt& e1, pt& s2, pt& e2) {
	bool can = 0;
	int d1 = orient(s1, e1, s2), d2 = orient(s1, e1, e2);
	if ((d1 != d2 && orient(s2, e2, s1) != orient(s2, e2, e1)))
		can = 1;
	else if (!d1 && !d2)
		can = in(s1, e1, s2) || in(s1, e1, e2) || in(s2, e2, s1) || in(s2, e2, e1);
	return can;
}