문제 설명
두 선분이 주어질 때, 이 두 선분이 교차하는지 여부를 판별하는 알고리즘을 구현하시오.
선분 A는 점 A1(x1, y1)와 점 A2(x2, y2)로 주어지며, 선분 B는 점 B1(x3, y3)와 점 B2(x4, y4)로 주어진다.
교차 여부는 선분이 서로 교차하는 경우, 선분의 끝점이 다른 선분의 안쪽에 위치하는 경우, 혹은 선분이 일직선 상에 위치하는 경우를 고려하여 판단한다.
예제 입력
A1: (1, 1)
A2: (4, 4)
B1: (1, 4)
B2: (4, 1)
예제 출력
교차함
문제 풀이 과정
이 문제를 해결하기 위해 우리는 몇 가지 지리적 개념과 수학적 계산을 활용할 것입니다.
선분 교차 여부를 판단하기 위해 우선 두 선분의 방향을 파악하고, 그에 따라 교차 여부를 결정하는 방법을 사용합니다.
1단계: 방향 계산
주어진 두 선분의 끝점들을 이용하여, 각 선분이 위치하는 방향을 계산합니다.
두 선분 A(A1, A2)와 B(B1, B2)가 있을 때, 우리는 다음과 같은 방법으로 방향을 계산할 수 있습니다:
def 방향(a1, a2, b1, b2):
# 방향 판단을 위한 함수
차 = (a2[0] - a1[0]) * (b1[1] - a1[1]) - (a2[1] - a1[1]) * (b1[0] - a1[0])
if 차 == 0:
return 0 # 같은 방향
return 1 if 차 > 0 else -1 # 왼쪽(+) 또는 오른쪽(-)
2단계: 교차 조건
두 선분이 서로 교차하는지 여부는 다음과 같은 조건에 따라 판단할 수 있습니다:
- 선분 A의 방향이 B1, B2에 대한 지점에서 일치하지 않으며, 선분 B의 방향이 A1, A2에 대한 지점에서 일치하지 않을 경우, 두 선분은 서로 교차합니다.
- 선분 A의 점들이 선분 B의 연장선에 존재할 경우, 즉 선의 끝점 중 하나가 다른 선의 내부에 포함되는 경우에도 교차으로 판단합니다.
- 모든 점이 동일한 직선 상에 존재하면서 끝점이 서로 겹치는 경우, 즉 중복 발생시에는 교차로 간주합니다.
3단계: 구현
이제 이 조건을 바탕으로 자바에서 구현해 보겠습니다.
public class LineIntersection {
static class Point {
int x, y;
Point(int x, int y) { this.x = x; this.y = y; }
}
static int direction(Point a1, Point a2, Point b) {
int 차 = (a2.x - a1.x) * (b.y - a1.y) - (a2.y - a1.y) * (b.x - a1.x);
return (차 == 0) ? 0 : (차 > 0) ? 1 : -1;
}
static boolean isIntersect(Point a1, Point a2, Point b1, Point b2) {
int d1 = direction(a1, a2, b1);
int d2 = direction(a1, a2, b2);
int d3 = direction(b1, b2, a1);
int d4 = direction(b1, b2, a2);
// Cross case
if(d1 != d2 && d3 != d4) return true;
// Collinear case
if(d1 == 0 && onSegment(a1, a2, b1)) return true;
if(d2 == 0 && onSegment(a1, a2, b2)) return true;
if(d3 == 0 && onSegment(b1, b2, a1)) return true;
if(d4 == 0 && onSegment(b1, b2, a2)) return true;
return false;
}
static boolean onSegment(Point a, Point b, Point p) {
return (p.x <= Math.max(a.x, b.x) && p.x >= Math.min(a.x, b.x) &&
p.y <= Math.max(a.y, b.y) && p.y >= Math.min(a.y, b.y));
}
public static void main(String[] args) {
Point A1 = new Point(1, 1);
Point A2 = new Point(4, 4);
Point B1 = new Point(1, 4);
Point B2 = new Point(4, 1);
if (isIntersect(A1, A2, B1, B2)) {
System.out.println("교차함");
} else {
System.out.println("교차하지 않음");
}
}
}
위의 코드를 실행하면 두 선분 간의 교차 여부를 파악할 수 있습니다.
4단계: 테스트
다양한 테스트 케이스를 시도하여 올바른 코드 작동 여부를 확인합니다.
// Test Case 1
A1: (1, 1)
A2: (4, 4)
B1: (1, 4)
B2: (4, 1) // Output: 교차함
// Test Case 2
A1: (1, 1)
A2: (1, 3)
B1: (1, 2)
B2: (1, 4) // Output: 교차함
// Test Case 3
A1: (1, 1)
A2: (2, 2)
B1: (3, 3)
B2: (4, 4) // Output: 교차하지 않음
이처럼 다양한 사례를 통해 알고리즘이 잘 작동하는지 검증할 수 있습니다.
결론
이번 강좌를 통해 선분의 교차 여부를 판단하는 알고리즘을 구현하는 방법을 배웠습니다.
문제 해결을 위해 기하학적 사고와 코드 구현을 통해 교차 조건을 이해하고 적용하는 과정이었습니다.
이 지식은 다양한 응용 분야에서 사용되므로, 알고리즘과 자료구조에 대한 이해도를 높이는 데 큰 도움이 될 것입니다.
함께한 여러분들이 여러 문제를 풀고 더 나아가 기본기를 다지는 데에 이 강좌가 도움이 되기를 바랍니다.