dcel 0.8.12

Implementation of doubly-connected edge list.
Documentation 
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
101
102
103
104
105
106
107
108
109
110
111
112
113

// SPDX-FileCopyrightText: 2026 dcel contributors
//
// SPDX-License-Identifier: MIT OR Apache-2.0

use maplike::{Clear, Get, Insert, Push, Remove, StableRemove};

use crate::{Dcel, EdgeId, Face, FaceId, HalfEdge, Vertex, VertexId};

impl<
    VW: Clone,
    HEW: Clone,
    FW: Clone,
    VC: Get<usize, Value = Vertex<VW>> + Insert<usize> + StableRemove<usize>,
    HEC: Get<usize, Value = HalfEdge<HEW>> + Insert<usize> + StableRemove<usize>,
    FC: Get<usize, Value = Face<FW>> + Insert<usize> + StableRemove<usize>,
> Dcel<VW, HEW, FW, VC, HEC, FC>
{
    pub fn remove_face(&mut self, face: FaceId) -> (Vec<EdgeId>, Vec<FaceId>) {
        let mut edges: Vec<EdgeId> = self.face_edges(face).collect();
        edges.extend(self.face_spokes(face));
        let interspokes: Vec<FaceId> = self.face_interspokes(face).collect();

        self.absorb_faces_over_edges_and_vertices(
            face,
            interspokes.clone(),
            edges.clone(),
            self.face_vertices(face).collect::<Vec<VertexId>>(),
        );

        (edges, interspokes)
    }

    pub fn remove_edge(&mut self, edge: EdgeId) -> FaceId {
        let absorbing_face = self.incident_face(edge.lesser());
        let face_to_absorb = self.opposite_face(edge.lesser());

        self.absorb_faces_over_edges_and_vertices(absorbing_face, [face_to_absorb], [edge], []);

        absorbing_face
    }

    pub fn remove_edge_chain(&mut self, edges: impl IntoIterator<Item = EdgeId>) -> FaceId {
        let edges: Vec<EdgeId> = edges.into_iter().collect();

        // XXX: Harden against empty iterators?
        let absorbing_face = self.incident_face(edges[0].lesser());
        let face_to_absorb = self.opposite_face(edges[0].lesser());

        self.absorb_faces_over_edges_and_vertices(absorbing_face, [face_to_absorb], edges, []);

        absorbing_face
    }
}

impl<VW, HEW, FW, VC: Remove<usize, Value = Vertex<VW>>, HEC, FC> Dcel<VW, HEW, FW, VC, HEC, FC> {
    pub(crate) fn remove_orphaned_vertices(
        &mut self,
        vertices: impl IntoIterator<Item = VertexId>,
    ) {
        for vertex in vertices.into_iter() {
            self.remove_orphaned_vertex(vertex);
        }
    }

    pub(crate) fn remove_orphaned_vertex(&mut self, vertex: VertexId) {
        self.vertices.remove(&vertex.id());
    }
}

impl<VW, HEW, FW, VC, HEC: Remove<usize, Value = HalfEdge<HEW>>, FC>
    Dcel<VW, HEW, FW, VC, HEC, FC>
{
    pub(crate) fn remove_orphaned_edges(&mut self, edges: impl IntoIterator<Item = EdgeId>) {
        for edge in edges.into_iter() {
            self.remove_orphaned_edge(edge);
        }
    }

    pub(crate) fn remove_orphaned_edge(&mut self, edge: EdgeId) {
        self.half_edges.remove(&edge.lesser().id());
        self.half_edges.remove(&edge.greater().id());
    }
}

impl<VW, HEW, FW, VC, HEC, FC: Remove<usize>> Dcel<VW, HEW, FW, VC, HEC, FC> {
    pub(crate) fn remove_orphaned_faces(&mut self, faces: impl IntoIterator<Item = FaceId>) {
        for face in faces.into_iter() {
            self.remove_orphaned_face(face);
        }
    }

    pub(crate) fn remove_orphaned_face(&mut self, face: FaceId) {
        self.faces.remove(&face.id());
    }
}

impl<VW, HEW, FW: Default, VC: Clear, HEC: Clear, FC: Clear + Push<usize, Value = Face<FW>>>
    Dcel<VW, HEW, FW, VC, HEC, FC>
{
    pub fn clear(&mut self) {
        self.vertices.clear();
        self.half_edges.clear();
        self.faces.clear();

        // Push the outermost face back. Having it is an invariant property.
        self.faces.push(Face {
            representative: None,
            weight: FW::default(),
        });
    }
}

// TODO: Tests.