1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

//! Implements the second phase of the algorithm.
//! Here, a planar embedding is created for the K-4 graph left over from the first phase.

use crate::data_structure::link_graph::{LinkDart, LinkGraph, LinkVertex};

pub struct Phase2<'a> {
    dcel: &'a mut LinkGraph,
}

impl Phase2<'_> {
    pub fn new(dcel: &mut LinkGraph) -> Phase2 {
        Phase2 { dcel }
    }

    pub fn execute(&mut self) {
        let v0 = self.dcel.new_vertex();
        let v1 = self.dcel.new_vertex();
        let v2 = self.dcel.new_vertex();
        let v3 = self.dcel.new_vertex();

        // Face 0
        let (d0, d1, d2) = self.create_face(v0.clone(), v1.clone(), v3.clone(), None, None, None);

        // Face 1
        let (_, d3, d4) =
            self.create_face(v1.clone(), v0.clone(), v2.clone(), Some(d0), None, None);

        // Face 2
        let (d5, _, _) = self.create_face(v3.clone(), v2.clone(), v0, None, Some(d3), Some(d2));

        // Face 3
        self.create_face(v2, v3, v1, Some(d5), Some(d1), Some(d4));
    }

    pub fn triangle_embedding(&mut self) {
        let v0 = self.dcel.new_vertex();
        let v1 = self.dcel.new_vertex();
        let v2 = self.dcel.new_vertex();

        // Face 0
        let (d0, d1, d2) = self.create_face(v0.clone(), v1.clone(), v2.clone(), None, None, None);

        // Face 1
        self.create_face(v0, v2, v1, Some(d2), Some(d1), Some(d0));
    }

    fn create_face(
        &mut self,
        v0: LinkVertex,
        v1: LinkVertex,
        v2: LinkVertex,
        t1: Option<LinkDart>,
        t2: Option<LinkDart>,
        t3: Option<LinkDart>,
    ) -> (LinkDart, LinkDart, LinkDart) {
        let d0 = self
            .dcel
            .new_dart(v0.clone(), v1.clone(), None, None, t1, None);
        let f0 = self.dcel.new_face(d0.clone());
        let d1 = self
            .dcel
            .new_dart(v1, v2.clone(), Some(d0.clone()), None, t2, Some(f0.clone()));
        let d2 = self
            .dcel
            .new_dart(v2, v0, Some(d1.clone()), Some(d0.clone()), t3, Some(f0));

        (d0, d1, d2)
    }
}

#[cfg(test)]
mod tests {
    use crate::data_structure::graph_dcel::GraphDCEL;
    use crate::data_structure::link_graph::LinkGraph;
    use crate::embedding::maximal_planar::phase2::Phase2;

    #[test]
    fn phase_2() {
        let mut dcel = LinkGraph::new();

        Phase2::new(&mut dcel).execute();

        dcel.validate();
        assert_eq!(dcel.get_vertexes().count(), 4);
        assert_eq!(dcel.edge_count(), 6);
        assert_eq!(dcel.get_faces().count(), 4);
    }

    #[test]
    fn triangle_embedding() {
        let mut dcel = LinkGraph::new();

        Phase2::new(&mut dcel).triangle_embedding();

        dcel.validate();
        assert_eq!(dcel.get_vertexes().count(), 3);
        assert_eq!(dcel.edge_count(), 3);
        assert_eq!(dcel.get_faces().count(), 2);
    }
}