dcel/
triangulate.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::{Dcel, EdgeId, Face, FaceId, HalfEdge, Vertex, VertexId};
8
9impl<
10    VW: Clone,
11    HEW: Clone + Default,
12    FW: Clone + Default,
13    VC: Get<usize, Item = Vertex<VW>> + Insert<usize> + Push<usize>,
14    HEC: Get<usize, Item = HalfEdge<HEW>> + Insert<usize> + Push<usize>,
15    FC: Get<usize, Item = Face<FW>> + Insert<usize> + Push<usize>,
16> Dcel<VW, HEW, FW, VC, HEC, FC>
17{
18    /// Partition a face into triangles by inserting a vertex inside and then
19    /// adding edges between it and the original face's vertexes.
20    ///
21    /// The original face is reused for the first triangle. New faces are
22    /// created for all the other triangles.
23    ///
24    /// Returns the new vertex id together with the face ids of all the new
25    /// triangles.
26    pub fn triangulate_around_vertex(&mut self, perimeter_face: FaceId, inner_vertex_weight: VW) {
27        let perimeter_vertex_count = self.face_vertexes(perimeter_face).count();
28
29        self.triangulate_around_vertex_with_all_weights(
30            perimeter_face,
31            inner_vertex_weight,
32            std::iter::repeat_n(Default::default(), perimeter_vertex_count),
33            std::iter::repeat_n(Default::default(), perimeter_vertex_count),
34        )
35    }
36
37    pub fn fan_triangulate(&mut self, perimeter_face: FaceId, apex: VertexId) {
38        let fan_vertexes_count = self.face_vertexes(perimeter_face).count() - 1;
39
40        self.fan_triangulate_with_all_weights(
41            perimeter_face,
42            apex,
43            std::iter::repeat_n(Default::default(), fan_vertexes_count),
44            std::iter::repeat_n(Default::default(), fan_vertexes_count),
45        )
46    }
47}
48
49impl<
50    VW: Clone,
51    HEW: Clone,
52    FW: Clone,
53    VC: Get<usize, Item = Vertex<VW>> + Insert<usize> + Push<usize>,
54    HEC: Get<usize, Item = HalfEdge<HEW>> + Insert<usize> + Push<usize>,
55    FC: Get<usize, Item = Face<FW>> + Insert<usize> + Push<usize>,
56> Dcel<VW, HEW, FW, VC, HEC, FC>
57{
58    pub fn triangulate_around_vertex_with_all_weights(
59        &mut self,
60        perimeter_face: FaceId,
61        inner_vertex_weight: VW,
62        inner_edge_weights: impl IntoIterator<Item = (HEW, HEW)>,
63        triangle_face_weights: impl IntoIterator<Item = FW>,
64    ) {
65        let inner_vertex = self.add_unwired_vertex(inner_vertex_weight);
66        self.fan_triangulate_with_all_weights(
67            perimeter_face,
68            inner_vertex,
69            inner_edge_weights,
70            triangle_face_weights,
71        );
72    }
73
74    pub fn fan_triangulate_with_all_weights(
75        &mut self,
76        perimeter_face: FaceId,
77        apex: VertexId,
78        inner_edge_weights: impl IntoIterator<Item = (HEW, HEW)>,
79        triangle_face_weights: impl IntoIterator<Item = FW>,
80    ) {
81        let triangle_faces =
82            self.add_unwired_triangulation_faces(perimeter_face, triangle_face_weights);
83        let inner_edges = self.add_unwired_triangulation_edges(
84            perimeter_face,
85            apex,
86            &triangle_faces,
87            inner_edge_weights,
88        );
89        self.wire_triangulation_faces_edges_vertexes(perimeter_face, &inner_edges);
90    }
91
92    fn add_unwired_triangulation_faces(
93        &mut self,
94        first_face: FaceId,
95        triangle_face_weights: impl IntoIterator<Item = FW>,
96    ) -> Vec<FaceId> {
97        let mut triangle_faces = vec![];
98
99        let mut face_weights_iter = triangle_face_weights.into_iter();
100        self.faces.insert(
101            first_face.id(),
102            Face {
103                incident_half_edge: self.faces.get(&first_face.id()).unwrap().incident_half_edge,
104                weight: face_weights_iter.next().unwrap(),
105            },
106        );
107        triangle_faces.push(first_face);
108
109        for face_weight in face_weights_iter {
110            triangle_faces.push(self.add_unwired_face(face_weight));
111        }
112
113        triangle_faces
114    }
115
116    fn add_unwired_triangulation_edges(
117        &mut self,
118        perimeter_face: FaceId,
119        inner_vertex: VertexId,
120        triangle_faces: &[FaceId],
121        inner_edge_weights: impl IntoIterator<Item = (HEW, HEW)>,
122    ) -> Vec<EdgeId> {
123        let mut inner_edge_weights = inner_edge_weights.into_iter();
124        let mut face_vertexes_walker = self.face_vertexes(perimeter_face).walker();
125        let mut edges = vec![];
126
127        let mut i: usize = 0;
128
129        while let Some(perimeter_vertex) = face_vertexes_walker.next(self) {
130            let (weight, twin_weight) = inner_edge_weights.next().unwrap();
131
132            let prev_face = if i == 0 {
133                // Wrap to avoid negative index.
134                triangle_faces[triangle_faces.len() - 1]
135            } else {
136                triangle_faces[i - 1]
137            };
138
139            edges.push(self.add_unwired_edge(
140                perimeter_vertex,
141                inner_vertex,
142                prev_face,
143                triangle_faces[i],
144                weight,
145                twin_weight,
146            ));
147
148            i += 1;
149        }
150
151        edges
152    }
153
154    fn wire_triangulation_faces_edges_vertexes(
155        &mut self,
156        perimeter_face: FaceId,
157        inner_edges: &[EdgeId],
158    ) {
159        let inner_edges_circular_tuple_windows = inner_edges
160            .iter()
161            .zip(inner_edges.iter().skip(1).chain(inner_edges.iter().take(1)));
162        let mut perimeter_half_edges_walker = self.face_half_edges(perimeter_face).walker();
163
164        for (inner_edge, next_inner_edge) in inner_edges_circular_tuple_windows {
165            let perimeter_half_edge = perimeter_half_edges_walker.next(self).unwrap();
166            let triangle_face = self.face_in_front(inner_edge.backward());
167
168            self.wire_inner_half_edge_chain(
169                triangle_face,
170                &[
171                    self.full_edge(perimeter_half_edge),
172                    self.full_edge(next_inner_edge.forward()),
173                    self.full_edge(inner_edge.backward()),
174                ],
175            );
176        }
177    }
178}
dcel/triangulate.rs

dcel/
triangulate.rs
