circle_geometry.hpp¶
求圆与圆/直线交点、切点、公切线和三点外接圆；适合圆相关构造题。
Complexity: Time: O(1) per primitive. Space: O(1), excluding returned points.
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(1) per primitive.
/// Space: O(1), excluding returned points.
#include "noya/geometry_base.hpp"
#include <algorithm>
#include <cassert>
#include <cmath>
#include <optional>
#include <utility>
#include <vector>
namespace noya {
namespace circle_geometry_internal {
template <class T> point<long double> cast_point(const point<T> &val) {
return {static_cast<long double>(val.x), static_cast<long double>(val.y)};
}
inline point<long double> perpendicular(const point<long double> &val) {
return {-val.y, val.x};
}
inline bool close_points(const point<long double> &lhs,
const point<long double> &rhs, long double eps) {
return norm2(lhs - rhs) <= eps * eps;
}
} // namespace circle_geometry_internal
/// @brief Intersect two circles: nullopt means coincident circles, while a
/// vector of size 0, 1, or 2 represents no, tangent, or two intersections.
template <class FirstReal, class SecondReal>
std::optional<std::vector<point<long double>>>
circle_intersections(const circle<FirstReal> &lhs,
const circle<SecondReal> &rhs, long double eps = 1e-12L) {
assert(lhs.r1 >= FirstReal{} && rhs.r1 >= SecondReal{});
using circle_geometry_internal::cast_point;
using circle_geometry_internal::perpendicular;
point<long double> o1 = cast_point(lhs.o);
point<long double> o2 = cast_point(rhs.o);
point<long double> dlt = o2 - o1;
long double d2 = norm2(dlt);
long double r1 = static_cast<long double>(lhs.r1);
long double r2 = static_cast<long double>(rhs.r1);
long double scl = std::max({1.0L, r1, r2, std::sqrt(d2)});
long double tol = eps * scl;
if (d2 <= tol * tol) {
if (std::abs(r1 - r2) <= tol) {
return std::nullopt;
}
return std::vector<point<long double>>{};
}
long double cd = std::sqrt(d2);
if (cd > r1 + r2 + tol || cd < std::abs(r1 - r2) - tol) {
return std::vector<point<long double>>{};
}
long double len = (d2 + r1 * r1 - r2 * r2) / (2 * cd);
long double h2 = r1 * r1 - len * len;
if (h2 < 0) {
h2 = 0;
}
point<long double> dir = dlt / cd;
point<long double> mid = o1 + dir * len;
if (h2 <= tol * tol) {
return std::vector<point<long double>>{mid};
}
point<long double> off = perpendicular(dir) * std::sqrt(h2);
return std::vector<point<long double>>{mid + off, mid - off};
}
/// @brief Intersect an infinite line through first and second with a circle,
/// returning zero, one, or two points.
template <class PointReal, class CircleReal>
std::vector<point<long double>> line_circle_intersections(
const point<PointReal> &lhs, const point<PointReal> &rhs,
const circle<CircleReal> &val, long double eps = 1e-12L) {
assert(val.r1 >= CircleReal{});
using circle_geometry_internal::cast_point;
point<long double> a = cast_point(lhs);
point<long double> b = cast_point(rhs);
point<long double> o = cast_point(val.o);
point<long double> dir = b - a;
long double ls = norm2(dir);
assert(ls > 0);
long double pro = dot(o - a, dir) / ls;
point<long double> cls = a + dir * pro;
long double r = static_cast<long double>(val.r1);
long double rem = r * r - norm2(cls - o);
long double tol = eps * std::max(1.0L, r);
if (rem < -tol * tol) {
return {};
}
if (rem <= tol * tol) {
return {cls};
}
point<long double> off = dir * std::sqrt(rem / ls);
return {cls - off, cls + off};
}
/// @brief Return the tangent points from an external/on-circle point; an
/// interior point has no tangent point.
template <class PointReal, class CircleReal>
std::vector<point<long double>>
point_circle_tangents(const point<PointReal> &ext,
const circle<CircleReal> &val, long double eps = 1e-12L) {
assert(val.r1 > CircleReal{});
using circle_geometry_internal::cast_point;
using circle_geometry_internal::perpendicular;
point<long double> o = cast_point(val.o);
point<long double> rel = cast_point(ext) - o;
long double d2 = norm2(rel);
long double r = static_cast<long double>(val.r1);
long double r21 = r * r;
long double tol = eps * std::max(1.0L, r21);
if (d2 < r21 - tol) {
return {};
}
if (std::abs(d2 - r21) <= tol) {
return {cast_point(ext)};
}
long double len = r21 / d2;
long double crs = r * std::sqrt(d2 - r21) / d2;
point<long double> mid = o + rel * len;
point<long double> off = perpendicular(rel) * crs;
return {mid + off, mid - off};
}
/// @brief Return all common tangents as pairs of contact points; nullopt means
/// equal coincident circles and therefore infinitely many tangents.
template <class FirstReal, class SecondReal>
std::optional<std::vector<std::pair<point<long double>, point<long double>>>>
common_circle_tangents(const circle<FirstReal> &lhs,
const circle<SecondReal> &rhs,
long double eps = 1e-12L) {
assert(lhs.r1 >= FirstReal{} && rhs.r1 >= SecondReal{});
using circle_geometry_internal::cast_point;
using circle_geometry_internal::close_points;
using circle_geometry_internal::perpendicular;
point<long double> o1 = cast_point(lhs.o);
point<long double> o2 = cast_point(rhs.o);
point<long double> dlt = o2 - o1;
long double d2 = norm2(dlt);
long double r1 = static_cast<long double>(lhs.r1);
long double r2 = static_cast<long double>(rhs.r1);
long double scl = std::max({1.0L, r1, r2, std::sqrt(d2)});
long double tol = eps * scl;
if (d2 <= tol * tol) {
if (std::abs(r1 - r2) <= tol) {
return std::nullopt;
}
return std::vector<std::pair<point<long double>, point<long double>>>{};
}
std::vector<std::pair<point<long double>, point<long double>>> res;
for (int sgn : {-1, 1}) {
long double sr2 = sgn * r2;
long double dr = r1 - sr2;
long double h2 = d2 - dr * dr;
if (h2 < -tol * tol) {
continue;
}
h2 = std::max(0.0L, h2);
long double h = std::sqrt(h2);
for (int sd : {-1, 1}) {
point<long double> nm = (dlt * dr + perpendicular(dlt) * (h * sd)) / d2;
std::pair<point<long double>, point<long double>> tg = {o1 + nm * r1,
o2 + nm * sr2};
bool dup = false;
for (const auto &old : res) {
dup |= close_points(old.first, tg.first, tol) &&
close_points(old.second, tg.second, tol);
}
if (!dup) {
res.push_back(tg);
}
if (h == 0) {
break;
}
}
}
return res;
}
/// @brief Return the circumcircle through three non-collinear points, or
/// nullopt when the points are collinear.
template <class T>
std::optional<circle<long double>>
circumcircle(const point<T> &lhs, const point<T> &rhs, const point<T> &z,
long double eps = 1e-18L) {
using circle_geometry_internal::cast_point;
point<long double> a = cast_point(lhs);
point<long double> b = cast_point(rhs);
point<long double> c = cast_point(z);
long double den = 2 * cross(a, b, c);
if (std::abs(den) <= eps) {
return std::nullopt;
}
long double s1 = norm2(a);
long double s2 = norm2(b);
long double s3 = norm2(c);
point<long double> o{
(s1 * (b.y - c.y) + s2 * (c.y - a.y) + s3 * (a.y - b.y)) / den,
(s1 * (c.x - b.x) + s2 * (a.x - c.x) + s3 * (b.x - a.x)) / den};
return circle<long double>{o, distance(o, a)};
}
} // namespace noya
#ifndef NOYA_CIRCLE_GEOMETRY_HPP
#define NOYA_CIRCLE_GEOMETRY_HPP 1
/// @complexity Time: O(1) per primitive.
/// Space: O(1), excluding returned points.
#include "noya/geometry_base.hpp"
#include <algorithm>
#include <cassert>
#include <cmath>
#include <optional>
#include <utility>
#include <vector>
namespace noya {
namespace circle_geometry_internal {
template <class T> point<long double> cast_point(const point<T> &val) {
return {static_cast<long double>(val.x), static_cast<long double>(val.y)};
}
inline point<long double> perpendicular(const point<long double> &val) {
return {-val.y, val.x};
}
inline bool close_points(const point<long double> &lhs,
const point<long double> &rhs, long double eps) {
return norm2(lhs - rhs) <= eps * eps;
}
} // namespace circle_geometry_internal
/// @brief Intersect two circles: nullopt means coincident circles, while a
/// vector of size 0, 1, or 2 represents no, tangent, or two intersections.
template <class FirstReal, class SecondReal>
std::optional<std::vector<point<long double>>>
circle_intersections(const circle<FirstReal> &lhs,
const circle<SecondReal> &rhs, long double eps = 1e-12L) {
assert(lhs.r1 >= FirstReal{} && rhs.r1 >= SecondReal{});
using circle_geometry_internal::cast_point;
using circle_geometry_internal::perpendicular;
point<long double> o1 = cast_point(lhs.o);
point<long double> o2 = cast_point(rhs.o);
point<long double> dlt = o2 - o1;
long double d2 = norm2(dlt);
long double r1 = static_cast<long double>(lhs.r1);
long double r2 = static_cast<long double>(rhs.r1);
long double scl = std::max({1.0L, r1, r2, std::sqrt(d2)});
long double tol = eps * scl;
if (d2 <= tol * tol) {
if (std::abs(r1 - r2) <= tol) {
return std::nullopt;
}
return std::vector<point<long double>>{};
}
long double cd = std::sqrt(d2);
if (cd > r1 + r2 + tol || cd < std::abs(r1 - r2) - tol) {
return std::vector<point<long double>>{};
}
long double len = (d2 + r1 * r1 - r2 * r2) / (2 * cd);
long double h2 = r1 * r1 - len * len;
if (h2 < 0) {
h2 = 0;
}
point<long double> dir = dlt / cd;
point<long double> mid = o1 + dir * len;
if (h2 <= tol * tol) {
return std::vector<point<long double>>{mid};
}
point<long double> off = perpendicular(dir) * std::sqrt(h2);
return std::vector<point<long double>>{mid + off, mid - off};
}
/// @brief Intersect an infinite line through first and second with a circle,
/// returning zero, one, or two points.
template <class PointReal, class CircleReal>
std::vector<point<long double>> line_circle_intersections(
const point<PointReal> &lhs, const point<PointReal> &rhs,
const circle<CircleReal> &val, long double eps = 1e-12L) {
assert(val.r1 >= CircleReal{});
using circle_geometry_internal::cast_point;
point<long double> a = cast_point(lhs);
point<long double> b = cast_point(rhs);
point<long double> o = cast_point(val.o);
point<long double> dir = b - a;
long double ls = norm2(dir);
assert(ls > 0);
long double pro = dot(o - a, dir) / ls;
point<long double> cls = a + dir * pro;
long double r = static_cast<long double>(val.r1);
long double rem = r * r - norm2(cls - o);
long double tol = eps * std::max(1.0L, r);
if (rem < -tol * tol) {
return {};
}
if (rem <= tol * tol) {
return {cls};
}
point<long double> off = dir * std::sqrt(rem / ls);
return {cls - off, cls + off};
}
/// @brief Return the tangent points from an external/on-circle point; an
/// interior point has no tangent point.
template <class PointReal, class CircleReal>
std::vector<point<long double>>
point_circle_tangents(const point<PointReal> &ext,
const circle<CircleReal> &val, long double eps = 1e-12L) {
assert(val.r1 > CircleReal{});
using circle_geometry_internal::cast_point;
using circle_geometry_internal::perpendicular;
point<long double> o = cast_point(val.o);
point<long double> rel = cast_point(ext) - o;
long double d2 = norm2(rel);
long double r = static_cast<long double>(val.r1);
long double r21 = r * r;
long double tol = eps * std::max(1.0L, r21);
if (d2 < r21 - tol) {
return {};
}
if (std::abs(d2 - r21) <= tol) {
return {cast_point(ext)};
}
long double len = r21 / d2;
long double crs = r * std::sqrt(d2 - r21) / d2;
point<long double> mid = o + rel * len;
point<long double> off = perpendicular(rel) * crs;
return {mid + off, mid - off};
}
/// @brief Return all common tangents as pairs of contact points; nullopt means
/// equal coincident circles and therefore infinitely many tangents.
template <class FirstReal, class SecondReal>
std::optional<std::vector<std::pair<point<long double>, point<long double>>>>
common_circle_tangents(const circle<FirstReal> &lhs,
const circle<SecondReal> &rhs,
long double eps = 1e-12L) {
assert(lhs.r1 >= FirstReal{} && rhs.r1 >= SecondReal{});
using circle_geometry_internal::cast_point;
using circle_geometry_internal::close_points;
using circle_geometry_internal::perpendicular;
point<long double> o1 = cast_point(lhs.o);
point<long double> o2 = cast_point(rhs.o);
point<long double> dlt = o2 - o1;
long double d2 = norm2(dlt);
long double r1 = static_cast<long double>(lhs.r1);
long double r2 = static_cast<long double>(rhs.r1);
long double scl = std::max({1.0L, r1, r2, std::sqrt(d2)});
long double tol = eps * scl;
if (d2 <= tol * tol) {
if (std::abs(r1 - r2) <= tol) {
return std::nullopt;
}
return std::vector<std::pair<point<long double>, point<long double>>>{};
}
std::vector<std::pair<point<long double>, point<long double>>> res;
for (int sgn : {-1, 1}) {
long double sr2 = sgn * r2;
long double dr = r1 - sr2;
long double h2 = d2 - dr * dr;
if (h2 < -tol * tol) {
continue;
}
h2 = std::max(0.0L, h2);
long double h = std::sqrt(h2);
for (int sd : {-1, 1}) {
point<long double> nm = (dlt * dr + perpendicular(dlt) * (h * sd)) / d2;
std::pair<point<long double>, point<long double>> tg = {o1 + nm * r1,
o2 + nm * sr2};
bool dup = false;
for (const auto &old : res) {
dup |= close_points(old.first, tg.first, tol) &&
close_points(old.second, tg.second, tol);
}
if (!dup) {
res.push_back(tg);
}
if (h == 0) {
break;
}
}
}
return res;
}
/// @brief Return the circumcircle through three non-collinear points, or
/// nullopt when the points are collinear.
template <class T>
std::optional<circle<long double>>
circumcircle(const point<T> &lhs, const point<T> &rhs, const point<T> &z,
long double eps = 1e-18L) {
using circle_geometry_internal::cast_point;
point<long double> a = cast_point(lhs);
point<long double> b = cast_point(rhs);
point<long double> c = cast_point(z);
long double den = 2 * cross(a, b, c);
if (std::abs(den) <= eps) {
return std::nullopt;
}
long double s1 = norm2(a);
long double s2 = norm2(b);
long double s3 = norm2(c);
point<long double> o{
(s1 * (b.y - c.y) + s2 * (c.y - a.y) + s3 * (a.y - b.y)) / den,
(s1 * (c.x - b.x) + s2 * (a.x - c.x) + s3 * (b.x - a.x)) / den};
return circle<long double>{o, distance(o, a)};
}
} // namespace noya
#endif // NOYA_CIRCLE_GEOMETRY_HPP
#include <algorithm>
#include <cassert>
#include <cmath>
#include <optional>
#include <utility>
#include <vector>
/// @complexity Time: O(1) per primitive.
/// Space: O(1), excluding returned points.
/// @complexity Time: O(1) per primitive; O(n log n) for convex hull.
/// Space: O(1) per primitive and O(n) for hull construction.
namespace noya {
/// @brief Two-dimensional point with vector arithmetic and lexicographic order.
template <class T> struct point {
T x{};
T y{};
point() = default;
point(T x_, T y_) : x(x_), y(y_) {}
point &operator+=(const point &rhs) {
x += rhs.x;
y += rhs.y;
return *this;
}
point &operator-=(const point &rhs) {
x -= rhs.x;
y -= rhs.y;
return *this;
}
point &operator*=(const T &scl) {
x *= scl;
y *= scl;
return *this;
}
point &operator/=(const T &scl) {
x /= scl;
y /= scl;
return *this;
}
friend point operator+(point l, const point &r) { return l += r; }
friend point operator-(point l, const point &r) { return l -= r; }
friend point operator*(point val, const T &scl) { return val *= scl; }
friend point operator*(const T &scl, point val) { return val *= scl; }
friend point operator/(point val, const T &scl) { return val /= scl; }
friend bool operator==(const point &, const point &) = default;
friend bool operator<(const point &l, const point &r) {
return l.x < r.x || (l.x == r.x && l.y < r.y);
}
};
/// @brief Circle represented by a center and a nonnegative radius.
template <class Real> struct circle {
point<Real> o;
Real r1{};
};
/// @brief Return the dot product of two vectors.
template <class T> T dot(const point<T> &a, const point<T> &b) {
return a.x * b.x + a.y * b.y;
}
/// @brief Return the signed cross product of two vectors.
template <class T> T cross(const point<T> &a, const point<T> &b) {
return a.x * b.y - a.y * b.x;
}
/// @brief Return cross(a - o1, b - o1).
template <class T>
T cross(const point<T> &o1, const point<T> &a, const point<T> &b) {
return cross(a - o1, b - o1);
}
/// @brief Return the squared Euclidean norm.
template <class T> T norm2(const point<T> &val) { return dot(val, val); }
/// @brief Compare a value with zero using an optional absolute tolerance.
template <class T> int sign(const T &val, const T &eps = T{}) {
return (val > eps) - (val < -eps);
}
/// @brief Return -1, 0, or 1 for a clockwise, collinear, or counter-clockwise
/// turn.
template <class T>
int orientation(const point<T> &a, const point<T> &b, const point<T> &c,
const T &eps = T{}) {
return sign(cross(a, b, c), eps);
}
/// @brief Test whether p lies on the closed segment [a, b].
template <class T>
bool on_segment(const point<T> &p, const point<T> &a, const point<T> &b,
const T &eps = T{}) {
if (orientation(a, b, p, eps) != 0) {
return false;
}
return std::min(a.x, b.x) - eps <= p.x && p.x <= std::max(a.x, b.x) + eps &&
std::min(a.y, b.y) - eps <= p.y && p.y <= std::max(a.y, b.y) + eps;
}
/// @brief Test whether the closed segments [a, b] and [c, d] intersect.
template <class T>
bool segments_intersect(const point<T> &a, const point<T> &b, const point<T> &c,
const point<T> &d, const T &eps = T{}) {
int s1 = orientation(a, b, c, eps);
int s2 = orientation(a, b, d, eps);
int s3 = orientation(c, d, a, eps);
int s4 = orientation(c, d, b, eps);
if (s1 == 0 && on_segment(c, a, b, eps)) {
return true;
}
if (s2 == 0 && on_segment(d, a, b, eps)) {
return true;
}
if (s3 == 0 && on_segment(a, c, d, eps)) {
return true;
}
if (s4 == 0 && on_segment(b, c, d, eps)) {
return true;
}
return s1 * s2 < 0 && s3 * s4 < 0;
}
/// @brief Intersect the infinite lines through (a, b) and (c, d), returning
/// nullopt when they are parallel or coincident.
template <class T>
std::optional<point<long double>>
line_intersection(const point<T> &a, const point<T> &b, const point<T> &c,
const point<T> &d, long double eps = 0) {
point<long double> lhs{static_cast<long double>(a.x),
static_cast<long double>(a.y)};
point<long double> b1{static_cast<long double>(b.x),
static_cast<long double>(b.y)};
point<long double> z{static_cast<long double>(c.x),
static_cast<long double>(c.y)};
point<long double> d1{static_cast<long double>(d.x),
static_cast<long double>(d.y)};
point<long double> da = b1 - lhs;
point<long double> db = d1 - z;
long double den = cross(da, db);
if (std::abs(den) <= eps) {
return std::nullopt;
}
long double rat = cross(z - lhs, db) / den;
return lhs + da * rat;
}
/// @brief Return the convex hull in counter-clockwise order without repetition.
template <class T>
std::vector<point<T>> convex_hull(std::vector<point<T>> pt, bool kc = false) {
std::sort(pt.begin(), pt.end());
pt.erase(std::unique(pt.begin(), pt.end()), pt.end());
if (pt.size() <= 1) {
return pt;
}
bool col = true;
for (int i = 2; i < int(pt.size()); i++) {
col &= orientation(pt[0], pt[1], pt[i]) == 0;
}
if (kc && col) {
return pt;
}
std::vector<point<T>> lo, hi;
for (const point<T> &p : pt) {
while (lo.size() >= 2) {
int rot = orientation(lo[lo.size() - 2], lo.back(), p);
if (rot > 0 || (kc && rot == 0)) {
break;
}
lo.pop_back();
}
lo.push_back(p);
}
for (auto it = pt.rbegin(); it != pt.rend(); ++it) {
while (hi.size() >= 2) {
int rot = orientation(hi[hi.size() - 2], hi.back(), *it);
if (rot > 0 || (kc && rot == 0)) {
break;
}
hi.pop_back();
}
hi.push_back(*it);
}
lo.pop_back();
hi.pop_back();
lo.insert(lo.end(), hi.begin(), hi.end());
return lo;
}
/// @brief Return twice the signed area of a polygon.
template <class T> T polygon_area2(const std::vector<point<T>> &pg) {
T res{};
for (int i = 0; i < int(pg.size()); i++) {
res += cross(pg[i], pg[(i + 1) % pg.size()]);
}
return res;
}
/// @brief Classify a point relative to a polygon: -1 outside, 0 boundary, 1
/// inside.
template <class T>
int point_in_polygon(const point<T> &p, const std::vector<point<T>> &pg) {
bool in = false;
for (int i = 0; i < int(pg.size()); i++) {
point<T> a = pg[i];
point<T> b = pg[(i + 1) % pg.size()];
if (on_segment(p, a, b)) {
return 0;
}
if (a.y <= p.y && p.y < b.y && orientation(a, b, p) > 0) {
in = !in;
}
if (b.y <= p.y && p.y < a.y && orientation(a, b, p) < 0) {
in = !in;
}
}
return in ? 1 : -1;
}
/// @brief Return the Euclidean distance between two points.
template <class T> long double distance(const point<T> &a, const point<T> &b) {
return std::hypot(
static_cast<long double>(a.x) - static_cast<long double>(b.x),
static_cast<long double>(a.y) - static_cast<long double>(b.y));
}
} // namespace noya
namespace noya {
namespace circle_geometry_internal {
template <class T> point<long double> cast_point(const point<T> &val) {
return {static_cast<long double>(val.x), static_cast<long double>(val.y)};
}
inline point<long double> perpendicular(const point<long double> &val) {
return {-val.y, val.x};
}
inline bool close_points(const point<long double> &lhs,
const point<long double> &rhs, long double eps) {
return norm2(lhs - rhs) <= eps * eps;
}
} // namespace circle_geometry_internal
/// @brief Intersect two circles: nullopt means coincident circles, while a
/// vector of size 0, 1, or 2 represents no, tangent, or two intersections.
template <class FirstReal, class SecondReal>
std::optional<std::vector<point<long double>>>
circle_intersections(const circle<FirstReal> &lhs,
const circle<SecondReal> &rhs, long double eps = 1e-12L) {
assert(lhs.r1 >= FirstReal{} && rhs.r1 >= SecondReal{});
using circle_geometry_internal::cast_point;
using circle_geometry_internal::perpendicular;
point<long double> o1 = cast_point(lhs.o);
point<long double> o2 = cast_point(rhs.o);
point<long double> dlt = o2 - o1;
long double d2 = norm2(dlt);
long double r1 = static_cast<long double>(lhs.r1);
long double r2 = static_cast<long double>(rhs.r1);
long double scl = std::max({1.0L, r1, r2, std::sqrt(d2)});
long double tol = eps * scl;
if (d2 <= tol * tol) {
if (std::abs(r1 - r2) <= tol) {
return std::nullopt;
}
return std::vector<point<long double>>{};
}
long double cd = std::sqrt(d2);
if (cd > r1 + r2 + tol || cd < std::abs(r1 - r2) - tol) {
return std::vector<point<long double>>{};
}
long double len = (d2 + r1 * r1 - r2 * r2) / (2 * cd);
long double h2 = r1 * r1 - len * len;
if (h2 < 0) {
h2 = 0;
}
point<long double> dir = dlt / cd;
point<long double> mid = o1 + dir * len;
if (h2 <= tol * tol) {
return std::vector<point<long double>>{mid};
}
point<long double> off = perpendicular(dir) * std::sqrt(h2);
return std::vector<point<long double>>{mid + off, mid - off};
}
/// @brief Intersect an infinite line through first and second with a circle,
/// returning zero, one, or two points.
template <class PointReal, class CircleReal>
std::vector<point<long double>> line_circle_intersections(
const point<PointReal> &lhs, const point<PointReal> &rhs,
const circle<CircleReal> &val, long double eps = 1e-12L) {
assert(val.r1 >= CircleReal{});
using circle_geometry_internal::cast_point;
point<long double> a = cast_point(lhs);
point<long double> b = cast_point(rhs);
point<long double> o = cast_point(val.o);
point<long double> dir = b - a;
long double ls = norm2(dir);
assert(ls > 0);
long double pro = dot(o - a, dir) / ls;
point<long double> cls = a + dir * pro;
long double r = static_cast<long double>(val.r1);
long double rem = r * r - norm2(cls - o);
long double tol = eps * std::max(1.0L, r);
if (rem < -tol * tol) {
return {};
}
if (rem <= tol * tol) {
return {cls};
}
point<long double> off = dir * std::sqrt(rem / ls);
return {cls - off, cls + off};
}
/// @brief Return the tangent points from an external/on-circle point; an
/// interior point has no tangent point.
template <class PointReal, class CircleReal>
std::vector<point<long double>>
point_circle_tangents(const point<PointReal> &ext,
const circle<CircleReal> &val, long double eps = 1e-12L) {
assert(val.r1 > CircleReal{});
using circle_geometry_internal::cast_point;
using circle_geometry_internal::perpendicular;
point<long double> o = cast_point(val.o);
point<long double> rel = cast_point(ext) - o;
long double d2 = norm2(rel);
long double r = static_cast<long double>(val.r1);
long double r21 = r * r;
long double tol = eps * std::max(1.0L, r21);
if (d2 < r21 - tol) {
return {};
}
if (std::abs(d2 - r21) <= tol) {
return {cast_point(ext)};
}
long double len = r21 / d2;
long double crs = r * std::sqrt(d2 - r21) / d2;
point<long double> mid = o + rel * len;
point<long double> off = perpendicular(rel) * crs;
return {mid + off, mid - off};
}
/// @brief Return all common tangents as pairs of contact points; nullopt means
/// equal coincident circles and therefore infinitely many tangents.
template <class FirstReal, class SecondReal>
std::optional<std::vector<std::pair<point<long double>, point<long double>>>>
common_circle_tangents(const circle<FirstReal> &lhs,
const circle<SecondReal> &rhs,
long double eps = 1e-12L) {
assert(lhs.r1 >= FirstReal{} && rhs.r1 >= SecondReal{});
using circle_geometry_internal::cast_point;
using circle_geometry_internal::close_points;
using circle_geometry_internal::perpendicular;
point<long double> o1 = cast_point(lhs.o);
point<long double> o2 = cast_point(rhs.o);
point<long double> dlt = o2 - o1;
long double d2 = norm2(dlt);
long double r1 = static_cast<long double>(lhs.r1);
long double r2 = static_cast<long double>(rhs.r1);
long double scl = std::max({1.0L, r1, r2, std::sqrt(d2)});
long double tol = eps * scl;
if (d2 <= tol * tol) {
if (std::abs(r1 - r2) <= tol) {
return std::nullopt;
}
return std::vector<std::pair<point<long double>, point<long double>>>{};
}
std::vector<std::pair<point<long double>, point<long double>>> res;
for (int sgn : {-1, 1}) {
long double sr2 = sgn * r2;
long double dr = r1 - sr2;
long double h2 = d2 - dr * dr;
if (h2 < -tol * tol) {
continue;
}
h2 = std::max(0.0L, h2);
long double h = std::sqrt(h2);
for (int sd : {-1, 1}) {
point<long double> nm = (dlt * dr + perpendicular(dlt) * (h * sd)) / d2;
std::pair<point<long double>, point<long double>> tg = {o1 + nm * r1,
o2 + nm * sr2};
bool dup = false;
for (const auto &old : res) {
dup |= close_points(old.first, tg.first, tol) &&
close_points(old.second, tg.second, tol);
}
if (!dup) {
res.push_back(tg);
}
if (h == 0) {
break;
}
}
}
return res;
}
/// @brief Return the circumcircle through three non-collinear points, or
/// nullopt when the points are collinear.
template <class T>
std::optional<circle<long double>>
circumcircle(const point<T> &lhs, const point<T> &rhs, const point<T> &z,
long double eps = 1e-18L) {
using circle_geometry_internal::cast_point;
point<long double> a = cast_point(lhs);
point<long double> b = cast_point(rhs);
point<long double> c = cast_point(z);
long double den = 2 * cross(a, b, c);
if (std::abs(den) <= eps) {
return std::nullopt;
}
long double s1 = norm2(a);
long double s2 = norm2(b);
long double s3 = norm2(c);
point<long double> o{
(s1 * (b.y - c.y) + s2 * (c.y - a.y) + s3 * (a.y - b.y)) / den,
(s1 * (c.x - b.x) + s2 * (a.x - c.x) + s3 * (b.x - a.x)) / den};
return circle<long double>{o, distance(o, a)};
}
} // namespace noya