From ca3736b3a896557536c0aa4c0cee1f156e118b54 Mon Sep 17 00:00:00 2001
From: Dan Goodliffe <dan@randomdan.homeip.net>
Date: Wed, 1 Jan 2025 12:53:43 +0000
Subject: Walk terrain along a curve - edge cases exist

---
 game/geoData.cpp      | 44 ++++++++++++++++++++++++++++++++++++++++++++
 game/geoData.h        |  6 ++++--
 test/test-geoData.cpp | 40 ++++++++++++++++++++++++++++++++++++++++
 3 files changed, 88 insertions(+), 2 deletions(-)

diff --git a/game/geoData.cpp b/game/geoData.cpp
index ce88e5b..37abc4c 100644
--- a/game/geoData.cpp
+++ b/game/geoData.cpp
@@ -289,6 +289,50 @@ GeoData::walkUntil(const PointFace & from, const GlobalPosition2D to, Tester<Wal
 	}
 }
 
+void
+GeoData::walk(const PointFace & from, GlobalPosition2D to, GlobalPosition2D centre, Consumer<WalkStep> op) const
+{
+	walkUntil(from, to, centre, [&op](const auto & fh) {
+		op(fh);
+		return false;
+	});
+}
+
+void
+GeoData::walkUntil(const PointFace & from, GlobalPosition2D to, GlobalPosition2D centre, Tester<WalkStep> op) const
+{
+	WalkStep step {
+			.current = from.face(this),
+	};
+	if (!step.current.is_valid()) {
+		const auto entryEdge = findEntry(from.point, to);
+		if (!entryEdge.is_valid()) {
+			return;
+		}
+		step.current = opposite_face_handle(entryEdge);
+	}
+	ArcSegment arc {centre, from.point, to};
+	while (step.current.is_valid() && !op(step)) {
+		step.previous = step.current;
+		for (const auto next : fh_range(step.current)) {
+			if (opposite_halfedge_handle(next) == step.exitHalfedge) {
+				continue;
+			}
+			step.current = opposite_face_handle(next);
+			if (step.current.is_valid()) {
+				const auto e1 = point(to_vertex_handle(next));
+				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();
+					break;
+				}
+			}
+			step.current.reset();
+		}
+	}
+}
+
 void
 GeoData::boundaryWalk(Consumer<HalfedgeHandle> op) const
 {
diff --git a/game/geoData.h b/game/geoData.h
index 68ce9a2..e3fc313 100644
--- a/game/geoData.h
+++ b/game/geoData.h
@@ -74,8 +74,10 @@ public:
 	template<typename T> using Consumer = const std::function<void(const T &)> &;
 	template<typename T> using Tester = const std::function<bool(const T &)> &;
 
-	void walk(const PointFace & from, const GlobalPosition2D to, Consumer<WalkStep> op) const;
-	void walkUntil(const PointFace & from, const GlobalPosition2D to, Tester<WalkStep> op) const;
+	void walk(const PointFace & from, GlobalPosition2D to, Consumer<WalkStep> op) const;
+	void walkUntil(const PointFace & from, GlobalPosition2D to, Tester<WalkStep> op) const;
+	void walk(const PointFace & from, GlobalPosition2D to, GlobalPosition2D centre, Consumer<WalkStep> op) const;
+	void walkUntil(const PointFace & from, GlobalPosition2D to, GlobalPosition2D centre, Tester<WalkStep> op) const;
 
 	void boundaryWalk(Consumer<HalfedgeHandle>) const;
 	void boundaryWalk(Consumer<HalfedgeHandle>, HalfedgeHandle start) const;
diff --git a/test/test-geoData.cpp b/test/test-geoData.cpp
index dd68375..049d896 100644
--- a/test/test-geoData.cpp
+++ b/test/test-geoData.cpp
@@ -191,6 +191,46 @@ BOOST_DATA_TEST_CASE(walkTerrainUntil,
 	BOOST_CHECK_EQUAL_COLLECTIONS(visited.begin(), visited.end(), visits.begin(), visits.end());
 }
 
+using WalkTerrainCurveData = std::tuple<GlobalPosition2D, GlobalPosition2D, GlobalPosition2D, std::vector<int>,
+		std::vector<GlobalPosition2D>>;
+
+BOOST_TEST_DECORATOR(*boost::unit_test::timeout(1))
+
+BOOST_DATA_TEST_CASE(walkTerrainCurveSetsFromFace,
+		boost::unit_test::data::make<WalkTerrainCurveData>({
+				{{310002000, 490003000}, {310002000, 490003000}, {310002000, 490003000}, {0}, {}},
+				{{310003000, 490002000}, {310003000, 490002000}, {310003000, 490002000}, {1}, {}},
+				{{310202000, 490203000}, {310002000, 490003000}, {310002000, 490203000},
+						{1600, 1601, 1202, 1201, 802, 803, 404, 403, 4, 3, 2, 1, 0},
+						{
+								{310201997, 490201997},
+								{310201977, 490200000},
+								{310200000, 490174787},
+								{310194850, 490150000},
+								{310192690, 490142690},
+								{310173438, 490100000},
+								{310150000, 490068479},
+								{310130806, 490050000},
+								{310100000, 490028656},
+								{310062310, 490012310},
+								{310050000, 490008845},
+								{310003003, 490003003},
+						}},
+		}),
+		from, to, centre, visits, exits)
+{
+	BOOST_REQUIRE_EQUAL(visits.size(), exits.size() + 1);
+
+	std::vector<int> visited;
+	std::vector<GlobalPosition2D> exited;
+	BOOST_CHECK_NO_THROW(fixedTerrtain.walk(from, to, centre, [&](const auto & step) {
+		visited.emplace_back(step.current.idx());
+		exited.emplace_back(step.exitPosition);
+	}));
+	BOOST_CHECK_EQUAL_COLLECTIONS(visited.begin(), visited.end(), visits.begin(), visits.end());
+	BOOST_CHECK_EQUAL_COLLECTIONS(exited.begin() + 1, exited.end(), exits.begin(), exits.end());
+}
+
 using FindEntiesData = std::tuple<GlobalPosition2D, GlobalPosition2D, int>;
 
 BOOST_DATA_TEST_CASE(findEntries,
-- 
cgit v1.2.3