[JS] CCW

1. 점과 직선의 거리

A(x1, y1)에서 직선 ax + by + c = 0까지 최단거리(수직 거리)를 구합니다.

1.1. 기울기 구하기

A(x1, y1)과 직선 위의 임의의 점 B(x2, y2)의 직선의 방정식을 구합니다. 임의의 직선의 방정식을 y = a'x + b'라고 할때 A(x1, y1)과 B(x2, y2)를 대입해서 기울기 a'를 구합니다.

y1 = a'x1 + b'
y2 = a'x2 + b'

b'를 기준으로 두 방정식을 합칩니다.

y1 - a'x1 = y2 - a'x2
a' = (y2 - y1) / (x2 - x1)

1.2. 기울기 곱하기

직선과 임의의 직선은 수직이기 때문에 기울기를 곱하면 -1이 나옵니다. 먼저 직선의 기울기를 구합니다.

ax + by + c = 0
by = -ax - c
y = -(a / b) * x - c

기울기 곱하여 임의의 수 k를 구합니다.

(y2 - y1) / (x2 - x1) * -(a / b) = -1
y2 - y1) / (x2 - x1) * (a / b) = 1
a * (y2 - y1) = b * (x2 - x1)
(y2 - y1) / b = (x2 - x1) / a = k

k를 활용해 임의의 점 B(x2, y2)를 표현합니다.

a * k = x2 - x1
b * k = y2 - y1
x2 = a * k + x1
y2 = b * k + y1

1.3. 임의의 점 B(x2, y2)을 직선에 대입

B(x2, y2)는 임의의 직선 뿐만 아니라 직선 ax + by + c = 0위에 있는 점이기도 합니다. k로 표현한 임의의 점 B(x2, y2) 대입합니다.

a * x2 + b * y2 + c = 0
a * (a * k + x1) + b * (b * k + y1) + c = 0
(a ** 2 + b ** 2) * k + a * x1 + b * y1 + c = 0
k = -(a * x1 + b * y1 + c) / (a ** 2 + b ** 2)

1.4. 두 점의 거리 구하기

삼각함수 사용해 구한 두 점의 거리에, 기울기로 구한 k값을 대입합니다.

sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)
sqrt((a * k) ** 2 + (b * k) ** 2)
sqrt((k ** 2) * (a ** 2 + b ** 2))
|k| * sqrt(a ** 2 + b ** 2)

임의의 점을 직선에 대입하여 구한 k값 대입합니다.

|(a * x1 + b * y1 + c) / (a ** 2 + b ** 2)| * sqrt(a ** 2 + b ** 2)
|(a * x1 + b * y1 + c)| / (a ** 2 + b ** 2) * sqrt(a ** 2 + b ** 2)
|(a * x1 + b * y1 + c)| / sqrt(a ** 2 + b ** 2)

1.5. Javascript로 표현하기

function solution(x1, y1, a, b, c) {
  const num = Math.abs(a * x1 + b * y1 + c);
  const den = Math.sqrt(a ** 2 + b ** 2);

  return den / num;
}

2. 세 점의 넓이

A(x1, x2), B(x2, y2), C(x3, y3)이 주어졌을 때 삼각형의 넓이를 구합니다.

2.1. 직선의 방정식 구하기

B(x2, y2)와 C(x3, y3)의 직선의 방정식 y = a'x + b'을 만들고, 기울기를 구합니다.

a' = (y3 - y2) / (x3 - x2)

다시 B(x2, y2)을 대입해서 상수 값 구합니다.

y2 = (y3 - y2) / (x3 - x2) * x2 + b'
b' = y2 - (y3 - y2) / (x3 - x2) * x2

기울기와 상수값을 사용하여 방정식을 다시 정리합니다.

y = (y3 - y2) / (x3 - x2) * x + y2 - (y3 - y2) / (x3 - x2) * x2
y - y2 = (y3 - y2) / (x3 - x2) * (x - x2)

