polygon_unionfind 0.5.7

Disjoint-set data structure (union-find) for polygons.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111

# 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 with an R-tree.

This library has optional integration with
[`undoredo`](https://crates.io/crates/undoredo), a crate which provides
[Undo/Redo](https://en.wikipedia.org/wiki/Undo) 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 merging and undo-redo
action, you can run our graphical demo implemented using the cross-platform
[`macroquad`](https://crates.io/crates/macroquad) crate by running the following
command:

```sh
cargo run --manifest-path=demo/Cargo.toml
```

## Usage

### Adding dependency

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

```toml
[dependencies]
polygon_unionfind = { version = "0.5.7", 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`.

```rust
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](https://docs.rs/dcel/latest/dcel) for more information
about `dcel`'s usage.

## Feature flags

- `std` (default): enables `std` support.
- `undoredo` (optional): provides recording of deltas for Undo/Redo with the
  [`undoredo`](https://crates.io/crates/undoredo) crate.

## Packaging

`dcel` is published as a [crate](https://crates.io/crates/dcel) on the
[Crates.io](https://crates.io/) registry.

## Contributing

We welcome issues and pull requests from anyone to our
[repository](https://github.com/mikwielgus/polygon_unionfind) on GitHub.

## Licence

### Outbound licence

`dcel` is dual-licensed as under either of

- [MIT license](./LICENSES/MIT.txt),
- [Apache License, Version 2.0](./LICENSES/Apache-2.0.txt),

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.