clipper

    A port of Clipper2: polygon union, intersection, difference, xor and offsetting, with results identical to the C++ library

    clipper2
    polygon
    clipping
    offset
    geometry
    Download zip
    Author
    Version
    0.1.0
    License
    Apache-2.0 AND BSL-1.0
    Last updated
    5 hours ago
    Downloads
    3

    No dependencies

    #clipper

    Clipper2 in MoonBit: polygon clipping (union, intersection, difference, xor) and offsetting on 64-bit integer coordinates. It is a port of Clipper2 2.0.1 whose results are identical to the C++ library's, vertex for vertex, on every MoonBit backend (wasm, wasm-gc, js, native). It has no dependencies besides moonbitlang/core.

    It is the geometry engine of mbt-map, a WebGIS library, published on its own.

    moon add t-ujiie-g/clipper

    fn square(x : Int64, y : Int64, s : Int64) -> Array[@clipper.Point64] {
    [{ x, y }, { x: x + s, y }, { x: x + s, y: y + s }, { x, y: y + s }]
    }

    test "clip and offset" {
    let a = [square(0L, 0L, 10L)]
    let b = [square(5L, 5L, 10L)]
    let both = @clipper.intersect(a, b, NonZero)
    assert_eq(@clipper.area(both[0][:]), 25.0)
    let either = @clipper.union(a, b, NonZero)
    assert_eq(@clipper.area(either[0][:]), 175.0)
    // A square grown by 1 with miter joins keeps its corners: 12 x 12.
    let grown = @clipper.inflate_paths(a, 1.0, Miter, Polygon)
    assert_eq(@clipper.area(grown[0][:]), 144.0)
    }

    #What is in it

    • union, intersect, difference, xor, boolean_op: closed paths in, closed paths out, by a fill rule (EvenOdd, NonZero, Positive, Negative).
    • Clipper64: the engine itself, for open subjects (add_open_subject) and for results as a tree of outer rings and holes (execute_tree, PolyPath64).
    • inflate_paths and ClipperOffset: growing and shrinking polygons and buffering lines, with Square, Bevel, Round and Miter joins and Polygon, Joined, Butt, Square and Round ends.
    • area (signed by orientation) and point_in_polygon.

    Coordinates are integers (Point64), as in Clipper2: scale your numbers first (for example by 1000 for millimeters) and keep them within MAX_COORD.

    Not ported: rectangle clipping, triangulation, Minkowski sums and Z values.

    #Matching the C++ library

    Clipper2's output depends on the order std::sort leaves equal elements in, so this port carries libc++'s sort (libcxx_sort.mbt). The repository checks 10,720 clipping runs and 4,500 offset runs against the C++ library compiled to WebAssembly from the same commit (clipper2-wasm 0.4.0): all identical on the js and wasm-gc backends.

    #License

    Apache-2.0 for the port; Clipper2 is under the Boost Software License 1.0 (see NOTICE).

    ClipType

    pub(all) enum ClipType {
    NoClip
    Intersection
    Union
    Difference
    Xor
    } derive(Eq,
    Debug
    )

    A boolean operation (Clipper2's ClipType; all but Difference commute).

    ClipType::equal

    fn ClipType::equal(ClipType, ClipType) -> Bool

    ClipType::not_equal

    fn ClipType::not_equal(x : ClipType, y : ClipType) -> Bool

    ClipType::to_repr

    Clipper64

    pub struct Clipper64 {
    // private fields
    }

    Clipper2's sweep-line engine (ClipperBase and Clipper64): add subject and clip paths, then execute a boolean operation.

    Clipper64::add_clip

    fn Clipper64::add_clip(self : Clipper64, paths : Array[Array[Point64]]) -> Unit

    Adds clip paths (always closed).

    Clipper64::add_open_subject

    fn Clipper64::add_open_subject(self : Clipper64, paths : Array[Array[Point64]]) -> Unit

    Adds open subject paths (polylines).

    Clipper64::add_subject

    fn Clipper64::add_subject(self : Clipper64, paths : Array[Array[Point64]]) -> Unit

    Adds closed subject paths.

    Clipper64::clear

    fn Clipper64::clear(self : Clipper64) -> Unit

    Forgets every added path.

    Clipper64::execute

    fn Clipper64::execute(self : Clipper64, clip_type : ClipType, fill_rule : FillRule) -> (Array[Array[Point64]], Array[Array[Point64]])?

    Runs clip_type with fill_rule over the added paths: closed solution paths (outer ones counter-clockwise in a y-up frame unless reversed) and open ones. None if the operation failed.

    Clipper64::execute_tree

    fn Clipper64::execute_tree(self : Clipper64, clip_type : ClipType, fill_rule : FillRule) -> (PolyPath64, Array[Array[Point64]])?

    Like execute, with the closed solution as a tree of nested polygons.

    Clipper64::new

    fn Clipper64::new() -> Clipper64

    Clipper64::set_preserve_collinear

    fn Clipper64::set_preserve_collinear(self : Clipper64, v : Bool) -> Unit

    Whether collinear edges are kept in solutions (default true; 180° spikes are always removed).

    Clipper64::set_reverse_solution

    fn Clipper64::set_reverse_solution(self : Clipper64, v : Bool) -> Unit

    Whether solutions are wound the other way round.

    ClipperOffset

    pub struct ClipperOffset {
    // private fields
    }

    Inflates or shrinks paths (Clipper2's ClipperOffset): add groups of paths with their join and end types, then execute with a distance.

    ClipperOffset::add_paths

    fn ClipperOffset::add_paths(self : ClipperOffset, paths : Array[Array[Point64]], join_type : JoinType, end_type : EndType) -> Unit

    Adds paths to offset together with join_type and end_type.

    ClipperOffset::execute

    fn ClipperOffset::execute(self : ClipperOffset, delta : Double) -> Array[Array[Point64]]

    The added paths offset by delta (outwards for positive values on polygons), with overlaps merged.

    ClipperOffset::new

    fn ClipperOffset::new(miter_limit? : Double, arc_tolerance? : Double, preserve_collinear? : Bool, reverse_solution? : Bool) -> ClipperOffset

    An offsetter; arc_tolerance 0 means the offset distance / 500.

    EndType

    pub(all) enum EndType {
    Polygon
    Joined
    Butt
    Square
    Round
    } derive(Eq)

    How offset paths end (EndType): Polygon one side of a closed path, Joined both sides with the ends joined, Butt, Square and Round both sides of an open path with those caps.

    EndType::equal

    fn EndType::equal(EndType, EndType) -> Bool

    EndType::not_equal

    fn EndType::not_equal(x : EndType, y : EndType) -> Bool

    FillRule

    pub(all) enum FillRule {
    EvenOdd
    NonZero
    Positive
    Negative
    } derive(Eq,
    Debug
    )

    Which regions of a set of paths count as filled (Clipper2's FillRule).

    FillRule::equal

    fn FillRule::equal(FillRule, FillRule) -> Bool

    FillRule::not_equal

    fn FillRule::not_equal(x : FillRule, y : FillRule) -> Bool

    FillRule::to_repr

    JoinType

    pub(all) enum JoinType {
    Square
    Bevel
    Round
    Miter
    } derive(Eq)

    How offset paths turn corners (JoinType): Square cuts them at exactly the offset distance, Bevel cuts them closer in, Round follows an arc, Miter extends edges up to the miter limit.

    JoinType::equal

    fn JoinType::equal(JoinType, JoinType) -> Bool

    JoinType::not_equal

    fn JoinType::not_equal(x : JoinType, y : JoinType) -> Bool

    Point64

    pub(all) struct Point64 {
    x : Int64
    y : Int64
    } derive(Eq,
    Debug
    )

    A point with integer coordinates (Clipper2's Point64).

    Point64::equal

    fn Point64::equal(Point64, Point64) -> Bool

    Point64::not_equal

    fn Point64::not_equal(x : Point64, y : Point64) -> Bool

    Point64::to_repr

    PointInPolygonResult

    pub(all) enum PointInPolygonResult {
    IsOn
    IsInside
    IsOutside
    } derive(Eq,
    Debug
    )

    Where a point lies relative to a polygon (PointInPolygonResult).

    PointInPolygonResult::equal

    PointInPolygonResult::not_equal

    PolyPath64

    pub struct PolyPath64 {
    polygon : Array[Point64]
    children : Array[PolyPath64]
    // private fields
    }

    A node of a solution's tree of nested polygons (PolyPath64): the root has no polygon; children of an outer polygon are its holes, and so on.

    PolyPath64::is_hole

    fn PolyPath64::is_hole(self : PolyPath64) -> Bool

    Whether the node's polygon is a hole (an even level other than 0).

    PolyPath64::level

    fn PolyPath64::level(self : PolyPath64) -> Int

    The node's depth below the root (0 for the root).

    PolyPath64::new

    fn PolyPath64::new() -> PolyPath64

    MAX_COORD

    let MAX_COORD : Int64

    Largest coordinate Clipper2 accepts (INT64_MAX >> 2).

    area

    fn area(path : ArrayView[Point64]) -> Double

    A path's signed area, positive for counter-clockwise paths in a y-up frame (Area).

    boolean_op

    fn boolean_op(clip_type : ClipType, fill_rule : FillRule, subjects : Array[Array[Point64]], clips : Array[Array[Point64]]) -> Array[Array[Point64]]

    subjects combined with clips by clip_type (Clipper2's BooleanOp): the closed solution, or empty if the operation failed.

    difference

    fn difference(subjects : Array[Array[Point64]], clips : Array[Array[Point64]], fill_rule : FillRule) -> Array[Array[Point64]]

    subjects without clips.

    inflate_paths

    fn inflate_paths(paths : Array[Array[Point64]], delta : Double, join_type : JoinType, end_type : EndType, miter_limit? : Double, arc_tolerance? : Double) -> Array[Array[Point64]]

    paths offset by delta with one join and end type (Clipper2's InflatePaths; a positive delta grows polygons).

    intersect

    fn intersect(subjects : Array[Array[Point64]], clips : Array[Array[Point64]], fill_rule : FillRule) -> Array[Array[Point64]]

    The intersection of subjects and clips.

    point_in_polygon

    fn point_in_polygon(pt : Point64, polygon : ArrayView[Point64]) -> PointInPolygonResult

    Whether pt is on, inside or outside polygon (PointInPolygon).

    union

    fn union(subjects : Array[Array[Point64]], clips : Array[Array[Point64]], fill_rule : FillRule) -> Array[Array[Point64]]

    The union of subjects and clips (pass no clips to merge subjects).

    xor

    fn xor(subjects : Array[Array[Point64]], clips : Array[Array[Point64]], fill_rule : FillRule) -> Array[Array[Point64]]

    What lies in exactly one of subjects and clips.