causal_triangulations/geometry/traits.rs
1#![forbid(unsafe_code)]
2
3//! Core geometry traits for CDT abstraction.
4//!
5//! This module defines the trait-based interface that completely isolates
6//! CDT algorithms from specific geometry implementations.
7
8use num_traits::Float;
9use std::error::Error as StdError;
10use std::fmt::Debug;
11use std::hash::Hash;
12
13/// Core numeric trait for coordinates in geometric calculations.
14///
15/// `num_traits::Float` already implies `Copy`, `Clone`, `PartialEq`, and `PartialOrd`.
16pub trait CoordinateScalar: Float {}
17
18impl<T: Float> CoordinateScalar for T {}
19
20/// Handle types for geometry entities - completely opaque to prevent coupling
21pub trait GeometryHandle: Clone + Eq + Hash + Debug {}
22
23// Blanket implementation for any type satisfying the constraints
24impl<T: Clone + Eq + Hash + Debug> GeometryHandle for T {}
25
26/// Core geometry backend trait - completely abstracted from implementation details.
27pub trait GeometryBackend {
28 /// Coordinate type used by this backend
29 type Coordinate: CoordinateScalar;
30 /// Opaque handle type for vertices
31 type VertexHandle: GeometryHandle;
32 /// Opaque handle type for edges
33 type EdgeHandle: GeometryHandle;
34 /// Opaque handle type for faces
35 type FaceHandle: GeometryHandle;
36 /// Error type for backend operations
37 type Error: StdError;
38
39 /// Backend identifier for debugging
40 fn backend_name(&self) -> &'static str;
41}
42
43/// Read-only triangulation operations
44pub trait TriangulationQuery: GeometryBackend {
45 /// Get the number of vertices in the triangulation
46 fn vertex_count(&self) -> usize;
47
48 /// Get the number of edges in the triangulation
49 fn edge_count(&self) -> usize;
50
51 /// Get the number of faces in the triangulation
52 fn face_count(&self) -> usize;
53
54 /// Get the dimensionality of the triangulation
55 fn dimension(&self) -> usize;
56
57 /// Iterate over all vertices in the triangulation.
58 ///
59 /// Implementations return a concrete iterator so repeated topology scans do
60 /// not require heap allocation or dynamic dispatch.
61 fn vertices(&self) -> impl Iterator<Item = Self::VertexHandle> + '_;
62
63 /// Iterate over all edges in the triangulation.
64 ///
65 /// Implementations return a concrete iterator so repeated topology scans do
66 /// not require heap allocation or dynamic dispatch.
67 fn edges(&self) -> impl Iterator<Item = Self::EdgeHandle> + '_;
68
69 /// Iterate over all faces in the triangulation.
70 ///
71 /// Implementations return a concrete iterator so repeated topology scans do
72 /// not require heap allocation or dynamic dispatch.
73 fn faces(&self) -> impl Iterator<Item = Self::FaceHandle> + '_;
74
75 /// Returns the coordinate vector for a vertex handle.
76 ///
77 /// # Errors
78 ///
79 /// Returns the backend error when the vertex handle is invalid or when the
80 /// backend cannot resolve the coordinate payload for that vertex.
81 fn vertex_coordinates(
82 &self,
83 vertex: &Self::VertexHandle,
84 ) -> Result<Vec<Self::Coordinate>, Self::Error>;
85
86 /// Returns the vertices that form a face.
87 ///
88 /// # Errors
89 ///
90 /// Returns the backend error when the face handle is invalid or when the
91 /// backend cannot resolve the face connectivity.
92 fn face_vertices(
93 &self,
94 face: &Self::FaceHandle,
95 ) -> Result<Vec<Self::VertexHandle>, Self::Error>;
96
97 /// Get the two vertices that form an edge.
98 ///
99 /// Returns `Some((v0, v1))` when endpoint resolution succeeds, or `None`
100 /// if the edge handle is invalid or endpoints are unavailable.
101 ///
102 /// # Examples
103 ///
104 /// ```
105 /// use causal_triangulations::prelude::testing::*;
106 ///
107 /// let backend = MockBackend::create_triangle();
108 /// assert!(backend
109 /// .edges()
110 /// .next()
111 /// .is_some_and(|edge| backend.edge_endpoints(&edge).is_some()));
112 /// ```
113 fn edge_endpoints(
114 &self,
115 edge: &Self::EdgeHandle,
116 ) -> Option<(Self::VertexHandle, Self::VertexHandle)>;
117
118 /// Get the two faces adjacent to an edge and their opposite vertices.
119 ///
120 /// Returns `Ok(Some(_))` for an interior edge shared by exactly two
121 /// triangular faces, `Ok(None)` for boundary or otherwise non-flippable
122 /// local topology, and `Err` when the edge handle itself is invalid.
123 ///
124 /// # Errors
125 ///
126 /// Returns the backend error when the edge handle is invalid. Boundary edges
127 /// and non-flippable local topology should return `Ok(None)`.
128 fn edge_adjacent_faces(
129 &self,
130 edge: &Self::EdgeHandle,
131 ) -> EdgeAdjacentFacesResult<Self::VertexHandle, Self::FaceHandle, Self::Error>;
132
133 /// Get all faces adjacent to a vertex.
134 ///
135 /// Backend implementations may build an adjacency index for this query.
136 /// The Delaunay backend currently rebuilds that index per call, so callers
137 /// should treat it as `O(F)` in the number of finite faces.
138 ///
139 /// # Errors
140 ///
141 /// Returns the backend error when the vertex handle is invalid or adjacency
142 /// information cannot be resolved.
143 fn adjacent_faces(
144 &self,
145 vertex: &Self::VertexHandle,
146 ) -> Result<Vec<Self::FaceHandle>, Self::Error>;
147
148 /// Get all edges incident to a vertex
149 ///
150 /// # Errors
151 ///
152 /// Returns the backend error when the vertex handle is invalid or incident
153 /// edge information cannot be resolved.
154 fn incident_edges(
155 &self,
156 vertex: &Self::VertexHandle,
157 ) -> Result<Vec<Self::EdgeHandle>, Self::Error>;
158
159 /// Get all faces neighboring a given face
160 ///
161 /// # Errors
162 ///
163 /// Returns the backend error when the face handle is invalid or neighboring
164 /// face information cannot be resolved.
165 fn face_neighbors(&self, face: &Self::FaceHandle)
166 -> Result<Vec<Self::FaceHandle>, Self::Error>;
167
168 /// Check if the triangulation is valid
169 fn is_valid(&self) -> bool;
170
171 /// Calculates the Euler characteristic `V - E + F`.
172 ///
173 /// Counts are widened before arithmetic so large triangulations cannot
174 /// silently clamp the topological invariant used by CDT validation.
175 fn euler_characteristic(&self) -> i128 {
176 let vertices = self.vertex_count() as i128;
177 let edges = self.edge_count() as i128;
178 let faces = self.face_count() as i128;
179 vertices - edges + faces
180 }
181}
182
183/// Results from edge flip operations
184#[derive(Debug, Clone)]
185pub struct FlipResult<E, F> {
186 /// The new edge created by the flip
187 pub new_edge: E,
188 /// Faces affected by the flip operation
189 pub affected_faces: Vec<F>,
190}
191
192impl<E, F> FlipResult<E, F> {
193 /// Create a new flip result
194 ///
195 /// # Examples
196 ///
197 /// ```
198 /// use causal_triangulations::prelude::geometry::FlipResult;
199 ///
200 /// let result = FlipResult::new("new edge", vec!["left face", "right face"]);
201 /// assert_eq!(result.new_edge, "new edge");
202 /// assert_eq!(result.affected_faces.len(), 2);
203 /// ```
204 pub const fn new(new_edge: E, affected_faces: Vec<F>) -> Self {
205 Self {
206 new_edge,
207 affected_faces,
208 }
209 }
210}
211
212/// Local topology adjacent to one edge in a 2D triangulation.
213#[derive(Debug, Clone)]
214pub struct EdgeAdjacentFaces<V, F> {
215 /// The two endpoints of the queried edge.
216 pub endpoints: (V, V),
217 /// The two faces sharing the edge.
218 pub faces: (F, F),
219 /// The vertex opposite the edge in each adjacent face.
220 pub opposite_vertices: (V, V),
221}
222
223/// Result type for querying the local faces adjacent to an edge.
224pub type EdgeAdjacentFacesResult<V, F, E> = Result<Option<EdgeAdjacentFaces<V, F>>, E>;
225
226impl<V, F> EdgeAdjacentFaces<V, F> {
227 /// Create a local edge-adjacency record.
228 ///
229 /// # Examples
230 ///
231 /// ```
232 /// use causal_triangulations::prelude::geometry::EdgeAdjacentFaces;
233 ///
234 /// let adjacency = EdgeAdjacentFaces::new(("a", "b"), ("left", "right"), ("c", "d"));
235 /// assert_eq!(adjacency.endpoints, ("a", "b"));
236 /// ```
237 pub const fn new(endpoints: (V, V), faces: (F, F), opposite_vertices: (V, V)) -> Self {
238 Self {
239 endpoints,
240 faces,
241 opposite_vertices,
242 }
243 }
244}
245
246/// Results from face subdivision operations
247#[derive(Debug, Clone)]
248pub struct SubdivisionResult<V, F> {
249 /// The new vertex created at the subdivision point
250 pub new_vertex: V,
251 /// New faces created by subdividing the original face
252 pub new_faces: Vec<F>,
253 /// The face that was subdivided (now removed)
254 pub removed_face: F,
255}
256
257impl<V, F> SubdivisionResult<V, F> {
258 /// Create a new subdivision result
259 ///
260 /// # Examples
261 ///
262 /// ```
263 /// use causal_triangulations::prelude::geometry::SubdivisionResult;
264 ///
265 /// let result = SubdivisionResult::new("new vertex", vec!["f0", "f1", "f2"], "old face");
266 /// assert_eq!(result.new_vertex, "new vertex");
267 /// assert_eq!(result.removed_face, "old face");
268 /// ```
269 pub const fn new(new_vertex: V, new_faces: Vec<F>, removed_face: F) -> Self {
270 Self {
271 new_vertex,
272 new_faces,
273 removed_face,
274 }
275 }
276}
277
278/// Mutable triangulation operations
279pub trait TriangulationMut: TriangulationQuery {
280 /// Insert a new vertex at the given coordinates
281 ///
282 /// # Errors
283 ///
284 /// Returns the backend error when coordinate arity or values are invalid,
285 /// allocation fails, or the insertion would violate backend invariants.
286 fn insert_vertex(
287 &mut self,
288 coords: &[Self::Coordinate],
289 ) -> Result<Self::VertexHandle, Self::Error>;
290
291 /// Remove a vertex from the triangulation
292 ///
293 /// # Errors
294 ///
295 /// Returns the backend error when the vertex handle is invalid, local
296 /// topology is not removable, or the removal would violate backend
297 /// invariants.
298 fn remove_vertex(
299 &mut self,
300 vertex: Self::VertexHandle,
301 ) -> Result<Vec<Self::FaceHandle>, Self::Error>;
302
303 /// Move a vertex to new coordinates
304 ///
305 /// # Errors
306 ///
307 /// Returns the backend error when the vertex handle is invalid, coordinate
308 /// arity or values are invalid, or the move would violate backend invariants.
309 fn move_vertex(
310 &mut self,
311 vertex: Self::VertexHandle,
312 new_coords: &[Self::Coordinate],
313 ) -> Result<(), Self::Error>;
314
315 /// Flip an edge in the triangulation
316 ///
317 /// # Errors
318 ///
319 /// Returns the backend error when the edge handle is invalid, the edge is not
320 /// flippable in the backend's local topology, or the flip would violate
321 /// backend invariants.
322 fn flip_edge(
323 &mut self,
324 edge: Self::EdgeHandle,
325 ) -> Result<FlipResult<Self::EdgeHandle, Self::FaceHandle>, Self::Error>;
326
327 /// Check if an edge can be flipped
328 fn can_flip_edge(&self, edge: &Self::EdgeHandle) -> bool;
329
330 /// Subdivide a face by adding a vertex at the given point
331 ///
332 /// # Errors
333 ///
334 /// Returns the backend error when the face handle is invalid, the point has
335 /// invalid coordinate arity or values, allocation fails, or subdivision would
336 /// violate backend invariants.
337 fn subdivide_face(
338 &mut self,
339 face: Self::FaceHandle,
340 point: &[Self::Coordinate],
341 ) -> Result<SubdivisionResult<Self::VertexHandle, Self::FaceHandle>, Self::Error>;
342
343 /// Remove every vertex, edge, and face from the triangulation.
344 ///
345 /// A successful call leaves the backend in an empty, reusable state. Backends
346 /// whose storage model cannot be cleared in place should report that through
347 /// their associated error type instead of silently leaving geometry behind.
348 ///
349 /// # Errors
350 ///
351 /// Returns an error when the backend cannot clear its current storage or
352 /// when the operation is unsupported by that backend.
353 ///
354 /// # Examples
355 ///
356 /// ```
357 /// use causal_triangulations::prelude::testing::*;
358 ///
359 /// fn main() -> Result<(), MockError> {
360 /// let mut backend = MockBackend::create_triangle();
361 /// assert!(backend.vertex_count() > 0);
362 ///
363 /// backend.clear()?;
364 ///
365 /// assert_eq!(backend.vertex_count(), 0);
366 /// assert_eq!(backend.edge_count(), 0);
367 /// assert_eq!(backend.face_count(), 0);
368 /// Ok(())
369 /// }
370 /// ```
371 fn clear(&mut self) -> Result<(), Self::Error>;
372
373 /// Reserve storage capacity for at least `vertices` vertices and `faces` faces.
374 ///
375 /// Implementations may reserve additional derived storage, such as edge or
376 /// adjacency buffers. Backends that cannot expose a meaningful reservation
377 /// operation should report that through their associated error type instead
378 /// of treating the request as a successful no-op.
379 ///
380 /// # Errors
381 ///
382 /// Returns an error when allocation fails, the backend cannot honor the
383 /// requested capacity, or the operation is unsupported by that backend.
384 ///
385 /// # Examples
386 ///
387 /// ```
388 /// use causal_triangulations::prelude::testing::*;
389 ///
390 /// fn main() -> Result<(), MockError> {
391 /// let mut backend = MockBackend::create_triangle();
392 /// let counts = (backend.vertex_count(), backend.edge_count(), backend.face_count());
393 ///
394 /// backend.reserve_capacity(16, 8)?;
395 ///
396 /// assert_eq!(counts, (backend.vertex_count(), backend.edge_count(), backend.face_count()));
397 /// Ok(())
398 /// }
399 /// ```
400 fn reserve_capacity(&mut self, vertices: usize, faces: usize) -> Result<(), Self::Error>;
401}