dcel/
walkers.rs

1// SPDX-FileCopyrightText: 2026 dcel contributors
2//
3// SPDX-License-Identifier: MIT OR Apache-2.0
4
5use maplike::Get;
6
7use crate::{Dcel, EdgeId, FaceId, HalfEdge, HalfEdgeId, VertexId};
8
9macro_rules! create_walker_and_iter {
10    ($walker:ident { $($field:ident: $type:ty),* $(,)? }, $iter:ident) => {
11        pub struct $walker {
12            $(pub $field: $type,)*
13        }
14
15        impl $walker {
16            pub fn iter<'a, VW, HEW, FW, VC, HEC, FC>(
17                self,
18                dcel: &'a Dcel<VW, HEW, FW, VC, HEC, FC>,
19            ) -> $iter<'a, VW, HEW, FW, VC, HEC, FC> {
20                $iter { walker: self, dcel }
21            }
22        }
23
24        pub struct $iter<'a, VW, HEW, FW, VC, HEC, FC> {
25            walker: $walker,
26            dcel: &'a Dcel<VW, HEW, FW, VC, HEC, FC>,
27        }
28
29        impl<'a, VW, HEW, FW, VC, HEC, FC> $iter<'a, VW, HEW, FW, VC, HEC, FC> {
30            pub fn walker(self) -> $walker {
31                self.walker
32            }
33        }
34    };
35}
36
37create_walker_and_iter!(
38    CirculateVertexesWithExcludesWalker {
39        circulator: CirculateHalfEdgesWithExcludesWalker,
40    },
41    CirculateVertexesWithExcludesIter
42);
43
44impl CirculateVertexesWithExcludesWalker {
45    #[inline]
46    pub fn next<VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC>(
47        &mut self,
48        dcel: &Dcel<VW, HEW, FW, VC, HEC, FC>,
49    ) -> Option<VertexId> {
50        self.circulator
51            .next(dcel)
52            .map(|half_edge| dcel.source(half_edge))
53    }
54}
55
56impl<'a, VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC> Iterator
57    for CirculateVertexesWithExcludesIter<'a, VW, HEW, FW, VC, HEC, FC>
58{
59    type Item = VertexId;
60
61    #[inline]
62    fn next(&mut self) -> Option<Self::Item> {
63        self.walker.next(self.dcel)
64    }
65}
66
67create_walker_and_iter!(
68    CirculateVertexesWithExcludesReverseWalker {
69        circulator: CirculateHalfEdgesWithExcludesReverseWalker,
70    },
71    CirculateVertexesWithExcludesReverseIter
72);
73
74impl CirculateVertexesWithExcludesReverseWalker {
75    #[inline]
76    pub fn next<VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC>(
77        &mut self,
78        dcel: &Dcel<VW, HEW, FW, VC, HEC, FC>,
79    ) -> Option<VertexId> {
80        self.circulator
81            .next(dcel)
82            .map(|half_edge| dcel.source(half_edge))
83    }
84}
85
86impl<'a, VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC> Iterator
87    for CirculateVertexesWithExcludesReverseIter<'a, VW, HEW, FW, VC, HEC, FC>
88{
89    type Item = VertexId;
90
91    #[inline]
92    fn next(&mut self) -> Option<Self::Item> {
93        self.walker.next(self.dcel)
94    }
95}
96
97create_walker_and_iter!(
98    HalfSpokesWalker {
99        initial_half_edge: HalfEdgeId,
100        curr_half_edge: Option<HalfEdgeId>,
101    },
102    HalfSpokesIter
103);
104
105impl HalfSpokesWalker {
106    #[inline]
107    pub fn next<VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC>(
108        &mut self,
109        dcel: &Dcel<VW, HEW, FW, VC, HEC, FC>,
110    ) -> Option<HalfEdgeId> {
111        let next_half_edge = dcel.turn(self.curr_half_edge?);
112
113        std::mem::replace(
114            &mut self.curr_half_edge,
115            (next_half_edge != self.initial_half_edge).then_some(next_half_edge),
116        )
117    }
118}
119
120impl<'a, VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC> Iterator
121    for HalfSpokesIter<'a, VW, HEW, FW, VC, HEC, FC>
122{
123    type Item = HalfEdgeId;
124
125    #[inline]
126    fn next(&mut self) -> Option<Self::Item> {
127        self.walker.next(self.dcel)
128    }
129}
130
131create_walker_and_iter!(
132    HalfSpokesReverseWalker {
133        initial_half_edge: HalfEdgeId,
134        curr_half_edge: Option<HalfEdgeId>,
135    },
136    HalfSpokesReverseIter
137);
138
139impl HalfSpokesReverseWalker {
140    #[inline]
141    pub fn next<VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC>(
142        &mut self,
143        dcel: &Dcel<VW, HEW, FW, VC, HEC, FC>,
144    ) -> Option<HalfEdgeId> {
145        let next_half_edge = dcel.turn_back(self.curr_half_edge?);
146
147        std::mem::replace(
148            &mut self.curr_half_edge,
149            (next_half_edge != self.initial_half_edge).then_some(next_half_edge),
150        )
151    }
152}
153
154impl<'a, VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC> Iterator
155    for HalfSpokesReverseIter<'a, VW, HEW, FW, VC, HEC, FC>
156{
157    type Item = HalfEdgeId;
158
159    #[inline]
160    fn next(&mut self) -> Option<Self::Item> {
161        self.walker.next(self.dcel)
162    }
163}
164
165create_walker_and_iter!(
166    SpokesWalker {
167        circulator: HalfSpokesWalker,
168    },
169    SpokesIter
170);
171
172impl SpokesWalker {
173    #[inline]
174    pub fn next<VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC>(
175        &mut self,
176        dcel: &Dcel<VW, HEW, FW, VC, HEC, FC>,
177    ) -> Option<EdgeId> {
178        self.circulator
179            .next(dcel)
180            .map(|half_edge| dcel.full_edge(half_edge))
181    }
182}
183
184impl<'a, VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC> Iterator
185    for SpokesIter<'a, VW, HEW, FW, VC, HEC, FC>
186{
187    type Item = EdgeId;
188
189    #[inline]
190    fn next(&mut self) -> Option<Self::Item> {
191        self.walker.next(self.dcel)
192    }
193}
194
195create_walker_and_iter!(
196    SpokesReverseWalker {
197        circulator: HalfSpokesReverseWalker,
198    },
199    SpokesReverseIter
200);
201
202impl SpokesReverseWalker {
203    #[inline]
204    pub fn next<VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC>(
205        &mut self,
206        dcel: &Dcel<VW, HEW, FW, VC, HEC, FC>,
207    ) -> Option<EdgeId> {
208        self.circulator
209            .next(dcel)
210            .map(|half_edge| dcel.full_edge(half_edge))
211    }
212}
213
214impl<'a, VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC> Iterator
215    for SpokesReverseIter<'a, VW, HEW, FW, VC, HEC, FC>
216{
217    type Item = EdgeId;
218
219    #[inline]
220    fn next(&mut self) -> Option<Self::Item> {
221        self.walker.next(self.dcel)
222    }
223}
224
225create_walker_and_iter!(
226    InterspokesWalker {
227        initial_half_edge: HalfEdgeId,
228        curr_half_edge: Option<HalfEdgeId>,
229    },
230    InterspokesIter
231);
232
233impl InterspokesWalker {
234    #[inline]
235    pub fn next<VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC>(
236        &mut self,
237        dcel: &Dcel<VW, HEW, FW, VC, HEC, FC>,
238    ) -> Option<HalfEdgeId> {
239        let next_half_edge = dcel.turn(self.curr_half_edge?);
240
241        std::mem::replace(
242            &mut self.curr_half_edge,
243            (next_half_edge != self.initial_half_edge).then_some(next_half_edge),
244        )
245    }
246}
247
248impl<'a, VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC> Iterator
249    for InterspokesIter<'a, VW, HEW, FW, VC, HEC, FC>
250{
251    type Item = FaceId;
252
253    #[inline]
254    fn next(&mut self) -> Option<Self::Item> {
255        self.walker
256            .next(self.dcel)
257            .map(|half_edge| self.dcel.incident_face(half_edge))
258    }
259}
260
261create_walker_and_iter!(
262    InterspokesReverseWalker {
263        initial_half_edge: HalfEdgeId,
264        curr_half_edge: Option<HalfEdgeId>,
265    },
266    InterspokesReverseIter
267);
268
269impl InterspokesReverseWalker {
270    #[inline]
271    pub fn next<VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC>(
272        &mut self,
273        dcel: &Dcel<VW, HEW, FW, VC, HEC, FC>,
274    ) -> Option<HalfEdgeId> {
275        let next_half_edge = dcel.turn_back(self.curr_half_edge?);
276
277        std::mem::replace(
278            &mut self.curr_half_edge,
279            (next_half_edge != self.initial_half_edge).then_some(next_half_edge),
280        )
281    }
282}
283
284impl<'a, VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC> Iterator
285    for InterspokesReverseIter<'a, VW, HEW, FW, VC, HEC, FC>
286{
287    type Item = FaceId;
288
289    #[inline]
290    fn next(&mut self) -> Option<Self::Item> {
291        self.walker
292            .next(self.dcel)
293            .map(|half_edge| self.dcel.incident_face(half_edge))
294    }
295}
296
297create_walker_and_iter!(
298    CirculateHalfEdgesWithExcludesWalker {
299        initial_half_edge: HalfEdgeId,
300        curr_half_edge: Option<HalfEdgeId>,
301        excluded_half_edges: Vec<HalfEdgeId>,
302    },
303    CirculateHalfEdgesWithExcludesIter
304);
305
306impl CirculateHalfEdgesWithExcludesWalker {
307    #[inline]
308    pub fn next<VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC>(
309        &mut self,
310        dcel: &Dcel<VW, HEW, FW, VC, HEC, FC>,
311    ) -> Option<HalfEdgeId> {
312        let mut candidate_next_half_edge = dcel.next(self.curr_half_edge?);
313
314        while self.excluded_half_edges.contains(&candidate_next_half_edge) {
315            candidate_next_half_edge = dcel.turn(candidate_next_half_edge);
316        }
317
318        let next_half_edge = candidate_next_half_edge;
319
320        std::mem::replace(
321            &mut self.curr_half_edge,
322            (next_half_edge != self.initial_half_edge).then_some(next_half_edge),
323        )
324    }
325}
326
327impl<'a, VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC> Iterator
328    for CirculateHalfEdgesWithExcludesIter<'a, VW, HEW, FW, VC, HEC, FC>
329{
330    type Item = HalfEdgeId;
331
332    #[inline]
333    fn next(&mut self) -> Option<Self::Item> {
334        self.walker.next(self.dcel)
335    }
336}
337
338create_walker_and_iter!(
339    CirculateHalfEdgesWithExcludesReverseWalker {
340        initial_half_edge: HalfEdgeId,
341        curr_half_edge: Option<HalfEdgeId>,
342        excluded_half_edges: Vec<HalfEdgeId>,
343    },
344    CirculateHalfEdgesWithExcludesReverseIter
345);
346
347impl CirculateHalfEdgesWithExcludesReverseWalker {
348    #[inline]
349    pub fn next<VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC>(
350        &mut self,
351        dcel: &Dcel<VW, HEW, FW, VC, HEC, FC>,
352    ) -> Option<HalfEdgeId> {
353        let mut candidate_next_half_edge = dcel.prev(self.curr_half_edge?);
354
355        while self.excluded_half_edges.contains(&candidate_next_half_edge) {
356            candidate_next_half_edge =
357                dcel.twin(dcel.turn_back(dcel.twin(candidate_next_half_edge)));
358        }
359
360        let next_half_edge = candidate_next_half_edge;
361
362        std::mem::replace(
363            &mut self.curr_half_edge,
364            (next_half_edge != self.initial_half_edge).then_some(next_half_edge),
365        )
366    }
367}
368
369impl<'a, VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC> Iterator
370    for CirculateHalfEdgesWithExcludesReverseIter<'a, VW, HEW, FW, VC, HEC, FC>
371{
372    type Item = HalfEdgeId;
373
374    #[inline]
375    fn next(&mut self) -> Option<Self::Item> {
376        self.walker.next(self.dcel)
377    }
378}
379
380create_walker_and_iter!(
381    CirculateEdgesWithExcludesWalker {
382        circulator: CirculateHalfEdgesWithExcludesWalker,
383    },
384    CirculateEdgesWithExcludesIter
385);
386
387impl CirculateEdgesWithExcludesWalker {
388    #[inline]
389    pub fn next<VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC>(
390        &mut self,
391        dcel: &Dcel<VW, HEW, FW, VC, HEC, FC>,
392    ) -> Option<EdgeId> {
393        self.circulator
394            .next(dcel)
395            .map(|half_edge| dcel.full_edge(half_edge))
396    }
397}
398
399impl<'a, VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC> Iterator
400    for CirculateEdgesWithExcludesIter<'a, VW, HEW, FW, VC, HEC, FC>
401{
402    type Item = EdgeId;
403
404    #[inline]
405    fn next(&mut self) -> Option<Self::Item> {
406        self.walker.next(self.dcel)
407    }
408}
409
410create_walker_and_iter!(
411    CirculateEdgesWithExcludesReverseWalker {
412        circulator: CirculateHalfEdgesWithExcludesReverseWalker,
413    },
414    CirculateEdgesWithExcludesReverseIter
415);
416
417impl CirculateEdgesWithExcludesReverseWalker {
418    #[inline]
419    pub fn next<VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC>(
420        &mut self,
421        dcel: &Dcel<VW, HEW, FW, VC, HEC, FC>,
422    ) -> Option<EdgeId> {
423        self.circulator
424            .next(dcel)
425            .map(|half_edge| dcel.full_edge(half_edge))
426    }
427}
428
429impl<'a, VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC> Iterator
430    for CirculateEdgesWithExcludesReverseIter<'a, VW, HEW, FW, VC, HEC, FC>
431{
432    type Item = EdgeId;
433
434    #[inline]
435    fn next(&mut self) -> Option<Self::Item> {
436        self.walker.next(self.dcel)
437    }
438}
439
440create_walker_and_iter!(
441    CirculationHalfSpokesWalker {
442        circulator: CirculateHalfEdgesWithExcludesWalker,
443        half_spokes_walker: HalfSpokesWalker,
444        prev_half_edge: HalfEdgeId,
445    },
446    CirculateHalfSpokesIter
447);
448
449impl CirculationHalfSpokesWalker {
450    #[inline]
451    pub fn next<VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC>(
452        &mut self,
453        dcel: &Dcel<VW, HEW, FW, VC, HEC, FC>,
454    ) -> Option<HalfEdgeId> {
455        loop {
456            while let Some(candidate_half_spoke) = self.half_spokes_walker.next(dcel) {
457                if !self
458                    .circulator
459                    .excluded_half_edges
460                    .contains(&candidate_half_spoke)
461                    && self.prev_half_edge != candidate_half_spoke
462                    && dcel.twin(candidate_half_spoke) != self.prev_half_edge
463                    && self.circulator.curr_half_edge.is_none_or(|half_edge| {
464                        candidate_half_spoke != half_edge
465                            && dcel.twin(candidate_half_spoke) != half_edge
466                    })
467                {
468                    return Some(candidate_half_spoke);
469                }
470            }
471
472            self.prev_half_edge = self.circulator.next(dcel)?;
473            self.half_spokes_walker = dcel.half_spokes(self.circulator.curr_half_edge?).walker();
474        }
475    }
476}
477
478impl<'a, VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC> Iterator
479    for CirculateHalfSpokesIter<'a, VW, HEW, FW, VC, HEC, FC>
480{
481    type Item = HalfEdgeId;
482
483    #[inline]
484    fn next(&mut self) -> Option<Self::Item> {
485        self.walker.next(self.dcel)
486    }
487}
488
489create_walker_and_iter!(
490    CirculationHalfSpokesReverseWalker {
491        circulator: CirculateHalfEdgesWithExcludesReverseWalker,
492        half_spokes_walker: HalfSpokesWalker,
493        prev_half_edge: HalfEdgeId,
494    },
495    CirculateHalfSpokesReverseIter
496);
497
498impl CirculationHalfSpokesReverseWalker {
499    #[inline]
500    pub fn next<VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC>(
501        &mut self,
502        dcel: &Dcel<VW, HEW, FW, VC, HEC, FC>,
503    ) -> Option<HalfEdgeId> {
504        loop {
505            while let Some(candidate_half_spoke) = self.half_spokes_walker.next(dcel) {
506                if !self
507                    .circulator
508                    .excluded_half_edges
509                    .contains(&candidate_half_spoke)
510                    && self.prev_half_edge != candidate_half_spoke
511                    && dcel.twin(candidate_half_spoke) != self.prev_half_edge
512                    && self.circulator.curr_half_edge.is_none_or(|half_edge| {
513                        candidate_half_spoke != half_edge
514                            && dcel.twin(candidate_half_spoke) != half_edge
515                    })
516                {
517                    return Some(candidate_half_spoke);
518                }
519            }
520
521            self.prev_half_edge = self.circulator.next(dcel)?;
522            self.half_spokes_walker = dcel.half_spokes(self.circulator.curr_half_edge?).walker();
523        }
524    }
525}
526
527impl<'a, VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC> Iterator
528    for CirculateHalfSpokesReverseIter<'a, VW, HEW, FW, VC, HEC, FC>
529{
530    type Item = HalfEdgeId;
531
532    #[inline]
533    fn next(&mut self) -> Option<Self::Item> {
534        self.walker.next(self.dcel)
535    }
536}
537
538create_walker_and_iter!(
539    CirculationSpokesWalker {
540        circulator: CirculationHalfSpokesWalker,
541    },
542    CirculationSpokesIter
543);
544
545impl CirculationSpokesWalker {
546    #[inline]
547    pub fn next<VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC>(
548        &mut self,
549        dcel: &Dcel<VW, HEW, FW, VC, HEC, FC>,
550    ) -> Option<EdgeId> {
551        self.circulator
552            .next(dcel)
553            .map(|half_spoke| dcel.full_edge(half_spoke))
554    }
555}
556
557impl<'a, VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC> Iterator
558    for CirculationSpokesIter<'a, VW, HEW, FW, VC, HEC, FC>
559{
560    type Item = EdgeId;
561
562    #[inline]
563    fn next(&mut self) -> Option<Self::Item> {
564        self.walker.next(self.dcel)
565    }
566}
567
568create_walker_and_iter!(
569    CirculationSpokesReverseWalker {
570        circulator: CirculationHalfSpokesReverseWalker,
571    },
572    CirculationSpokesReverseIter
573);
574
575impl CirculationSpokesReverseWalker {
576    #[inline]
577    pub fn next<VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC>(
578        &mut self,
579        dcel: &Dcel<VW, HEW, FW, VC, HEC, FC>,
580    ) -> Option<EdgeId> {
581        self.circulator
582            .next(dcel)
583            .map(|half_spoke| dcel.full_edge(half_spoke))
584    }
585}
586
587impl<'a, VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC> Iterator
588    for CirculationSpokesReverseIter<'a, VW, HEW, FW, VC, HEC, FC>
589{
590    type Item = EdgeId;
591
592    #[inline]
593    fn next(&mut self) -> Option<Self::Item> {
594        self.walker.next(self.dcel)
595    }
596}
597
598create_walker_and_iter!(
599    CirculationInterspokesWalker {
600        circulator: CirculationHalfSpokesWalker,
601    },
602    CirculationInterspokesIter
603);
604
605impl CirculationInterspokesWalker {
606    #[inline]
607    pub fn next<VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC>(
608        &mut self,
609        dcel: &Dcel<VW, HEW, FW, VC, HEC, FC>,
610    ) -> Option<FaceId> {
611        self.circulator
612            .next(dcel)
613            .map(|half_spoke| dcel.incident_face(half_spoke))
614    }
615}
616
617impl<'a, VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC> Iterator
618    for CirculationInterspokesIter<'a, VW, HEW, FW, VC, HEC, FC>
619{
620    type Item = FaceId;
621
622    #[inline]
623    fn next(&mut self) -> Option<Self::Item> {
624        self.walker.next(self.dcel)
625    }
626}
627
628create_walker_and_iter!(
629    CirculationInterspokesReverseWalker {
630        circulator: CirculationHalfSpokesReverseWalker,
631    },
632    CirculationInterspokesReverseIter
633);
634
635impl CirculationInterspokesReverseWalker {
636    #[inline]
637    pub fn next<VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC>(
638        &mut self,
639        dcel: &Dcel<VW, HEW, FW, VC, HEC, FC>,
640    ) -> Option<FaceId> {
641        self.circulator
642            .next(dcel)
643            .map(|half_spoke| dcel.incident_face(half_spoke))
644    }
645}
646
647impl<'a, VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC> Iterator
648    for CirculationInterspokesReverseIter<'a, VW, HEW, FW, VC, HEC, FC>
649{
650    type Item = FaceId;
651
652    #[inline]
653    fn next(&mut self) -> Option<Self::Item> {
654        self.walker.next(self.dcel)
655    }
656}
dcel/walkers.rs

dcel/
walkers.rs
