dcel/
insert.rs

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

dcel/
insert.rs
