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.6.1", 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, PolygonWithWeight};

let mut polygon_unionfind = PolygonUnionFind::<i64, PolygonWithWeight<i64, &str>>::new();

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

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

// Overlapping polygons are now in the same set and thus have the same
// representative.
let polygon1_repr = polygon_unionfind.find(polygon1).exterior.len();
let polygon2_repr = polygon_unionfind.find(polygon2).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.