두 선의 교차점 구하기

이 글은 두 선분의 교차점을 구하는 알고리즘이 작업에 필요해서 작성해둔 글이다. 참고로, 예전에 두선분의 교차점을 구하는 것 자체가 쉬울 것으로 생각하고 흔히 생각하는 기울기, y 절편을 이용하여 접근하려고 하였다. 이는 상당히 비효율적 방법이였고 조금 더 효율적인 방법으로 접근하였다.

먼저 직선의 방정식으로써, 기울기와 절편으로 나타내지 말고, t 매개변수를 이용해 나타내면 다음과 같다.


P1과 P2는 직선의 시작점과 끝점을 나타내며, t의 범위는 0에서 1까지이다. (P1, P2에서 1, 2는 아래첨자로 생각하기 바란다)

선의 식을 알았으니, 이제 두선의 교점을 구해보는 것으로 응용해보자. 먼저 아래 그림을 보자.


Line1은 P1과 P2로 이루어져 있으며, Line2는 P3와 P4로 이루어져 있다. 두개의 라인을 식으로 표현해보면 다음과 같다.


이미 알겠지만, t와 s는 0에서 1부터의 값이며, 두선의 교점은 두선의 공통된 값이므로 P(t)와 P(s)는 같으므로 위의 2개의 식은 아래의 1개의 식으로 나타낼 수 있다.


다시 위의 식을 x, y로 분리해보면 아래와 같은 두개의 식들로 분리된다.


위의 식을 t와 s에 대해서 정리를 해보면 다음과 같다.


즉, 위의 t와 s는 두선이 서로 만날때의 값이므로, 최종적으로 두선의 교점은 다음과 같이 나타낼 수 있다.


위의 x, y가 우리가 구하고자하는 두 직선의 교점이다.

마지막으로 t와 s에 대해 정리해 보도록 하자.

s와 t의 값이 0과 1 사이를 벗어나는 경우, 두 선은 교차하지 않는다고 판정해야 한다. 그리고 s와 t를 구하는 공식에서 분모가 0인 경우 두 선은 평행하다는 의미이므로 교점은 존재하지 않다. 분모와 분자 모두 0인 경우 두 선은 동일한 선이다.

아래의 코드는 위의 설명을 토대로 작성하였다.

“두 선의 교차점 구하기”에 대한 23개의 댓글

  1. 코드 정말 잘 이용하고 있습니다.
    한가지 문제점이 있는데,
    선분이 다른 선분을 포함하는 경우( 기울기가 같은 경우에만 발생 )
    위의 코드는 false를 리턴하도록 돼있더군요.
    이 부분에 약간의 보완이 필요할 것 같습니다.

  2. 네, ^^ 그렇군요. 위의 함수는 교차점을 구하는 함수인지라.. 교차점이 무한 개인 경우는 교차점 없는 것으로 판단하기 때문에 false를 리턴합니다. 말씀하신 경우와 같은 문제점이나 오해가 분명이 존재할거라 판단되네요. 좋은 댓글 감사합니다~

  3. t,s는 단지 t와 s만을 좌항에 남기고 정리한 것 뿐이랍니다. 먼저 가장 처음에 언급된 직선의 방정식을 이해하고 받아들이시는게 관건인듯합니다. 가장 잘 나온 책은 고등수학 학습서인것같습니다. 댓글 감사합니다~ ^^

  4. 좋은 글 감사드립니다.
    출처를 밝히고 저의 개인 블로그에 제가 필요한 대로 수정한 내용으로 올렸는데(나중에 제가 참고할 요량으로), 양해 부탁드립니다.

  5. 이미 알겠지만, t와 s는 0에서 1부터의 값이며, 두선의 교점은 두선의 공통된 값이므로 P(t)와 P(s)는 같으므로 위의 2개의 식은 아래의 1개의 식으로 나타낼 수 있다.
    까지는 이해햇는데

    다시 위의 식을 x, y로 분리해보면 아래와 같은 두개의 식들로 분리된다. 부터
    위의 식을 t와 s에 대해서 정리를 해보면 다음과 같다. 까지가 이해가 안되네요

    x y로 어떻게 분리하길래.. 정말 너무 궁금합니다 어제부터 오늘 하루젱일 보면서 공부중이에요

  6. 아 다시 위의 식을 x, y로 분리해보면 아래와 같은 두개의 식들로 분리된다. 는 어느정도 이해했는데

    위의 식을 t와 s에 대해서 정리를 해보면 다음과 같다.
    이게 이해가 안되네요 t s로 정리 헠헠 진짜 빡세다

  7. 아 다 알았어요..
    와 진짜 감탄스럽습니다 와.. 진짜 대단하다
    어떻게 이런 생각을 수학 천재심
    잘배워갑니다 고맙습니다

  8. 수학을 공부하는거랑 수학을 프로그래밍으로 짜는거랑 전혀 다른것 같아요
    아무리 수학공부를해도 이런걸 짤수가 없는데
    도대체 어떻게해야 이런 경지에 이르나요?

  9. 이미 알겠지만, t와 s는 0에서 1부터의 값이며, 두선의 교점은 두선의 공통된 값이므로 P(t)와 P(s)는 같으므로 위의 2개의 식은 아래의 1개의 식으로 나타낼 수 있다.

    다음의 공식에서 오른쪽이 P3,P4인데 P1,P2로 되어있는거 같네요

    1. 안녕하세요, 김형준입니다.
      말씀하신 부분이 맞습니다.
      내용 중 오타가 있네요.
      글 내용을 쫓다보면 오타임을 알 수 있으니 다행입니다..
      오타 알려주셔서 감사합니다.

    1. 선분의 정의 시에 2개의 좌표를 통해 정의되는데..
      이 2개의 좌표계 선분의 시작점과 끝점입니다.
      시작점은 t가 0일때, 끝점은 t=1일때입니다.
      결론을 통해 t의 범위를 유추할수있는 방법이고..
      선분을 구성하는 t의 범위 제한은 사실 없습니다.

답글 남기기

이메일은 공개되지 않습니다. 필수 입력창은 * 로 표시되어 있습니다