[알고리즘] 직선의 교차점

---

두 직선의 교차점은 두 식의 일치점을 찾고, 여러 직선으로 도형의 꼭짓점을 구할 때 계산을 필요로 합니다.

직선의 교차점을 구하는 몇 가지 방법에 대해 알아보겠습니다.

---

직선의 방정식을 알 때 사용하는 방법

\(x+y-3=0 \cdots ① \)

\(x+2y-4=0 \cdots ② \)

①, ②의 교차점은 (2, 1)입니다. 이렇게 두 직선의 방정식을 알고 있을 때, 교차점을 계산하는 방법입니다.

1. 연립방정식을 활용한 교차점 구하기

두 식을 연립방정식으로 풀이합니다. 연립방정식의 해를 구하는 방법으로는 역행렬을 사용합니다.

 

\(ax+by+m=0 \cdots ① \)

\(cx+dy+n=0 \cdots ② \)

 

이 식 ①, ②을 행렬로 나타내면 아래와 같습니다.

$$\begin{pmatrix}a & b\\c & d\end{pmatrix} \begin{pmatrix}x \\y \end{pmatrix} + \begin{pmatrix}m \\n \end{pmatrix}=\begin{pmatrix}0 \\0 \end{pmatrix}$$

그리고 역행렬을 이용하여 이 식을 \(x, y\)에 대한 식으로 정리하면 교차점을 구할 수 있습니다.

단, 경우에 따라서 교차점이 단 하나가 아닐 수 있음을 확인하여야 합니다.

 

1. 두 직선의 방정식이 같고 범위가 겹치는 부분이 있을 때, 무수히 해가 많다. (교차점이 무수히 많다)
2. 두 직선이 평행할 때, 해가 없다. (교차점이 없다)

위 2가지 상황을 고려해야 합니다. 

 

역행렬을 이용하여 정리하면 다음과 같이 표현할 수 있습니다.

$$\begin{pmatrix}x\\y\end{pmatrix}=\frac{1}{ad-bc}\begin{pmatrix}-d & c\\b & -a\end{pmatrix}\begin{pmatrix}m \\n \end{pmatrix}({\sf cond.} \; ad-bc \neq 0)$$

\(ad-bc = 0\)일 때는 위의 특수상황 1, 2 중 하나에 해당하므로 단 하나의 교차점을 찾을 수 없습니다.

 

이 행렬을 바탕으로 \(x, y\)에 대해서 식을 정리하면,

$$ \begin{aligned}&x = \frac{nb-md}{ad-bc} \\ &y = \frac{mc-na}{ad-bc}\end{aligned}  ({\sf cond.} \; ad-bc \neq 0) $$

이므로 그대로 코드를 구성하면 됩니다.

double* cross_p1(double exp1[3], double exp2[3]) {
	// exp 배열에 2, 3, 4가 들어있다면, 식 2x + 3y + 4 = 0 에 해당합니다.
	double* coord = new double[2];
	double denom = exp1[0] * exp2[1] - exp1[1] * exp2[0];
	if (denom == 0) {
		// 해가 무수히 많거나 없다.
		coord[0] = inf; // x
		coord[1] = inf; // y
		return coord;
	}
	coord[0] = (exp2[2] * exp1[1] - exp1[2] * exp2[1]) / denom;
	coord[1] = (exp1[2] * exp2[0] - exp2[2] * exp1[0]) / denom;
	if (coord[0] == 0) coord[0] = 0; // double 형은 -0값을 가지기도 합니다.
	if (coord[1] == 0) coord[1] = 0; // 따라서, -0을 0으로 변환해줍니다.
	return coord;
}

방정식을 위의 일반형이 아닌 표준형으로 나타내면 아래와 같습니다.

$$\begin{aligned} y=m_1 x+b_2  \\  y=m_2 x+b_2  \end{aligned}$$

이렇게 표현된 경우에는 x와 y를 아래와 같이 구할 수 있습니다.

$$ \begin{aligned}&x = \frac{b_2-b_1}{m_1-m_2} \\ &y = \frac{m_1b_2-m_2b_1}{m_1-m_2}\end{aligned}  ({\sf cond.} \; m_1-m_2 \neq 0) $$

이때, \(m_1-m_2 = 0\)이라면, 직선이 겹치거나 만나지 않는 경우에 해당합니다.

 

---

두 직선 쌍의 끝점이 주어졌을 때 사용하는 방법

