polyclip 0.0.6

//! Plane sweep over a fully noded arrangement.
//!
//! The sweep line moves in lexicographic `(x, y)` order (a vertical line sheared
//! infinitesimally so that vertical edges behave like edges leaning right). Because the
//! edges never cross and meet only at shared endpoints, their relative order in the status
//! never changes while they are active; at every vertex the edges ending there form a
//! contiguous run of the status, which is replaced by the edges starting there.

use crate::geom::Point;
use crate::predicates::{cmp_dir_halfplane, orient, sub};
use core::cmp::Ordering;
use core::ops::Range;

/// Orders edges `(lo, hi)` (with `lo < hi`) for [`sweep`]: by `lo`, then bottom to top.
#[inline]
pub(crate) fn cmp_sweep_edges(a: (Point, Point), b: (Point, Point)) -> Ordering {
    a.0.cmp(&b.0)
        .then_with(|| cmp_dir_halfplane(sub(a.1, a.0), sub(b.1, b.0)))
}

/// Sweep status: the active edges bottom to top, split into blocks of bounded size so that
/// insertions and removals stay cheap however wide the status grows. Every entry carries a
/// copy of its edge, so the binary searches read contiguous memory; `last[b]` mirrors the
/// last entry of block `b` in a dense array for the top-level search.
struct Status {
    blocks: Vec<Vec<Entry>>,
    last: Vec<Entry>,
}

/// A status entry: an edge `(lo, hi)` and its index.
#[derive(Clone, Copy)]
struct Entry {
    lo: Point,
    hi: Point,
    id: u32,
}

impl Entry {
    #[inline]
    fn new(edges: &[(Point, Point)], id: u32) -> Self {
        let (lo, hi) = edges[id as usize];
        Entry { lo, hi, id }
    }
}

const BLOCK: usize = 128;

impl Status {
    /// A status holding `ids` (bottom to top).
    fn from_sorted(edges: &[(Point, Point)], ids: &[u32]) -> Self {
        let mut st = Status {
            blocks: Vec::new(),
            last: Vec::new(),
        };
        for c in ids.chunks(BLOCK) {
            let mut b = Vec::with_capacity(2 * BLOCK);
            b.extend(c.iter().map(|&e| Entry::new(edges, e)));
            st.last.push(b[b.len() - 1]);
            st.blocks.push(b);
        }
        st
    }

    /// All edges, bottom to top.
    fn into_vec(self) -> Vec<u32> {
        self.blocks.iter().flatten().map(|e| e.id).collect()
    }

    /// Position `(block, index)` of the first edge for which `below(lo, hi)` is false.
    #[inline]
    fn find(&self, below: impl Fn(Point, Point) -> bool) -> (usize, usize) {
        let b = self.last.partition_point(|e| below(e.lo, e.hi));
        if b == self.blocks.len() {
            return match self.blocks.last() {
                Some(l) => (b - 1, l.len()),
                None => (0, 0),
            };
        }
        (b, self.blocks[b].partition_point(|e| below(e.lo, e.hi)))
    }

    /// The edge just before position `(b, i)`.
    #[inline]
    fn before(&self, b: usize, i: usize) -> Option<u32> {
        if i > 0 {
            Some(self.blocks[b][i - 1].id)
        } else if b > 0 {
            Some(self.last[b - 1].id)
        } else {
            None
        }
    }

    /// The edge `skip` positions after `(b, i)` (if any).
    fn after(&self, mut b: usize, mut i: usize, mut skip: usize) -> Option<u32> {
        while b < self.blocks.len() {
            let len = self.blocks[b].len();
            if i + skip < len {
                return Some(self.blocks[b][i + skip].id);
            }
            skip -= len.saturating_sub(i).min(skip);
            b += 1;
            i = 0;
        }
        None
    }

