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, Value = Vertex<VW>> + Insert<usize> + Push<usize>,
14    HEC: Get<usize, Value = HalfEdge<HEW>> + Insert<usize> + Push<usize>,
15    FC: Get<usize, Value = 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 adding
19    /// edges between it and the original face's vertices.
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 ids of all the newly created
25    /// edges and faces (the reused already existing edges and face are not
26    /// included).
27    pub fn triangulate_face_around_point(
28        &mut self,
29        perimeter_face: FaceId,
30        inner_vertex_weight: VW,
31    ) -> (VertexId, Vec<EdgeId>, Vec<FaceId>) {
32        let perimeter_vertex_count = self.face_vertices(perimeter_face).count();
33
34        self.triangulate_face_around_point_with_all_weights(
35            perimeter_face,
36            inner_vertex_weight,
37            std::iter::repeat_n(Default::default(), perimeter_vertex_count),
38            std::iter::repeat_n(Default::default(), perimeter_vertex_count),
39        )
40    }
41
42    pub fn fan_triangulate(
43        &mut self,
44        perimeter_face: FaceId,
45        apex: VertexId,
46    ) -> (Vec<EdgeId>, Vec<FaceId>) {
47        let perimeter_vertex_count = self.face_vertices(perimeter_face).count();
48
49        self.fan_triangulate_with_all_weights(
50            perimeter_face,
51            apex,
52            std::iter::repeat_n(Default::default(), perimeter_vertex_count),
53            std::iter::repeat_n(Default::default(), perimeter_vertex_count),
54        )
55    }
56}
57
58impl<
59    VW: Clone,
60    HEW: Clone,
61    FW: Clone,
62    VC: Get<usize, Value = Vertex<VW>> + Insert<usize> + Push<usize>,
63    HEC: Get<usize, Value = HalfEdge<HEW>> + Insert<usize> + Push<usize>,
64    FC: Get<usize, Value = Face<FW>> + Insert<usize> + Push<usize>,
65> Dcel<VW, HEW, FW, VC, HEC, FC>
66{
67    pub fn triangulate_face_around_point_with_all_weights(
68        &mut self,
69        perimeter_face: FaceId,
70        inner_vertex_weight: VW,
71        inner_edge_weights: impl IntoIterator<Item = (HEW, HEW)>,
72        triangle_face_weights: impl IntoIterator<Item = FW>,
73    ) -> (VertexId, Vec<EdgeId>, Vec<FaceId>) {
74        let inner_vertex = self.add_unwired_vertex(inner_vertex_weight);
75        let (new_edges, new_faces) = self.fan_triangulate_with_all_weights(
76            perimeter_face,
77            inner_vertex,
78            inner_edge_weights,
79            triangle_face_weights,
80        );
81
82        (inner_vertex, new_edges, new_faces)
83    }
84
85    pub fn fan_triangulate_with_all_weights(
86        &mut self,
87        perimeter_face: FaceId,
88        apex: VertexId,
89        inner_edge_weights: impl IntoIterator<Item = (HEW, HEW)>,
90        triangle_face_weights: impl IntoIterator<Item = FW>,
91    ) -> (Vec<EdgeId>, Vec<FaceId>) {
92        let new_faces = self.add_unwired_triangulation_faces(perimeter_face, triangle_face_weights);
93
94        let mut triangle_faces = vec![perimeter_face];
95        triangle_faces.extend(new_faces.clone());
96
97        let new_edges = self.add_unwired_triangulation_edges(
98            perimeter_face,
99            apex,
100            &triangle_faces,
101            inner_edge_weights,
102        );
103        self.wire_triangulation_faces_edges_vertices(perimeter_face, &new_edges);
104
105        (new_edges, new_faces)
106    }
107
108    fn add_unwired_triangulation_faces(
109        &mut self,
110        first_face: FaceId,
111        triangle_face_weights: impl IntoIterator<Item = FW>,
112    ) -> Vec<FaceId> {
113        let mut new_faces = vec![];
114
115        let mut face_weights_iter = triangle_face_weights.into_iter();
116        self.faces.insert(
117            first_face.id(),
118            Face {
119                representative: self.faces.get(&first_face.id()).unwrap().representative,
120                weight: face_weights_iter.next().unwrap(),
121            },
122        );
123
124        for face_weight in face_weights_iter {
125            new_faces.push(self.add_unwired_face(face_weight));
126        }
127
128        new_faces
129    }
130
131    fn add_unwired_triangulation_edges(
132        &mut self,
133        perimeter_face: FaceId,
134        inner_vertex: VertexId,
135        triangle_faces: &[FaceId],
136        inner_edge_weights: impl IntoIterator<Item = (HEW, HEW)>,
137    ) -> Vec<EdgeId> {
138        let mut inner_edge_weights = inner_edge_weights.into_iter();
139        let mut face_vertices_walker = self.face_vertices(perimeter_face).walker();
140        let mut edges = vec![];
141
142        let mut i: usize = 0;
143
144        while let Some(perimeter_vertex) = face_vertices_walker.next(self) {
145            let (weight, twin_weight) = inner_edge_weights.next().unwrap();
146
147            let prev_face = if i == 0 {
148                // Wrap to avoid negative index.
149                triangle_faces[triangle_faces.len() - 1]
150            } else {
151                triangle_faces[i - 1]
152            };
153
154            let (forward, _backward) = self.add_unwired_edge(
155                perimeter_vertex,
156                inner_vertex,
157                prev_face,
158                triangle_faces[i],
159                weight,
160                twin_weight,
161            );
162            edges.push(self.full_edge(forward));
163
164            i += 1;
165        }
166
167        edges
168    }
169
170    fn wire_triangulation_faces_edges_vertices(
171        &mut self,
172        perimeter_face: FaceId,
173        inner_edges: &[EdgeId],
174    ) {
175        let inner_edges_circular_tuple_windows = inner_edges
176            .iter()
177            .zip(inner_edges.iter().skip(1).chain(inner_edges.iter().take(1)));
178        let mut perimeter_half_edges_walker = self.face_half_edges(perimeter_face).walker();
179
180        for (inner_edge, next_inner_edge) in inner_edges_circular_tuple_windows {
181            let perimeter_half_edge = perimeter_half_edges_walker.next(self).unwrap();
182            let triangle_face = self.incident_face(inner_edge.greater());
183
184            self.wire_inner_half_edge_chain(
185                triangle_face,
186                &[
187                    perimeter_half_edge,
188                    next_inner_edge.lesser(),
189                    inner_edge.greater(),
190                ],
191            );
192        }
193    }
194}
195
196// TODO: Tests.
dcel/triangulate.rs

dcel/
triangulate.rs
