기하[1] -2차원 세 점의 관계 - 평행 및 시계, 반시계 방향

  2차원에서 세 점이 주어졌을 때 이 세 점을 이었을 때 이루는 두 선분의 연결 관계를 평행 그리고 시계, 반시계 방향으로 구분할 수 있다. 단, 두 선분이 존재하기 위해서는 점이 아닌 선으로 있어야하기 때문에 세 점 중 어느 점도 중복되지 않는다는 전제가 필요하다.  

p1=(x1, y1), p2=(x2, y2), p3=(x3, y3)

  p1을 시작점으로 두는 세 점 p1, p2, p3가 이룰 수 있는 선분 관계는 아래처럼 정의된다. 

 

평행

반시계방향

시계방향

  ※ 이외 세 점이 나올 수 있는 위치에 대해선 뒤 세 가지 경우를 회전 변환하여 똑같이 적용할 수 있기에 따로 작성하지 않았습니다.

 

  판단 방법은 꽤 간단하다. p1과 p2가 이루는 기울기를 A, p2와 p3가 이루는 기울기를 A3라고 할 때 A가 B보다 크다면 볼록, 같다면 평행, 작다면 오목이다. 이를 수식으로 나타내면 아래와 같다.

A=(y2-y1)/(x2-x1) B=(y3-y2)/(x3-x2)   선분을 이루는 두 점의 x좌표가 같을 수 있으므로 비교할 땐 분모를 없애고 비교한다.   comp = (y2-y1) * (x3-x2) - (y3-y2) * (x2-x1)

시계, 반시계 판정

  판별할 때는 부호 체크하여 판별하면 되시겠다~

  이때 세 점 관계에서 시계 방향으로 이뤄지는 경우 "오목하다"라고 본다. 반대로 반시계 방향으로 이뤄지는 경우엔 "볼록한다"고 본다.

comp > 0 (시계, 볼록) comp = 0 (평행) comp < 0 (반시계, 오목)

 

  코드로 작성하면 아래와 같다.

struct pt { double x, y; };
int orient(pt& p1, pt& p2, pt& p3) {
	double d = (p2.y - p1.y) * (p3.x - p2.x) - (p3.y - p2.y) * (p2.x - p1.x);
	return d < 0 ? -1 : (d > 0);
}