    /// Copies the `count` edges starting at `(b, i)` into `out`.
    fn collect(&self, mut b: usize, mut i: usize, mut count: usize, out: &mut Vec<u32>) {
        out.clear();
        while count > 0 && b < self.blocks.len() {
            let blk = &self.blocks[b];
            let k = count.min(blk.len() - i.min(blk.len()));
            out.extend(blk[i..i + k].iter().map(|e| e.id));
            count -= k;
            b += 1;
            i = 0;
        }
    }

    /// Removes `remove` edges at `(b, i)` and inserts the edges `insert` there.
    fn splice(
        &mut self,
        edges: &[(Point, Point)],
        b: usize,
        i: usize,
        mut remove: usize,
        insert: impl ExactSizeIterator<Item = u32>,
    ) {
        let mut insert = insert.map(|e| Entry::new(edges, e));
        if self.blocks.is_empty() {
            if insert.len() == 0 {
                return;
            }
            self.blocks.push(Vec::with_capacity(2 * BLOCK));
            self.last.push(Entry {
                lo: Point::default(),
                hi: Point::default(),
                id: 0,
            });
        }
        // Replace in place as far as possible (an edge continuing a chain replaces the
        // ending one without moving the others).
        let mut i = i;
        let blk = &mut self.blocks[b];
        while remove > 0 && i < blk.len() {
            let Some(e) = insert.next() else { break };
            blk[i] = e;
            i += 1;
            remove -= 1;
        }
        // Remove (possibly spilling into following blocks).
        let mut bb = b;
        let mut ii = i;
        while remove > 0 && bb < self.blocks.len() {
            let blk = &mut self.blocks[bb];
            let k = remove.min(blk.len() - ii);
            blk.drain(ii..ii + k);
            remove -= k;
            bb += 1;
            ii = 0;
        }
        let blk = &mut self.blocks[b];
        let i = i.min(blk.len());
        blk.splice(i..i, insert);
        if blk.len() > 2 * BLOCK {
            let tail = blk.split_off(BLOCK);
            let l = tail[tail.len() - 1];
            self.blocks.insert(b + 1, tail);
            self.last.insert(b + 1, l);
        }
        // Refresh `last` for touched blocks and drop empty ones.
        let end = bb.max(b + 2).min(self.blocks.len());
        let mut k = b;
        let mut end = end;
        while k < end {
            match self.blocks[k].last() {
                None => {
                    self.blocks.remove(k);
                    self.last.remove(k);
                    end -= 1;
                }
                Some(&l) => {
                    self.last[k] = l;
                    k += 1;
                }
            }
        }
    }
}

/// Runs the sweep. `edges[i] = (lo, hi)` with `lo < hi`, sorted by [`cmp_sweep_edges`],
/// pairwise non-crossing, with no vertex on another edge's interior.
///
/// `on_insert(e, below)` is called for every edge, in sweep order and bottom to top at each
/// vertex, with the edge immediately below it at the moment it is inserted.
pub(crate) fn sweep(edges: &[(Point, Point)], mut on_insert: impl FnMut(u32, Option<u32>)) {
    sweep_events(edges, |below, _, _, starting| {
        for k in starting.clone() {
            let bl = if k == starting.start {
                below
            } else {
                Some(k - 1)
            };
            on_insert(k, bl);
        }
    });
}

/// Like [`sweep`], with one call per vertex: `on_event(below, above, ending, starting)`
/// receives the edges just below and just above the vertex (excluding the edges incident to
/// it), the edges ending at the vertex (bottom to top) and the range of edges starting
/// there (bottom to top).
pub(crate) fn sweep_events(
    edges: &[(Point, Point)],
    on_event: impl FnMut(Option<u32>, Option<u32>, &[u32], Range<u32>),
) {
    let mut his: Vec<Point> = edges.iter().map(|e| e.1).collect();
    his.sort_unstable();
    sweep_band(edges, &his, 0..edges.len(), &[], on_event);
}

