Geometry/Line.hpp

• View this file on GitHub
• Last update: 2021-03-21 09:12:36+09:00
• Include: #include "Geometry/Line.hpp"

Depends on

• Geometry/Geometric.hpp
• Geometry/Vec2.hpp

Required by

• Geometry/Geometric.cpp
• Geometry/Polygon.hpp
• Geometry/Rect.hpp
• Geometry/Triangle.hpp
• Geometry/area_of_intersection.cpp
• Geometry/closest_pair.cpp
• Geometry/common_tangent.cpp

Verified with

• test/Geometric_area_of_intersection_between_circle_and_polygon.test.cpp
• test/Geometric_area_of_intersection_between_two_circles.test.cpp
• test/Geometric_cirnnumscribed_circle.test.cpp
• test/Geometric_closest_pair.test.cpp
• test/Geometric_common_tangent.test.cpp
• test/Geometric_convex_hull.test.cpp
• test/Geometric_cross_point_of_circles.test.cpp
• test/Geometric_cross_points_between_line_and_circle.test.cpp
• test/Geometric_dot_cross.test.cpp
• test/Geometric_iSP.test.cpp
• test/Geometric_incircle_of_triangle.test.cpp
• test/Geometric_is_convex.test.cpp
• test/Geometric_is_parallel_is_orthogonal.test.cpp
• test/Geometric_line_intersection.test.cpp
• test/Geometric_polygon_cut.test.cpp
• test/Geometric_polygon_diameter.test.cpp
• test/Geometric_polygon_point_containment.test.cpp
• test/Geometric_projection.test.cpp
• test/Geometric_reflection.test.cpp
• test/Geometric_segment_distance.test.cpp
• test/Geometric_segment_intersection.test.cpp
• test/Geometric_tangent_to_circle.test.cpp

Code

#pragma once
#include "./Geometric.hpp"
#include "./Vec2.hpp"
#include <iostream>
#include <utility>
#include <tuple>
#include <cmath>

namespace Geometric {

	namespace internal {
		struct LineBase {
		protected:
			constexpr LineBase() = default;
			constexpr LineBase(const Vec2& _begin, const Vec2& _end)
			    : begin(_begin), end(_end) {}
			constexpr LineBase(LD begin_x, LD begin_y, LD end_x, LD end_y)
			    : begin(begin_x, begin_y), end(end_x, end_y) {}

		public:
			Vec2 begin, end;
			constexpr LineBase operator+(const Vec2& v) {
				return LineBase(*this) += v;
			}
			constexpr LineBase operator-(const Vec2& v) {
				return LineBase(*this) -= v;
			}
			constexpr LineBase& operator+=(const Vec2& v) {
				begin += v;
				end += v;
				return *this;
			}
			constexpr LineBase& operator-=(const Vec2& v) {
				begin -= v;
				end -= v;
				return *this;
			}
			constexpr Vec2 vec() const {
				return end - begin;
			}
			constexpr Vec2 counter_vec() const {
				return begin - end;
			}
			// 平行判定
			constexpr bool is_parallel(const LineBase& l) const {
				return sgn(vec().cross(l.vec())) == 0;
			}
			// 直交判定
			constexpr bool is_orthogonal(const LineBase& l) const {
				return sgn(vec().dot(l.vec())) == 0;
			}
			friend std::ostream& operator<<(std::ostream& os, const LineBase& l) {
				return os << '(' << l.begin << ", " << l.end << ')';
			}
			friend std::istream& operator>>(std::istream& is, LineBase& l) {
				return is >> l.begin >> l.end;
			}
		};
	}  // namespace internal

	struct Line : internal::LineBase {
		constexpr Line() = default;
		constexpr Line(const Vec2& _begin, const Vec2& _end) : LineBase(_begin, _end) {}
		constexpr Line(LD begin_x, LD begin_y, LD end_x, LD end_y)
		    : LineBase(begin_x, begin_y, end_x, end_y) {}
		constexpr Line(const LineBase& l) : LineBase(l) {}
		// ax + by + c = 0 の式に変形する
		std::tuple<LD, LD, LD> abc() const {
			if (sgn(begin.x - end.x) == 0) {
				return {1, 0, -begin.x};
			} else {
				LD slope = (end.y - begin.y) / (end.x - begin.x);
				return {slope, -1, begin.y - begin.x * slope};
			}
		}
	};

