graph_algo_ptas/algorithm/
triangulation.rs

1//! Contains the triangulate function
2use crate::data_structure::{
3    graph_dcel::GraphDCEL,
4    link_graph::{LinkDart, LinkFace, LinkGraphIter, LinkVertex},
5};
6use std::collections::HashSet;
7
8/// Returns the edges of a graph that need to be added to be fully triangulated.
9/// The graph needs to be connected.
10pub fn triangulate(
11    graph: &impl GraphDCEL<
12        LinkVertex,
13        LinkDart,
14        LinkFace,
15        LinkGraphIter<LinkVertex>,
16        LinkGraphIter<LinkDart>,
17        LinkGraphIter<LinkFace>,
18    >,
19) -> HashSet<(LinkVertex, LinkVertex)> {
20    let mut edges: HashSet<(LinkVertex, LinkVertex)> = HashSet::new();
21
22    for face in graph.get_faces() {
23        edges.extend(triangulate_face(graph, &face));
24    }
25
26    edges
27}
28
29/// Returns the edges of a face that need to be added to be fully triangulated.
30fn triangulate_face(
31    graph: &impl GraphDCEL<
32        LinkVertex,
33        LinkDart,
34        LinkFace,
35        LinkGraphIter<LinkVertex>,
36        LinkGraphIter<LinkDart>,
37        LinkGraphIter<LinkFace>,
38    >,
39    face: &LinkFace,
40) -> HashSet<(LinkVertex, LinkVertex)> {
41    let mut edges: HashSet<(LinkVertex, LinkVertex)> = HashSet::new();
42
43    let mut current = graph.dart_face(face);
44
45    if graph.next(&graph.next(&current)) == current {
46        // single edge (|v| < 3)
47        return edges;
48    } else if graph.dart_target(&graph.next(&current)) == graph.dart_target(&graph.twin(&current)) {
49        // outgoing edge
50        current = graph.next(&current);
51    }
52
53    let start_vertex = &graph.dart_target(&graph.twin(&current));
54
55    loop {
56        let next = graph.next(&current);
57
58        if graph.dart_target(&graph.next(&next)) == *start_vertex {
59            break;
60        }
61
62        let from = graph.dart_target(&next);
63
64        edges.insert((from, start_vertex.clone()));
65        current = next;
66    }
67
68    edges
69}
70
71#[cfg(test)]
72mod tests {
73    use crate::algorithm::triangulation::triangulate;
74    use crate::data_structure::link_graph::LinkGraph;
75    use crate::utils::single_face::generate_single_face;
76
77    #[test]
78    fn single_edge() {
79        let mut lg = LinkGraph::new();
80        let lv1 = lg.new_vertex();
81        let lv2 = lg.new_vertex();
82
83        let ld1 = lg.new_dart(lv1.clone(), lv2.clone(), None, None, None, None);
84        lg.new_face(ld1.clone());
85        lg.new_dart(
86            lv2,
87            lv1,
88            Some(ld1.clone()),
89            Some(ld1.clone()),
90            Some(ld1),
91            None,
92        );
93
94        let edges = triangulate(&lg);
95        assert!(edges.is_empty())
96    }
97
98    #[test]
99    fn single_face() {
100        for x in 3..100 {
101            let graph = generate_single_face(x);
102
103            let edges = triangulate(&graph);
104
105            assert_eq!(edges.len(), (x - 3) * 2)
106        }
107    }
108
109    #[test]
110    fn outgoing_edge() {
111        let mut lg = LinkGraph::new();
112        let lv1 = lg.new_vertex();
113        let lv2 = lg.new_vertex();
114        let lv3 = lg.new_vertex();
115        let lv4 = lg.new_vertex();
116
117        let ld1 = lg.new_dart(lv1.clone(), lv2.clone(), None, None, None, None);
118        let lf = lg.new_face(ld1.clone());
119        let ld2 = lg.new_dart(
120            lv2.clone(),
121            lv3.clone(),
122            Some(ld1.clone()),
123            None,
124            None,
125            Some(lf.clone()),
126        );
127        let ld3 = lg.new_dart(
128            lv3.clone(),
129            lv1.clone(),
130            Some(ld2.clone()),
131            Some(ld1.clone()),
132            None,
133            Some(lf),
134        );
135
136        let ld4 = lg.new_dart(lv3.clone(), lv4.clone(), None, None, None, None);
137        let lof = lg.new_face(ld4.clone());
138        let lt4 = lg.new_dart(
139            lv4.clone(),
140            lv3.clone(),
141            Some(ld4.clone()),
142            None,
143            Some(ld4.clone()),
144            Some(lof.clone()),
145        );
146        let lt2 = lg.new_dart(
147            lv3.clone(),
148            lv2.clone(),
149            Some(lt4),
150            None,
151            Some(ld2),
152            Some(lof.clone()),
153        );
154        let lt1 = lg.new_dart(
155            lv2.clone(),
156            lv1.clone(),
157            Some(lt2),
158            None,
159            Some(ld1),
160            Some(lof.clone()),
161        );
162        lg.new_dart(
163            lv1.clone(),
164            lv3.clone(),
165            Some(lt1),
166            Some(ld4),
167            Some(ld3),
168            Some(lof),
169        );
170
171        let edges = triangulate(&lg);
172        println!("\n[RESULT]: {:?}", edges);
173        assert!(!edges.is_empty());
174        assert_eq!(edges.len(), 2);
175        assert!(edges.contains(&(lv2.clone(), lv4.clone())));
176        assert!(edges.contains(&(lv1, lv4)) || edges.contains(&(lv2, lv3)));
177    }
178
179    #[test]
180    fn three_edges() {
181        let mut lg = LinkGraph::new();
182        let lv0 = lg.new_vertex();
183        let lv1 = lg.new_vertex();
184        let lv2 = lg.new_vertex();
185        let lv3 = lg.new_vertex();
186
187        let ld0 = lg.new_dart(lv0.clone(), lv1.clone(), None, None, None, None);
188        let lof = lg.new_face(ld0.clone());
189        let ld1 = lg.new_dart(
190            lv1.clone(),
191            lv2.clone(),
192            Some(ld0.clone()),
193            None,
194            None,
195            Some(lof.clone()),
196        );
197        let ld2 = lg.new_dart(
198            lv2.clone(),
199            lv3.clone(),
200            Some(ld1.clone()),
201            None,
202            None,
203            Some(lof.clone()),
204        );
205
206        let lt2 = lg.new_dart(
207            lv3.clone(),
208            lv2.clone(),
209            Some(ld2.clone()),
210            None,
211            Some(ld2),
212            Some(lof.clone()),
213        );
214        let lt1 = lg.new_dart(
215            lv2.clone(),
216            lv1.clone(),
217            Some(lt2),
218            None,
219            Some(ld1),
220            Some(lof.clone()),
221        );
222        lg.new_dart(
223            lv1,
224            lv0.clone(),
225            Some(lt1),
226            Some(ld0.clone()),
227            Some(ld0),
228            Some(lof),
229        );
230
231        let edges = triangulate(&lg);
232        println!("\n[RESULT]: {:?}", edges);
233        assert!(!edges.is_empty());
234        assert_eq!(edges.len(), 2);
235        assert!(edges.contains(&(lv0.clone(), lv2.clone())) || edges.contains(&(lv2, lv0.clone())));
236        assert!(edges.contains(&(lv0.clone(), lv3.clone())) || edges.contains(&(lv3, lv0)));
237    }
238}
graph_algo_ptas/algorithm/triangulation.rs

graph_algo_ptas/algorithm/
triangulation.rs
