2차원 평면 위에서 두 직선이 주어졌을 때, 이 두 직선이 만나는 지점인 교차점(Intersection Point)을 구하는 방법과 C++ 구현 코드를 소개합니다.
문제 정의
직선 AB를 구성하는 두 점 A와 B, 그리고 직선 PQ를 구성하는 두 점 P와 Q가 주어졌을 때, 두 직선의 교차점을 찾는 것이 목표입니다.
참고: 모든 좌표는 X축과 Y축으로 이루어진 2차원 평면 위의 점으로 주어집니다.
예를 들어 A(a1, a2), B(b1, b2)와 C(c1, c2), D(d1, d2)가 각각 서로 다른 두 직선을 형성하고 있으며, P(p1, p2)가 바로 두 직선의 교차점에 해당합니다.
교차점을 구하는 원리
두 직선의 교차점은 연립방정식을 풀어서 구할 수 있습니다. 먼저 각 직선을 일반형 방정식으로 표현해 보겠습니다.
좌표 (a1, a2), (b1, b2), (c1, c2), (d1, d2)를 이용하여 다음을 계산합니다: A1 = b2 - a2 B1 = a1 - b1 C1 = (A1 * a1) + (B1 * a2) A2 = d2 - c2 B2 = c1 - d1 C2 = (A2 * c1) + (B2 * c2) 두 직선은 다음과 같이 표현됩니다: 1. A1x + B1y = C1 2. A2x + B2y = C2 교차점을 구하려면 이 두 방정식을 연립하여 풀어야 합니다. 식 1에 B2를 곱하고 식 2에 B1을 곱하면: A1B2x + B1B2y = C1B2 A2B1x + B2B1y = C2B1 두 식을 빼면 다음과 같습니다: (A1B2 - A2B1)x = C1B2 - C2B1
이렇게 하면 x값을 구할 수 있고, 같은 방법으로 y값도 구할 수 있습니다. 최종적으로 x가 p1, y가 p2가 되어 교차점 P(p1, p2)를 얻게 됩니다.
주의: 위 공식은 무한히 뻗어나가는 '직선'의 교차점을 구하는 것입니다. 만약 유한한 길이의 '선분'이 주어진 경우라면, 계산된 교차점이 실제로 선분 위에 존재하는지 반드시 다음 조건으로 검증해야 합니다.
- min(x1, x2) <= x <= max(x1, x2)
- min(y1, y2) <= y <= max(y1, y2)
문제 해결 접근 방법
- 네 점의 좌표 값을 입력받습니다.
- 행렬식(determinant)을 계산합니다: det = a * b1 - a1 * b
- 행렬식이 0이면 두 직선은 평행하므로 교차점이 없습니다.
- 행렬식이 0이 아니라면 x = (b1*c - b*c1)/det, y = (a*c1 - a1*c)/det로 교차점을 계산합니다.
- 결과를 반환하고 출력합니다.
알고리즘
시작
Step 1 -> x, y 좌표를 출력하는 함수 선언
void display(mk_pair par)
par.first와 par.second 출력
Step 2 -> 교차점을 계산하는 함수 선언
mk_pair intersection(mk_pair A, mk_pair B, mk_pair C, mk_pair D)
double a = B.second - A.second 선언
double b = A.first - B.first 선언
double c = a*(A.first) + b*(A.second) 선언
double a1 = D.second - C.second 선언
double b1 = C.first - D.first 선언
double c1 = a1*(C.first) + b1*(C.second) 선언
double det = a*b1 - a1*b 선언
IF (det == 0)
return make_pair(FLT_MAX, FLT_MAX)
End
Else
double x = (b1*c - b*c1)/det 선언
double y = (a*c1 - a1*c)/det 선언
return make_pair(x, y)
End
Step 3 -> main() 함수에서
mk_pair q = make_pair(2, 1) 등의 점들을 선언하고 intersection 호출
IF (inter.first == FLT_MAX AND inter.second == FLT_MAX)
"두 직선은 평행합니다" 출력
End
Else
display(inter) 호출
End
종료C++ 전체 구현 코드
#include <bits/stdc++.h>
using namespace std;
#define mk_pair pair<double, double>
// x, y 좌표 출력 함수
void display(mk_pair par) {
cout << "(" << par.first << ", " << par.second << ")" << endl;
}
// 두 직선의 교차점 계산 함수
mk_pair intersection(mk_pair A, mk_pair B, mk_pair C, mk_pair D) {
// 직선 AB를 a1x + b1y = c1 형태로 표현
double a = B.second - A.second;
double b = A.first - B.first;
double c = a*(A.first) + b*(A.second);
// 직선 CD를 a2x + b2y = c2 형태로 표현
double a1 = D.second - C.second;
double b1 = C.first - D.first;
double c1 = a1*(C.first)+ b1*(C.second);
double det = a*b1 - a1*b;
if (det == 0) {
// 행렬식이 0이면 평행
return make_pair(FLT_MAX, FLT_MAX);
} else {
double x = (b1*c - b*c1)/det;
double y = (a*c1 - a1*c)/det;
return make_pair(x, y);
}
}
int main() {
mk_pair q = make_pair(2, 1);
mk_pair r = make_pair(2, 7);
mk_pair s = make_pair(4, 4);
mk_pair t = make_pair(6, 4);
mk_pair inter = intersection(q, r, s, t);
if (inter.first == FLT_MAX && inter.second==FLT_MAX) {
cout << "주어진 두 직선 AB와 CD는 평행합니다.\n";
} else {
cout << "주어진 두 직선 AB와 CD의 교차점은: ";
display(inter);
}
return 0;
}실행 결과
주어진 두 직선 AB와 CD의 교차점은: (2, 4)
코드 설명
위 코드는 크게 세 부분으로 나뉩니다. 첫째, display() 함수는 계산된 교차점 좌표를 화면에 출력하는 역할을 합니다. 둘째, intersection() 함수는 네 개의 점을 받아 두 직선의 방정식 계수를 구한 뒤, 행렬식(det)을 통해 평행 여부를 판단하고 교차점을 계산합니다. 셋째, main() 함수에서는 예제 좌표를 설정하고 결과를 확인합니다.
행렬식이 0이라는 것은 두 직선의 기울기가 같다는 의미이며, 이 경우 두 직선은 평행하거나 일치하므로 고유한 교차점이 존재하지 않습니다. 코드에서는 이런 경우 FLT_MAX를 반환하여 평행함을 알립니다.