geometry/distance-between-segments.hpp

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

Depends on

• geometry/base.hpp
• geometry/ccw.hpp
• geometry/circle.hpp
• geometry/cross.hpp
• geometry/distance-between-segment-and-point.hpp
• geometry/dot.hpp
• geometry/is-intersect.hpp
• geometry/line.hpp
• geometry/segment.hpp

Required by

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

Verified with

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

Code

#pragma once

#include <algorithm>

#include "distance-between-segment-and-point.hpp"
#include "is-intersect.hpp"

namespace geometry {
    // 線分sとtの距離
    inline D distanceBetweenSegments(const Segment &s, const Segment &t) {
        if(isIntersect(s, t, 1)) return (D)(0);
        D ans = distanceBetweenSegmentAndPoint(s, t.a);
        ans = std::min(ans, distanceBetweenSegmentAndPoint(s, t.b));
        ans = std::min(ans, distanceBetweenSegmentAndPoint(t, s.a));
        ans = std::min(ans, distanceBetweenSegmentAndPoint(t, s.b));
        return ans;
    }
} // namespace geometry

#line 2 "geometry/distance-between-segments.hpp"

#include <algorithm>

#line 2 "geometry/distance-between-segment-and-point.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 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/distance-between-segment-and-point.hpp"

namespace geometry {
    // 線分lと点pの距離を求める
    // 定義：点pから「線分lのどこか」への最短距離
    inline D distanceBetweenSegmentAndPoint(const Segment &l, const Point &p) {
        if(dot(l.b - l.a, p - l.a) < EPS) return std::abs(p - l.a);
        if(dot(l.a - l.b, p - l.b) < EPS) return std::abs(p - l.b);
        return std::abs(cross(l.b - l.a, p - l.a)) / std::abs(l.b - l.a);
    }
} // namespace geometry
#line 2 "geometry/is-intersect.hpp"

#line 2 "geometry/ccw.hpp"

#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 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
#line 7 "geometry/distance-between-segments.hpp"

namespace geometry {
    // 線分sとtの距離
    inline D distanceBetweenSegments(const Segment &s, const Segment &t) {
        if(isIntersect(s, t, 1)) return (D)(0);
        D ans = distanceBetweenSegmentAndPoint(s, t.a);
        ans = std::min(ans, distanceBetweenSegmentAndPoint(s, t.b));
        ans = std::min(ans, distanceBetweenSegmentAndPoint(t, s.a));
        ans = std::min(ans, distanceBetweenSegmentAndPoint(t, s.b));
        return ans;
    }
} // namespace geometry

Back to top page