(알고리즘) 기하파트-2

<교차와 거리, 면적>

*직선과 직선의 교차

x좌표에 대해 푼 뒤 방정식에 대입해 y좌표를 구하는 코드를 작성하거나 하면 수평선이나 수직선 같은 예외에 제대로 대응 할 수 없습니다.

직선의 교차를 작성할 수 있는 간단한 방법은 직선을 한 점과 방향벡터, 즉 a+p*b형태로 표현하는 것입니다.
a+p*b와 c+q*d의 교점을 구하기 위해서는 a+p*b=c+q*d방정식을 풀면 된다.

ax+p*bx=cx+q*dx
ay+p*by=cy+q*dy

연립방정식을 p에 대해 정리하면
p=(c-a)Xd/bXd

이 p를 a+p*b에 대입해 원하는 점을 구할 수 있다.

*선분과 선분의 교차

이 경우는 한 직선위에 두 선분의 판단에 유의해야 한다. 한 직선위에 두 선분이 있을 때, 이 선분들의 관계는 넷 중 하나이다.

1. 두 선분이 서로 겹치지 않음
2. 두 선분이 한 점에서 닿음
3. 두 선분이 서로 겹쳐짐
4. 한 선분이 다른 선분 안에 포함됨

lineIntersection()함수는 네 경우 모두 거짓을 반환하는데 (a)외의 경우에는 두 선분이 교차한다고 말할 수 있습니다. 문제의 특성상 이런 경우가 없다면 모르지만, 이 외의 겨우 이들을 꼭 고려해야한다.

*선분과 선분의교차: 교차점이 필요 없을 때

교차점을 구할 필요 없을 때 두 선분의 교차 여부를 확인하기만 할 거라면 보다 단순한 방법을 사용할 수 있다. 바로 ccw()를 사용하는 것이다.

교차하는 두 선분 ab와 cd가 있다. a입장에서 ㅂ면 c와 d중 한쪽은 b를 기준으로 시계방향에, 다른한쪽은 시계반대 방향에 있다. 반대로 c입장에서보면 a와 b중 한쪽은 d의 시계방향에, 다른한쪽은 시계 반대방향에 있어야 합니다. 이 두 조건과 선분의 교차 여부는 동치임을 알 수 있다.
결국 ccw(a,b,c)와 ccw(a,b,d)중 하나는 양수, 하나는 음수가 되어야 하므로 이들의 곱은 항상 음수여야한다.

두 선분이 한 직선위에 있는 경우를 어떻게 예외 처리하는지를 유의해보자. 이때도 벡터의 비교 연산자가 유용하게 사용된다.
비교연산자에 의해 a<b, c<d인 네 점 a,b,c,d가 일직선 상에 있을 경우 두 선분이 겹치지 않기 위해서는 b<c 혹은 d<a여야 함을 이용하는것이다.
이 외에 선분들이 교차하지 않고 접촉만 하는 경우도 인식하기 위해 ab나 cd중 하나가 0인경우에도 참을 반환한다는 점을 눈여겨보자.

*점과 선사이의 거리

한 직선에 포함딘 두 점의 벡터 a,b가 주어졌을 때 이 직선과 다른 점 p사이의 거리르 계산해보자.
한 가지 방법으 p가 이 직선에 내리는 수선의 발(perpendicular foot)을 계산한 뒤 p와 의거리를 구하는 것이다. 이것은 벡터의 내적을 이용하면 손쉽게 계산 할 수 있다.
직선위에서 p와 가장 가까운 점 q는 벡터 p-a가 벡터 b-a에 내린 벡터사영을 이용해 계산할 수 있기 때문이다.