geometry/is-intersect.hpp

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

Depends on

Required by

Verified with

test/mytest/geometry/geometry.test.cpp

Code

#pragma once

#include "ccw.hpp"
#include "circle.hpp"
#include "segment.hpp"

namespace geometry {
    // 線分sと線分tが交差しているかどうか
    // bound:線分の端点を含むか
    inline bool isIntersect(const Segment &s, const Segment &t, bool bound) {
        return ccw(s.a, s.b, t.a) * ccw(s.a, s.b, t.b) < bound &&
               ccw(t.a, t.b, s.a) * ccw(t.a, t.b, s.b) < bound;
    }

    // 2つの円の交差判定
    // 返り値は共通接線の数
    inline int isIntersect(const Circle &c1, const Circle &c2) {
        D d = std::abs(c1.p - c2.p);
        // 2つの円が離れている場合
        if(d > c1.r + c2.r + EPS) return 4;
        // 外接している場合
        if(equal(d, c1.r + c2.r)) return 3;
        // 内接している場合
        if(equal(d, std::abs(c1.r - c2.r))) return 1;
        // 内包している場合
        if(d < std::abs(c1.r - c2.r) - EPS) return 0;
        return 2;
    }
} // namespace geometry

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

#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 2 "geometry/circle.hpp"

#line 4 "geometry/circle.hpp"

namespace geometry {
    // Circle : 円を表す構造体
    // pが中心の位置ベクトル、rは半径
    struct Circle {
        Point p;
        D r;

        Circle() = default;

        Circle(Point p, D r) : p(p), r(r) {}
    };
} // namespace geometry
#line 2 "geometry/segment.hpp"

#line 2 "geometry/line.hpp"

#line 4 "geometry/line.hpp"

namespace geometry {
    // Line : 直線を表す構造体
    // b - a で直線・線分を表せる
    struct Line {
        Point a, b;
        Line() = default;
        Line(Point a, Point b) : a(a), b(b) {}
        // Ax+By=C
        Line(D A, D B, D C) {
            if(equal(A, 0)) {
                a = Point(0, C / B), b = Point(1, C / B);
            } else if(equal(B, 0)) {
                a = Point(C / A, 0), b = Point(C / A, 1);
            } else if(equal(C, 0)) {
                a = Point(0, C / B), b = Point(1, (C - A) / B);
            } else {
                a = Point(0, C / B), b = Point(C / A, 0);
            }
        }
    };
} // namespace geometry
#line 4 "geometry/segment.hpp"

namespace geometry {
    // Segment : 線分を表す構造体
    // Lineと同じ
    struct Segment : Line {
        Segment() = default;

        Segment(Point a, Point b) : Line(a, b) {}
        D get_dist() { return std::abs(a - b); }
    };
} // namespace geometry
#line 6 "geometry/is-intersect.hpp"

namespace geometry {
    // 線分sと線分tが交差しているかどうか
    // bound:線分の端点を含むか
    inline bool isIntersect(const Segment &s, const Segment &t, bool bound) {
        return ccw(s.a, s.b, t.a) * ccw(s.a, s.b, t.b) < bound &&
               ccw(t.a, t.b, s.a) * ccw(t.a, t.b, s.b) < bound;
    }

    // 2つの円の交差判定
    // 返り値は共通接線の数
    inline int isIntersect(const Circle &c1, const Circle &c2) {
        D d = std::abs(c1.p - c2.p);
        // 2つの円が離れている場合
        if(d > c1.r + c2.r + EPS) return 4;
        // 外接している場合
        if(equal(d, c1.r + c2.r)) return 3;
        // 内接している場合
        if(equal(d, std::abs(c1.r - c2.r))) return 1;
        // 内包している場合
        if(d < std::abs(c1.r - c2.r) - EPS) return 0;
        return 2;
    }
} // namespace geometry