[Algorithm] 선분교차(Line-segment intersection) 판정 알고리즘

• Line-segment intersection 판별 알고리즘의 필요성Line-segment의 교차 판정은 PS에서 흔히 다뤄지는 문제이다. 예컨대 네 점이 주어졌다고 하자. 이 때 다음과 같은 두 선분을 생각할 수 있다.이때 두 선분의 교차 관계를 판단하는 가장 직관적인 방법은 역시 slope를 구해서 일차 함수로 표현한 뒤 교점을 구하여 범위를 인식하는 방법이다.위의 두 line-segment의 intersection을 일차 함수를 이용하여 파악해 보자.위와 같은 두 선형 함수를 만들 수 있고, 두 함수의 교점을 쉽게 구할 수 있다. 구한 교점에 대하여 x값과 y값의 범위를 계산하면 선분의 교차 관계를 매우 직관적으로 얻을 수 있다.다만 이 방법엔 문제가 있다. 다음 문제들을 떠올릴 수 있겠다.• ..