From 49a422ed91289a31142a8c0fb8b7030d2dea98a1 Mon Sep 17 00:00:00 2001
From: Dan Goodliffe <dan@randomdan.homeip.net>
Date: Sun, 29 Oct 2023 14:11:46 +0000
Subject: Initial commit of findPoint on terrain

2D navigate from a default/given starting point, possible scope for improvement, but it's
not exactly slow; <9ms
---
 game/terrain2.cpp | 33 ++++++++++++++++++++++++++++++++-
 game/terrain2.h   |  4 ++++
 2 files changed, 36 insertions(+), 1 deletion(-)

(limited to 'game')

diff --git a/game/terrain2.cpp b/game/terrain2.cpp
index 83df3fa..cc0bf90 100644
--- a/game/terrain2.cpp
+++ b/game/terrain2.cpp
@@ -48,6 +48,32 @@ TerrainMesh::TerrainMesh(const std::filesystem::path & input)
 	update_vertex_normals();
 };
 
+OpenMesh::FaceHandle
+TerrainMesh::findPoint(glm::vec2 p) const
+{
+	return findPoint(p, *faces_begin());
+}
+
+OpenMesh::FaceHandle
+TerrainMesh::findPoint(glm::vec2 p, OpenMesh::FaceHandle f) const
+{
+	ConstFaceVertexIter vertices;
+	while (f.is_valid() && !triangleContainsPoint(p, vertices = cfv_iter(f))) {
+		for (auto next = cfh_iter(f); next.is_valid(); ++next) {
+			f = opposite_face_handle(*next);
+			if (f.is_valid()) {
+				const auto e1 = point(to_vertex_handle(*next));
+				const auto e2 = point(to_vertex_handle(opposite_halfedge_handle(*next)));
+				if ((e2.x - e1.x) * (p.y - e1.y) > (e2.y - e1.y) * (p.x - e1.x)) {
+					break;
+				}
+			}
+			f.reset();
+		}
+	}
+	return f;
+}
+
 bool
 TerrainMesh::triangleContainsPoint(const glm::vec2 p, const glm::vec2 a, const glm::vec2 b, const glm::vec2 c)
 {
@@ -61,6 +87,11 @@ TerrainMesh::triangleContainsPoint(const glm::vec2 p, const glm::vec2 a, const g
 bool
 TerrainMesh::triangleContainsPoint(const glm::vec2 p, FaceHandle face) const
 {
-	auto vertices = cfv_iter(face);
+	return triangleContainsPoint(p, cfv_iter(face));
+}
+
+bool
+TerrainMesh::triangleContainsPoint(const glm::vec2 p, ConstFaceVertexIter vertices) const
+{
 	return triangleContainsPoint(p, point(*vertices++), point(*vertices++), point(*vertices++));
 }
diff --git a/game/terrain2.h b/game/terrain2.h
index d2da8d0..713fe23 100644
--- a/game/terrain2.h
+++ b/game/terrain2.h
@@ -18,7 +18,11 @@ class TerrainMesh : public OpenMesh::TriMesh_ArrayKernelT<TerrainTraits> {
 public:
 	explicit TerrainMesh(const std::filesystem::path &);
 
+	[[nodiscard]] FaceHandle findPoint(glm::vec2) const;
+	[[nodiscard]] FaceHandle findPoint(glm::vec2, FaceHandle start) const;
+
 protected:
 	[[nodiscard]] static bool triangleContainsPoint(const glm::vec2, const glm::vec2, const glm::vec2, const glm::vec2);
 	[[nodiscard]] bool triangleContainsPoint(const glm::vec2, FaceHandle) const;
+	[[nodiscard]] bool triangleContainsPoint(const glm::vec2, ConstFaceVertexIter) const;
 };
-- 
cgit v1.2.3