segment
(geometry/segment.hpp)

• View this file on GitHub
• Last update: 2023-06-08 15:34:10+09:00
• Include: #include "geometry/segment.hpp"

説明

平面での線分の各種操作

segment

線分の端点 $a$, $b$ を持つ

intersection_segment_and_vec(segment a, vec p)

線分 $a$ 上に点 $p$ が存在するか判定。

intersection_segment(segment a, segment b)

線分 $a$, $b$ が交わるか判定。端点も含む。

intersection_segment_nobundary(segment a, segement b)

線分 $a$, $b$ が端点を除いて交わるか判定。

cross_point(segment a, segment b)

線分 $a$, $b$ の交点を返す。

distance(segment a, vec c)

線分 $a$ と点 $c$ の距離を返す。

distance(segment a, segment b)

線分 $a$, $b$ の距離を返す。

Depends on

• base_ld (geometry/base_ld.hpp)
• line (geometry/line.hpp)
• テンプレート (template/template.hpp)

Verified with

• test/geometry/Convex_Hull.test.cpp
• test/geometry/Cross_Point.test.cpp
• test/geometry/Distance.test.cpp
• test/geometry/Intersection.test.cpp

Code

#pragma once

#include "../geometry/line.hpp"

namespace lib {

struct segment : line {};

bool intersection_segment_and_vec(const segment &a, const vec &p) {
    return isp(a.a, a.a, p) == 0;
}

bool intersection_segment(const segment &a, const segment &b) {
    if (sgn(isp(a.a, a.b, b.a) * isp(a.a, a.b, b.b)) <= 0 &&
        sgn(isp(b.a, b.b, a.a) * isp(b.a, b.b, a.b)) <= 0) {
        return true;
    } else
        return false;
}

vec cross_point(const segment &a, const segment &b) {
    assert(intersection_segment(a, b));
    return a.a + (a.b - a.a) * cross(b.a - a.a, b.b - b.a) /
                     cross(a.b - a.a, b.b - b.a);
}

ld dist(const segment &a, const vec &c) {
    if (sgn(dot(a.b - a.a, c - a.a)) <= 0) {
        return abs(c - a.a);
    } else if (sgn(dot(a.a - a.b, c - a.b)) <= 0) {
        return abs(c - a.b);
    } else {
        return abs(cross(c - a.a, a.b - a.a) / abs(a.b - a.a));
    }
}

ld dist(const segment &a, const segment &b) {
    if (intersection_segment(a, b))
        return 0;
    else
        return min(min(dist(a, b.a), dist(a, b.b)),
                   min(dist(b, a.a), dist(b, a.b)));
}

}  // namespace lib

#line 2 "geometry/segment.hpp"

#line 2 "geometry/line.hpp"

#line 2 "geometry/base_ld.hpp"

#line 2 "template/template.hpp"

#include <bits/stdc++.h>

#define rep(i, s, n) for (int i = (int)(s); i < (int)(n); i++)
#define rrep(i, s, n) for (int i = (int)(n)-1; i >= (int)(s); i--)
#define all(v) v.begin(), v.end()

using ll = long long;
using ld = long double;
using ull = unsigned long long;

template <typename T> bool chmin(T &a, const T &b) {
    if (a <= b) return false;
    a = b;
    return true;
}
template <typename T> bool chmax(T &a, const T &b) {
    if (a >= b) return false;
    a = b;
    return true;
}

namespace lib {

using namespace std;

}  // namespace lib

// using namespace lib;
#line 4 "geometry/base_ld.hpp"

namespace lib {

using vec = complex<ld>;

const ld PI = acos(-1);

void ldout(int len = 20) {
    cout << fixed << setprecision(len);
}

int sgn(ld a, const ld eps = 1e-7) {
    return (a < -eps) ? -1 : (a > eps) ? 1 : 0;
}

bool same_vec(vec a, vec b) {
    a -= b;
    return sgn(a.real()) == 0 && sgn(a.imag()) == 0;
}

ld dot(const vec &a, const vec &b) {
    return (conj(a) * b).real();
}

ld cross(const vec &a, const vec &b) {
    return (conj(a) * b).imag();
}

int isp(const vec &a, const vec &b, const vec &c) {
    int cross_sgn = sgn(cross(b - a, c - a));
    if (cross_sgn == 0) {
        if (sgn(dot(b - a, c - a)) < 0) return -2;
        if (sgn(dot(a - b, c - b)) < 0) return 2;
    }
    return cross_sgn;
}

vec rot90(const vec &a) {
    return {-a.imag(), a.real()};
}

vec rot(const vec &a, ld rad) {
    return a * vec(cosl(rad), sinl(rad));
}

bool comp_for_argument_sort(const vec &lhs, const vec &rhs) {
    // if (abs(arg(lhs)-arg(rhs)) < eps) return false; // need ?
    return arg(lhs) < arg(rhs);
}

}  // namespace lib
#line 4 "geometry/line.hpp"

namespace lib {

struct line {
    vec a, b;
};

vec proj(const line &l, const vec &p) {
    vec ab = l.b - l.a;
    return l.a + ab * (dot(ab, p - l.a) / norm(ab));
}

vec refl(const line &l, const vec &p) {
    return proj(l, p) * ld(2) - p;
}

int intersection(const line &a, const line &b) {
    if (sgn(cross(a.b - a.a, b.a - b.b)) != 0) {
        if (sgn(dot(a.b - a.a, b.a - b.b)) == 0) {
            return 1;
        }
        return 0;
    } else if (sgn(cross(a.b - a.a, b.a - a.a)) != 0) {
        return 2;
    } else {
        return 3;
    }
}

ld dist(const line &a, const vec &p) {
    return abs(cross(p - a.a, a.b - a.a) / abs(a.b - a.a));
}

vec cross_point(const line &a, const line &b) {
    assert(intersection(a, b) < 2);
    return a.a + (a.b - a.a) * cross(b.a - a.a, b.b - b.a) /
                     cross(a.b - a.a, b.b - b.a);
}

}  // namespace lib
#line 4 "geometry/segment.hpp"

namespace lib {

struct segment : line {};

bool intersection_segment_and_vec(const segment &a, const vec &p) {
    return isp(a.a, a.a, p) == 0;
}

bool intersection_segment(const segment &a, const segment &b) {
    if (sgn(isp(a.a, a.b, b.a) * isp(a.a, a.b, b.b)) <= 0 &&
        sgn(isp(b.a, b.b, a.a) * isp(b.a, b.b, a.b)) <= 0) {
        return true;
    } else
        return false;
}

vec cross_point(const segment &a, const segment &b) {
    assert(intersection_segment(a, b));
    return a.a + (a.b - a.a) * cross(b.a - a.a, b.b - b.a) /
                     cross(a.b - a.a, b.b - b.a);
}

ld dist(const segment &a, const vec &c) {
    if (sgn(dot(a.b - a.a, c - a.a)) <= 0) {
        return abs(c - a.a);
    } else if (sgn(dot(a.a - a.b, c - a.b)) <= 0) {
        return abs(c - a.b);
    } else {
        return abs(cross(c - a.a, a.b - a.a) / abs(a.b - a.a));
    }
}

ld dist(const segment &a, const segment &b) {
    if (intersection_segment(a, b))
        return 0;
    else
        return min(min(dist(a, b.a), dist(a, b.b)),
                   min(dist(b, a.a), dist(b, a.b)));
}

}  // namespace lib

Back to top page