JavaScript로 볼록 다각형(Convex Polygon) 판별하기

볼록 다각형(Convex Polygon)이란?

볼록 다각형은 모든 내각이 180°보다 작은 다각형을 의미합니다. 직관적으로 말하면, 다각형의 어떤 변을 연장했을 때 그 선이 다각형의 내부를 가로지르지 않는 형태를 뜻합니다.

문제 정의

좌표 배열을 입력받는 JavaScript 함수를 작성해야 합니다. 배열의 각 요소는 정확히 두 개의 숫자를 담고 있는 하위 배열이며, 이는 2차원 평면 위의 한 점을 나타냅니다.

이 함수는 주어진 점들이 순서대로 이루어진 다각형이 볼록 다각형인지 판별하고, 볼록 다각형이라면 true를, 그렇지 않다면 false를 반환해야 합니다.

예를 들어, 함수에 다음과 같이 입력한다면 −

const arr = [[0,0],[0,1],[1,1],[1,0]];

출력 결과는 다음과 같아야 합니다.

const output = true;

출력 설명

위 네 개의 점은 완벽한 정사각형을 그리며, 모든 꼭짓점의 내각은 90°입니다. 따라서 이 다각형은 볼록 다각형에 해당합니다.

알고리즘 원리: 외적(Cross Product)

이 문제는 벡터의 외적을 활용하면 효율적으로 해결할 수 있습니다. 인접한 세 점씩 순회하면서 외적 값을 계산하고, 그 부호가 일관되게 유지되는지 확인하는 방식입니다.

모든 외적 값의 부호가 동일하면(전부 양수 또는 전부 음수) → 볼록 다각형
부호가 중간에 바뀌면 → 오목 다각형(concave polygon)
외적 값이 0인 경우는 세 점이 일직선상에 놓여 있다는 의미이므로 판단에서 제외합니다.

예제 코드

const arr = [[0,0],[0,1],[1,1],[1,0]];
const isConvex = (arr = []) => {
   const { length } = arr;
   let pre = 0, curr = 0;
   for (let i = 0; i < length; ++i) {
      let dx1 = arr[(i + 1) % length][0] - arr[i][0];
      let dx2 = arr[(i + 2) % length][0] - arr[(i + 1) % length][0];
      let dy1 = arr[(i + 1) % length][1] - arr[i][1];
      let dy2 = arr[(i + 2) % length][1] - arr[(i + 1) % length][1];
      curr = dx1 * dy2 - dx2 * dy1;
      if (curr != 0) {
         if ((curr > 0 && pre < 0) || (curr < 0 && pre > 0))
            return false;
         else
            pre = curr;
      };
   };
   return true;
};
console.log(isConvex(arr));

코드 설명

핵심 로직을 단계별로 살펴보면 다음과 같습니다.

배열의 길이를 구하고, 이전 외적 값(pre)과 현재 외적 값(curr)을 저장할 변수를 초기화합니다.
모듈로 연산(%)을 사용해 마지막 점에서 첫 번째 점으로 자연스럽게 순환하며 인접한 세 점을 가져옵니다.
두 벡터의 외적을 계산하여 회전 방향(시계 방향 또는 반시계 방향)을 판단합니다.
외적 값이 0이 아니면서 부호가 이전 값과 반대라면, 다각형이 한 방향으로만 꺾이지 않았다는 뜻이므로 오목 다각형입니다. 즉, false를 반환합니다.
모든 점을 순회한 후에도 부호가 일관되면 true를 반환합니다.

출력 결과

콘솔에 출력되는 결과는 다음과 같습니다.

true