dcel/
iter.rs

1// SPDX-FileCopyrightText: 2026 dcel contributors
2//
3// SPDX-License-Identifier: MIT OR Apache-2.0
4
5use maplike::Get;
6
7use crate::{
8    Dcel, EdgeId, Face, FaceId, HalfEdge, HalfEdgeId, Vertex, VertexId,
9    walkers::{
10        CirculateEdgesWithExcludesIter, CirculateEdgesWithExcludesReverseIter,
11        CirculateEdgesWithExcludesReverseWalker, CirculateEdgesWithExcludesWalker,
12        CirculateHalfEdgesWithExcludesIter, CirculateHalfEdgesWithExcludesReverseIter,
13        CirculateHalfEdgesWithExcludesReverseWalker, CirculateHalfEdgesWithExcludesWalker,
14        CirculateVertexesWithExcludesIter, CirculateVertexesWithExcludesReverseIter,
15        CirculateVertexesWithExcludesReverseWalker, CirculateVertexesWithExcludesWalker,
16        FaceEdgesIter, FaceEdgesReverseIter, FaceEdgesReverseWalker, FaceEdgesWalker,
17        FaceHalfEdgesIter, FaceHalfEdgesReverseIter, FaceHalfEdgesReverseWalker,
18        FaceHalfEdgesWalker, FaceVertexesIter, FaceVertexesReverseIter, FaceVertexesReverseWalker,
19        FaceVertexesWalker, HalfSpokesIter, HalfSpokesReverseIter, HalfSpokesReverseWalker,
20        HalfSpokesWalker, InterspokesIter, InterspokesReverseIter, InterspokesReverseWalker,
21        InterspokesWalker, SpokesIter, SpokesReverseIter, SpokesReverseWalker, SpokesWalker,
22    },
23};
24
25impl<VW, HEW, FW, VC: Get<usize, Value = Vertex<VW>>, HEC: Get<usize, Value = HalfEdge<HEW>>, FC>
26    Dcel<VW, HEW, FW, VC, HEC, FC>
27{
28    #[inline]
29    pub fn vertex_rim_vertexes(
30        &self,
31        vertex: VertexId,
32    ) -> CirculateVertexesWithExcludesIter<'_, VW, HEW, FW, VC, HEC, FC> {
33        CirculateVertexesWithExcludesWalker {
34            circulator: self.vertex_rim_half_edges(vertex).walker(),
35        }
36        .iter(self)
37    }
38
39    #[inline]
40    pub fn vertex_rim_vertexes_reverse(
41        &self,
42        vertex: VertexId,
43    ) -> CirculateVertexesWithExcludesReverseIter<'_, VW, HEW, FW, VC, HEC, FC> {
44        CirculateVertexesWithExcludesReverseWalker {
45            circulator: self.vertex_rim_half_edges_reverse(vertex).walker(),
46        }
47        .iter(self)
48    }
49}
50
51impl<VW, HEW, FW, VC: Get<usize, Value = Vertex<VW>>, HEC, FC> Dcel<VW, HEW, FW, VC, HEC, FC> {
52    #[inline]
53    pub fn vertex_half_spokes(
54        &self,
55        vertex: VertexId,
56    ) -> HalfSpokesIter<'_, VW, HEW, FW, VC, HEC, FC> {
57        self.half_spokes(self.outgoing_next_half_edge(vertex))
58    }
59
60    #[inline]
61    pub fn vertex_half_spokes_reverse(
62        &self,
63        vertex: VertexId,
64    ) -> HalfSpokesReverseIter<'_, VW, HEW, FW, VC, HEC, FC> {
65        self.half_spokes_reverse(self.outgoing_next_half_edge(vertex))
66    }
67}
68
69impl<VW, HEW, FW, VC: Get<usize, Value = Vertex<VW>>, HEC: Get<usize, Value = HalfEdge<HEW>>, FC>
70    Dcel<VW, HEW, FW, VC, HEC, FC>
71{
72    #[inline]
73    pub fn vertex_rim_half_edges(
74        &self,
75        vertex: VertexId,
76    ) -> CirculateHalfEdgesWithExcludesIter<'_, VW, HEW, FW, VC, HEC, FC> {
77        let initial_half_edge = self.next_half_edge(self.outgoing_next_half_edge(vertex));
78        let excluded_half_edges = self
79            .vertex_spokes(vertex)
80            .flat_map(|edge| [edge.forward(), edge.backward()])
81            .collect::<Vec<HalfEdgeId>>();
82
83        // Boundary vertexes do not have cycles circulating them.
84        // Return an empty walker-iterator instead.
85        if self.is_boundary_vertex(vertex) {
86            return CirculateHalfEdgesWithExcludesWalker {
87                initial_half_edge,
88                curr_half_edge: None,
89                excluded_half_edges,
90            }
91            .iter(self);
92        }
93
94        self.circulate_half_edges_with_excludes(initial_half_edge, excluded_half_edges)
95    }
96
97    #[inline]
98    pub fn vertex_rim_half_edges_reverse(
99        &self,
100        vertex: VertexId,
101    ) -> CirculateHalfEdgesWithExcludesReverseIter<'_, VW, HEW, FW, VC, HEC, FC> {
102        let initial_half_edge = self.prev_half_edge(self.incoming_next_half_edge(vertex));
103        let excluded_half_edges = self
104            .vertex_spokes(vertex)
105            .flat_map(|edge| [edge.forward(), edge.backward()])
106            .collect::<Vec<HalfEdgeId>>();
107
108        // Boundary vertexes do not have cycles circulating them.
109        // Return an empty walker-iterator instead.
110        if self.is_boundary_vertex(vertex) {
111            return CirculateHalfEdgesWithExcludesReverseWalker {
112                initial_half_edge,
113                curr_half_edge: None,
114                excluded_half_edges,
115            }
116            .iter(self);
117        }
118
119        self.circulate_half_edges_with_excludes_reverse(initial_half_edge, excluded_half_edges)
120    }
121}
122
123impl<VW, HEW, FW, VC, HEC, FC> Dcel<VW, HEW, FW, VC, HEC, FC> {
124    #[inline]
125    pub fn half_spokes(
126        &self,
127        initial_half_edge: HalfEdgeId,
128    ) -> HalfSpokesIter<'_, VW, HEW, FW, VC, HEC, FC> {
129        HalfSpokesWalker {
130            initial_half_edge,
131            curr_half_edge: Some(initial_half_edge),
132        }
133        .iter(self)
134    }
135
136    #[inline]
137    pub fn half_spokes_reverse(
138        &self,
139        initial_half_edge: HalfEdgeId,
140    ) -> HalfSpokesReverseIter<'_, VW, HEW, FW, VC, HEC, FC> {
141        HalfSpokesReverseWalker {
142            initial_half_edge,
143            curr_half_edge: Some(initial_half_edge),
144        }
145        .iter(self)
146    }
147}
148
149impl<VW, HEW, FW, VC: Get<usize, Value = Vertex<VW>>, HEC: Get<usize, Value = HalfEdge<HEW>>, FC>
150    Dcel<VW, HEW, FW, VC, HEC, FC>
151{
152    #[inline]
153    pub fn vertex_spokes(&self, vertex: VertexId) -> SpokesIter<'_, VW, HEW, FW, VC, HEC, FC> {
154        self.spokes(self.vertex_next_edge(vertex))
155    }
156
157    #[inline]
158    pub fn vertex_spokes_reverse(
159        &self,
160        vertex: VertexId,
161    ) -> SpokesReverseIter<'_, VW, HEW, FW, VC, HEC, FC> {
162        self.spokes_reverse(self.vertex_next_edge(vertex))
163    }
164}
165
166impl<VW, HEW, FW, VC: Get<usize, Value = Vertex<VW>>, HEC: Get<usize, Value = HalfEdge<HEW>>, FC>
167    Dcel<VW, HEW, FW, VC, HEC, FC>
168{
169    #[inline]
170    pub fn vertex_rim_edges(
171        &self,
172        vertex: VertexId,
173    ) -> CirculateEdgesWithExcludesIter<'_, VW, HEW, FW, VC, HEC, FC> {
174        CirculateEdgesWithExcludesWalker {
175            circulator: self.vertex_rim_half_edges(vertex).walker(),
176        }
177        .iter(self)
178    }
179
180    #[inline]
181    pub fn vertex_rim_edges_reverse(
182        &self,
183        vertex: VertexId,
184    ) -> CirculateEdgesWithExcludesReverseIter<'_, VW, HEW, FW, VC, HEC, FC> {
185        CirculateEdgesWithExcludesReverseWalker {
186            circulator: self.vertex_rim_half_edges_reverse(vertex).walker(),
187        }
188        .iter(self)
189    }
190}
191
192impl<VW, HEW, FW, VC: Get<usize, Value = Vertex<VW>>, HEC: Get<usize, Value = HalfEdge<HEW>>, FC>
193    Dcel<VW, HEW, FW, VC, HEC, FC>
194{
195    #[inline]
196    pub fn vertex_interspokes(
197        &self,
198        vertex: VertexId,
199    ) -> InterspokesIter<'_, VW, HEW, FW, VC, HEC, FC> {
200        self.interspokes(self.outgoing_next_half_edge(vertex))
201    }
202
203    #[inline]
204    pub fn vertex_interspokes_reverse(
205        &self,
206        vertex: VertexId,
207    ) -> InterspokesReverseIter<'_, VW, HEW, FW, VC, HEC, FC> {
208        self.interspokes_reverse(self.outgoing_next_half_edge(vertex))
209    }
210}
211
212impl<VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC> Dcel<VW, HEW, FW, VC, HEC, FC> {
213    #[inline]
214    pub fn spokes(&self, initial_edge: EdgeId) -> SpokesIter<'_, VW, HEW, FW, VC, HEC, FC> {
215        SpokesWalker {
216            initial_edge,
217            curr_edge: Some(initial_edge),
218        }
219        .iter(self)
220    }
221
222    #[inline]
223    pub fn spokes_reverse(
224        &self,
225        initial_edge: EdgeId,
226    ) -> SpokesReverseIter<'_, VW, HEW, FW, VC, HEC, FC> {
227        SpokesReverseWalker {
228            initial_edge,
229            curr_edge: Some(initial_edge),
230        }
231        .iter(self)
232    }
233
234    #[inline]
235    pub fn interspokes(
236        &self,
237        initial_half_edge: HalfEdgeId,
238    ) -> InterspokesIter<'_, VW, HEW, FW, VC, HEC, FC> {
239        InterspokesWalker {
240            initial_half_edge,
241            curr_half_edge: Some(initial_half_edge),
242        }
243        .iter(self)
244    }
245
246    #[inline]
247    pub fn interspokes_reverse(
248        &self,
249        initial_half_edge: HalfEdgeId,
250    ) -> InterspokesReverseIter<'_, VW, HEW, FW, VC, HEC, FC> {
251        InterspokesReverseWalker {
252            initial_half_edge,
253            curr_half_edge: Some(initial_half_edge),
254        }
255        .iter(self)
256    }
257}
258
259impl<VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC> Dcel<VW, HEW, FW, VC, HEC, FC> {
260    #[inline]
261    pub fn circulate_vertexes_with_excludes(
262        &self,
263        initial_edge: EdgeId,
264        excluded_edges: impl IntoIterator<Item = EdgeId>,
265    ) -> CirculateVertexesWithExcludesIter<'_, VW, HEW, FW, VC, HEC, FC> {
266        CirculateVertexesWithExcludesWalker {
267            circulator: self
268                .circulate_half_edges_with_excludes(
269                    initial_edge.forward(),
270                    excluded_edges
271                        .into_iter()
272                        .flat_map(|edge| [edge.forward(), edge.backward()]),
273                )
274                .walker(),
275        }
276        .iter(self)
277    }
278
279    #[inline]
280    pub fn circulate_vertexes_with_excludes_reverse(
281        &self,
282        initial_edge: EdgeId,
283        excluded_edges: impl IntoIterator<Item = EdgeId>,
284    ) -> CirculateVertexesWithExcludesReverseIter<'_, VW, HEW, FW, VC, HEC, FC> {
285        CirculateVertexesWithExcludesReverseWalker {
286            circulator: self
287                .circulate_half_edges_with_excludes_reverse(
288                    initial_edge.forward(),
289                    excluded_edges
290                        .into_iter()
291                        .flat_map(|edge| [edge.forward(), edge.backward()]),
292                )
293                .walker(),
294        }
295        .iter(self)
296    }
297
298    #[inline]
299    pub fn circulate_half_edges_with_excludes(
300        &self,
301        initial_half_edge: HalfEdgeId,
302        excluded_half_edges: impl IntoIterator<Item = HalfEdgeId>,
303    ) -> CirculateHalfEdgesWithExcludesIter<'_, VW, HEW, FW, VC, HEC, FC> {
304        CirculateHalfEdgesWithExcludesWalker {
305            initial_half_edge,
306            curr_half_edge: Some(initial_half_edge),
307            excluded_half_edges: excluded_half_edges.into_iter().collect(),
308        }
309        .iter(self)
310    }
311
312    #[inline]
313    pub fn circulate_half_edges_with_excludes_reverse(
314        &self,
315        initial_half_edge: HalfEdgeId,
316        excluded_half_edges: impl IntoIterator<Item = HalfEdgeId>,
317    ) -> CirculateHalfEdgesWithExcludesReverseIter<'_, VW, HEW, FW, VC, HEC, FC> {
318        CirculateHalfEdgesWithExcludesReverseWalker {
319            initial_half_edge,
320            curr_half_edge: Some(initial_half_edge),
321            excluded_half_edges: excluded_half_edges.into_iter().collect(),
322        }
323        .iter(self)
324    }
325
326    #[inline]
327    pub fn circulate_edges_with_excludes(
328        &self,
329        initial_edge: EdgeId,
330        excluded_edges: impl IntoIterator<Item = EdgeId>,
331    ) -> CirculateEdgesWithExcludesIter<'_, VW, HEW, FW, VC, HEC, FC> {
332        CirculateEdgesWithExcludesWalker {
333            circulator: self
334                .circulate_half_edges_with_excludes(
335                    initial_edge.forward(),
336                    excluded_edges
337                        .into_iter()
338                        .flat_map(|edge| [edge.forward(), edge.backward()]),
339                )
340                .walker(),
341        }
342        .iter(self)
343    }
344
345    #[inline]
346    pub fn circulate_edges_with_excludes_reverse(
347        &self,
348        initial_edge: EdgeId,
349        excluded_edges: impl IntoIterator<Item = EdgeId>,
350    ) -> CirculateEdgesWithExcludesReverseIter<'_, VW, HEW, FW, VC, HEC, FC> {
351        CirculateEdgesWithExcludesReverseWalker {
352            circulator: self
353                .circulate_half_edges_with_excludes_reverse(
354                    initial_edge.forward(),
355                    excluded_edges
356                        .into_iter()
357                        .flat_map(|edge| [edge.forward(), edge.backward()]),
358                )
359                .walker(),
360        }
361        .iter(self)
362    }
363}
364
365impl<
366    VW,
367    HEW,
368    FW,
369    VC: Get<usize, Value = Vertex<VW>>,
370    HEC: Get<usize, Value = HalfEdge<HEW>>,
371    FC: Get<usize, Value = Face<FW>>,
372> Dcel<VW, HEW, FW, VC, HEC, FC>
373{
374    #[inline]
375    pub fn face_vertexes(&self, face: FaceId) -> FaceVertexesIter<'_, VW, HEW, FW, VC, HEC, FC> {
376        FaceVertexesWalker {
377            circulator: self.face_half_edges(face).walker(),
378        }
379        .iter(self)
380    }
381
382    #[inline]
383    pub fn face_vertexes_reverse(
384        &self,
385        face: FaceId,
386    ) -> FaceVertexesReverseIter<'_, VW, HEW, FW, VC, HEC, FC> {
387        FaceVertexesReverseWalker {
388            circulator: self.face_half_edges_reverse(face).walker(),
389        }
390        .iter(self)
391    }
392}
393
394impl<VW, HEW, FW, VC, HEC, FC: Get<usize, Value = Face<FW>>> Dcel<VW, HEW, FW, VC, HEC, FC> {
395    #[inline]
396    pub fn face_half_edges(&self, face: FaceId) -> FaceHalfEdgesIter<'_, VW, HEW, FW, VC, HEC, FC> {
397        // Unbounded face has no half-edges. Since the unbounded face is
398        // supposed to behave similarly to other faces, it is better to branch
399        // out here than to have the code below panic.
400        if face == self.unbounded_face() {
401            return FaceHalfEdgesWalker {
402                // Uninitialized half-edge.
403                initial_half_edge: HalfEdgeId::new(0),
404                // Setting `curr_edge` to None makes the iterator produce no
405                // elements.
406                curr_half_edge: None,
407            }
408            .iter(self);
409        }
410
411        let initial_half_edge = self
412            .faces
413            .get(&face.id())
414            .unwrap()
415            .incident_half_edge
416            .unwrap();
417
418        FaceHalfEdgesWalker {
419            initial_half_edge,
420            curr_half_edge: Some(initial_half_edge),
421        }
422        .iter(self)
423    }
424
425    #[inline]
426    pub fn face_half_edges_reverse(
427        &self,
428        face: FaceId,
429    ) -> FaceHalfEdgesReverseIter<'_, VW, HEW, FW, VC, HEC, FC> {
430        // Unbounded face has no half-edges. Since the unbounded face is
431        // supposed to behave similarly to other faces, it is better to branch
432        // out here than to have the code below panic.
433        if face == self.unbounded_face() {
434            return FaceHalfEdgesReverseWalker {
435                // Uninitialized half-edge.
436                initial_half_edge: HalfEdgeId::new(0),
437                // Setting `curr_edge` to None makes the iterator produce no
438                // elements.
439                curr_half_edge: None,
440            }
441            .iter(self);
442        }
443
444        let initial_half_edge = self
445            .faces
446            .get(&face.id())
447            .unwrap()
448            .incident_half_edge
449            .unwrap();
450
451        FaceHalfEdgesReverseWalker {
452            initial_half_edge,
453            curr_half_edge: Some(initial_half_edge),
454        }
455        .iter(self)
456    }
457}
458
459impl<VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC: Get<usize, Value = Face<FW>>>
460    Dcel<VW, HEW, FW, VC, HEC, FC>
461{
462    #[inline]
463    pub fn face_edges(&self, face: FaceId) -> FaceEdgesIter<'_, VW, HEW, FW, VC, HEC, FC> {
464        FaceEdgesWalker {
465            circulator: self.face_half_edges(face).walker(),
466        }
467        .iter(self)
468    }
469
470    #[inline]
471    pub fn face_edges_reverse(
472        &self,
473        face: FaceId,
474    ) -> FaceEdgesReverseIter<'_, VW, HEW, FW, VC, HEC, FC> {
475        FaceEdgesReverseWalker {
476            circulator: self.face_half_edges_reverse(face).walker(),
477        }
478        .iter(self)
479    }
480}
481
482#[cfg(test)]
483mod test {
484    use crate::{
485        Dcel, assert_face_boundary, assert_vertex_rim, assert_vertex_spokes_interspokes,
486        init_dcel_with_3x3_hex_mesh,
487    };
488
489    #[test]
490    fn test_vertex_rim() {
491        let dcel = init_dcel_with_3x3_hex_mesh!(Dcel<(i32, i32)>);
492
493        assert_vertex_rim!(&dcel, 0, 0);
494        assert_vertex_rim!(&dcel, 1, 0);
495        assert_vertex_rim!(&dcel, 2, 0);
496        assert_vertex_rim!(&dcel, 3, 0);
497        assert_vertex_rim!(&dcel, 4, 0);
498        assert_vertex_rim!(&dcel, 5, 12);
499        assert_vertex_rim!(&dcel, 6, 0);
500        assert_vertex_rim!(&dcel, 7, 0);
501        assert_vertex_rim!(&dcel, 8, 12);
502        assert_vertex_rim!(&dcel, 9, 12);
503        assert_vertex_rim!(&dcel, 10, 0);
504        assert_vertex_rim!(&dcel, 11, 0);
505        assert_vertex_rim!(&dcel, 12, 12);
506        assert_vertex_rim!(&dcel, 13, 0);
507        assert_vertex_rim!(&dcel, 14, 0);
508        assert_vertex_rim!(&dcel, 15, 12);
509        assert_vertex_rim!(&dcel, 16, 12);
510        assert_vertex_rim!(&dcel, 17, 12);
511        assert_vertex_rim!(&dcel, 18, 12);
512        assert_vertex_rim!(&dcel, 19, 0);
513        assert_vertex_rim!(&dcel, 20, 0);
514        assert_vertex_rim!(&dcel, 21, 0);
515        assert_vertex_rim!(&dcel, 22, 0);
516        assert_vertex_rim!(&dcel, 23, 0);
517        assert_vertex_rim!(&dcel, 24, 0);
518        assert_vertex_rim!(&dcel, 25, 0);
519        assert_vertex_rim!(&dcel, 26, 0);
520        assert_vertex_rim!(&dcel, 27, 0);
521        assert_vertex_rim!(&dcel, 28, 0);
522        assert_vertex_rim!(&dcel, 29, 0);
523    }
524
525    #[test]
526    fn test_vertex_spokes_interspokes() {
527        let dcel = init_dcel_with_3x3_hex_mesh!(Dcel<(i32, i32)>);
528
529        assert_vertex_spokes_interspokes!(&dcel, 0, 3);
530        assert_vertex_spokes_interspokes!(&dcel, 1, 2);
531        assert_vertex_spokes_interspokes!(&dcel, 2, 2);
532        assert_vertex_spokes_interspokes!(&dcel, 3, 2);
533        assert_vertex_spokes_interspokes!(&dcel, 4, 3);
534        assert_vertex_spokes_interspokes!(&dcel, 5, 3);
535        assert_vertex_spokes_interspokes!(&dcel, 6, 3);
536        assert_vertex_spokes_interspokes!(&dcel, 7, 2);
537        assert_vertex_spokes_interspokes!(&dcel, 8, 3);
538        assert_vertex_spokes_interspokes!(&dcel, 9, 3);
539        assert_vertex_spokes_interspokes!(&dcel, 10, 2);
540        assert_vertex_spokes_interspokes!(&dcel, 11, 2);
541        assert_vertex_spokes_interspokes!(&dcel, 12, 3);
542        assert_vertex_spokes_interspokes!(&dcel, 13, 3);
543        assert_vertex_spokes_interspokes!(&dcel, 14, 3);
544        assert_vertex_spokes_interspokes!(&dcel, 15, 3);
545        assert_vertex_spokes_interspokes!(&dcel, 16, 3);
546        assert_vertex_spokes_interspokes!(&dcel, 17, 3);
547        assert_vertex_spokes_interspokes!(&dcel, 18, 3);
548        assert_vertex_spokes_interspokes!(&dcel, 19, 2);
549        assert_vertex_spokes_interspokes!(&dcel, 20, 3);
550        assert_vertex_spokes_interspokes!(&dcel, 21, 2);
551        assert_vertex_spokes_interspokes!(&dcel, 22, 2);
552        assert_vertex_spokes_interspokes!(&dcel, 23, 2);
553        assert_vertex_spokes_interspokes!(&dcel, 24, 2);
554        assert_vertex_spokes_interspokes!(&dcel, 25, 3);
555        assert_vertex_spokes_interspokes!(&dcel, 26, 2);
556        assert_vertex_spokes_interspokes!(&dcel, 27, 3);
557        assert_vertex_spokes_interspokes!(&dcel, 28, 2);
558        assert_vertex_spokes_interspokes!(&dcel, 29, 2);
559    }
560
561    #[test]
562    fn test_face_boundary() {
563        let dcel = init_dcel_with_3x3_hex_mesh!(Dcel<(i32, i32)>);
564
565        assert_face_boundary!(&dcel, 0, 0);
566        assert_face_boundary!(&dcel, 1, 6);
567        assert_face_boundary!(&dcel, 2, 6);
568        assert_face_boundary!(&dcel, 3, 6);
569        assert_face_boundary!(&dcel, 4, 6);
570        assert_face_boundary!(&dcel, 5, 6);
571        assert_face_boundary!(&dcel, 6, 6);
572        assert_face_boundary!(&dcel, 7, 6);
573        assert_face_boundary!(&dcel, 8, 6);
574        assert_face_boundary!(&dcel, 9, 6);
575    }
576}
dcel/iter.rs

dcel/
iter.rs
