| 76 | } |
| 77 | |
| 78 | pub fn digraph(&self) -> GeometryGraph<Directed> { |
| 79 | let nodes = self.points.len(); |
| 80 | let edges = self.triangulation.halfedges.len(); |
| 81 | let mut graph = GeometryGraph::with_capacity(nodes, edges); |
| 82 | |
| 83 | // Add all the nodes |
| 84 | for (_i, point) in self.points.iter().enumerate() { |
| 85 | let point = Point::new(point.x, point.y); |
| 86 | // NOTE: It's important that the _node_index is the same as the index into the |
| 87 | // self.points array! |
| 88 | let _node_index = graph.add_node(point); |
| 89 | debug_assert_eq!(_node_index.index(), _i); |
| 90 | } |
| 91 | |
| 92 | // Add the hull edges |
| 93 | for window in self.triangulation.hull.windows(2) { |
| 94 | let curr = window[0]; |
| 95 | let next = window[1]; |
| 96 | |
| 97 | graph.add_edge(curr.into(), next.into(), ()); |
| 98 | } |
| 99 | // NOTE: The hull is open and needs to be closed in order to capture the last edge! |
| 100 | if let (Some(first), Some(last)) = ( |
| 101 | self.triangulation.hull.first(), |
| 102 | self.triangulation.hull.last(), |
| 103 | ) { |
| 104 | graph.add_edge( |
| 105 | petgraph::graph::NodeIndex::new(*last), |
| 106 | petgraph::graph::NodeIndex::new(*first), |
| 107 | (), |
| 108 | ); |
| 109 | } |
| 110 | |
| 111 | // Add the interior half-edges |
| 112 | for (dst_i, src_i) in self.triangulation.halfedges.iter().enumerate() { |
| 113 | // This is a hull edge. The half-edges array doesn't contain enough information to |
| 114 | // build the graph edge, which is why we loop over the hull above. |
| 115 | if *src_i == delaunator::EMPTY { |
| 116 | continue; |
| 117 | } |
| 118 | |
| 119 | // dst_i and src_i are indices into the triangles array, which itself contains indices |
| 120 | // into the nodes array. |
| 121 | let src = self.triangulation.triangles[*src_i]; |
| 122 | let dst = self.triangulation.triangles[dst_i]; |
| 123 | |
| 124 | graph.add_edge(src.into(), dst.into(), ()); |
| 125 | } |
| 126 | |
| 127 | graph |
| 128 | } |
| 129 | |
| 130 | pub fn graph(&self) -> GeometryGraph<Undirected> { |
| 131 | let digraph = self.digraph(); |