| 153 | } |
| 154 | |
| 155 | fn tri_grid(width: usize, height: usize, size_x: f64, size_y: f64) -> GeometryGraph<Undirected> { |
| 156 | let nodes = (width + 1) * (height + 1); |
| 157 | let edges = 2 * nodes; |
| 158 | let mut graph = GeometryGraph::<Undirected>::with_capacity(nodes, edges); |
| 159 | |
| 160 | let triangle_height = f64::sqrt(size_y.powi(2) - (size_x.powi(2) / 4.0)); |
| 161 | |
| 162 | // Add the nodes |
| 163 | for j in 0..=height { |
| 164 | for i in 0..=width { |
| 165 | let node_index = (width + 1) * j + i; |
| 166 | let odd_row = j % 2 != 0; |
| 167 | let x = tri_i2x(i, size_x, odd_row); |
| 168 | let y = tri_j2y(j, triangle_height); |
| 169 | let point = Point::new(x, y); |
| 170 | let index = graph.add_node(point); |
| 171 | tracing::trace!("id={} node={point:?}", index.index()); |
| 172 | debug_assert_eq!(index.index(), node_index); |
| 173 | } |
| 174 | } |
| 175 | |
| 176 | // Add the edges |
| 177 | for j in 0..=height { |
| 178 | for i in 0..=width { |
| 179 | let current_index = (width + 1) * j + i; |
| 180 | let odd_row = j % 2 != 0; |
| 181 | tracing::trace!("adding neighbors for id={current_index}"); |
| 182 | |
| 183 | // Start to the left of the current node, and work clockwise around its neighbors. |
| 184 | // |
| 185 | // Around the left and right border, only the odd rows have upper and lower left |
| 186 | // neighbors, and only the even rows have upper and lower right neighbors. |
| 187 | // |
| 188 | // even j=0 0---1---2 |
| 189 | // \ / \ / \ |
| 190 | // odd j=1 3---4---5 |
| 191 | // / \ / \ / |
| 192 | // even j=2 6---7---8 |
| 193 | if i > 0 { |
| 194 | let left = current_index - 1; |
| 195 | tracing::trace!("added left id={left}"); |
| 196 | graph.update_edge(current_index.into(), left.into(), ()); |
| 197 | } |
| 198 | if j > 0 && (i > 0 || odd_row) { |
| 199 | let upper_left = if odd_row { |
| 200 | current_index - (width + 1) |
| 201 | } else { |
| 202 | current_index - (width + 2) |
| 203 | }; |
| 204 | tracing::trace!("added upper left id={upper_left}"); |
| 205 | graph.update_edge(current_index.into(), upper_left.into(), ()); |
| 206 | } |
| 207 | if j > 0 && (!odd_row || i < width) { |
| 208 | let upper_right = if odd_row { |
| 209 | current_index - width |
| 210 | } else { |
| 211 | current_index - (width + 1) |
| 212 | }; |