JavaScriptで凸多角形かどうかを判定する方法

凸多角形とは

凸多角形とは、すべての内角が180度未満である多角形のことを指します。別の見方をすると、どの辺を一直線に延長しても、多角形全体が必ずその直線の片側だけに収まるような形状です。代表的な例として、正方形や正三角形などが挙げられます。

問題

座標の配列を受け取り、それらの点によって形成される多角形が凸多角形かどうかを判定するJavaScript関数を作成する必要があります。

入力となる配列は「配列の中に配列が入った構造」になっており、各サブ配列には2次元平面上の1点を表す、ちょうど2つの数値（x座標とy座標）が格納されています。

この関数は、点群から形成される多角形が凸多角形であれば true を、そうでなければ false を返す必要があります。

入力例

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

出力例

const output = true;

出力の解説

上記の4つの頂点は完全な正方形を描きます。正方形のすべての頂点における内角は90度であり、180度未満であるため、これは凸多角形と判定されます。

解決アプローチ：外積を使った判定

凸多角形の判定には、ベクトルの外積（クロス積）を利用するのが一般的です。隣り合う3つの頂点ごとに外積を計算し、その符号がすべて同じ方向（すべて正またはすべて負）であれば、多角形は凸であると判断できます。途中で符号が反転する箇所があれば、そこに凹んだ部分があることになります。

サンプルコード

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));

コードのポイント

• 変数 dx1・dy1 は現在の頂点から次の頂点への辺ベクトルを、dx2・dy2 は次の頂点からそのさらに次の頂点への辺ベクトルを表します。
• curr = dx1 * dy2 - dx2 * dy1 の計算が外積に相当し、その符号によって進行方向に対して左回りか右回りかが分かります。
• 外積が 0 の場合は3点が同一直線上にある（コリニアな）状態を意味するため、判定対象から除外しています。
• ループ内で外積の符号が前回と異なる場合、凹んでいる頂点が存在すると判断し、即座に false を返します。

実行結果

コンソールに出力される結果は以下の通りです。

true

このように、外積の符号の一貫性をチェックするだけで、O(n) の計算量で効率よく凸多角形の判定を行うことができます。