점(0, 3)과 점(3,0)이 이루는 직선과 점(0, 2)과 점(4, 0)이 이루는 직선의 교차점은 (2, 1)입니다. 이렇게 점 2개가 이루는 직선쌍이 주어진 경우, 교차점을 구하는 방법입니다.

1. 함수를 구하여 교차점 구하기

주어진 끝점으로부터 함수를 구할 수 있습니다. 교차점이 존재하는지 여부에 대해서는 CCW 알고리즘을 찾아보시길 바랍니다. 편의상 두 직선이 교차한다고 가정하고 계산해보겠습니다.

 

4개의 점(P), \( P_1(x_1, y_1), P_2(x_2, y_2), P_3(x_3, y_3), P_4(x_4, y_4) \)가 주어졌을 때, \(P_1, P_2\)로 이루어진 직선을 \(L_1\), 그리고 \(P_3, P_3\)로 이루어진 직선을 \(L_2\)으로 정합니다.

 

그러면, 각 직선의 끝점으로부터 기울기와 y절편을 구해 직선의 방정식을 계산합니다.

$$ \begin{aligned} &y=m_1x+(y_1-m_1x_1)=\frac{y_2-y_1}{x_2-x_1}x+(y_1-\frac{y_2-y_1}{x_2-x_1}x_1) \; \cdots \; L_1 \\ & y=m_2x+(y_3-m_2x_3)=\frac{y_4-y_3}{x_4-x_3}x+(y_3-\frac{y_4-y_3}{x_4-x_3}x_3) \; \cdots \; L_2 \end{aligned}$$

그리고 이 식으로부터 위의 표준형에서의 x, y 식에 대입하면 아래와 같이 x와 y를 얻을 수 있습니다.

$$ \begin{aligned}&x = \frac{(x_1y_2-y_1x_2)(x_4-x_3)-(x_3y_4-y_3x_4)(x_2-x_1)}{(y_2-y_1)(x_4-x_3)-(y_4-y_3)(x_2-x_1)} \\ &y = \frac{(x_1y_2-y_1x_2)(y_4-y_3)-(x_3y_4-y_3x_4)(y_2-y_1)}{(y_2-y_1)(x_4-x_3)-(y_4-y_3)(x_2-x_1)} \end{aligned} ({\sf cond.} \; (y_2-y_1)(x_4-x_3)-(y_4-y_3)(x_2-x_1) \neq 0) $$

double* cross_p2(double P1[2], double P2[2], double P3[2], double P4[2]) {
	// P1 배열에 1, 2가 들어있다면, (1, 2) 좌표에 해당합니다.
	double* coord = new double[2];
	double denom = (P2[1] - P1[1]) * (P4[0] - P3[0]) - (P4[1] - P3[1]) * (P2[0] - P1[0]);
	if (denom == 0) {
		// 해가 무수히 많거나 없다.
		coord[0] = inf; // x
		coord[1] = inf; // y
		return coord;
	}
	coord[0] = ((P1[0] * P2[1] - P1[1] * P2[0]) * (P4[0] - P3[0]) - (P3[0] * P4[1] - P3[1] * P4[0]) * (P2[0] - P1[0])) / denom;
	coord[1] = ((P1[0] * P2[1] - P1[1] * P2[0]) * (P4[1] - P3[1]) - (P3[0] * P4[1] - P3[1] * P4[0]) * (P2[1] - P1[1])) / denom;
	if (coord[0] == 0) coord[0] = 0; // double 형은 -0값을 가지기도 합니다.
	if (coord[1] == 0) coord[1] = 0; // 따라서, -0을 0으로 변환해줍니다.
	return coord;
}

단, 두 좌표가 직선이 아닌 점을 만드는 경우에는 예외로 계산해주어야 합니다.

위 코드에는 범위를 계산하는 코드는 포함되어 있지 않으며, 직선으로부터 함수를 구하여 교차점을 구하는 방법입니다.

---

실행

int main() {
	double exp1[3] = { 1, 1, -3 };
	double exp2[3] = { 1, 2, -4 };
	double* res1 = cross_p1(exp1, exp2);
	cout << res1[0] << ' ' << res1[1] << '\n';

	double P1[2] = { 0,3 };
	double P2[2] = { 3,0 };
	double P3[2] = { 0,2 };
	double P4[2] = { 4,0 };
	double* res2 = cross_p2(P1, P2, P3, P4);
	cout << res2[0] << ' ' << res2[1] << '\n';
}

결과