From 39985f36e807126b2c7b9ec6096bda3922903a54 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sun, 15 Dec 2024 14:38:00 +0000 Subject: 2D triangle area support --- test/test-maths.cpp | 34 ++++++++++++++++++++++++++++++++++ 1 file changed, 34 insertions(+) (limited to 'test/test-maths.cpp') diff --git a/test/test-maths.cpp b/test/test-maths.cpp index b9d08bb..1278c44 100644 --- a/test/test-maths.cpp +++ b/test/test-maths.cpp @@ -12,6 +12,7 @@ #include #include #include +#include #include using vecter_and_angle = std::tuple; @@ -341,3 +342,36 @@ static_assert(linesIntersectAt(GlobalPosition2D {311000100, 491100100}, {3110500 .value() == GlobalPosition2D {311000100, 491100100}); static_assert(!linesIntersectAt(glm::dvec2 {0, 1}, {0, 4}, {1, 8}, {1, 4}).has_value()); + +BOOST_AUTO_TEST_CASE(triangle2d_helpers) +{ + constexpr static Triangle<2, float> t {{0, 0}, {5, 0}, {5, 5}}; + + BOOST_CHECK_CLOSE(t.angle(0), quarter_pi, 0.01F); + BOOST_CHECK_CLOSE(t.angleAt({0, 0}), quarter_pi, 0.01F); + BOOST_CHECK_CLOSE(t.angle(1), half_pi, 0.01F); + BOOST_CHECK_CLOSE(t.angleAt({5, 0}), half_pi, 0.01F); + BOOST_CHECK_CLOSE(t.angle(2), quarter_pi, 0.01F); + BOOST_CHECK_CLOSE(t.angleAt({5, 5}), quarter_pi, 0.01F); + + BOOST_CHECK_CLOSE(t.angleAt({0, 1}), 0.F, 0.01F); + + BOOST_CHECK_CLOSE(t.area(), 12.5F, 0.01F); +} + +BOOST_AUTO_TEST_CASE(triangle3d_helpers) +{ + constexpr static Triangle<3, float> t {{0, 0, 0}, {5, 0, 0}, {5, 5, 0}}; + + BOOST_CHECK_EQUAL(t.nnormal(), up); + BOOST_CHECK_CLOSE(t.angle(0), quarter_pi, 0.01F); + BOOST_CHECK_CLOSE(t.angleAt({0, 0, 0}), quarter_pi, 0.01F); + BOOST_CHECK_CLOSE(t.angle(1), half_pi, 0.01F); + BOOST_CHECK_CLOSE(t.angleAt({5, 0, 0}), half_pi, 0.01F); + BOOST_CHECK_CLOSE(t.angle(2), quarter_pi, 0.01F); + BOOST_CHECK_CLOSE(t.angleAt({5, 5, 0}), quarter_pi, 0.01F); + + BOOST_CHECK_CLOSE(t.angleAt({0, 1, 0}), 0.F, 0.01F); + + BOOST_CHECK_CLOSE(t.area(), 12.5F, 0.01F); +} -- cgit v1.2.3 From 06e64d7ccf053dbb11547edf3ba986d096b50045 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Tue, 31 Dec 2024 12:52:10 +0000 Subject: Add ArcSegment Extends Arc, with method for determining intersection point with line segment --- lib/maths.h | 68 ++++++++++++++++++++++++++++++++++++++++++++++++++++ lib/stream_support.h | 11 +++++++++ test/test-maths.cpp | 31 ++++++++++++++++++++++++ 3 files changed, 110 insertions(+) (limited to 'test/test-maths.cpp') diff --git a/lib/maths.h b/lib/maths.h index 7f2d7b4..f43321a 100644 --- a/lib/maths.h +++ b/lib/maths.h @@ -1,6 +1,8 @@ #pragma once #include "config/types.h" +#include +#include #include #include #include @@ -36,6 +38,26 @@ struct Arc : public std::pair { } }; +template 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> 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}; @@ -471,3 +493,49 @@ operator"" _degrees(long double degrees) { return static_cast(degrees) * degreesToRads; } + +// Late implementations due to dependencies +template +constexpr ArcSegment::ArcSegment(PointType centre, PointType ep0, PointType ep1) : + Arc {centre, ep0, ep1}, centre {centre}, ep0 {ep0}, ep1 {ep1}, radius {glm::length(difference(centre, ep0))} +{ +} + +template +[[nodiscard]] constexpr std::optional> +ArcSegment::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 points { + RelativePosition2D {((determinant * lineDiff.y) + sgn * lineDiff.x * rootDiscriminant), + ((-determinant * lineDiff.x) + std::abs(lineDiff.y) * rootDiscriminant)} + / drdr, + RelativePosition2D {((determinant * lineDiff.y) - sgn * lineDiff.x * rootDiscriminant), + ((-determinant * lineDiff.x) - std::abs(lineDiff.y) * rootDiscriminant)} + / drdr, + }; + const auto end + = std::remove_if(points.begin(), points.end(), [this, lineRelStart, lineDiff, drdr](const auto point) { + const auto dot = glm::dot(lineDiff, point - lineRelStart); + return !angleWithinArc(vector_yaw(point)) || dot < 0 || dot > drdr; + }); + if (points.begin() == end) { + return std::nullopt; + } + return centre + *std::ranges::min_element(points.begin(), end, {}, [lineRelStart](const auto point) { + return glm::distance(lineRelStart, point); + }); +} diff --git a/lib/stream_support.h b/lib/stream_support.h index f21622a..f5c5e37 100644 --- a/lib/stream_support.h +++ b/lib/stream_support.h @@ -4,6 +4,7 @@ #include #include #include +#include #include #include #include @@ -82,6 +83,16 @@ namespace std { { return s << EnumTypeDetails::typeName << "::" << EnumDetails::to_string(e).value(); } + + template + inline std::ostream & + operator<<(std::ostream & s, const std::optional & v) + { + if (v) { + return s << *v; + } + return s << "nullopt"; + } } template diff --git a/test/test-maths.cpp b/test/test-maths.cpp index 1278c44..aa2b9c8 100644 --- a/test/test-maths.cpp +++ b/test/test-maths.cpp @@ -375,3 +375,34 @@ BOOST_AUTO_TEST_CASE(triangle3d_helpers) BOOST_CHECK_CLOSE(t.area(), 12.5F, 0.01F); } + +using ArcLineIntersectData = std::tuple>; + +BOOST_DATA_TEST_CASE(arcline_intersection, + boost::unit_test::data::make({ + {{0, 0}, {0, 100}, {100, 0}, {200, 0}, {0, 200}, std::nullopt}, + {{0, 0}, {0, 100}, {100, 0}, {0, 0}, {10, 10}, std::nullopt}, + {{0, 0}, {0, 100}, {100, 0}, {0, 0}, {100, 100}, GlobalPosition2D {71, 71}}, + {{15, 27}, {15, 127}, {115, 27}, {15, 27}, {115, 127}, GlobalPosition2D {86, 98}}, + {{0, 0}, {0, 100}, {100, 0}, {0, 0}, {-100, -100}, std::nullopt}, + {{0, 0}, {0, 100}, {100, 0}, {-10, 125}, {125, -10}, GlobalPosition2D {16, 99}}, + {{0, 0}, {0, 100}, {100, 0}, {125, -10}, {-10, 125}, GlobalPosition2D {99, 16}}, + {{0, 0}, {0, 100}, {100, 0}, {10, 125}, {125, -10}, GlobalPosition2D {38, 93}}, + {{0, 0}, {0, 100}, {100, 0}, {12, 80}, {125, -10}, GlobalPosition2D {99, 10}}, + {{0, 0}, {0, 100}, {100, 0}, {40, 80}, {125, -10}, GlobalPosition2D {98, 18}}, + {{0, 0}, {0, 100}, {100, 0}, {40, 80}, {80, 20}, std::nullopt}, + {{0, 0}, {0, 100}, {100, 0}, {40, 80}, {80, 80}, GlobalPosition2D {60, 80}}, + {{0, 0}, {0, 100}, {100, 0}, {80, 40}, {80, 80}, GlobalPosition2D {80, 60}}, + {{310002000, 490203000}, {310202000, 490203000}, {310002000, 490003000}, {310200000, 490150000}, + {310150000, 490150000}, GlobalPosition2D {310194850, 490150000}}, + }), + centre, arcStart, arcEnd, lineStart, lineEnd, intersection) +{ + const ArcSegment arc {centre, arcStart, arcEnd}; + BOOST_TEST_INFO(arc.first); + BOOST_TEST_INFO(arc.second); + BOOST_TEST_INFO(arc.length()); + + BOOST_CHECK_EQUAL(arc.crossesLineAt(lineStart, lineEnd), intersection); +} -- cgit v1.2.3 From c0d05b1ad0f2d82f9ce94437370648e7dfdd994e Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Wed, 1 Jan 2025 16:00:35 +0000 Subject: Return angle of intersection of arc with line --- game/geoData.cpp | 2 +- lib/maths.h | 30 +++++++++++++++--------------- test/test-maths.cpp | 32 +++++++++++++++++++------------- 3 files changed, 35 insertions(+), 29 deletions(-) (limited to 'test/test-maths.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index 37abc4c..45e6590 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -324,7 +324,7 @@ GeoData::walkUntil(const PointFace & from, GlobalPosition2D to, GlobalPosition2D const auto e2 = point(to_vertex_handle(opposite_halfedge_handle(next))); if (const auto intersect = arc.crossesLineAt(e1, e2)) { step.exitHalfedge = next; - step.exitPosition = intersect.value(); + step.exitPosition = intersect.value().first; break; } } diff --git a/lib/maths.h b/lib/maths.h index f43321a..671313d 100644 --- a/lib/maths.h +++ b/lib/maths.h @@ -48,7 +48,7 @@ template struct ArcSegment : publi PointType ep1; RelativeDistance radius; - [[nodiscard]] constexpr std::optional> crossesLineAt( + [[nodiscard]] constexpr std::optional, Angle>> crossesLineAt( const glm::vec<2, T, Q> & lineStart, const glm::vec<2, T, Q> & lineEnd) const; [[nodiscard]] constexpr bool @@ -502,7 +502,7 @@ constexpr ArcSegment::ArcSegment(PointType centre, PointType ep0, PointTyp } template -[[nodiscard]] constexpr std::optional> +[[nodiscard]] constexpr std::optional, Angle>> ArcSegment::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 @@ -519,23 +519,23 @@ ArcSegment::crossesLineAt(const glm::vec<2, T, Q> & lineStart, const glm:: const auto rootDiscriminant = std::sqrt(discriminant); const auto drdr = lineLen * lineLen; const RelativeDistance sgn = (lineDiff.y < 0 ? -1 : 1); - std::array points { - RelativePosition2D {((determinant * lineDiff.y) + sgn * lineDiff.x * rootDiscriminant), - ((-determinant * lineDiff.x) + std::abs(lineDiff.y) * rootDiscriminant)} - / drdr, - RelativePosition2D {((determinant * lineDiff.y) - sgn * lineDiff.x * rootDiscriminant), - ((-determinant * lineDiff.x) - std::abs(lineDiff.y) * rootDiscriminant)} - / drdr, - }; + std::array, 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 - lineRelStart); - return !angleWithinArc(vector_yaw(point)) || dot < 0 || dot > drdr; - }); + const auto dot = glm::dot(lineDiff, point.first - lineRelStart); + return !angleWithinArc(point.second) || dot < 0 || dot > drdr; + }); if (points.begin() == end) { return std::nullopt; } - return centre + *std::ranges::min_element(points.begin(), end, {}, [lineRelStart](const auto point) { - return glm::distance(lineRelStart, point); + 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); } diff --git a/test/test-maths.cpp b/test/test-maths.cpp index aa2b9c8..5906757 100644 --- a/test/test-maths.cpp +++ b/test/test-maths.cpp @@ -376,33 +376,39 @@ BOOST_AUTO_TEST_CASE(triangle3d_helpers) BOOST_CHECK_CLOSE(t.area(), 12.5F, 0.01F); } +using ArcLineIntersectExp = std::pair; using ArcLineIntersectData = std::tuple>; + GlobalPosition2D, std::optional>; BOOST_DATA_TEST_CASE(arcline_intersection, boost::unit_test::data::make({ {{0, 0}, {0, 100}, {100, 0}, {200, 0}, {0, 200}, std::nullopt}, {{0, 0}, {0, 100}, {100, 0}, {0, 0}, {10, 10}, std::nullopt}, - {{0, 0}, {0, 100}, {100, 0}, {0, 0}, {100, 100}, GlobalPosition2D {71, 71}}, - {{15, 27}, {15, 127}, {115, 27}, {15, 27}, {115, 127}, GlobalPosition2D {86, 98}}, + {{0, 0}, {0, 100}, {100, 0}, {0, 0}, {100, 100}, ArcLineIntersectExp {{71, 71}, quarter_pi}}, + {{15, 27}, {15, 127}, {115, 27}, {15, 27}, {115, 127}, ArcLineIntersectExp {{86, 98}, quarter_pi}}, {{0, 0}, {0, 100}, {100, 0}, {0, 0}, {-100, -100}, std::nullopt}, - {{0, 0}, {0, 100}, {100, 0}, {-10, 125}, {125, -10}, GlobalPosition2D {16, 99}}, - {{0, 0}, {0, 100}, {100, 0}, {125, -10}, {-10, 125}, GlobalPosition2D {99, 16}}, - {{0, 0}, {0, 100}, {100, 0}, {10, 125}, {125, -10}, GlobalPosition2D {38, 93}}, - {{0, 0}, {0, 100}, {100, 0}, {12, 80}, {125, -10}, GlobalPosition2D {99, 10}}, - {{0, 0}, {0, 100}, {100, 0}, {40, 80}, {125, -10}, GlobalPosition2D {98, 18}}, + {{0, 0}, {0, 100}, {100, 0}, {-10, 125}, {125, -10}, ArcLineIntersectExp {{16, 99}, 0.164F}}, + {{0, 0}, {0, 100}, {100, 0}, {125, -10}, {-10, 125}, ArcLineIntersectExp {{99, 16}, 1.407F}}, + {{0, 0}, {0, 100}, {100, 0}, {10, 125}, {125, -10}, ArcLineIntersectExp {{38, 93}, 0.385F}}, + {{0, 0}, {0, 100}, {100, 0}, {12, 80}, {125, -10}, ArcLineIntersectExp {{99, 10}, 1.467F}}, + {{0, 0}, {0, 100}, {100, 0}, {40, 80}, {125, -10}, ArcLineIntersectExp {{98, 18}, 1.387F}}, {{0, 0}, {0, 100}, {100, 0}, {40, 80}, {80, 20}, std::nullopt}, - {{0, 0}, {0, 100}, {100, 0}, {40, 80}, {80, 80}, GlobalPosition2D {60, 80}}, - {{0, 0}, {0, 100}, {100, 0}, {80, 40}, {80, 80}, GlobalPosition2D {80, 60}}, + {{0, 0}, {0, 100}, {100, 0}, {40, 80}, {80, 80}, ArcLineIntersectExp {{60, 80}, 0.6435F}}, + {{0, 0}, {0, 100}, {100, 0}, {80, 40}, {80, 80}, ArcLineIntersectExp {{80, 60}, 0.9273F}}, {{310002000, 490203000}, {310202000, 490203000}, {310002000, 490003000}, {310200000, 490150000}, - {310150000, 490150000}, GlobalPosition2D {310194850, 490150000}}, + {310150000, 490150000}, ArcLineIntersectExp {{310194850, 490150000}, 1.839F}}, }), - centre, arcStart, arcEnd, lineStart, lineEnd, intersection) + centre, arcStart, arcEnd, lineStart, lineEnd, expected) { const ArcSegment arc {centre, arcStart, arcEnd}; BOOST_TEST_INFO(arc.first); BOOST_TEST_INFO(arc.second); BOOST_TEST_INFO(arc.length()); - BOOST_CHECK_EQUAL(arc.crossesLineAt(lineStart, lineEnd), intersection); + const auto intersection = arc.crossesLineAt(lineStart, lineEnd); + BOOST_REQUIRE_EQUAL(expected.has_value(), intersection.has_value()); + if (expected.has_value()) { + BOOST_CHECK_EQUAL(expected->first, intersection->first); + BOOST_CHECK_CLOSE(expected->second, intersection->second, 1.F); + } } -- cgit v1.2.3 From ecbb621171af0f20751bbc590453d00a7bd38320 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sun, 9 Feb 2025 15:18:35 +0000 Subject: Move lots of geoData helpers into lib --- game/geoData.cpp | 41 ----------------------------------------- lib/maths.h | 46 +++++++++++++++++++++++++++++++++++++++++++--- lib/triangle.h | 27 +++++++++++++++++++++++++++ test/test-maths.cpp | 25 +++++++++++++++++++++++++ 4 files changed, 95 insertions(+), 44 deletions(-) (limited to 'test/test-maths.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index 816ce03..3b94564 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -142,47 +142,6 @@ GeoData::PointFace::face(const GeoData * mesh) const } namespace { - template typename Op> - [[nodiscard]] constexpr inline auto - pointLineOp(const GlobalPosition2D p, const GlobalPosition2D e1, const GlobalPosition2D e2) - { - return Op {}(CalcDistance(e2.x - e1.x) * CalcDistance(p.y - e1.y), - CalcDistance(e2.y - e1.y) * CalcDistance(p.x - e1.x)); - } - - constexpr auto pointLeftOfLine = pointLineOp; - constexpr auto pointLeftOfOrOnLine = pointLineOp; - - static_assert(pointLeftOfLine({1, 2}, {1, 1}, {2, 2})); - static_assert(pointLeftOfLine({2, 1}, {2, 2}, {1, 1})); - static_assert(pointLeftOfLine({2, 2}, {1, 2}, {2, 1})); - static_assert(pointLeftOfLine({1, 1}, {2, 1}, {1, 2})); - static_assert(pointLeftOfOrOnLine({310000000, 490000000}, {310000000, 490000000}, {310050000, 490050000})); - static_assert(pointLeftOfOrOnLine({310000000, 490000000}, {310050000, 490050000}, {310000000, 490050000})); - static_assert(pointLeftOfOrOnLine({310000000, 490000000}, {310000000, 490050000}, {310000000, 490000000})); - - [[nodiscard]] constexpr inline bool - linesCross( - const GlobalPosition2D a1, const GlobalPosition2D a2, const GlobalPosition2D b1, const GlobalPosition2D b2) - { - return (pointLeftOfLine(a2, b1, b2) == pointLeftOfLine(a1, b2, b1)) - && (pointLeftOfLine(b1, a1, a2) == pointLeftOfLine(b2, a2, a1)); - } - - static_assert(linesCross({1, 1}, {2, 2}, {1, 2}, {2, 1})); - static_assert(linesCross({2, 2}, {1, 1}, {1, 2}, {2, 1})); - - [[nodiscard]] constexpr inline bool - linesCrossLtR( - const GlobalPosition2D a1, const GlobalPosition2D a2, const GlobalPosition2D b1, const GlobalPosition2D b2) - { - return pointLeftOfLine(a2, b1, b2) && pointLeftOfLine(a1, b2, b1) && pointLeftOfLine(b1, a1, a2) - && pointLeftOfLine(b2, a2, a1); - } - - static_assert(linesCrossLtR({1, 1}, {2, 2}, {1, 2}, {2, 1})); - static_assert(!linesCrossLtR({2, 2}, {1, 1}, {1, 2}, {2, 1})); - constexpr GlobalPosition3D positionOnTriangle(const GlobalPosition2D point, const GeoData::Triangle<3> & t) { diff --git a/lib/maths.h b/lib/maths.h index 3d4f440..2049c78 100644 --- a/lib/maths.h +++ b/lib/maths.h @@ -14,6 +14,9 @@ template concept Arithmetic = std::is_arithmetic_v; +template using CalcType = std::conditional_t, T, int64_t>; +template using DifferenceType = std::conditional_t, T, float>; + struct Arc : public std::pair { template requires(Lc >= 2, Le >= 2) @@ -102,7 +105,7 @@ operator-(const GlobalPosition & global, const CalcPosition & relative) } template -using DifferenceVector = glm::vec, T, float>, Q>; +using DifferenceVector = glm::vec, Q>; template constexpr DifferenceVector @@ -111,6 +114,16 @@ difference(const glm::vec & globalA, const glm::vec & globalB) return globalA - globalB; } +template +using CalcVector = glm::vec, Q>; + +template +constexpr CalcVector +calcDifference(const glm::vec & globalA, const glm::vec & globalB) +{ + return globalA - globalB; +} + template constexpr auto distance(const glm::vec & pointA, const glm::vec & pointB) @@ -364,8 +377,6 @@ normalize(T ang) return ang; } -template using CalcType = std::conditional_t, T, int64_t>; - template [[nodiscard]] constexpr std::optional> linesIntersectAt(const glm::vec<2, T, Q> Aabs, const glm::vec<2, T, Q> Babs, const glm::vec<2, T, Q> Cabs, @@ -547,3 +558,32 @@ ArcSegment::crossesLineAt(const glm::vec<2, T, Q> & lineStart, const glm:: }); return std::make_pair(centre + first.first, first.second); } + +namespace { + template 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; +constexpr auto pointLeftOfOrOnLine = pointLineOp; + +[[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); +} diff --git a/lib/triangle.h b/lib/triangle.h index e430653..abd697c 100644 --- a/lib/triangle.h +++ b/lib/triangle.h @@ -64,6 +64,12 @@ struct Triangle : public glm::vec<3, glm::vec> { return difference(p(side), p(0)); } + [[nodiscard]] constexpr auto + calcSideDifference(glm::length_t side) const + { + return calcDifference(p(side), p(0)); + } + [[nodiscard]] constexpr auto angle(glm::length_t corner) const { @@ -126,4 +132,25 @@ struct Triangle : public glm::vec<3, glm::vec> { { return begin() + 3; } + + [[nodiscard]] + constexpr auto + positionOnPlane(const glm::vec<2, T, Q> coord2d) const + requires(Dim == 3) + { + const auto edgeCrossProduct = crossProduct(calcSideDifference(1), calcSideDifference(2)); + return coord2d + || static_cast( + ((edgeCrossProduct.x * p(0).x) + (edgeCrossProduct.y * p(0).y) + (edgeCrossProduct.z * p(0).z) + - (edgeCrossProduct.x * coord2d.x) - (edgeCrossProduct.y * coord2d.y)) + / edgeCrossProduct.z); + } + + [[nodiscard]] + constexpr bool + containsPoint(const GlobalPosition2D coord) const + { + return pointLeftOfOrOnLine(coord, p(0), p(1)) && pointLeftOfOrOnLine(coord, p(1), p(2)) + && pointLeftOfOrOnLine(coord, p(2), p(0)); + } }; diff --git a/test/test-maths.cpp b/test/test-maths.cpp index 5906757..a6b780a 100644 --- a/test/test-maths.cpp +++ b/test/test-maths.cpp @@ -412,3 +412,28 @@ BOOST_DATA_TEST_CASE(arcline_intersection, BOOST_CHECK_CLOSE(expected->second, intersection->second, 1.F); } } + +static_assert(pointLeftOfLine({1, 2}, {1, 1}, {2, 2})); +static_assert(pointLeftOfLine({2, 1}, {2, 2}, {1, 1})); +static_assert(pointLeftOfLine({2, 2}, {1, 2}, {2, 1})); +static_assert(pointLeftOfLine({1, 1}, {2, 1}, {1, 2})); +static_assert(pointLeftOfOrOnLine({310000000, 490000000}, {310000000, 490000000}, {310050000, 490050000})); +static_assert(pointLeftOfOrOnLine({310000000, 490000000}, {310050000, 490050000}, {310000000, 490050000})); +static_assert(pointLeftOfOrOnLine({310000000, 490000000}, {310000000, 490050000}, {310000000, 490000000})); + +static_assert(linesCross({1, 1}, {2, 2}, {1, 2}, {2, 1})); +static_assert(linesCross({2, 2}, {1, 1}, {1, 2}, {2, 1})); + +static_assert(linesCrossLtR({1, 1}, {2, 2}, {1, 2}, {2, 1})); +static_assert(!linesCrossLtR({2, 2}, {1, 1}, {1, 2}, {2, 1})); + +static_assert(Triangle<3, GlobalDistance> {{1, 2, 3}, {1, 0, 1}, {-2, 1, 0}}.positionOnPlane({7, -2}) + == GlobalPosition3D {7, -2, 3}); +static_assert(Triangle<3, GlobalDistance> { + {310000000, 490000000, 32800}, {310050000, 490050000, 33000}, {310000000, 490050000, 32700}} + .positionOnPlane({310000000, 490000000}) + == GlobalPosition3D {310000000, 490000000, 32800}); +static_assert(Triangle<3, GlobalDistance> { + {310750000, 490150000, 58400}, {310800000, 490200000, 55500}, {310750000, 490200000, 57600}} + .positionOnPlane({310751000, 490152000}) + == GlobalPosition3D {310751000, 490152000, 58326}); -- cgit v1.2.3