	struct Segment : internal::LineBase {
		constexpr Segment() = default;
		constexpr Segment(const Vec2& _begin, const Vec2& _end) : LineBase(_begin, _end) {}
		constexpr Segment(LD begin_x, LD begin_y, LD end_x, LD end_y)
		    : LineBase(begin_x, begin_y, end_x, end_y) {}
		constexpr Segment(const LineBase& l) : LineBase(l) {}
	};

}  // namespace Geometric

#line 2 "Geometry/Geometric.hpp"
#include <iostream>
#include <vector>
#include <algorithm>
#include <optional>

namespace Geometric {

	using LD = long double;
	constexpr long double PI = 3.14159265358979323846, EPS = 1e-12;

	// a > 0 : +1
	// a = 0 :  0
	// a < 0 : -1
	constexpr int sgn(LD a);
	constexpr LD deg_to_rad(LD deg);
	constexpr LD rad_to_deg(LD rad);

	struct Vec2;
	struct Line;
	struct Segment;
	struct Rect;
	struct Circle;
	struct Polygon;

	// AB から見て BC が左に曲がる   : +1
	// AB から見て BC が右に曲がる   : -1
	// ABC, CBA の順に一直線上に並ぶ : +2
	// ACB, BCA の順に一直線上に並ぶ :  0
	// BAC, CAB の順に一直線上に並ぶ : -2
	int iSP(const Vec2& a, const Vec2& b, const Vec2& c);

	// ∠ABC が鋭角 : 0, 直角 : 1, 鈍角 : 2
	int angle_type(const Vec2& a, const Vec2& b, const Vec2& c);

	// ∠ABC の値 (radian)
	LD angle(const Vec2& a, const Vec2& b, const Vec2& c);

	// 距離
	LD distance(const Vec2& v1, const Vec2& v2);
	LD distance(const Vec2& v, const Line& l);
	LD distance(const Vec2& v, const Segment& s);
	LD distance(const Vec2& v, const Circle& c);
	LD distance(const Line& l, const Vec2& v);
	LD distance(const Line& l1, const Line& l2);
	LD distance(const Segment& s, const Vec2& v);
	LD distance(const Segment& s1, const Segment& s2);
	LD distance(const Circle& c, const Vec2& v);
	LD distance(const Circle& c1, const Circle& c2);

	// 交差判定 （内包しているときも true を返す）
	bool intersect(const Vec2& v1, const Vec2& v2);
	bool intersect(const Vec2& v, const Line& l);
	bool intersect(const Vec2& v, const Segment& l);
	bool intersect(const Vec2& v, const Circle& c);
	bool intersect(const Vec2& v, const Rect& r);
	bool intersect(const Vec2& v, const Polygon& p);
	bool intersect(const Line& l, const Vec2& v);
	bool intersect(const Line& l1, const Line& l2);
	bool intersect(const Line& l, const Circle& c);
	bool intersect(const Segment& l, const Vec2& v);
	bool intersect(const Segment& s1, const Segment& s2);
	bool intersect(const Segment& s, const Circle& c);
	bool intersect(const Circle& c, const Vec2& v);
	bool intersect(const Circle& c, const Line& l);
	bool intersect(const Circle& c, const Segment& s);
	bool intersect(const Circle& c1, const Circle& c2);
	bool intersect(const Circle& c, const Rect& r);
	bool intersect(const Rect& r, const Vec2& v);
	bool intersect(const Rect& r1, const Rect& r2);
	bool intersect(const Rect& r, const Circle& c);
	bool intersect(const Polygon& p, const Vec2& v);

	// 接するか判定
	bool tangent(const Vec2& v1, const Vec2& v2);
	bool tangent(const Vec2& v, const Line& l);
	bool tangent(const Vec2& v, const Segment& l);
	bool tangent(const Vec2& v, const Circle& c);
	bool tangent(const Vec2& v, const Rect& r);
	bool tangent(const Vec2& v, const Polygon& p);
	bool tangent(const Line& l, const Vec2& v);
	bool tangent(const Line& l, const Circle& c);
	bool tangent(const Line& l, const Rect& r);
	bool tangent(const Segment& l, const Vec2& v);
	bool tangent(const Circle& c, const Vec2& v);
	bool tangent(const Circle& c, const Line& l);
	bool tangent(const Circle& c1, const Circle& c2);
	bool tangent(const Rect& r, const Vec2& v);
	bool tangent(const Rect& r, const Line& l);
	bool tangent(const Polygon& p, const Vec2& v);

