polygon_unionfind

polygon_unionfind is a disjoint-set data structure (union-find) 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, polygons are spatially filtered by being kept in an R-tree.

Usage

Adding dependency

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

[dependencies]
polygon_unionfind = "0.5"

Basic usage

Following is a basic usage example of polygon_unionfind.

use polygon_unionfind::{Point, Polygon, PolygonUnionFind};

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

let first = polygon_unionfind.insert(Polygon {
    vertices: vec![
        Point { x: 0, y: 0 },
        Point { x: 3, y: 0 },
        Point { x: 0, y: 3 },
    ],
    weight: "first",
});

let second = polygon_unionfind.insert(Polygon {
    vertices: vec![
        Point { x: 1, y: 0 },
        Point { x: 4, y: 0 },
        Point { x: 1, y: 3 },
    ],
    weight: "second",
});

// Overlapping polygons are now in the same set and thus have the same
// representative.
let repr_first = polygon_unionfind.find(first).vertices.len();
let repr_second = polygon_unionfind.find(second).vertices.len();
assert_eq!(rep_first, rep_second);

Documentation

See the documentation for more information about dcel's usage.

Features

std (default): enables std support.
undoredo (optional): enables integration with the undoredo crate.

Packaging

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

Contributing

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

Licence

Outbound licence

dcel is dual-licensed as under either of

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.

polygon_unionfind 0.5.5