Function snap_graph_grid

generative/snap.rs:330–368

(mut graph: GeometryGraph<D>, tolerance: f64)

}

fn snap_graph_grid<D>(mut graph: GeometryGraph<D>, tolerance: f64) -> GeometryGraph<D>
where
    D: EdgeType,
{
    let mut index = GraphKdTree::new(2);
    let mut nodes_to_remove = Vec::new();
    for node_idx in graph.node_indices() {
        let snapped_coord = snap_coord_grid(graph[node_idx].0, tolerance);

        // Check if there's already a node that has been snapped to that point, if so, snap the two
        // together in a way that properly adjusts their adjacencies.
        let mut already_snapped = None;
        let snapped_coords = [snapped_coord.x, snapped_coord.y];
        let nearest = index
            .within(&snapped_coords, tolerance / 2.0, &squared_euclidean)
            .unwrap();
        for (_distance, node_idx) in nearest {
            if graph[*node_idx].0 == snapped_coord {
                already_snapped = Some(node_idx);
            }
        }

        if let Some(already_snapped) = already_snapped {
            nodes_to_remove.push(node_idx);
            snap_graph_nodes(&mut graph, node_idx, *already_snapped);
        } else {
            index.add(snapped_coords, node_idx).unwrap();
            graph[node_idx].0 = snapped_coord;
        }
    }

    // Removing nodes invalidates any existing indices >= the removed index, so remove nodes from
    // greater to smaller, so that smaller indices aren't invalidated by the removal
    nodes_to_remove.sort_unstable();
    for node_idx in nodes_to_remove.into_iter().rev() {
        graph.remove_node(node_idx);
    }
    graph
}

#[cfg(test)]
mod tests {