geometry

기울기

p1(x1,y1), p2(x2,y2) 두점이 있을때 두점을 잊는 직선의 기울기는 아래처럼 표현된다.

$$
기울기 = \frac{y 변화값}{x변화값} = \frac{y2-y1}{x2-x1}
$$

orientation

P, Q, R 세점이 있다. 이 세점의 방향성은 어떻게 찰을 수 있을까.
(P,Q)의 기울기와 (Q,R)의 기울기를 비교해보면 방향을 알 수 있다.
그렇다면 (p,q) 의 기울기가 더 크다면 pqr은 시계방향으로 굽어 있는 것이고, 그 반대라면 반시계방향으로 굽어 있는 것이다. 두 기울기가 같다면 평행한 것이고.

이것을 수식으로 나타내면

$$
기울기 \overrightarrow{PQ} = \frac{Q_y-P_y}{Q_x-P_x}
$$

$$
기울기 \overrightarrow{QR} = \frac{R_y-Q_y}{R_x-Q_x}
$$

위의 두 값을 비교하면 pqr의 상대적인 위치를 알 수 있는 함수를 만들 수 있다. R이 시계방향쪽에 위치하고 있는지 아닌지를..

이것을 orientation이라고 정의하고 함수로 구현하면 아래처럼 구현할 수 있다.

// To find orientation of ordered triplet (p, q, r).
// The function returns following values
// 0 --> p, q and r are colinear
// 1 --> Clockwise
// 2 --> Counterclockwise
int orientation(Point p, Point q, Point r)
{
    int val = (q.y - p.y) * (r.x - q.x) -
              (q.x - p.x) * (r.y - q.y);

    if (val == 0) return 0;  // colinear
    return (val > 0)? 1: 2; // clock or counterclock wise
}

convex hull

앞서 말한 orientation 은 convex hull알고리즘으로 발전할 수 있다.

https://www.geeksforgeeks.org/convex-hull-set-2-graham-scan/