	// 交点
	std::optional<Vec2> cross_point(const Line& l1, const Line& l2);
	std::optional<Vec2> cross_point(const Segment& s1, const Segment& s2);

	std::vector<Vec2> cross_points(const Line& l, const Circle& c);
	std::vector<Vec2> cross_points(const Segment& s, const Circle& c);
	std::vector<Vec2> cross_points(const Circle& c, const Line& l);
	std::vector<Vec2> cross_points(const Circle& c, const Segment& s);
	std::vector<Vec2> cross_points(const Circle& c1, const Circle& c2);

	// 円の接線
	std::vector<Vec2> tangent_to_circle(const Circle& c, const Vec2& v);
}  // namespace Geometric
#line 4 "Geometry/Vec2.hpp"
#include <utility>
#include <cmath>

namespace Geometric {

	struct Vec2 {
		LD x, y;
		static constexpr bool compare_x(const Vec2& v1, const Vec2& v2) {
			return v1.x < v2.x;
		}
		static constexpr bool compare_y(const Vec2& v1, const Vec2& v2) {
			return v1.y < v2.y;
		}
		static constexpr bool compare_xy(const Vec2& v1, const Vec2& v2) {
			return std::make_pair(v1.x, v1.y) < std::make_pair(v2.x, v2.y);
		}
		static constexpr bool compare_yx(const Vec2& v1, const Vec2& v2) {
			return std::make_pair(v1.y, v1.x) < std::make_pair(v2.y, v2.x);
		}
		static constexpr Vec2 zero() {
			return Vec2(0, 0);
		}
		constexpr Vec2() : x(0), y(0) {}
		constexpr Vec2(LD _x, LD _y) : x(_x), y(_y) {}
		Vec2(LD rad) : x(std::cos(rad)), y(std::sin(rad)) {}
		constexpr bool operator==(const Vec2& v) const {
			return sgn(x - v.x) == 0 && sgn(y - v.y) == 0;
		}
		constexpr bool operator!=(const Vec2& v) const {
			return !(*this == v);
		}
		constexpr Vec2 operator+() const {
			return *this;
		}
		constexpr Vec2 operator-() const {
			return {-x, -y};
		}
		constexpr Vec2 operator+(const Vec2& v) const {
			return Vec2(*this) += v;
		}
		constexpr Vec2 operator-(const Vec2& v) const {
			return Vec2(*this) -= v;
		}
		constexpr Vec2 operator*(const Vec2& v) const {
			return Vec2(*this) *= v;
		}
		constexpr Vec2 operator/(const Vec2& v) const {
			return Vec2(*this) /= v;
		}
		constexpr Vec2 operator+(LD n) const {
			return Vec2(*this) += n;
		}
		constexpr Vec2 operator-(LD n) const {
			return Vec2(*this) -= n;
		}
		constexpr Vec2 operator*(LD n) const {
			return Vec2(*this) *= n;
		}
		constexpr Vec2 operator/(LD n) const {
			return Vec2(*this) /= n;
		}
		constexpr Vec2& operator+=(const Vec2& v) {
			x += v.x;
			y += v.y;
			return *this;
		}
		constexpr Vec2& operator-=(const Vec2& v) {
			x -= v.x;
			y -= v.y;
			return *this;
		}
		constexpr Vec2& operator*=(const Vec2& v) {
			x *= v.x;
			y *= v.y;
			return *this;
		}
		constexpr Vec2& operator/=(const Vec2& v) {
			x /= v.x;
			y /= v.y;
			return *this;
		}
		constexpr Vec2& operator+=(LD n) {
			x += n;
			y += n;
			return *this;
		}
		constexpr Vec2& operator-=(LD n) {
			x -= n;
			y -= n;
			return *this;
		}
		constexpr Vec2& operator*=(LD n) {
			x *= n;
			y *= n;
			return *this;
		}
		constexpr Vec2& operator/=(LD n) {
			x /= n;
			y /= n;
			return *this;
		}
		constexpr LD operator[](size_t i) const {
			return i == 0 ? x : i == 1 ? y : 0;
		}
		constexpr std::pair<LD, LD> pair() const {
			return {x, y};
		}
		LD manhattan(const Vec2& v) const {
			return std::abs(x - v.x) + std::abs(y - v.y);
		}
		constexpr LD length_square() const {
			return dot(*this);
		}
		LD length() const {
			return std::sqrt(length_square());
		}
		// 内積
		constexpr LD dot(const Vec2& v) const {
			return x * v.x + y * v.y;
		}
		// 外積
		constexpr LD cross(const Vec2& v) const {
			return x * v.y - y * v.x;
		}
		// 正規化（長さを1にした）ベクトル
		Vec2 normalized() const {
			return *this / length();
		}
		// 原点中心に rad 回転した座標
		Vec2 rotation(LD rad) const {
			LD c = std::cos(rad), s = std::sin(rad);
			return {x * c - y * s, x * s + y * c};
		}
		// 原点中心の円上に乗っているとしたときの偏角
		LD angle() const {
			return std::atan2(y, x);
		}
		// 正射影
		Vec2 projection(const Line& l) const;
		// 鏡映変換
		Vec2 reflection(const Line& l) const;
		constexpr Vec2 rotate90() const {
			return {y, -x};
		}
		constexpr Vec2 rotate180() const {
			return {-x, -y};
		}
		constexpr Vec2 rotate270() const {
			return {-y, x};
		}
		friend std::ostream& operator<<(std::ostream& os, const Vec2& v) {
			return os << '(' << v.x << ", " << v.y << ')';
		}
		friend std::istream& operator>>(std::istream& is, Vec2& v) {
			return is >> v.x >> v.y;
		}
	};

}  // namespace Geometric
#line 6 "Geometry/Line.hpp"
#include <tuple>
#line 8 "Geometry/Line.hpp"

