iron_shapes_booleanop/
lib.rs

1// Copyright (c) 2018-2021 Thomas Kramer.
2// SPDX-FileCopyrightText: 2022 Thomas Kramer
3//
4// SPDX-License-Identifier: AGPL-3.0-or-later
5//
6// Original licence until 2020: MIT
7// SPDX-FileCopyrightText: 2020 Fabian Keller <github.100.fkeller@spamgourmet.com> (contributions under MIT licence)
8// SPDX-FileCopyrightText: 2020 Bodo Junglas <junglas@objectcode.de> (contributions under MIT licence)
9// SPDX-FileCopyrightText: 2020 Boyd Johnson (all contributions overwritten by now)
10// SPDX-FileCopyrightText: 2020 Robert Sayre (all contributions overwritten by now)
11
12#![deny(missing_docs)]
13
14//! Library for boolean operations on polygons.
15//!
16//! # Example
17//!
18//! ```
19//! use iron_shapes::prelude::*;
20//! use iron_shapes_booleanop::BooleanOp;
21//!
22//! // Create two polygons.
23//! let p1 = Polygon::from(vec![(0., 0.), (2., 0.), (2., 1.), (0., 1.)]);
24//! let p2 = p1.translate((1., 0.).into()); // Shift p1 by (1, 0).
25//!
26//! // Compute the boolean intersection of the two squares.
27//! let intersection = p1.intersection(&p2);
28//! assert_eq!(intersection.polygons.len(), 1);
29//! assert_eq!(intersection.polygons[0], Polygon::from(vec![(1., 0.), (2., 0.), (2., 1.), (1., 1.)]));
30//!
31//! // Compute the boolean exclusive-or of the two squares.
32//! // This results in two unconnected polygons. This demonstrates why boolean operations return always
33//! // a `MultiPolygon`.
34//! let intersection = p1.xor(&p2);
35//! assert_eq!(intersection.polygons.len(), 2);
36//! ```
37//!
38//! # References
39//! * This work is originally loosely based: F. Martinez, A. Rueda, F. Feito, "A new algorithm for computing Boolean operations on polygons", 2013, doi:10.1016/j.advengsoft.2013.04.004
40//!
41//! The algorithm implemented here deviates from the reference paper. Most notably, the ordering of lines
42//! 6-9 in Listing 2 is done differently to properly handle vertical overlapping edges.
43//!
44//! * More systematic approach: [PDF](https://www.boost.org/doc/libs/1_44_0/libs/polygon/doc/GTL_boostcon2009.pdf), [archived](https://web.archive.org/save/https://www.boost.org/doc/libs/1_44_0/libs/polygon/doc/GTL_boostcon2009.pdf)
45
46extern crate iron_shapes;
47
48mod booleanop;
49mod connect_edges;
50pub mod connectivity_extraction;
51mod init_events;
52mod sweep_line;
53
54use num_rational::{Rational32, Rational64};
55
56// API exports.
57pub use booleanop::edges_boolean_op;
58pub use sweep_line::intersection::{
59    edge_intersection_float, edge_intersection_integer, edge_intersection_rational,
60};
61
62use iron_shapes::prelude::{CoordinateType, MultiPolygon, Polygon};
63
64// /// Abstraction of a line segment or 'edge'.
65// pub trait Segment {
66//     /// Numeric type used for coordinates.
67//     type Coord: CoordinateType;
68//
69//     /// Get the starting point of the segment.
70//     fn start(&self) -> Point<Self::Coord>;
71//
72//     /// Get the end point of the segment.
73//     fn end(&self) -> Point<Self::Coord>;
74//
75//     /// If start and end point are equal.
76//     fn is_degenerate(&self) -> bool {
77//         self.start() == self.end()
78//     }
79// }
80
81/// Type of boolean operation.
82#[derive(Clone, Copy, PartialEq, Eq, Debug)]
83pub enum Operation {
84    /// Compute the boolean AND.
85    Intersection,
86    /// Compute the boolean difference `A & (not B)`.
87    Difference,
88    /// Compute the boolean OR.
89    Union,
90    /// Compute the boolean XOR (symmetric difference).
91    Xor,
92}
93
94/// Define the 'inside' of a polygon. Significant for self-overlapping polygons.
95///
96/// * `Union`: A point `p` is inside the polygon if the winding number is larger than `0`.
97/// This means that if a polygon overlaps with itself or multiple polygons overlap, the overlapping
98/// area is always 'inside'.
99/// * `XOR`: A point `p` is inside the polygon if the winding number modulo 2 is larger than `0`.
100/// This means that if an odd number of polygons overlap, the overlapping area is 'inside' the polygon.
101/// In case of an even number of overlaps, the overlapping area is 'outside'.
102///
103/// This plays an important role for self-overlapping polygons and self-overlapping multi-polygons.
104#[derive(Clone, Copy, PartialEq, Eq, Debug)]
105pub enum PolygonSemantics {
106    /// A point `p` is inside the polygon if the winding number is larger than `0`.
107    Union,
108    /// A point `p` is inside the polygon if the winding number modulo 2 is larger than `0`.
109    XOR,
110}
111
112/// Trait for geometric primitives that support boolean operations.
113pub trait BooleanOp<T: CoordinateType> {
114    /// Compute the boolean operation of `self` and `other`.
115    ///
116    /// # Parameters
117    ///
118    /// * `operation`: The type of boolean operation to be computed (intersection, union, difference, XOR).
119    /// * `other`: The other operand. A geometric object of the same type as `self`.
120    /// * `polygon_semantics`: Define the 'inside' of a polygon. In case of doubt `Union`-semantics
121    /// could be a good choice.
122    fn boolean_op(
123        &self,
124        operation: Operation,
125        other: &Self,
126        polygon_semantics: PolygonSemantics,
127    ) -> MultiPolygon<T>;
128
129    /// Compute the boolean intersection `self & other`.
130    ///
131    /// Union semantics are used for self-overlapping polygons.
132    fn intersection(&self, other: &Self) -> MultiPolygon<T> {
133        self.boolean_op(Operation::Intersection, other, PolygonSemantics::Union)
134    }
135
136    /// Compute the boolean difference `self - other`.
137    ///
138    /// Union semantics are used for self-overlapping polygons.
139    fn difference(&self, other: &Self) -> MultiPolygon<T> {
140        self.boolean_op(Operation::Difference, other, PolygonSemantics::Union)
141    }
142
143    /// Compute the boolean union `self | other`.
144    ///
145    /// Union semantics are used for self-overlapping polygons.
146    fn union(&self, other: &Self) -> MultiPolygon<T> {
147        self.boolean_op(Operation::Union, other, PolygonSemantics::Union)
148    }
149
150    /// Compute the boolean exclusive OR `self ^ other`.
151    ///
152    /// Union semantics are used for self-overlapping polygons.
153    fn xor(&self, other: &Self) -> MultiPolygon<T> {
154        self.boolean_op(Operation::Xor, other, PolygonSemantics::Union)
155    }
156}
157
158/// Implement the `BooleanOp` trait for `MultiPolygon<...>`.
159macro_rules! impl_booleanop_multipolygon {
160    ($coord:ty, $edge_intersection:ident) => {
161        impl BooleanOp<$coord> for MultiPolygon<$coord> {
162            fn boolean_op(
163                &self,
164                operation: Operation,
165                other: &Self,
166                polygon_semantics: PolygonSemantics,
167            ) -> MultiPolygon<$coord> {
168                let subject = self.all_edges_iter();
169                let clipping = other.all_edges_iter();
170                edges_boolean_op(
171                    &$edge_intersection,
172                    subject,
173                    clipping,
174                    operation,
175                    polygon_semantics,
176                )
177            }
178        }
179    };
180}
181
182impl_booleanop_multipolygon!(f32, edge_intersection_float);
183impl_booleanop_multipolygon!(f64, edge_intersection_float);
184impl_booleanop_multipolygon!(i32, edge_intersection_integer);
185impl_booleanop_multipolygon!(i64, edge_intersection_integer);
186
187impl_booleanop_multipolygon!(Rational32, edge_intersection_rational);
188impl_booleanop_multipolygon!(Rational64, edge_intersection_rational);
189
190/// Implement the `BooleanOp` trait for `Polygon<...>`.
191macro_rules! impl_booleanop_polygon {
192    ($coord:ty, $edge_intersection:ident) => {
193        impl BooleanOp<$coord> for Polygon<$coord> {
194            fn boolean_op(
195                &self,
196                operation: Operation,
197                other: &Self,
198                polygon_semantics: PolygonSemantics,
199            ) -> MultiPolygon<$coord> {
200                let subject = self.all_edges_iter();
201                let clipping = other.all_edges_iter();
202                edges_boolean_op(
203                    &$edge_intersection,
204                    subject,
205                    clipping,
206                    operation,
207                    polygon_semantics,
208                )
209            }
210        }
211    };
212}
213
214impl_booleanop_polygon!(f32, edge_intersection_float);
215impl_booleanop_polygon!(f64, edge_intersection_float);
216impl_booleanop_polygon!(i32, edge_intersection_integer);
217impl_booleanop_polygon!(i64, edge_intersection_integer);
218
219impl_booleanop_polygon!(Rational32, edge_intersection_rational);
220impl_booleanop_polygon!(Rational64, edge_intersection_rational);
iron_shapes_booleanop/lib.rs

iron_shapes_booleanop/
lib.rs