방정식을 ax + by + c = 0 형태로 표현합니다.

(y - y2) * (x3 - x2) = (y3 - y2) * (x - x2)
x3 * y - x2 * y - x3 * y2 = x * y3 - x2 * y3 - x * y2
(y3 - y2) * x - (x3 - x2) * y - x2 * y3 + x3 * y2 = 0
a = y3 - y2
b = -(x3 - x2)
c = -(x2 * y3 - x3 * y2)

2.2. 삼각형의 넓이 구하기

점과 직선의 방정식 사이의 거리 구하기 공식을 사용해서, A(x1, y1)과 직선의 거리를 구해 높이로 사용합니다.

|(a * x1 + b * y1 + c)| / sqrt(a ** 2 + b ** 2)

삼각함수를 사용해 B(x2, y2)와 C(x3, y3)의 거리를 구해 밑변으로 사용합니다.

sqrt(((x3 - x2) ** 2) * (y3 - y2) ** 2)
sqrt(a ** 2 + b ** 2)

밑변과 높이를 곱한 후 2로 나눕니다.

(|(a * x1 + b * y1 + c)| / sqrt(a ** 2 + b ** 2)) * (sqrt(a ** 2 + b ** 2) / 2
|(a * x1 + b * y1 + c)| / 2
|((y3 - y2) * x1 + -(x3 - x2) * y1 - x2 * y3 + x3 * y2)| / 2

2.3. Javascript로 표현하기

function solution(x1, y1, x2, y2, x3, y3) {
  const num = (y3 - y2) * x1 + -(x3 - x2) * y1 - x2 * y3 + x3 * y2;
  return Math.abs(num) / 2;
}

3. CCW

A(x1, y1), B(x2, y2), C(x3, y3)가 반시계방향이면 1, 직선이면 0, 시계방향이면 -1을 반환합니다.

3.1. 직선의 방정식 구하기

A(x1, y1)와 B(x2, y2)의 직선의 방정식을 구합니다.

y = (y2 - y1) / (x2 - x1) * (x - x1) + y1

3.2. C(x3, y3) 대입하기

x2 - x1 값이 음수인 경우 (직선 방향이 왼쪽인 경우)

y3 - y1 < (y2 - y1) / (x2 - x1) * (x3 - x1) (반시계 방향)
y3 - y1 = (y2 - y1) / (x2 - x1) * (x3 - x1) (직선 방향)
y3 - y1 > (y2 - y1) / (x2 - x1) * (x3 - x1) (시계 방향)

x2 - x1 값이 양수인 경우 (직선 방향이 오른쪽인 경우)

y3 - y1 < (y2 - y1) / (x2 - x1) * (x3 - x1) (시계 방향)
y3 - y1 = (y2 - y1) / (x2 - x1) * (x3 - x1) (직선 방향)
y3 - y1 > (y2 - y1) / (x2 - x1) * (x3 - x1) (반시계 방향)

3.3. 두 경우 통일 시키기

x2 - x1 값이 양수냐 음수냐에 따라 부등호의 결과가 반대이므로, x2 - x1를 양쪽에 곱해서 부등호를 통일시킵니다. x2 - x1이 양수일 때는 곱해도 부등호가 유지되고, x2 - x1가 음수일 경우 곱하면 부등호가 뒤집히는 것을 이용합니다.

(y3 - y1) * (x2 - x1) < (y2 - y1) * (x3 - x1) (시계 방향)
(y3 - y1) * (x2 - x1) = (y2 - y1) * (x3 - x1) (직선 방향)
(y3 - y1) * (x2 - x1) > (y2 - y1) * (x3 - x1) (반시계 방향)

3.4. Javascript로 표현하기

function solution(x1, y1, x2, y2, x3, y3) {
  const num1 = (y3 - y1) * (x2 - x1);
  const num2 = (y2 - y1) * (x3 - x1);

  if (num1 < num2) return "-1";
  if (num1 > num2) return "1";
  return "0";
}