Programming Serendipity

気まぐれに大まかに生きるブログ

Variadic Templateで多角形と点の当たり判定

三角形と点の当たり判定を応用して、可変長引数テンプレートでN角形と点の当たり判定を書いてみました。
参考:ゲームプログラミング技術集

struct Vec2
{
    Vec2(float a, float b) : x(a), y(b) {}
    float x, y;
};

Vec2 operator-(const Vec2& a, const Vec2& b)
{
    return Vec2(a.x - b.x, a.y - b.y);
}

// 三角形と点の当たり判定(2Dの場合)
bool CollTriangleDot(const Vec2& P, const Vec2& A, const Vec2& B, const Vec2& C)
{
    Vec2 AB = B - A;
    Vec2 BP = P - B;

    Vec2 BC = C - B;
    Vec2 CP = P - C;

    Vec2 CA = A - C;
    Vec2 AP = P - A;

    // 外積の計算
    float c1 = AB.x * BP.y - AB.y * BP.x;
    float c2 = BC.x * CP.y - BC.y * CP.x;
    float c3 = CA.x * AP.y - CA.y * AP.x;

    return ( c1 > 0 && c2 > 0 && c3 > 0 ) || ( c1 < 0 && c2 < 0 && c3 < 0 );
}

template<typename T = void>
bool CollPolygonDot(const Vec2& P, const Vec2& A, const Vec2& B, const Vec2& C)
{
    return CollTriangleDot(P, A, B, C);
}

template<typename... Ts>
bool CollPolygonDot(const Vec2& P, const Vec2& A, const Vec2& B, const Vec2& C, Ts... ts)
{
    return CollTriangleDot(P, A, B, C) || CollPolygonDot(P, A, C, ts...);
}

// 追記:イテレータを取るオーバーロードを追加してみた
template<typename FwdIt>
bool CollPolygonDot(const Vec2& P, FwdIt begin, FwdIt end)
{
    const size_t points = end - begin;
    // 保険
    if (points < 3 || 1024 < points) return false;
    std::vector<Vec2> ps(begin, end);
    for (size_t i = 1; i < ps.size() - 1; ++i)
    {
        if (CollTriangleDot(P, ps[0], ps[i], ps[i + 1]))
        {
            return true;
        }
    }
    return false;
}

たとえば7角形ABCDEFGがあったとすると、ABC, ACD, ADE, AEF, AEGの5つと内外判定を取ることで実現しています。
なお、これは内角が180°を越える角を持つ変形多角形には適用できませんので、そういう場合はあらかじめ分割しておくか、別の図形にするかなどの対処が必要になります。
各辺のベクトルから算出して自動で割り振ることもできるかもしれませんが、、、
今回の私のケースではそこまで必要なかったのでやっていません。。。