namespace Geometric {

	namespace internal {
		struct LineBase {
		protected:
			constexpr LineBase() = default;
			constexpr LineBase(const Vec2& _begin, const Vec2& _end)
			    : begin(_begin), end(_end) {}
			constexpr LineBase(LD begin_x, LD begin_y, LD end_x, LD end_y)
			    : begin(begin_x, begin_y), end(end_x, end_y) {}

		public:
			Vec2 begin, end;
			constexpr LineBase operator+(const Vec2& v) {
				return LineBase(*this) += v;
			}
			constexpr LineBase operator-(const Vec2& v) {
				return LineBase(*this) -= v;
			}
			constexpr LineBase& operator+=(const Vec2& v) {
				begin += v;
				end += v;
				return *this;
			}
			constexpr LineBase& operator-=(const Vec2& v) {
				begin -= v;
				end -= v;
				return *this;
			}
			constexpr Vec2 vec() const {
				return end - begin;
			}
			constexpr Vec2 counter_vec() const {
				return begin - end;
			}
			// 平行判定
			constexpr bool is_parallel(const LineBase& l) const {
				return sgn(vec().cross(l.vec())) == 0;
			}
			// 直交判定
			constexpr bool is_orthogonal(const LineBase& l) const {
				return sgn(vec().dot(l.vec())) == 0;
			}
			friend std::ostream& operator<<(std::ostream& os, const LineBase& l) {
				return os << '(' << l.begin << ", " << l.end << ')';
			}
			friend std::istream& operator>>(std::istream& is, LineBase& l) {
				return is >> l.begin >> l.end;
			}
		};
	}  // namespace internal

	struct Line : internal::LineBase {
		constexpr Line() = default;
		constexpr Line(const Vec2& _begin, const Vec2& _end) : LineBase(_begin, _end) {}
		constexpr Line(LD begin_x, LD begin_y, LD end_x, LD end_y)
		    : LineBase(begin_x, begin_y, end_x, end_y) {}
		constexpr Line(const LineBase& l) : LineBase(l) {}
		// ax + by + c = 0 の式に変形する
		std::tuple<LD, LD, LD> abc() const {
			if (sgn(begin.x - end.x) == 0) {
				return {1, 0, -begin.x};
			} else {
				LD slope = (end.y - begin.y) / (end.x - begin.x);
				return {slope, -1, begin.y - begin.x * slope};
			}
		}
	};

	struct Segment : internal::LineBase {
		constexpr Segment() = default;
		constexpr Segment(const Vec2& _begin, const Vec2& _end) : LineBase(_begin, _end) {}
		constexpr Segment(LD begin_x, LD begin_y, LD end_x, LD end_y)
		    : LineBase(begin_x, begin_y, end_x, end_y) {}
		constexpr Segment(const LineBase& l) : LineBase(l) {}
	};

}  // namespace Geometric

Back to top page