Crate polygon_unionfind 

polygon_unionfind

polygon_unionfind is a Rust library that implements disjoint-polygon data structure (polygon union-find): a disjoint-set data structure where sets are polygons.

Upon insertion, each polygon is merged with all the intersecting polygons that are already present. To reduce the cost of finding intersecting polygons, they are spatially filtered with an R-tree.

This library has optional integration with undoredo, a crate which provides Undo/Redo functionality for any data structure, allowing to programmatically revert and restore any change using deltas or snapshots.

Demo

For an interactive visualization of polygon_unionfind’s polygon addition, subtraction, and undo-redo action, you can run our graphical demos implemented using the cross-platform macroquad crate by running the following commands. The first one is shown in action on the animation above.

cargo run --manifest-path=demos/polygon_set/Cargo.toml

cargo run --manifest-path=demos/combinators/Cargo.toml

cargo run --manifest-path=demos/layers_with_transitions/Cargo.toml

Usage

Adding dependency

First, add polygon_unionfind as a dependency to your Cargo.toml:

[dependencies]
polygon_unionfind = { version = "0.7.4", features = ["undoredo"] }

If you don’t need to perform undo and redo operations, you can remove the undoredo feature.

Basic usage

Following is a basic usage example of polygon_unionfind.

use polygon_unionfind::{PolygonUnionFind, PolygonWithData};

let mut polygon_unionfind = PolygonUnionFind::<i32, PolygonWithData<i32, &str>>::new();

let polygon1 = polygon_unionfind.add(PolygonWithData {
    exterior: vec![
        [0, 0],
        [3, 0],
        [4, 2],
        [3, 4],
        [0, 4],
        [-1, 2],
    ],
    interiors: vec![],
    data: "first",
});

let polygon2 = polygon_unionfind.add(PolygonWithData {
    exterior: vec![
        [2, 0],
        [5, 0],
        [6, 2],
        [5, 4],
        [2, 4],
        [1, 2],
    ],
    interiors: vec![],
    data: "second",
});

// Overlapping polygons are now in the same set and thus have the same
// representative.
let polygon1_repr = polygon_unionfind.find(polygon1.index()).exterior.len();
let polygon2_repr = polygon_unionfind.find(polygon2.index()).exterior.len();
assert_eq!(polygon1_repr, polygon2_repr);

Documentation

See the documentation for more information about polygon_unionfind’s usage.

Feature flags

• std (default): enables std support.
• undoredo (optional): provides recording of deltas for Undo/Redo with the undoredo crate.

Packaging

polygon_unionfind is published as a crate on the Crates.io registry.

Contributing

We welcome issues and pull requests from anyone to our repository on GitHub.

Licence

Outbound licence

polygon_unionfind is dual-licensed as under either of

• MIT license,
• Apache License, Version 2.0,

at your option.

Inbound licence

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you will be dual-licensed as described above, without any additional terms or conditions.

Structs

Inflated

Laminate

Negated

Paralleled

Polygon

PolygonId

An index pointing to a polygon.

PolygonSet

PolygonUnionFind

PolygonWithData

UnionFind

Disjoint-set union data structure, widely also known as union-find.

Traits

Add

Clip

Difference

Inflate

Intersection

Rings

Sub

Union

Type Aliases

LaminateDelta

Delta of Laminate for delta-based Undo/Redo.

LaminateHalfDelta

Half-delta of Laminate.

PolygonSetDelta

Delta of PolygonSet for delta-based Undo/Redo.

PolygonSetHalfDelta

Half-delta of PolygonSet.

PolygonUnionFindDelta

Delta of PolygonUnionFind for delta-based Undo/Redo.

PolygonUnionFindHalfDelta

Half-delta of PolygonUnionFind.

RecordingInflated

Inflated that records changes for delta-based Undo/Redo.

RecordingLaminate

Laminate-equivalent using recording container combinators.

RecordingNegated

Negated that records changes for delta-based Undo/Redo.

RecordingParalleled

Paralleled that records changes for delta-based Undo/Redo.

RecordingPolygonSet

PolygonSet that records changes for delta-based Undo/Redo.

RecordingPolygonUnionFind

PolygonUnionFind that records changes for delta-based Undo/Redo.