summaryrefslogtreecommitdiff
path: root/lib/maths.h
diff options
context:
space:
mode:
Diffstat (limited to 'lib/maths.h')
-rw-r--r--lib/maths.h517
1 files changed, 415 insertions, 102 deletions
diff --git a/lib/maths.h b/lib/maths.h
index 018ef0e..43d6dcd 100644
--- a/lib/maths.h
+++ b/lib/maths.h
@@ -1,15 +1,24 @@
#pragma once
#include "config/types.h"
+#include <algorithm>
+#include <array>
#include <cmath>
#include <glm/glm.hpp>
#include <glm/gtc/constants.hpp>
#include <numeric>
+#include <optional>
#include <stdexcept>
#include <utility>
+template<typename T>
+concept Arithmetic = std::is_arithmetic_v<T>;
+
+template<Arithmetic T> using CalcType = std::conditional_t<std::is_floating_point_v<T>, T, int64_t>;
+template<Arithmetic T> using DifferenceType = std::conditional_t<std::is_floating_point_v<T>, T, float>;
+
struct Arc : public std::pair<Angle, Angle> {
- template<glm::length_t Lc, glm::length_t Le, typename T, glm::qualifier Q>
+ template<glm::length_t Lc, glm::length_t Le, Arithmetic T, glm::qualifier Q = glm::defaultp>
requires(Lc >= 2, Le >= 2)
Arc(const glm::vec<Lc, T, Q> & centre, const glm::vec<Le, T, Q> & e0p, const glm::vec<Le, T, Q> & e1p) :
Arc {RelativePosition2D {e0p.xy() - centre.xy()}, RelativePosition2D {e1p.xy() - centre.xy()}}
@@ -17,22 +26,42 @@ struct Arc : public std::pair<Angle, Angle> {
}
Arc(const RelativePosition2D & dir0, const RelativePosition2D & dir1);
- Arc(const Angle angb, const Angle anga);
+ Arc(Angle anga, Angle angb);
auto
- operator[](bool i) const
+ operator[](bool getSecond) const
{
- return i ? second : first;
+ return getSecond ? second : first;
}
- [[nodiscard]] constexpr inline float
+ [[nodiscard]] constexpr float
length() const
{
return second - first;
}
};
-constexpr const RelativePosition3D up {0, 0, 1};
+template<typename T, glm::qualifier Q = glm::defaultp> struct ArcSegment : public Arc {
+ using PointType = glm::vec<2, T, Q>;
+
+ constexpr ArcSegment(PointType centre, PointType ep0, PointType ep1);
+
+ PointType centre;
+ PointType ep0;
+ PointType ep1;
+ RelativeDistance radius;
+
+ [[nodiscard]] constexpr std::optional<std::pair<glm::vec<2, T, Q>, Angle>> crossesLineAt(
+ const glm::vec<2, T, Q> & lineStart, const glm::vec<2, T, Q> & lineEnd) const;
+
+ [[nodiscard]] constexpr bool
+ angleWithinArc(Angle angle) const
+ {
+ return first <= angle && angle <= second;
+ }
+};
+
+constexpr const RelativePosition3D up {0, 0, 1}; // NOLINT(readability-identifier-length)
constexpr const RelativePosition3D down {0, 0, -1};
constexpr const RelativePosition3D north {0, 1, 0};
constexpr const RelativePosition3D south {0, -1, 0};
@@ -40,158 +69,341 @@ constexpr const RelativePosition3D east {1, 0, 0};
constexpr const RelativePosition3D west {-1, 0, 0};
constexpr auto half_pi {glm::half_pi<float>()};
constexpr auto quarter_pi {half_pi / 2};
-constexpr auto pi {glm::pi<float>()};
+constexpr auto pi {glm::pi<float>()}; // NOLINT(readability-identifier-length)
constexpr auto two_pi {glm::two_pi<float>()};
+constexpr auto degreesToRads = pi / 180.F;
+
+constexpr auto earthMeanRadius = 6371.01F; // In km
+constexpr auto astronomicalUnit = 149597890.F; // In km
template<glm::length_t D>
-constexpr inline GlobalPosition<D>
-operator+(const GlobalPosition<D> & g, const RelativePosition<D> & r)
+constexpr GlobalPosition<D>
+operator+(const GlobalPosition<D> & global, const RelativePosition<D> & relative)
{
- return g + GlobalPosition<D>(glm::round(r));
+ return global + GlobalPosition<D>(glm::round(relative));
}
template<glm::length_t D>
-constexpr inline GlobalPosition<D>
-operator+(const GlobalPosition<D> & g, const CalcPosition<D> & r)
+constexpr GlobalPosition<D>
+operator+(const GlobalPosition<D> & global, const CalcPosition<D> & relative)
{
- return g + GlobalPosition<D>(r);
+ return global + GlobalPosition<D>(relative);
}
template<glm::length_t D>
-constexpr inline GlobalPosition<D>
-operator-(const GlobalPosition<D> & g, const RelativePosition<D> & r)
+constexpr GlobalPosition<D>
+operator-(const GlobalPosition<D> & global, const RelativePosition<D> & relative)
{
- return g - GlobalPosition<D>(glm::round(r));
+ return global - GlobalPosition<D>(glm::round(relative));
}
template<glm::length_t D>
-constexpr inline GlobalPosition<D>
-operator-(const GlobalPosition<D> & g, const CalcPosition<D> & r)
+constexpr GlobalPosition<D>
+operator-(const GlobalPosition<D> & global, const CalcPosition<D> & relative)
{
- return g - GlobalPosition<D>(r);
+ return global - GlobalPosition<D>(relative);
+}
+
+template<glm::length_t D, Arithmetic T, glm::qualifier Q = glm::defaultp>
+using DifferenceVector = glm::vec<D, DifferenceType<T>, Q>;
+
+template<glm::length_t D, Arithmetic T, glm::qualifier Q = glm::defaultp>
+constexpr DifferenceVector<D, T, Q>
+difference(const glm::vec<D, T, Q> & globalA, const glm::vec<D, T, Q> & globalB)
+{
+ return globalA - globalB;
+}
+
+template<glm::length_t D, Arithmetic T, glm::qualifier Q = glm::defaultp>
+using CalcVector = glm::vec<D, CalcType<T>, Q>;
+
+template<glm::length_t D, Arithmetic T, glm::qualifier Q = glm::defaultp>
+constexpr CalcVector<D, T, Q>
+calcDifference(const glm::vec<D, T, Q> & globalA, const glm::vec<D, T, Q> & globalB)
+{
+ return globalA - globalB;
+}
+
+template<glm::length_t D, Arithmetic T, glm::qualifier Q = glm::defaultp>
+constexpr auto
+distance(const glm::vec<D, T, Q> & pointA, const glm::vec<D, T, Q> & pointB)
+{
+ return glm::length(difference(pointA, pointB));
}
glm::mat4 flat_orientation(const Rotation3D & diff);
-// C++ wrapper for C's sincosf, but with references, not pointers
-inline auto
-sincosf(float a, float & s, float & c)
+namespace {
+ // Helpers
+ // C++ wrapper for C's sincosf, but with references, not pointers
+ template<std::floating_point T>
+ constexpr void
+ sincos(T angle, T & sinOut, T & cosOut)
+ {
+ if consteval {
+ sinOut = std::sin(angle);
+ cosOut = std::cos(angle);
+ }
+ else {
+ if constexpr (std::is_same_v<T, float>) {
+ ::sincosf(angle, &sinOut, &cosOut);
+ }
+ else if constexpr (std::is_same_v<T, double>) {
+ ::sincos(angle, &sinOut, &cosOut);
+ }
+ else if constexpr (std::is_same_v<T, long double>) {
+ ::sincosl(angle, &sinOut, &cosOut);
+ }
+ }
+ }
+
+ template<std::floating_point T, glm::qualifier Q = glm::qualifier::defaultp>
+ constexpr auto
+ sincos(const T angle)
+ {
+ glm::vec<2, T, Q> sincosOut {};
+ sincos(angle, sincosOut.x, sincosOut.y);
+ return sincosOut;
+ }
+
+ // Helper to lookup into a matrix given an xy vector coordinate
+ template<glm::length_t C, glm::length_t R, Arithmetic T, glm::qualifier Q = glm::defaultp,
+ std::integral I = glm::length_t>
+ constexpr auto &
+ operator^(glm::mat<C, R, T, Q> & matrix, const glm::vec<2, I> rowCol)
+ {
+ return matrix[rowCol.x][rowCol.y];
+ }
+
+ // Create a matrix for the angle, given the targets into the matrix
+ template<glm::length_t D, std::floating_point T, glm::qualifier Q = glm::defaultp, std::integral I = glm::length_t>
+ constexpr auto
+ rotation(const T angle, const glm::vec<2, I> cos1, const glm::vec<2, I> sin1, const glm::vec<2, I> cos2,
+ const glm::vec<2, I> negSin1)
+ {
+ glm::mat<D, D, T, Q> out(1);
+ sincos(angle, out ^ sin1, out ^ cos1);
+ out ^ cos2 = out ^ cos1;
+ out ^ negSin1 = -(out ^ sin1);
+ return out;
+ }
+}
+
+// Create a flat transformation matrix
+template<glm::length_t D = 2, glm::qualifier Q = glm::qualifier::defaultp, std::floating_point T>
+ requires(D >= 2)
+constexpr auto
+rotate_flat(const T angle)
{
- return sincosf(a, &s, &c);
+ return rotation<D, T, Q>(angle, {0, 0}, {0, 1}, {1, 1}, {1, 0});
}
-inline Rotation2D
-sincosf(float a)
+// Create a yaw transformation matrix
+template<glm::length_t D = 3, glm::qualifier Q = glm::qualifier::defaultp, std::floating_point T>
+ requires(D >= 2)
+constexpr auto
+rotate_yaw(const T angle)
{
- Rotation2D sc;
- sincosf(a, sc.x, sc.y);
- return sc;
+ return rotation<D, T, Q>(angle, {0, 0}, {1, 0}, {1, 1}, {0, 1});
}
-glm::mat2 rotate_flat(float);
-glm::mat4 rotate_roll(float);
-glm::mat4 rotate_yaw(float);
-glm::mat4 rotate_pitch(float);
-glm::mat4 rotate_yp(Rotation2D);
-glm::mat4 rotate_ypr(Rotation3D);
+// Create a roll transformation matrix
+template<glm::length_t D = 3, glm::qualifier Q = glm::qualifier::defaultp, std::floating_point T>
+ requires(D >= 3)
+constexpr auto
+rotate_roll(const T angle)
+{
+ return rotation<D, T, Q>(angle, {0, 0}, {2, 0}, {2, 2}, {0, 2});
+}
-float vector_yaw(const Direction2D & diff);
-float vector_pitch(const Direction3D & diff);
+// Create a pitch transformation matrix
+template<glm::length_t D = 3, glm::qualifier Q = glm::qualifier::defaultp, std::floating_point T>
+ requires(D >= 3)
+constexpr auto
+rotate_pitch(const T angle)
+{
+ return rotation<D, T, Q>(angle, {1, 1}, {1, 2}, {2, 2}, {2, 1});
+}
-template<typename T, glm::qualifier Q>
-glm::vec<2, T, Q>
-vector_normal(const glm::vec<2, T, Q> & v)
+// Create a combined yaw, pitch, roll transformation matrix
+template<glm::length_t D = 3, glm::qualifier Q = glm::qualifier::defaultp, std::floating_point T>
+ requires(D >= 3)
+constexpr auto
+rotate_ypr(const glm::vec<3, T, Q> & angles)
{
- return {-v.y, v.x};
+ return rotate_yaw<D>(angles.y) * rotate_pitch<D>(angles.x) * rotate_roll<D>(angles.z);
+}
+
+template<glm::length_t D = 3, glm::qualifier Q = glm::qualifier::defaultp, std::floating_point T>
+ requires(D >= 3)
+constexpr auto
+rotate_yp(const T yaw, const T pitch)
+{
+ return rotate_yaw<D>(yaw) * rotate_pitch<D>(pitch);
+}
+
+template<glm::length_t D = 3, glm::qualifier Q = glm::qualifier::defaultp, std::floating_point T>
+ requires(D >= 3)
+constexpr auto
+rotate_yp(const glm::vec<2, T, Q> & angles)
+{
+ return rotate_yp<D>(angles.y, angles.x);
+}
+
+template<glm::length_t D, glm::qualifier Q = glm::qualifier::defaultp, std::floating_point T>
+ requires(D >= 2)
+constexpr auto
+vector_yaw(const glm::vec<D, T, Q> & diff)
+{
+ return std::atan2(diff.x, diff.y);
+}
+
+template<glm::length_t D, glm::qualifier Q = glm::qualifier::defaultp, std::floating_point T>
+ requires(D >= 3)
+constexpr auto
+vector_pitch(const glm::vec<D, T, Q> & diff)
+{
+ return std::atan(diff.z);
+}
+
+template<Arithmetic T, glm::qualifier Q = glm::defaultp>
+constexpr glm::vec<2, T, Q>
+vector_normal(const glm::vec<2, T, Q> & vector)
+{
+ return {-vector.y, vector.x};
};
-float round_frac(const float & v, const float & frac);
+template<std::floating_point T>
+constexpr auto
+round_frac(const T value, const T frac)
+{
+ return std::round(value / frac) * frac;
+}
-template<typename T>
-inline constexpr auto
-sq(T v)
+template<Arithmetic T>
+ requires requires(T value) { value * value; }
+constexpr auto
+sq(T value)
{
- return v * v;
+ return value * value;
}
-template<glm::qualifier Q>
-inline constexpr glm::vec<3, int64_t, Q>
-crossProduct(const glm::vec<3, int64_t, Q> a, const glm::vec<3, int64_t, Q> b)
+template<glm::qualifier Q = glm::defaultp>
+constexpr glm::vec<3, int64_t, Q>
+crossProduct(const glm::vec<3, int64_t, Q> & valueA, const glm::vec<3, int64_t, Q> & valueB)
{
return {
- (a.y * b.z) - (a.z * b.y),
- (a.z * b.x) - (a.x * b.z),
- (a.x * b.y) - (a.y * b.x),
+ (valueA.y * valueB.z) - (valueA.z * valueB.y),
+ (valueA.z * valueB.x) - (valueA.x * valueB.z),
+ (valueA.x * valueB.y) - (valueA.y * valueB.x),
};
}
-template<std::integral T, glm::qualifier Q>
-inline constexpr glm::vec<3, T, Q>
-crossProduct(const glm::vec<3, T, Q> a, const glm::vec<3, T, Q> b)
+template<std::integral T, glm::qualifier Q = glm::defaultp>
+constexpr glm::vec<3, T, Q>
+crossProduct(const glm::vec<3, T, Q> & valueA, const glm::vec<3, T, Q> & valueB)
+{
+ return crossProduct<Q>(valueA, valueB);
+}
+
+template<std::floating_point T, glm::qualifier Q = glm::defaultp>
+constexpr glm::vec<3, T, Q>
+crossProduct(const glm::vec<3, T, Q> & valueA, const glm::vec<3, T, Q> & valueB)
{
- return crossProduct<Q>(a, b);
+ return glm::cross(valueA, valueB);
}
-template<std::floating_point T, glm::qualifier Q>
-inline constexpr glm::vec<3, T, Q>
-crossProduct(const glm::vec<3, T, Q> a, const glm::vec<3, T, Q> b)
+template<Arithmetic R = float, Arithmetic Ta, Arithmetic Tb>
+constexpr auto
+ratio(const Ta valueA, const Tb valueB)
{
- return glm::cross(a, b);
+ using Common = std::common_type_t<Ta, Ta, R>;
+ return static_cast<R>((static_cast<Common>(valueA) / static_cast<Common>(valueB)));
}
-template<typename R = float, typename Ta, typename Tb>
-inline constexpr auto
-ratio(Ta a, Tb b)
+template<Arithmetic R = float, Arithmetic T, glm::qualifier Q = glm::defaultp>
+constexpr auto
+ratio(const glm::vec<2, T, Q> & value)
{
- return (static_cast<R>(a) / static_cast<R>(b));
+ return ratio<R>(value.x, value.y);
}
-template<typename R = float, typename T, glm::qualifier Q>
-inline constexpr auto
-ratio(glm::vec<2, T, Q> v)
+template<glm::length_t L = 3, std::floating_point T, glm::qualifier Q = glm::defaultp>
+constexpr auto
+perspective_divide(const glm::vec<4, T, Q> & value)
{
- return ratio<R>(v.x, v.y);
+ return value / value.w;
}
-template<glm::length_t L = 3, typename T, glm::qualifier Q>
-inline constexpr glm::vec<L, T, Q>
-perspective_divide(glm::vec<4, T, Q> v)
+template<glm::length_t L1, glm::length_t L2, Arithmetic T, glm::qualifier Q = glm::defaultp>
+constexpr glm::vec<L1 + L2, T, Q>
+operator||(const glm::vec<L1, T, Q> valueA, const glm::vec<L2, T, Q> valueB)
{
- return v / v.w;
+ return {valueA, valueB};
}
-template<glm::length_t L1, glm::length_t L2, typename T, glm::qualifier Q>
-inline constexpr glm::vec<L1 + L2, T, Q>
-operator||(const glm::vec<L1, T, Q> v1, const glm::vec<L2, T, Q> v2)
+template<glm::length_t L, Arithmetic T, glm::qualifier Q = glm::defaultp>
+constexpr glm::vec<L + 1, T, Q>
+operator||(const glm::vec<L, T, Q> valueA, const T valueB)
{
- return {v1, v2};
+ return {valueA, valueB};
}
-template<glm::length_t L, typename T, glm::qualifier Q>
-inline constexpr glm::vec<L + 1, T, Q>
-operator||(const glm::vec<L, T, Q> v1, const T v2)
+template<glm::length_t L, std::floating_point T, glm::qualifier Q = glm::defaultp>
+constexpr glm::vec<L, T, Q>
+perspectiveMultiply(const glm::vec<L, T, Q> & base, const glm::mat<L + 1, L + 1, T, Q> & mutation)
{
- return {v1, v2};
+ const auto mutated = mutation * (base || T(1));
+ return mutated / mutated.w;
}
-template<glm::length_t L, typename T, glm::qualifier Q>
-inline constexpr glm::vec<L, T, Q>
-perspectiveMultiply(const glm::vec<L, T, Q> & p, const glm::mat<L + 1, L + 1, T, Q> & mutation)
+template<glm::length_t L, std::floating_point T, glm::qualifier Q = glm::defaultp>
+constexpr glm::vec<L, T, Q>
+perspectiveApply(glm::vec<L, T, Q> & base, const glm::mat<L + 1, L + 1, T, Q> & mutation)
{
- const auto p2 = mutation * (p || T(1));
- return p2 / p2.w;
+ return base = perspectiveMultiply(base, mutation);
}
-template<glm::length_t L, typename T, glm::qualifier Q>
-inline constexpr glm::vec<L, T, Q>
-perspectiveApply(glm::vec<L, T, Q> & p, const glm::mat<L + 1, L + 1, T, Q> & mutation)
+template<std::floating_point T>
+constexpr T
+normalize(T ang)
{
- return p = perspectiveMultiply(p, mutation);
+ while (ang > glm::pi<T>()) {
+ ang -= glm::two_pi<T>();
+ }
+ while (ang <= -glm::pi<T>()) {
+ ang += glm::two_pi<T>();
+ }
+ return ang;
}
-float normalize(float ang);
+template<Arithmetic T, glm::qualifier Q = glm::defaultp>
+[[nodiscard]] constexpr std::optional<glm::vec<2, T, Q>>
+linesIntersectAt(const glm::vec<2, T, Q> Aabs, const glm::vec<2, T, Q> Babs, const glm::vec<2, T, Q> Cabs,
+ const glm::vec<2, T, Q> Dabs)
+{
+ using CT = CalcType<T>;
+ using CVec = glm::vec<2, CT, Q>;
+ // Line AB represented as a1x + b1y = c1
+ const CVec Brel = Babs - Aabs;
+ const CT a1 = Brel.y;
+ const CT b1 = -Brel.x;
+
+ // Line CD represented as a2x + b2y = c2
+ const CVec Crel = Cabs - Aabs, Del = Dabs - Aabs;
+ const CT a2 = Del.y - Crel.y;
+ const CT b2 = Crel.x - Del.x;
+ const CT c2 = (a2 * Crel.x) + (b2 * Crel.y);
+
+ const auto determinant = (a1 * b2) - (a2 * b1);
+
+ if (determinant == 0) {
+ return std::nullopt;
+ }
+ return Aabs + CVec {(b1 * c2) / -determinant, (a1 * c2) / determinant};
+}
-template<typename T, glm::qualifier Q>
+template<Arithmetic T, glm::qualifier Q = glm::defaultp>
std::pair<glm::vec<2, T, Q>, bool>
find_arc_centre(glm::vec<2, T, Q> start, Rotation2D startDir, glm::vec<2, T, Q> end, Rotation2D endDir)
{
@@ -204,17 +416,17 @@ find_arc_centre(glm::vec<2, T, Q> start, Rotation2D startDir, glm::vec<2, T, Q>
throw std::runtime_error("no intersection");
}
-template<typename T, glm::qualifier Q>
+template<Arithmetic T, glm::qualifier Q = glm::defaultp>
std::pair<glm::vec<2, T, Q>, bool>
find_arc_centre(glm::vec<2, T, Q> start, Angle entrys, glm::vec<2, T, Q> end, Angle entrye)
{
if (start == end) {
return {start, false};
}
- return find_arc_centre(start, sincosf(entrys + half_pi), end, sincosf(entrye - half_pi));
+ return find_arc_centre(start, sincos(entrys + half_pi), end, sincos(entrye - half_pi));
}
-template<typename T, glm::qualifier Q>
+template<Arithmetic T, glm::qualifier Q = glm::defaultp>
Angle
find_arcs_radius(glm::vec<2, T, Q> start, Rotation2D ad, glm::vec<2, T, Q> end, Rotation2D bd)
{
@@ -239,38 +451,139 @@ find_arcs_radius(glm::vec<2, T, Q> start, Rotation2D ad, glm::vec<2, T, Q> end,
/ (2 * (sq(X) - 2 * X * Z + sq(Z) + sq(Y) - 2 * Y * W + sq(W) - 4));
}
-template<typename T, glm::qualifier Q>
+template<Arithmetic T, glm::qualifier Q = glm::defaultp>
std::pair<Angle, Angle>
find_arcs_radius(glm::vec<2, T, Q> start, Angle entrys, glm::vec<2, T, Q> end, Angle entrye)
{
const auto getrad = [&](auto leftOrRight) {
- return find_arcs_radius(start, sincosf(entrys + leftOrRight), end, sincosf(entrye + leftOrRight));
+ return find_arcs_radius(start, sincos(entrys + leftOrRight), end, sincos(entrye + leftOrRight));
};
return {getrad(-half_pi), getrad(half_pi)};
}
-template<typename T>
+template<Arithmetic T>
auto
midpoint(const std::pair<T, T> & v)
{
return std::midpoint(v.first, v.second);
}
+template<glm::length_t D, std::integral T, glm::qualifier Q = glm::defaultp>
+auto
+midpoint(const glm::vec<D, T, Q> & valueA, const glm::vec<D, T, Q> & valueB)
+{
+ return valueA + (valueB - valueA) / 2;
+}
+
+// std::pow is not constexpr
+template<Arithmetic T>
+ requires requires(T n) { n *= n; }
+constexpr T
+pow(const T base, std::integral auto exp)
+{
+ T res {1};
+ while (exp--) {
+ res *= base;
+ }
+ return res;
+}
+
// Conversions
-template<typename T>
-inline constexpr auto
+template<Arithmetic T>
+constexpr auto
mph_to_ms(T v)
{
return v / 2.237L;
}
-template<typename T>
-inline constexpr auto
+template<Arithmetic T>
+constexpr auto
kph_to_ms(T v)
{
return v / 3.6L;
}
// ... literals are handy for now, probably go away when we load stuff externally
-float operator"" _mph(const long double v);
-float operator"" _kph(const long double v);
+float operator""_mph(const long double v);
+float operator""_kph(const long double v);
+
+constexpr float
+operator""_degrees(long double degrees)
+{
+ return static_cast<float>(degrees) * degreesToRads;
+}
+
+// Late implementations due to dependencies
+template<typename T, glm::qualifier Q>
+constexpr ArcSegment<T, Q>::ArcSegment(PointType centre, PointType ep0, PointType ep1) :
+ Arc {centre, ep0, ep1}, centre {centre}, ep0 {ep0}, ep1 {ep1}, radius {::distance(centre, ep0)}
+{
+}
+
+template<typename T, glm::qualifier Q>
+[[nodiscard]] constexpr std::optional<std::pair<glm::vec<2, T, Q>, Angle>>
+ArcSegment<T, Q>::crossesLineAt(const glm::vec<2, T, Q> & lineStart, const glm::vec<2, T, Q> & lineEnd) const
+{
+ // Based on formulas from https://mathworld.wolfram.com/Circle-LineIntersection.html
+ const auto lineDiff = difference(lineEnd, lineStart);
+ const auto lineLen = glm::length(lineDiff);
+ const auto lineRelStart = difference(lineStart, centre);
+ const auto lineRelEnd = difference(lineEnd, centre);
+ const auto determinant = (lineRelStart.x * lineRelEnd.y) - (lineRelEnd.x * lineRelStart.y);
+ const auto discriminant = (radius * radius * lineLen * lineLen) - (determinant * determinant);
+ if (discriminant < 0) {
+ return std::nullopt;
+ }
+
+ const auto rootDiscriminant = std::sqrt(discriminant);
+ const auto drdr = lineLen * lineLen;
+ const RelativeDistance sgn = (lineDiff.y < 0 ? -1 : 1);
+ std::array<std::pair<RelativePosition2D, Angle>, 2> points;
+ std::ranges::transform(std::initializer_list {1, -1}, points.begin(), [&](RelativeDistance N) {
+ const auto point = RelativePosition2D {((determinant * lineDiff.y) + sgn * lineDiff.x * rootDiscriminant * N),
+ ((-determinant * lineDiff.x) + std::abs(lineDiff.y) * rootDiscriminant * N)}
+ / drdr;
+ return std::make_pair(point, vector_yaw(point));
+ });
+ const auto end
+ = std::remove_if(points.begin(), points.end(), [this, lineRelStart, lineDiff, drdr](const auto point) {
+ const auto dot = glm::dot(lineDiff, point.first - lineRelStart);
+ return !angleWithinArc(point.second) || dot < 0 || dot > drdr;
+ });
+ if (points.begin() == end) {
+ return std::nullopt;
+ }
+ const auto first = *std::ranges::min_element(points.begin(), end, {}, [lineRelStart](const auto point) {
+ return glm::distance(lineRelStart, point.first);
+ });
+ return std::make_pair(centre + first.first, first.second);
+}
+
+namespace {
+ template<template<typename> typename Op>
+ [[nodiscard]] constexpr auto
+ pointLineOp(const GlobalPosition2D point, const GlobalPosition2D end1, const GlobalPosition2D end2)
+ {
+ return Op {}(CalcDistance(end2.x - end1.x) * CalcDistance(point.y - end1.y),
+ CalcDistance(end2.y - end1.y) * CalcDistance(point.x - end1.x));
+ }
+}
+
+constexpr auto pointLeftOfLine = pointLineOp<std::greater>;
+constexpr auto pointLeftOfOrOnLine = pointLineOp<std::greater_equal>;
+
+[[nodiscard]] constexpr bool
+linesCross(const GlobalPosition2D lineAend1, const GlobalPosition2D lineAend2, const GlobalPosition2D lineBend1,
+ const GlobalPosition2D lineBend2)
+{
+ return (pointLeftOfLine(lineAend2, lineBend1, lineBend2) == pointLeftOfLine(lineAend1, lineBend2, lineBend1))
+ && (pointLeftOfLine(lineBend1, lineAend1, lineAend2) == pointLeftOfLine(lineBend2, lineAend2, lineAend1));
+}
+
+[[nodiscard]] constexpr bool
+linesCrossLtR(const GlobalPosition2D lineAend1, const GlobalPosition2D lineAend2, const GlobalPosition2D lineBend1,
+ const GlobalPosition2D lineBend2)
+{
+ return pointLeftOfLine(lineAend2, lineBend1, lineBend2) && pointLeftOfLine(lineAend1, lineBend2, lineBend1)
+ && pointLeftOfLine(lineBend1, lineAend1, lineAend2) && pointLeftOfLine(lineBend2, lineAend2, lineAend1);
+}