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, Vertex, 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.origin(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.origin(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_half_edge(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_half_edge(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        initial_half_edge: HalfEdgeId,
168        curr_half_edge: Option<HalfEdgeId>,
169    },
170    SpokesIter
171);
172
173impl SpokesWalker {
174    #[inline]
175    pub fn next<VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC>(
176        &mut self,
177        dcel: &Dcel<VW, HEW, FW, VC, HEC, FC>,
178    ) -> Option<EdgeId> {
179        let next_half_edge = dcel.turn_half_edge(self.curr_half_edge?);
180
181        std::mem::replace(
182            &mut self.curr_half_edge,
183            (next_half_edge != self.initial_half_edge).then_some(next_half_edge),
184        )
185        .map(|half_edge| dcel.full_edge(half_edge))
186    }
187}
188
189impl<'a, VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC> Iterator
190    for SpokesIter<'a, VW, HEW, FW, VC, HEC, FC>
191{
192    type Item = EdgeId;
193
194    #[inline]
195    fn next(&mut self) -> Option<Self::Item> {
196        self.walker.next(self.dcel)
197    }
198}
199
200create_walker_and_iter!(
201    SpokesReverseWalker {
202        initial_half_edge: HalfEdgeId,
203        curr_half_edge: Option<HalfEdgeId>,
204    },
205    SpokesReverseIter
206);
207
208impl SpokesReverseWalker {
209    #[inline]
210    pub fn next<VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC>(
211        &mut self,
212        dcel: &Dcel<VW, HEW, FW, VC, HEC, FC>,
213    ) -> Option<EdgeId> {
214        let next_half_edge = dcel.turn_back_half_edge(self.curr_half_edge?);
215
216        std::mem::replace(
217            &mut self.curr_half_edge,
218            (next_half_edge != self.initial_half_edge).then_some(next_half_edge),
219        )
220        .map(|half_edge| dcel.full_edge(half_edge))
221    }
222}
223
224impl<'a, VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC> Iterator
225    for SpokesReverseIter<'a, VW, HEW, FW, VC, HEC, FC>
226{
227    type Item = EdgeId;
228
229    #[inline]
230    fn next(&mut self) -> Option<Self::Item> {
231        self.walker.next(self.dcel)
232    }
233}
234
235create_walker_and_iter!(
236    InterspokesWalker {
237        initial_half_edge: HalfEdgeId,
238        curr_half_edge: Option<HalfEdgeId>,
239    },
240    InterspokesIter
241);
242
243impl InterspokesWalker {
244    #[inline]
245    pub fn next<VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC>(
246        &mut self,
247        dcel: &Dcel<VW, HEW, FW, VC, HEC, FC>,
248    ) -> Option<HalfEdgeId> {
249        let next_half_edge = dcel.turn_half_edge(self.curr_half_edge?);
250
251        std::mem::replace(
252            &mut self.curr_half_edge,
253            (next_half_edge != self.initial_half_edge).then_some(next_half_edge),
254        )
255    }
256}
257
258impl<'a, VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC> Iterator
259    for InterspokesIter<'a, VW, HEW, FW, VC, HEC, FC>
260{
261    type Item = FaceId;
262
263    #[inline]
264    fn next(&mut self) -> Option<Self::Item> {
265        self.walker
266            .next(self.dcel)
267            .map(|half_edge| self.dcel.face_in_front(half_edge))
268    }
269}
270
271create_walker_and_iter!(
272    InterspokesReverseWalker {
273        initial_half_edge: HalfEdgeId,
274        curr_half_edge: Option<HalfEdgeId>,
275    },
276    InterspokesReverseIter
277);
278
279impl InterspokesReverseWalker {
280    #[inline]
281    pub fn next<VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC>(
282        &mut self,
283        dcel: &Dcel<VW, HEW, FW, VC, HEC, FC>,
284    ) -> Option<HalfEdgeId> {
285        let next_half_edge = dcel.turn_back_half_edge(self.curr_half_edge?);
286
287        std::mem::replace(
288            &mut self.curr_half_edge,
289            (next_half_edge != self.initial_half_edge).then_some(next_half_edge),
290        )
291    }
292}
293
294impl<'a, VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC> Iterator
295    for InterspokesReverseIter<'a, VW, HEW, FW, VC, HEC, FC>
296{
297    type Item = FaceId;
298
299    #[inline]
300    fn next(&mut self) -> Option<Self::Item> {
301        self.walker
302            .next(self.dcel)
303            .map(|half_edge| self.dcel.face_in_front(half_edge))
304    }
305}
306
307create_walker_and_iter!(
308    CirculateHalfEdgesWithExcludesWalker {
309        initial_half_edge: HalfEdgeId,
310        curr_half_edge: Option<HalfEdgeId>,
311        excluded_half_edges: Vec<HalfEdgeId>,
312    },
313    CirculateHalfEdgesWithExcludesIter
314);
315
316impl CirculateHalfEdgesWithExcludesWalker {
317    #[inline]
318    pub fn next<VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC>(
319        &mut self,
320        dcel: &Dcel<VW, HEW, FW, VC, HEC, FC>,
321    ) -> Option<HalfEdgeId> {
322        let mut candidate_next_half_edge = dcel.next_half_edge(self.curr_half_edge?);
323
324        while self.excluded_half_edges.contains(&candidate_next_half_edge) {
325            candidate_next_half_edge = dcel.turn_half_edge(candidate_next_half_edge);
326        }
327
328        let next_half_edge = candidate_next_half_edge;
329
330        std::mem::replace(
331            &mut self.curr_half_edge,
332            (next_half_edge != self.initial_half_edge).then_some(next_half_edge),
333        )
334    }
335}
336
337impl<'a, VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC> Iterator
338    for CirculateHalfEdgesWithExcludesIter<'a, VW, HEW, FW, VC, HEC, FC>
339{
340    type Item = HalfEdgeId;
341
342    #[inline]
343    fn next(&mut self) -> Option<Self::Item> {
344        self.walker.next(self.dcel)
345    }
346}
347
348create_walker_and_iter!(
349    CirculateHalfEdgesWithExcludesReverseWalker {
350        initial_half_edge: HalfEdgeId,
351        curr_half_edge: Option<HalfEdgeId>,
352        excluded_half_edges: Vec<HalfEdgeId>,
353    },
354    CirculateHalfEdgesWithExcludesReverseIter
355);
356
357impl CirculateHalfEdgesWithExcludesReverseWalker {
358    #[inline]
359    pub fn next<VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC>(
360        &mut self,
361        dcel: &Dcel<VW, HEW, FW, VC, HEC, FC>,
362    ) -> Option<HalfEdgeId> {
363        let mut candidate_next_half_edge = dcel.prev_half_edge(self.curr_half_edge?);
364
365        while self.excluded_half_edges.contains(&candidate_next_half_edge) {
366            candidate_next_half_edge =
367                dcel.twin(dcel.turn_back_half_edge(dcel.twin(candidate_next_half_edge)));
368        }
369
370        let next_half_edge = candidate_next_half_edge;
371
372        std::mem::replace(
373            &mut self.curr_half_edge,
374            (next_half_edge != self.initial_half_edge).then_some(next_half_edge),
375        )
376    }
377}
378
379impl<'a, VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC> Iterator
380    for CirculateHalfEdgesWithExcludesReverseIter<'a, VW, HEW, FW, VC, HEC, FC>
381{
382    type Item = HalfEdgeId;
383
384    #[inline]
385    fn next(&mut self) -> Option<Self::Item> {
386        self.walker.next(self.dcel)
387    }
388}
389
390create_walker_and_iter!(
391    CirculateEdgesWithExcludesWalker {
392        circulator: CirculateHalfEdgesWithExcludesWalker,
393    },
394    CirculateEdgesWithExcludesIter
395);
396
397impl CirculateEdgesWithExcludesWalker {
398    #[inline]
399    pub fn next<VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC>(
400        &mut self,
401        dcel: &Dcel<VW, HEW, FW, VC, HEC, FC>,
402    ) -> Option<EdgeId> {
403        self.circulator
404            .next(dcel)
405            .map(|half_edge| dcel.full_edge(half_edge))
406    }
407}
408
409impl<'a, VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC> Iterator
410    for CirculateEdgesWithExcludesIter<'a, VW, HEW, FW, VC, HEC, FC>
411{
412    type Item = EdgeId;
413
414    #[inline]
415    fn next(&mut self) -> Option<Self::Item> {
416        self.walker.next(self.dcel)
417    }
418}
419
420create_walker_and_iter!(
421    CirculateEdgesWithExcludesReverseWalker {
422        circulator: CirculateHalfEdgesWithExcludesReverseWalker,
423    },
424    CirculateEdgesWithExcludesReverseIter
425);
426
427impl CirculateEdgesWithExcludesReverseWalker {
428    #[inline]
429    pub fn next<VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC>(
430        &mut self,
431        dcel: &Dcel<VW, HEW, FW, VC, HEC, FC>,
432    ) -> Option<EdgeId> {
433        self.circulator
434            .next(dcel)
435            .map(|half_edge| dcel.full_edge(half_edge))
436    }
437}
438
439impl<'a, VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC> Iterator
440    for CirculateEdgesWithExcludesReverseIter<'a, VW, HEW, FW, VC, HEC, FC>
441{
442    type Item = EdgeId;
443
444    #[inline]
445    fn next(&mut self) -> Option<Self::Item> {
446        self.walker.next(self.dcel)
447    }
448}
449
450create_walker_and_iter!(
451    FaceVertexesWalker {
452        circulator: FaceHalfEdgesWalker,
453    },
454    FaceVertexesIter
455);
456
457impl FaceVertexesWalker {
458    #[inline]
459    pub fn next<
460        VW,
461        HEW,
462        FW,
463        VC: Get<usize, Value = Vertex<VW>>,
464        HEC: Get<usize, Value = HalfEdge<HEW>>,
465        FC,
466    >(
467        &mut self,
468        dcel: &Dcel<VW, HEW, FW, VC, HEC, FC>,
469    ) -> Option<VertexId> {
470        self.circulator
471            .next(dcel)
472            .map(|half_edge| dcel.origin(half_edge))
473    }
474}
475
476impl<
477    'a,
478    VW,
479    HEW,
480    FW,
481    VC: Get<usize, Value = Vertex<VW>>,
482    HEC: Get<usize, Value = HalfEdge<HEW>>,
483    FC,
484> Iterator for FaceVertexesIter<'a, VW, HEW, FW, VC, HEC, FC>
485{
486    type Item = VertexId;
487
488    #[inline]
489    fn next(&mut self) -> Option<Self::Item> {
490        self.walker.next(self.dcel)
491    }
492}
493
494create_walker_and_iter!(
495    FaceVertexesReverseWalker {
496        circulator: FaceHalfEdgesReverseWalker,
497    },
498    FaceVertexesReverseIter
499);
500
501impl FaceVertexesReverseWalker {
502    #[inline]
503    pub fn next<
504        VW,
505        HEW,
506        FW,
507        VC: Get<usize, Value = Vertex<VW>>,
508        HEC: Get<usize, Value = HalfEdge<HEW>>,
509        FC,
510    >(
511        &mut self,
512        dcel: &Dcel<VW, HEW, FW, VC, HEC, FC>,
513    ) -> Option<VertexId> {
514        self.circulator
515            .next(dcel)
516            .map(|half_edge| dcel.origin(half_edge))
517    }
518}
519
520impl<
521    'a,
522    VW,
523    HEW,
524    FW,
525    VC: Get<usize, Value = Vertex<VW>>,
526    HEC: Get<usize, Value = HalfEdge<HEW>>,
527    FC,
528> Iterator for FaceVertexesReverseIter<'a, VW, HEW, FW, VC, HEC, FC>
529{
530    type Item = VertexId;
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    FaceHalfEdgesWalker {
540        initial_half_edge: HalfEdgeId,
541        curr_half_edge: Option<HalfEdgeId>,
542    },
543    FaceHalfEdgesIter
544);
545
546impl FaceHalfEdgesWalker {
547    #[inline]
548    pub fn next<VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC>(
549        &mut self,
550        dcel: &Dcel<VW, HEW, FW, VC, HEC, FC>,
551    ) -> Option<HalfEdgeId> {
552        let next_half_edge = dcel.next_half_edge(self.curr_half_edge?);
553
554        std::mem::replace(
555            &mut self.curr_half_edge,
556            (next_half_edge != self.initial_half_edge).then_some(next_half_edge),
557        )
558    }
559}
560
561impl<'a, VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC> Iterator
562    for FaceHalfEdgesIter<'a, VW, HEW, FW, VC, HEC, FC>
563{
564    type Item = HalfEdgeId;
565
566    #[inline]
567    fn next(&mut self) -> Option<Self::Item> {
568        self.walker.next(self.dcel)
569    }
570}
571
572create_walker_and_iter!(
573    FaceHalfEdgesReverseWalker {
574        initial_half_edge: HalfEdgeId,
575        curr_half_edge: Option<HalfEdgeId>,
576    },
577    FaceHalfEdgesReverseIter
578);
579
580impl FaceHalfEdgesReverseWalker {
581    #[inline]
582    pub fn next<VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC>(
583        &mut self,
584        dcel: &Dcel<VW, HEW, FW, VC, HEC, FC>,
585    ) -> Option<HalfEdgeId> {
586        let next_half_edge = dcel.prev_half_edge(self.curr_half_edge?);
587
588        std::mem::replace(
589            &mut self.curr_half_edge,
590            (next_half_edge != self.initial_half_edge).then_some(next_half_edge),
591        )
592    }
593}
594
595impl<'a, VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC> Iterator
596    for FaceHalfEdgesReverseIter<'a, VW, HEW, FW, VC, HEC, FC>
597{
598    type Item = HalfEdgeId;
599
600    #[inline]
601    fn next(&mut self) -> Option<Self::Item> {
602        self.walker.next(self.dcel)
603    }
604}
605
606create_walker_and_iter!(
607    FaceEdgesWalker {
608        circulator: FaceHalfEdgesWalker,
609    },
610    FaceEdgesIter
611);
612
613impl FaceEdgesWalker {
614    #[inline]
615    pub fn next<VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC>(
616        &mut self,
617        dcel: &Dcel<VW, HEW, FW, VC, HEC, FC>,
618    ) -> Option<EdgeId> {
619        self.circulator
620            .next(dcel)
621            .map(|half_edge| dcel.full_edge(half_edge))
622    }
623}
624
625impl<'a, VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC> Iterator
626    for FaceEdgesIter<'a, VW, HEW, FW, VC, HEC, FC>
627{
628    type Item = EdgeId;
629
630    #[inline]
631    fn next(&mut self) -> Option<Self::Item> {
632        self.walker.next(self.dcel)
633    }
634}
635
636create_walker_and_iter!(
637    FaceEdgesReverseWalker {
638        circulator: FaceHalfEdgesReverseWalker,
639    },
640    FaceEdgesReverseIter
641);
642
643impl FaceEdgesReverseWalker {
644    #[inline]
645    pub fn next<VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC>(
646        &mut self,
647        dcel: &Dcel<VW, HEW, FW, VC, HEC, FC>,
648    ) -> Option<EdgeId> {
649        self.circulator
650            .next(dcel)
651            .map(|half_edge| dcel.full_edge(half_edge))
652    }
653}
654
655impl<'a, VW, HEW, FW, VC, HEC: Get<usize, Value = HalfEdge<HEW>>, FC> Iterator
656    for FaceEdgesReverseIter<'a, VW, HEW, FW, VC, HEC, FC>
657{
658    type Item = EdgeId;
659
660    #[inline]
661    fn next(&mut self) -> Option<Self::Item> {
662        self.walker.next(self.dcel)
663    }
664}
dcel/walkers.rs

dcel/
walkers.rs
