Linesweeper API

Overview

Linesweeper is a Rust crate implementing a robust Bentley-Ottmann sweep-line algorithm for boolean operations on sets bounded by Bézier paths. It handles unions, intersections, differences, and XOR operations between curved shapes.

When to Use

•Boolean operations on 2D paths (union, intersection, difference, XOR)
•Computing overlapping regions between shapes
•Working with path winding numbers
•Processing font outlines or vector graphics
•N-ary operations on multiple shapes with custom rules

When NOT to use:

•Simple path operations (use kurbo directly)
•Non-closed paths (linesweeper requires closed paths)
•Single-path analysis without boolean ops (use kurbo's Area, Winding)

Quick Reference

Task	Function/Type
Simple boolean op	`binary_op(&path_a, &path_b, fill_rule, op)`
With epsilon control	`binary_op_with_eps(..., eps)`
Custom winding rules	`Topology::<W>::from_paths(...)`
Polyline input	`Topology::from_polylines_binary(...)`
Get nested contours	`contours.grouped()`

Core Types

rust

use linesweeper::{binary_op, FillRule, BinaryOp, Error};
use linesweeper::topology::{Topology, Contours, Contour, BinaryWindingNumber, WindingNumber};

FillRule: EvenOdd | NonZero BinaryOp: Union | Intersection | Difference | Xor

Usage Patterns

Basic Boolean Operation

rust

use kurbo::Shape;
use linesweeper::{binary_op, FillRule, BinaryOp};

let square = kurbo::Rect::from_center_size((0.0, 0.0), (2.0, 2.0)).to_path(1e-6);
let circle = kurbo::Circle::new((0.0, 0.0), 1.2).to_path(1e-6);

let result = binary_op(&square, &circle, FillRule::EvenOdd, BinaryOp::Intersection)?;

for contour in result.contours() {
    // contour.path: BezPath - the geometry
    // contour.outer: bool - true if outer boundary, false if hole
    // contour.parent: Option<ContourIdx> - parent contour for holes
}

Hierarchical Contours (Shapes with Holes)

rust

let result = binary_op(&outer, &inner, FillRule::EvenOdd, BinaryOp::Difference)?;

// grouped() returns Vec<Vec<ContourIdx>> organized by nesting
for group in result.grouped() {
    let outer_contour = &result[group[0]];  // First is always outer
    let holes = &group[1..];                 // Rest are holes

    for &hole_idx in holes {
        let hole = &result[hole_idx];
    }
}

Custom N-ary Operations

For operations on more than two shapes, implement WindingNumber:

rust

use linesweeper::topology::{Topology, WindingNumber};

#[derive(Copy, Clone, Debug, Default, PartialEq, Eq)]
struct MyWindings {
    main: i32,
    cutout: i32,
}

#[derive(Copy, Clone, Debug, PartialEq, Eq)]
enum Tag { Main, Cutout }

impl WindingNumber for MyWindings {
    type Tag = Tag;
    fn single(tag: Self::Tag, positive: bool) -> Self {
        let delta = if positive { 1 } else { -1 };
        match tag {
            Tag::Main => Self { main: delta, cutout: 0 },
            Tag::Cutout => Self { main: 0, cutout: delta },
        }
    }
}

impl std::ops::Add for MyWindings {
    type Output = Self;
    fn add(self, rhs: Self) -> Self {
        Self { main: self.main + rhs.main, cutout: self.cutout + rhs.cutout }
    }
}

impl std::ops::AddAssign for MyWindings {
    fn add_assign(&mut self, rhs: Self) {
        *self = *self + rhs;
    }
}

let topology = Topology::<MyWindings>::from_paths(
    [(&main_path, Tag::Main), (&cutout_path, Tag::Cutout)],
    1e-6,  // epsilon
)?;

// Custom inside predicate: main shape minus cutout
let contours = topology.contours(|w| w.main > 0 && w.cutout == 0);

Polyline Input

rust

use linesweeper::topology::Topology;
use linesweeper::Point;  // re-exported at crate root

let poly_a = vec![vec![
    Point::new(0.0, 0.0),
    Point::new(1.0, 0.0),
    Point::new(1.0, 1.0),
    Point::new(0.0, 1.0),
]];

let topology = Topology::from_polylines_binary(poly_a, poly_b, 0.001);
let result = topology.contours(|w| w.shape_a != 0 || w.shape_b != 0);  // Union

Topology Query Methods

rust

let topology = Topology::from_paths_binary(&path_a, &path_b, eps)?;

// Whole-topology queries
topology.bounding_box()              // -> kurbo::Rect
topology.segment_indices()           // -> Iterator<Item = OutputSegIdx>

// Per-half-segment queries (use OutputSegIdx::first_half() or second_half())
let half_idx = seg_idx.first_half(); // -> HalfOutputSegIdx
topology.winding_clockwise(half_idx)         // -> &W
topology.winding_counter_clockwise(half_idx) // -> &W
topology.point(half_idx)                     // -> &Point

Common Mistakes

Mistake	Fix
Forgetting `?` on `binary_op`	Returns `Result<Contours, Error>`
Using unclosed paths	Paths must be closed; check for `NonClosedPath` error
Epsilon too large/small	Start with `1e-6`; adjust based on coordinate scale
Ignoring holes	Use `grouped()` for proper hole handling
Missing trait impls for custom winding	`WindingNumber` requires `Clone + Debug + Add<Output=Self> + AddAssign + Default + Eq`

Error Handling

rust

use linesweeper::Error;

match binary_op(&a, &b, fill_rule, op) {
    Ok(contours) => { /* process */ }
    Err(Error::Infinity) => { /* path contains infinite values */ }
    Err(Error::NaN) => { /* path contains NaN */ }
    Err(Error::NonClosedPath(_)) => { /* path not closed */ }
}