geometry/is-convex.hpp

• View this file on GitHub
• Last update: 2026-08-30 15:33:14+09:00
• Include: #include "geometry/is-convex.hpp"

Depends on

• geometry/base.hpp
• geometry/ccw.hpp
• geometry/cross.hpp
• geometry/dot.hpp

Required by

• 幾何ライブラリ (geometry/geometry.hpp)

Verified with

• test/mytest/geometry/geometry.test.cpp

Code

#pragma once

#include <vector>

#include "ccw.hpp"

namespace geometry {
    // 凸多角形かどうか
    inline bool isConvex(const std::vector<Point> &p) {
        int n = p.size();
        int now, pre, nxt;
        for(int i = 0; i < n; i++) {
            pre = (i - 1 + n) % n;
            nxt = (i + 1) % n;
            now = i;
            if(ccw(p[pre], p[now], p[nxt]) == -1) return false;
        }
        return true;
    }
} // namespace geometry

#line 2 "geometry/is-convex.hpp"

#include <vector>

#line 2 "geometry/ccw.hpp"

#line 2 "geometry/cross.hpp"

#line 2 "geometry/base.hpp"

#include <cmath>
#include <complex>

namespace geometry {
    // Point : 複素数型を位置ベクトルとして扱う
    // 実軸(real)をx軸、挙軸(imag)をy軸として見る
    using D = long double;
    using Point = std::complex<D>;
    const D EPS = 1e-7;
    const D PI = std::acos(D(-1));

    inline bool equal(const D &a, const D &b) { return std::fabs(a - b) < EPS; }
} // namespace geometry
#line 4 "geometry/cross.hpp"

namespace geometry {
    // 外積(cross product) : a×b = |a||b|sinΘ
    inline D cross(const Point &a, const Point &b) {
        return (a.real() * b.imag() - a.imag() * b.real());
    }
} // namespace geometry
#line 2 "geometry/dot.hpp"

#line 4 "geometry/dot.hpp"

namespace geometry {
    // 内積(dot product) : a・b = |a||b|cosΘ
    inline D dot(const Point &a, const Point &b) {
        return (a.real() * b.real() + a.imag() * b.imag());
    }
} // namespace geometry
#line 5 "geometry/ccw.hpp"

namespace geometry {
    // 点の回転方向
    // 点a, b, cの位置関係について(aが基準点)
    inline int ccw(const Point &a, Point b, Point c) {
        b -= a, c -= a;
        // 点a, b, c が
        // 反時計回りの時、
        if(cross(b, c) > EPS) return 1;
        // 時計回りの時、
        if(cross(b, c) < -EPS) return -1;
        // c, a, bがこの順番で同一直線上にある時、
        if(dot(b, c) < 0) return 2;
        // a, b, cがこの順番で同一直線上にある場合、
        if(std::norm(b) < std::norm(c)) return -2;
        // cが線分ab上にある場合、
        return 0;
    }
} // namespace geometry
#line 6 "geometry/is-convex.hpp"

namespace geometry {
    // 凸多角形かどうか
    inline bool isConvex(const std::vector<Point> &p) {
        int n = p.size();
        int now, pre, nxt;
        for(int i = 0; i < n; i++) {
            pre = (i - 1 + n) % n;
            nxt = (i + 1) % n;
            now = i;
            if(ccw(p[pre], p[now], p[nxt]) == -1) return false;
        }
        return true;
    }
} // namespace geometry

Back to top page