geo_booleanop/boolean/
mod.rs

1use geo_types::{Coordinate, LineString, MultiPolygon, Polygon};
2
3pub mod compare_segments;
4pub mod compute_fields;
5mod connect_edges;
6mod divide_segment;
7pub mod fill_queue;
8mod helper;
9pub mod possible_intersection;
10mod segment_intersection;
11mod signed_area;
12pub mod subdivide_segments;
13pub mod sweep_event;
14
15pub use helper::{BoundingBox, Float};
16
17use self::connect_edges::connect_edges;
18use self::fill_queue::fill_queue;
19use self::subdivide_segments::subdivide;
20
21#[derive(Clone, Copy, PartialEq, Eq, Debug)]
22pub enum Operation {
23    Intersection,
24    Difference,
25    Union,
26    Xor,
27}
28
29pub trait BooleanOp<F, Rhs = Self>
30where
31    F: Float,
32{
33    fn boolean(&self, rhs: &Rhs, operation: Operation) -> MultiPolygon<F>;
34
35    fn intersection(&self, rhs: &Rhs) -> MultiPolygon<F> {
36        self.boolean(rhs, Operation::Intersection)
37    }
38
39    fn difference(&self, rhs: &Rhs) -> MultiPolygon<F> {
40        self.boolean(rhs, Operation::Difference)
41    }
42
43    fn union(&self, rhs: &Rhs) -> MultiPolygon<F> {
44        self.boolean(rhs, Operation::Union)
45    }
46
47    fn xor(&self, rhs: &Rhs) -> MultiPolygon<F> {
48        self.boolean(rhs, Operation::Xor)
49    }
50}
51
52impl<F> BooleanOp<F> for Polygon<F>
53where
54    F: Float,
55{
56    fn boolean(&self, rhs: &Polygon<F>, operation: Operation) -> MultiPolygon<F> {
57        boolean_operation(&[self.clone()], &[rhs.clone()], operation)
58    }
59}
60
61impl<F> BooleanOp<F, MultiPolygon<F>> for Polygon<F>
62where
63    F: Float,
64{
65    fn boolean(&self, rhs: &MultiPolygon<F>, operation: Operation) -> MultiPolygon<F> {
66        boolean_operation(&[self.clone()], rhs.0.as_slice(), operation)
67    }
68}
69
70impl<F> BooleanOp<F> for MultiPolygon<F>
71where
72    F: Float,
73{
74    fn boolean(&self, rhs: &MultiPolygon<F>, operation: Operation) -> MultiPolygon<F> {
75        boolean_operation(self.0.as_slice(), rhs.0.as_slice(), operation)
76    }
77}
78
79impl<F> BooleanOp<F, Polygon<F>> for MultiPolygon<F>
80where
81    F: Float,
82{
83    fn boolean(&self, rhs: &Polygon<F>, operation: Operation) -> MultiPolygon<F> {
84        boolean_operation(self.0.as_slice(), &[rhs.clone()], operation)
85    }
86}
87
88fn boolean_operation<F>(subject: &[Polygon<F>], clipping: &[Polygon<F>], operation: Operation) -> MultiPolygon<F>
89where
90    F: Float,
91{
92    let mut sbbox = BoundingBox {
93        min: Coordinate {
94            x: F::infinity(),
95            y: F::infinity(),
96        },
97        max: Coordinate {
98            x: F::neg_infinity(),
99            y: F::neg_infinity(),
100        },
101    };
102    let mut cbbox = sbbox;
103
104    let mut event_queue = fill_queue(subject, clipping, &mut sbbox, &mut cbbox, operation);
105
106    if sbbox.min.x > cbbox.max.x || cbbox.min.x > sbbox.max.x || sbbox.min.y > cbbox.max.y || cbbox.min.y > sbbox.max.y
107    {
108        return trivial_result(subject, clipping, operation);
109    }
110
111    let sorted_events = subdivide(&mut event_queue, &sbbox, &cbbox, operation);
112
113    let contours = connect_edges(&sorted_events);
114
115    // Convert contours into polygons
116    let polygons: Vec<Polygon<F>> = contours
117        .iter()
118        .filter(|contour| contour.is_exterior())
119        .map(|contour| {
120            let exterior = LineString(contour.points.clone());
121            let mut interios: Vec<LineString<F>> = Vec::new();
122            for hole_id in &contour.hole_ids {
123                interios.push(LineString(contours[*hole_id as usize].points.clone()));
124            }
125            Polygon::new(exterior, interios)
126        })
127        .collect();
128
129    MultiPolygon(polygons)
130}
131
132fn trivial_result<F>(subject: &[Polygon<F>], clipping: &[Polygon<F>], operation: Operation) -> MultiPolygon<F>
133where
134    F: Float,
135{
136    match operation {
137        Operation::Intersection => MultiPolygon(vec![]),
138        Operation::Difference => MultiPolygon(Vec::from(subject)),
139        Operation::Union | Operation::Xor => MultiPolygon(subject.iter().chain(clipping).cloned().collect()),
140    }
141}
geo_booleanop/boolean/mod.rs

geo_booleanop/boolean/
mod.rs
