Function quad_grid

tools/grid.rs:253–309

(width: usize, height: usize, size_x: f64, size_y: f64)

}

fn quad_grid(width: usize, height: usize, size_x: f64, size_y: f64) -> GeometryGraph<Undirected> {
    let nodes = (width + 1) * (height + 1);
    let edges = 2 * width * height - width - height;
    let mut graph = GeometryGraph::<Undirected>::with_capacity(nodes, edges);

    // Add the nodes
    for j in 0..=height {
        for i in 0..=width {
            let x = quad_i2x(i, size_x, 0.0);
            let y = quad_j2y(j, size_y, 0.0);
            let point = Point::new(x, y);
            let index = graph.add_node(point);
            let node_index = (width + 1) * j + i;
            tracing::trace!("id={} node={point:?}", index.index());
            debug_assert_eq!(index.index(), node_index);
        }
    }

    // Add the edges
    for j in 0..=height {
        for i in 0..=width {
            // As an implementation detail, the GeometryGraph gives nodes integer IDs in the order
            // they were added. This is the index of the current node in the graph.
            let current_index = (width + 1) * j + i;
            tracing::trace!("adding neighbors for id={current_index}");

            // Add the four neighbors, starting at the left and working clockwise
            //
            // 0--1--2
            // |  |  |
            // 3--4--5
            // |  |  |
            // 6--7--8
            if i > 0 {
                let left = current_index - 1;
                tracing::trace!("added left id={left}");
                graph.update_edge(current_index.into(), left.into(), ());
            }
            if j < height {
                let upper = current_index + width + 1;
                tracing::trace!("added upper id={upper}");
                graph.update_edge(current_index.into(), upper.into(), ());
            }
            if i < width {
                let right = current_index + 1;
                tracing::trace!("added right id={right}");
                graph.update_edge(current_index.into(), right.into(), ());
            }
            if j > 0 {
                let lower = current_index - width - 1;
                tracing::trace!("added lower id={lower}");
                graph.update_edge(current_index.into(), lower.into(), ());
            }
        }
    }
    graph
}