/// Runs the part of the sweep between two vertices `v0 < v1` (with `v0 = -inf`, `v1 = +inf`
/// for the whole sweep), as [`sweep_events`] does, and returns the status reached (the
/// edges `e` with `lo < v1 <= hi`, bottom to top).
///
/// `his` holds the sorted `hi` endpoints in `[v0, v1)`, `starting` the edges with `lo` in
/// `[v0, v1)` and `initial` the status just before `v0` (the edges with `lo < v0 <= hi`,
/// bottom to top, see [`cmp_status`]).
pub(crate) fn sweep_band(
    edges: &[(Point, Point)],
    his: &[Point],
    starting: Range<usize>,
    initial: &[u32],
    mut on_event: impl FnMut(Option<u32>, Option<u32>, &[u32], Range<u32>),
) -> Vec<u32> {
    let mut status = Status::from_sorted(edges, initial);
    let mut ending_buf: Vec<u32> = Vec::new();
    let n = starting.end;
    let mut si = starting.start;
    let mut hi = 0usize;
    loop {
        let v = match (edges[..n].get(si), his.get(hi)) {
            (Some(e), Some(&h)) => e.0.min(h),
            (Some(e), None) => e.0,
            (None, Some(&h)) => h,
            (None, None) => break,
        };
        let mut ending = 0usize;
        while hi < his.len() && his[hi] == v {
            ending += 1;
            hi += 1;
        }
        let s0 = si;
        while si < n && edges[si].0 == v {
            si += 1;
        }
        let (b, i) = status.find(|lo, h| h != v && orient(lo, h, v) > 0);
        let below = status.before(b, i);
        status.collect(b, i, ending, &mut ending_buf);
        status.splice(edges, b, i, ending, (s0..si).map(|e| e as u32));
        let above = status.after(b, i, si - s0);
        on_event(below, above, &ending_buf, s0 as u32..si as u32);
    }
    status.into_vec()
}

/// Bottom-to-top order of two edges `a`, `b` (indices into `edges`, sorted by
/// [`cmp_sweep_edges`]) that are both in the sweep status at some moment.
pub(crate) fn cmp_status(edges: &[(Point, Point)], a: u32, b: u32) -> Ordering {
    let (ea, eb) = (edges[a as usize], edges[b as usize]);
    if ea.0 == eb.0 {
        // Same start: sweep order is bottom to top.
        return a.cmp(&b);
    }
    // The edge starting later lies above or below the other one at its start (never on
    // it: no vertex lies on another edge's interior).
    if ea.0 > eb.0 {
        orient(eb.0, eb.1, ea.0).cmp(&0).then(a.cmp(&b))
    } else {
        0.cmp(&orient(ea.0, ea.1, eb.0)).then(a.cmp(&b))
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn nested_squares() {
        let p = Point::new;
        // Outer square 0..10 and inner square 2..8, edges as (lo, hi).
        let mut e = vec![
            (p(0, 0), p(10, 0)),
            (p(0, 0), p(0, 10)),
            (p(0, 10), p(10, 10)),
            (p(10, 0), p(10, 10)),
            (p(2, 2), p(8, 2)),
            (p(2, 2), p(2, 8)),
            (p(2, 8), p(8, 8)),
            (p(8, 2), p(8, 8)),
        ];
        e.sort_by(|a, b| cmp_sweep_edges(*a, *b));
        let mut below = vec![None; e.len()];
        sweep(&e, |i, b| below[i as usize] = b.map(|b| e[b as usize]));
        let idx = |x: (Point, Point)| e.iter().position(|&y| y == x).unwrap();
        assert_eq!(below[idx((p(0, 0), p(10, 0)))], None);
        assert_eq!(below[idx((p(0, 0), p(0, 10)))], Some((p(0, 0), p(10, 0))));
        assert_eq!(below[idx((p(2, 2), p(8, 2)))], Some((p(0, 0), p(10, 0))));
        assert_eq!(below[idx((p(2, 8), p(8, 8)))], Some((p(2, 2), p(8, 2))));
        assert_eq!(below[idx((p(10, 0), p(10, 10)))], None);
    }
}