Function sutherland_hodgman

nodedb-spatial/src/predicates/intersection.rs:116–162

Sutherland-Hodgman polygon clipping. Clips `subject` polygon against `clip` polygon. Both are coordinate rings (closed or unclosed). Returns the clipped polygon vertices (unclosed). The clip polygon's edges define half-planes. For each edge, vertices of the subject that are "inside" (left of the edge) are kept. Vertices that cross from inside to outside (or vice versa) generate intersection poin

(subject: &[[f64; 2]], clip: &[[f64; 2]])

/// that cross from inside to outside (or vice versa) generate intersection
/// points on the clip edge.
fn sutherland_hodgman(subject: &[[f64; 2]], clip: &[[f64; 2]]) -> Vec<[f64; 2]> {
    if subject.is_empty() || clip.is_empty() {
        return Vec::new();
    }

    let mut output = strip_closing(subject);
    let clip_edges = strip_closing(clip);

    let n = clip_edges.len();
    for i in 0..n {
        if output.is_empty() {
            return Vec::new();
        }

        let edge_start = clip_edges[i];
        let edge_end = clip_edges[(i + 1) % n];

        let input = output;
        output = Vec::with_capacity(input.len());

        let m = input.len();
        for j in 0..m {
            let current = input[j];
            let previous = input[(j + m - 1) % m];

            let curr_inside = is_inside(current, edge_start, edge_end);
            let prev_inside = is_inside(previous, edge_start, edge_end);

            if curr_inside {
                if !prev_inside {
                    // Entering: add intersection point.
                    if let Some(pt) = line_intersection(previous, current, edge_start, edge_end) {
                        output.push(pt);
                    }
                }
                output.push(current);
            } else if prev_inside {
                // Leaving: add intersection point.
                if let Some(pt) = line_intersection(previous, current, edge_start, edge_end) {
                    output.push(pt);
                }
            }
        }
    }

    output
}

/// Check if a point is on the "inside" (left side) of a directed edge.
fn is_inside(point: [f64; 2], edge_start: [f64; 2], edge_end: [f64; 2]) -> bool {