[C++] 두 선분의 교차 여부 판단 방법

이번에는 두 선분이 교차하는지를 판단하는 방법에 대해 알아보도록 하겠습니다. 외적(cross product) 두 선분의 교차를 판단하기 위해서는 약간의 수학 기본이 필요하여 외적에 대해 간략히 알아보겠습니다.

두 벡터를 외적하면 두 벡터에 수직인 벡터를 구할 수 있습니다. 이는 오른손법칙에 의해 방향이 결정되는데, 아래와 같습니다.

출처: https://assortrock.com/24 즉 연산 순서에 따라 외적 값이 양수 또는 음수가 나올 수 있다는 의미 입니다. 그럼 만약 두 벡터가 평행한 경우에는 수직 벡터는 0이 나오게 됩니다.

수식을 간단히 살펴보면 아래와 같이 나타낼 수 있습니다. CCW(Conter Clock Wise) 알고리즘 CCW는 "외적을 이용하여 세 점의 방향 관계를 구하는 알고리즘"이라고 정의할 수 있습니다.

다시 말하면 CCW를 이용하면 아래와 같이 세 점이 주어졌을 때 이 세점이 시계 방향의 관계인지 반시계 방향의 관계인지 평행 관계인지를 알아낼 수 있습니다...

요청 처리 중입니다...

[C++] 두 선분의 교차 여부 판단 방법 - CCW를 이용한 방법

등록된 다른 글