dcel/
insert.rs

1// SPDX-FileCopyrightText: 2026 dcel contributors
2//
3// SPDX-License-Identifier: MIT OR Apache-2.0
4
5use maplike::{Get, Insert, Push};
6
7use crate::{
8    Dcel, EdgeId, Face, FaceId, HalfEdge, HalfEdgeId, Vertex, VertexId,
9    track::{EdgesTracker, VertexTracker},
10};
11
12impl<
13    VW: Clone + Eq + Ord,
14    HEW: Clone + Default,
15    FW: Clone + Default,
16    VC: Get<usize, Value = Vertex<VW>> + Insert<usize> + Push<usize>,
17    HEC: Get<usize, Value = HalfEdge<HEW>> + Insert<usize> + Push<usize>,
18    FC: Get<usize, Value = Face<FW>> + Insert<usize> + Push<usize>,
19> Dcel<VW, HEW, FW, VC, HEC, FC>
20{
21    pub fn insert_mesh(
22        &mut self,
23        face_polygons: impl IntoIterator<Item = impl IntoIterator<Item = VW>>,
24    ) -> Vec<FaceId> {
25        self.insert_mesh_in_face(face_polygons)
26    }
27
28    pub fn insert_mesh_in_face(
29        &mut self,
30        face_polygons: impl IntoIterator<Item = impl IntoIterator<Item = VW>>,
31    ) -> Vec<FaceId> {
32        let mut vertex_weights_counter = VertexTracker::new();
33        let mut edges_tracker = EdgesTracker::new();
34        let mut faces = vec![];
35
36        for face_polygon in face_polygons {
37            faces.push(self.insert_adjoined_polygon(
38                &mut vertex_weights_counter,
39                &mut edges_tracker,
40                face_polygon,
41            ));
42        }
43
44        faces
45    }
46
47    fn insert_adjoined_polygon(
48        &mut self,
49        vertex_weights_counter: &mut VertexTracker<VW>,
50        edges_tracker: &mut EdgesTracker,
51        vertex_weights: impl IntoIterator<Item = VW>,
52    ) -> FaceId {
53        self.insert_adjoined_polygon_in_face(
54            vertex_weights_counter,
55            edges_tracker,
56            self.unbounded_face(),
57            vertex_weights,
58        )
59    }
60
61    fn insert_adjoined_polygon_in_face(
62        &mut self,
63        vertex_weights_counter: &mut VertexTracker<VW>,
64        edges_tracker: &mut EdgesTracker,
65        outer_face: FaceId,
66        vertex_weights: impl IntoIterator<Item = VW>,
67    ) -> FaceId {
68        self.insert_adjoined_polygon_in_face_with_all_weights(
69            vertex_weights_counter,
70            edges_tracker,
71            outer_face,
72            vertex_weights,
73            std::iter::repeat((HEW::default(), HEW::default())),
74            FW::default(),
75        )
76    }
77}
78
79impl<
80    VW: Clone,
81    HEW: Clone + Default,
82    FW: Clone + Default,
83    VC: Get<usize, Value = Vertex<VW>> + Insert<usize> + Push<usize>,
84    HEC: Get<usize, Value = HalfEdge<HEW>> + Insert<usize> + Push<usize>,
85    FC: Get<usize, Value = Face<FW>> + Insert<usize> + Push<usize>,
86> Dcel<VW, HEW, FW, VC, HEC, FC>
87{
88    pub fn insert_polygon(&mut self, vertex_weights: impl IntoIterator<Item = VW>) -> FaceId {
89        self.insert_polygon_in_face(self.unbounded_face(), vertex_weights)
90    }
91
92    pub fn insert_polygon_in_face(
93        &mut self,
94        outer_face: FaceId,
95        vertex_weights: impl IntoIterator<Item = VW>,
96    ) -> FaceId {
97        self.insert_polygon_in_face_with_all_weights(
98            outer_face,
99            vertex_weights,
100            std::iter::repeat((HEW::default(), HEW::default())),
101            FW::default(),
102        )
103    }
104}
105
106impl<
107    VW: Clone + Eq + Ord,
108    HEW: Clone,
109    FW: Clone,
110    VC: Get<usize, Value = Vertex<VW>> + Insert<usize> + Push<usize>,
111    HEC: Get<usize, Value = HalfEdge<HEW>> + Insert<usize> + Push<usize>,
112    FC: Get<usize, Value = Face<FW>> + Insert<usize> + Push<usize>,
113> Dcel<VW, HEW, FW, VC, HEC, FC>
114{
115    fn insert_adjoined_polygon_with_all_weights(
116        &mut self,
117        vertex_weights_counter: &mut VertexTracker<VW>,
118        edges_tracker: &mut EdgesTracker,
119        vertex_weights: impl IntoIterator<Item = VW>,
120        edge_weights: impl IntoIterator<Item = (HEW, HEW)>,
121        face_weight: FW,
122    ) -> FaceId {
123        self.insert_adjoined_polygon_in_face_with_all_weights(
124            vertex_weights_counter,
125            edges_tracker,
126            self.unbounded_face(),
127            vertex_weights,
128            edge_weights,
129            face_weight,
130        )
131    }
132
133    fn insert_adjoined_polygon_in_face_with_all_weights(
134        &mut self,
135        vertex_weights_tracker: &mut VertexTracker<VW>,
136        edges_tracker: &mut EdgesTracker,
137        outer_face: FaceId,
138        vertex_weights: impl IntoIterator<Item = VW>,
139        edge_weights: impl IntoIterator<Item = (HEW, HEW)>,
140        face_weight: FW,
141    ) -> FaceId {
142        let new_face = self.add_unwired_face(face_weight);
143        let vertices =
144            self.add_deduplicated_unwired_polygon_vertices(vertex_weights_tracker, vertex_weights);
145        let edges = self.add_adjoined_unwired_polygon_edges(
146            edges_tracker,
147            &vertices,
148            new_face,
149            outer_face,
150            edge_weights,
151        );
152
153        self.wire_outer_half_edge_chain_adjoiningly(
154            outer_face,
155            &edges
156                .iter()
157                .map(|(_, backward)| *backward)
158                .collect::<Vec<_>>(),
159        );
160        self.wire_inner_half_edge_chain(
161            new_face,
162            &edges
163                .iter()
164                .map(|(forward, _)| *forward)
165                .collect::<Vec<_>>(),
166        );
167
168        new_face
169    }
170
171    fn add_deduplicated_unwired_polygon_vertices(
172        &mut self,
173        vertex_weights_counter: &mut VertexTracker<VW>,
174        vertex_weights: impl IntoIterator<Item = VW>,
175    ) -> Vec<VertexId> {
176        vertex_weights
177            .into_iter()
178            .map(|weight| {
179                vertex_weights_counter
180                    .vertex(weight.clone())
181                    .unwrap_or_else(|| {
182                        let vertex = self.add_unwired_vertex(weight.clone());
183                        vertex_weights_counter.visit_vertex(weight, vertex);
184                        vertex
185                    })
186            })
187            .collect()
188    }
189
190    fn add_adjoined_unwired_polygon_edges(
191        &mut self,
192        edges_tracker: &mut EdgesTracker,
193        vertices: &[VertexId],
194        new_face: FaceId,
195        outer_face: FaceId,
196        edge_weights: impl IntoIterator<Item = (HEW, HEW)>,
197    ) -> Vec<(HalfEdgeId, HalfEdgeId)> {
198        let vertices_circular_tuple_windows = vertices
199            .iter()
200            .zip(vertices.iter().skip(1).chain(vertices.iter().take(1)));
201
202        let mut edges: Vec<(HalfEdgeId, HalfEdgeId)> = vec![];
203
204        for ((&from_vertex, &to_vertex), (forward_half_edge_weight, backward_half_edge_weight)) in
205            vertices_circular_tuple_windows.zip(edge_weights)
206        {
207            let edge = if let Some(existing_half_edge) =
208                edges_tracker.vertices_half_edge(to_vertex, from_vertex)
209            {
210                // Reuse already existing shared edge.
211                let forward = self.twin(existing_half_edge);
212                let reused_edge = (forward, existing_half_edge);
213
214                // Make the forward half-edge point to the new face.
215                self.half_edges.insert(
216                    forward.id(),
217                    HalfEdge {
218                        face: new_face,
219                        ..self.half_edges.get(&forward.id()).unwrap().clone()
220                    },
221                );
222
223                reused_edge
224            } else {
225                // There is no preexisting shared edge. Add a new one.
226                let (forward, backward) = self.add_unwired_edge(
227                    from_vertex,
228                    to_vertex,
229                    new_face,
230                    outer_face,
231                    forward_half_edge_weight,
232                    backward_half_edge_weight,
233                );
234                (forward, backward)
235            };
236
237            edges_tracker.visit_vertices_edge(from_vertex, to_vertex, edge.0);
238            edges.push(edge);
239        }
240
241        edges
242    }
243}
244
245impl<
246    VW: Clone,
247    HEW: Clone,
248    FW: Clone,
249    VC: Get<usize, Value = Vertex<VW>> + Insert<usize> + Push<usize>,
250    HEC: Get<usize, Value = HalfEdge<HEW>> + Insert<usize> + Push<usize>,
251    FC: Get<usize, Value = Face<FW>> + Insert<usize> + Push<usize>,
252> Dcel<VW, HEW, FW, VC, HEC, FC>
253{
254    pub fn insert_polygon_with_all_weights(
255        &mut self,
256        vertex_weights: impl IntoIterator<Item = VW>,
257        edge_weights: impl IntoIterator<Item = (HEW, HEW)>,
258        face_weight: FW,
259    ) -> FaceId {
260        self.insert_polygon_in_face_with_all_weights(
261            self.unbounded_face(),
262            vertex_weights,
263            edge_weights,
264            face_weight,
265        )
266    }
267
268    pub fn insert_polygon_in_face_with_all_weights(
269        &mut self,
270        outer_face: FaceId,
271        vertex_weights: impl IntoIterator<Item = VW>,
272        edge_weights: impl IntoIterator<Item = (HEW, HEW)>,
273        face_weight: FW,
274    ) -> FaceId {
275        let new_face = self.add_unwired_face(face_weight);
276        let vertices = self.add_unwired_polygon_vertices(vertex_weights);
277        let edges = self.add_unwired_polygon_edges(&vertices, new_face, outer_face, edge_weights);
278
279        self.wire_outer_half_edge_chain_circularly(
280            &edges.iter().map(|edge| edge.greater()).collect::<Vec<_>>(),
281        );
282        self.wire_inner_half_edge_chain(
283            new_face,
284            &edges.iter().map(|edge| edge.lesser()).collect::<Vec<_>>(),
285        );
286
287        new_face
288    }
289
290    fn add_unwired_polygon_vertices(
291        &mut self,
292        vertex_weights: impl IntoIterator<Item = VW>,
293    ) -> Vec<VertexId> {
294        vertex_weights
295            .into_iter()
296            .map(|vertex_weight| self.add_unwired_vertex(vertex_weight))
297            .collect()
298    }
299
300    fn add_unwired_polygon_edges(
301        &mut self,
302        vertices: &[VertexId],
303        new_face: FaceId,
304        outer_face: FaceId,
305        edge_weights: impl IntoIterator<Item = (HEW, HEW)>,
306    ) -> Vec<EdgeId> {
307        let vertices_circular_tuple_windows = vertices
308            .iter()
309            .zip(vertices.iter().skip(1).chain(vertices.iter().take(1)));
310
311        let mut edges = vec![];
312
313        for ((from_vertex, to_vertex), (forward_half_edge_weight, backward_half_edge_weight)) in
314            vertices_circular_tuple_windows.zip(edge_weights)
315        {
316            let (forward, _) = self.add_unwired_edge(
317                *from_vertex,
318                *to_vertex,
319                new_face,
320                outer_face,
321                forward_half_edge_weight,
322                backward_half_edge_weight,
323            );
324            edges.push(self.full_edge(forward));
325        }
326
327        edges
328    }
329}
330
331impl<
332    VW: Clone,
333    HEW: Clone + Default,
334    FW: Clone + Default,
335    VC: Get<usize, Value = Vertex<VW>> + Insert<usize> + Push<usize>,
336    HEC: Get<usize, Value = HalfEdge<HEW>> + Insert<usize> + Push<usize>,
337    FC: Get<usize, Value = Face<FW>> + Insert<usize> + Push<usize>,
338> Dcel<VW, HEW, FW, VC, HEC, FC>
339{
340    pub fn insert_edge(
341        &mut self,
342        from: VertexId,
343        to: VertexId,
344    ) -> ((HalfEdgeId, HalfEdgeId), FaceId) {
345        self.split_face_by_edge(from, to, self.find_vertices_common_face(from, to).unwrap())
346    }
347
348    pub fn insert_edge_chain(
349        &mut self,
350        from: VertexId,
351        to: VertexId,
352        vertex_weights: impl IntoIterator<Item = VW>,
353    ) -> (Vec<(HalfEdgeId, HalfEdgeId)>, FaceId) {
354        self.split_face_by_edge_chain(
355            from,
356            to,
357            vertex_weights,
358            self.find_vertices_common_face(from, to).unwrap(),
359        )
360    }
361}
362
363impl<
364    VW: Clone,
365    HEW: Clone,
366    FW: Clone + Default,
367    VC: Get<usize, Value = Vertex<VW>> + Insert<usize> + Push<usize>,
368    HEC: Get<usize, Value = HalfEdge<HEW>> + Insert<usize> + Push<usize>,
369    FC: Get<usize, Value = Face<FW>> + Insert<usize> + Push<usize>,
370> Dcel<VW, HEW, FW, VC, HEC, FC>
371{
372    fn insert_edge_chain_with_edge_weights(
373        &mut self,
374        from: VertexId,
375        to: VertexId,
376        vertex_weights: impl IntoIterator<Item = VW>,
377        edge_weights: impl IntoIterator<Item = (HEW, HEW)>,
378    ) -> (Vec<(HalfEdgeId, HalfEdgeId)>, FaceId) {
379        self.split_face_by_edge_chain_with_all_weights(
380            from,
381            to,
382            vertex_weights,
383            edge_weights,
384            self.find_vertices_common_face(from, to).unwrap(),
385            FW::default(),
386        )
387    }
388}
389
390#[cfg(test)]
391mod test {
392    use crate::{HalfEdgeId, assert_face_boundary, init_dcel_with_3x3_hex_mesh};
393
394    use super::*;
395
396    #[test]
397    fn test_insert_polygon() {
398        let mut dcel = Dcel::<(i32, i32)>::new();
399        let face = dcel.insert_polygon([(0, 0), (10, 0), (10, 10), (0, 10)]);
400
401        assert_eq!(dcel.faces().len(), 2);
402
403        assert_face_boundary!(dcel, 0, 0);
404        assert_face_boundary!(dcel, face.id(), 4);
405    }
406
407    #[test]
408    fn test_insert_edge() {
409        let mut dcel = init_dcel_with_3x3_hex_mesh!(Dcel<(i32, i32)>);
410        let face_to_split = FaceId::new(5);
411        let face_to_split_vertices: Vec<VertexId> = dcel.face_vertices(face_to_split).collect();
412
413        // Split face 5 in two with a single edge.
414        let (_new_edge, _new_face) =
415            dcel.insert_edge(face_to_split_vertices[0], face_to_split_vertices[3]);
416
417        // There are now eleven faces in total: one unbounded and ten bounded.
418        assert_eq!(dcel.faces().len(), 11);
419
420        // The original hexagon is now split into two quads.
421        assert_face_boundary!(dcel, 0, 0);
422        assert_face_boundary!(dcel, 1, 6);
423        assert_face_boundary!(dcel, 2, 6);
424        assert_face_boundary!(dcel, 3, 6);
425        assert_face_boundary!(dcel, 4, 6);
426        // First quad face.
427        assert_face_boundary!(dcel, 5, 4);
428        assert_face_boundary!(dcel, 6, 6);
429        assert_face_boundary!(dcel, 7, 6);
430        assert_face_boundary!(dcel, 8, 6);
431        assert_face_boundary!(dcel, 9, 6);
432        // Second quad face.
433        assert_face_boundary!(dcel, 10, 4);
434    }
435
436    #[test]
437    fn test_insert_adjoined_squares() {
438        let two_adjoined_squares: Vec<Vec<(i64, i64)>> = vec![
439            // Left square (CCW).
440            vec![(0, 0), (0, 1), (-1, 1), (-1, 0)],
441            // Right square sharing edge with left square (CCW).
442            vec![(0, 0), (1, 0), (1, 1), (0, 1)],
443        ];
444
445        let mut dcel: Dcel<(i64, i64)> = Dcel::new();
446        dcel.insert_mesh(two_adjoined_squares);
447
448        assert_eq!(dcel.vertices().len(), 6);
449        assert_eq!(dcel.half_edges().len(), 14);
450        assert_eq!(dcel.faces().len(), 3);
451
452        assert_eq!(
453            dcel.face_vertices(FaceId::new(0))
454                .collect::<Vec<VertexId>>()
455                .len(),
456            0
457        );
458        assert_eq!(
459            dcel.face_half_edges(FaceId::new(0))
460                .collect::<Vec<HalfEdgeId>>()
461                .len(),
462            0
463        );
464        assert_eq!(
465            dcel.face_edges(FaceId::new(0))
466                .collect::<Vec<EdgeId>>()
467                .len(),
468            0
469        );
470        assert_eq!(
471            dcel.face_half_edges(FaceId::new(1))
472                .collect::<Vec<HalfEdgeId>>()
473                .len(),
474            4
475        );
476        assert_eq!(
477            dcel.face_edges(FaceId::new(1))
478                .collect::<Vec<EdgeId>>()
479                .len(),
480            4
481        );
482        assert_eq!(
483            dcel.face_half_edges(FaceId::new(1))
484                .collect::<Vec<HalfEdgeId>>()
485                .len(),
486            4
487        );
488        assert_eq!(
489            dcel.face_edges(FaceId::new(2))
490                .collect::<Vec<EdgeId>>()
491                .len(),
492            4
493        );
494    }
495
496    #[test]
497    fn test_insert_noisy_4x4_grid_mesh() {
498        // A 2D grid mesh of 4x4 faces with slightly noisified (i64, i64)
499        // coordinates.
500        let mesh: Vec<Vec<(i64, i64)>> = vec![
501            // Row 1.
502            vec![(2, 3), (48, -2), (53, 54), (-4, 48)],
503            vec![(48, -2), (102, 4), (98, 51), (53, 54)],
504            vec![(102, 4), (155, -3), (147, 55), (98, 51)],
505            vec![(155, -3), (201, 2), (197, 49), (147, 55)],
506            // Row 2.
507            vec![(-4, 48), (53, 54), (47, 103), (3, 98)],
508            vec![(53, 54), (98, 51), (104, 97), (47, 103)],
509            vec![(98, 51), (147, 55), (149, 102), (104, 97)],
510            vec![(147, 55), (197, 49), (203, 99), (149, 102)],
511            // Row 3.
512            vec![(3, 98), (47, 103), (51, 155), (-2, 147)],
513            vec![(47, 103), (104, 97), (97, 149), (51, 155)],
514            vec![(104, 97), (149, 102), (155, 148), (97, 149)],
515            vec![(149, 102), (203, 99), (198, 152), (155, 148)],
516            // Row 4.
517            vec![(-2, 147), (51, 155), (49, 204), (5, 197)],
518            vec![(51, 155), (97, 149), (102, 198), (49, 204)],
519            vec![(97, 149), (155, 148), (146, 201), (102, 198)],
520            vec![(155, 148), (198, 152), (204, 199), (146, 201)],
521        ];
522
523        let mut dcel: Dcel<(i64, i64)> = Dcel::new();
524        dcel.insert_mesh(mesh);
525
526        for (i, _face) in dcel.faces().iter().enumerate() {
527            if FaceId::new(i) == dcel.unbounded_face() {
528                assert_eq!(
529                    dcel.face_vertices(FaceId::new(i))
530                        .collect::<Vec<VertexId>>()
531                        .len(),
532                    0
533                );
534                assert_eq!(
535                    dcel.face_half_edges(FaceId::new(i))
536                        .collect::<Vec<HalfEdgeId>>()
537                        .len(),
538                    0
539                );
540                assert_eq!(
541                    dcel.face_edges(FaceId::new(i))
542                        .collect::<Vec<EdgeId>>()
543                        .len(),
544                    0
545                );
546                continue;
547            }
548
549            assert_eq!(
550                dcel.face_vertices(FaceId::new(i))
551                    .collect::<Vec<VertexId>>()
552                    .len(),
553                4
554            );
555            assert_eq!(
556                dcel.face_half_edges(FaceId::new(i))
557                    .collect::<Vec<HalfEdgeId>>()
558                    .len(),
559                4
560            );
561            assert_eq!(
562                dcel.face_edges(FaceId::new(i))
563                    .collect::<Vec<EdgeId>>()
564                    .len(),
565                4
566            );
567        }
568
569        assert_eq!(dcel.vertices().len(), 25);
570        assert_eq!(dcel.half_edges().len(), 80);
571        assert_eq!(dcel.faces().len(), 17);
572    }
573}
dcel/insert.rs

dcel/
insert.rs
