[Geometry] 두 선분의 교점 및 교차 여부

자율주행 연구를 하다 보면 기하학적 문제를 해결해야 하는 경우가 종종 있습니다. 그중 하나가 두 선분의 관계입니다. 두 선분의 교점, 교차 여부를 확인하는 방법에 대해 알아보겠습니다.

 

 

1. 직선의 방정식

두 점이 주어졌을 때, 직선의 방정식을 x가 아닌 두 점에 대한 거리 비율 t로 표현할 수 있습니다.

 

2. 교점 구하기

두 직선의 교점을 찾기 위해 위 두 식을 연립하면 아래와 같이 나타낼 수 있습니다.

이를 풀면 다음과 같은 식이 유도됩니다:

여기서 구한 t를 P(t) 식에 대입하면 교점 Q의 좌표를 찾을 수 있습니다. 

 

 

3. 교차 여부 확인

교차 여부는 수평 여부 확인과 내분 확인 2가지 과정으로 구성됩니다. 

 

3-1) 수평 여부 확인

두 직선이 수평인 경우 교차하지 않습니다. 수평 여부는 외적을 통해 확인할 수 있으며, 수평인 경우 두 벡터의 외적의 크기가 0이 됩니다.

이 값이 t의 분모와 동일합니다. 따라서 이 값이 0일 경우 3-2)로 가지 않도록 예외 처리를 해줘야 합니다.

 

3-2) 내분 확인

위에서 유도한 식으로 t와 s를 계산합니다. t, s가 모두 0~1 사이 범위에 있다면 두 선분은 교차하는 겁니다.

 

 

 

def calculate_intersection(p1, p2, q1, q2):
    """
    두 선분의 교차 여부와 교점을 계산합니다.

    Parameters:
        p1, p2: 선분 1의 시작점과 끝점 (x1, y1), (x2, y2)
        q1, q2: 선분 2의 시작점과 끝점 (x3, y3), (x4, y4)

    Returns:
        (bool, (float, float) or None): 교차 여부와 교점 좌표
    """
    x1, y1 = p1
    x2, y2 = p2
    x3, y3 = q1
    x4, y4 = q2

    # 선분 방향 벡터 계산
    denominator = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4)

    if abs(denominator) < 1e-6:  # 두 선분이 평행함
        return False, None

    # t와 s 계산
    t = ((x1 - x3) * (y3 - y4) - (y1 - y3) * (x3 - x4)) / denominator
    s = ((x1 - x3) * (y1 - y2) - (y1 - y3) * (x1 - x2)) / denominator

    # 교차 여부 확인
    if 0 <= t <= 1 and 0 <= s <= 1:
        # 교점 계산
        intersection_x = x1 + t * (x2 - x1)
        intersection_y = y1 + t * (y2 - y1)
        return True, (intersection_x, intersection_y)

    return False, None  # 교차하지 않음



# 예제 사용
p1 = (1, 1)
p2 = (4, 4)
q1 = (1, 4)
q2 = (4, 1)

is_intersect, intersection = calculate_intersection(p1, p2, q1, q2)
print(f"Do the segments intersect? {is_intersect}")
if is_intersect:
    print(f"Intersection point: {intersection}")

import matplotlib.pyplot as plt
plt.figure()
plt.plot([p1[0],p2[0]],[p1[1],p2[1]])
plt.plot([q1[0],q2[0]],[q1[1],q2[1]])
plt.show()