C++で凸多角形を判定するアルゴリズム：外積を使った効率的な実装方法

順番に頂点を結ぶと多角形になる点列が与えられたとき、その多角形が凸多角形であるかどうかを判定する問題を考えます。

制約条件は以下の通りです。

• 点の数は最低3個、最大10,000個
• 各座標の値は -10,000 以上 10,000 以下の範囲に収まる
• 与えられた点列が形成する多角形は常に単純多角形(simple polygon)であると仮定できる。つまり、各頂点でちょうど2本の辺が交わり、それ以外の場所で辺同士が交差することはない

例えば、入力が [[0,0],[0,1],[1,1],[1,0]] の場合、この4点は単位正方形を形成するため凸多角形であり、結果として true を返します。

解法のアプローチ：外積による回転方向の判定

凸多角形の重要な性質として、「多角形の境界に沿って一周したとき、すべての頂点で同じ方向(左回りまたは右回り)に曲がる」というものがあります。この性質を利用すると、隣接する3点ごとに外積(cross product)を計算し、その符号が一貫しているかどうかを調べることで凸性を判定できます。

外積の値が正なら反時計回り(CCW)のターン、負なら時計回り(CW)のターンを意味します。途中で符号が混在した場合、その多角形には凹んだ部分があることになり、凸多角形ではないと分かります。

アルゴリズムの手順

1. calc() メソッドを定義する:引数として ax, ay, bx, by, cx, cy の6つの座標を受け取り、以下のように動作します。
   • BAx := ax − bx、BAy := ay − by、BCx := cx − bx、BCy := cy − by を計算
   • 外積「BAx × BCy − BAy × BCx」を返す(これはベクトルBAとベクトルBCの外積のZ成分)
2. メインメソッドでの処理:
   • neg := false、pos := false と初期化し、n := 点列のサイズとする
   • i を 0 から n−1 までループ:
     • a := i、b := (i + 1) mod n、c := (i + 2) mod n とする(末尾では先頭に戻る循環インデックス)
     • cross_prod := calc(p[a][0], p[a][1], p[b][0], p[b][1], p[c][0], p[c][1]) を計算
     • cross_prod < 0 なら neg := true、cross_prod > 0 なら pos := true を設定
     • neg と pos が両方 true になった時点で、即座に false を返す
   • ループが完了すれば true を返す

この手法の計算量は O(n) であり、最大10,000点の入力でも高速に処理できます。また、外積計算では整数演算のみを使用するため、浮動小数点誤差の心配もありません。

C++による実装例

以下の実装を見ると、理解がより深まります。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    bool isConvex(vector<vector<int>>& points) {
        bool neg = false;
        bool pos = false;
        int n = points.size();
        for(int i = 0; i < n; i++){
            int a = i;
            int b = (i + 1) % n;
            int c = (i + 2) % n;
            int crossProduct = calc(points[a][0], points[a][1], points[b][0], points[b][1], points[c][0], points[c][1]);
            if(crossProduct < 0) neg = true;
            else if(crossProduct > 0) pos = true;
            if(neg && pos) return false;
        }
        return true;
    }
    int calc(int ax, int ay, int bx, int by, int cx, int cy){
        int BAx = ax - bx;
        int BAy = ay - by;
        int BCx = cx - bx;
        int BCy = cy - by;
        return (BAx * BCy - BAy * BCx);
    }
};
main(){
    vector<vector<int>> v = {{0,0},{0,1},{1,1},{1,0}};
    Solution ob;
    cout << (ob.isConvex(v));
}

入力

[[0,0],[0,1],[1,1],[1,0]]

出力

1

出力が 1(true)となり、この4点で構成される多角形が凸多角形であることが確認できました。