1 use geo_types::{Coordinate, LineString, MultiPolygon, Polygon};
2
3 pub mod compare_segments;
4 pub mod compute_fields;
5 mod connect_edges;
6 mod divide_segment;
7 pub mod fill_queue;
8 mod helper;
9 pub mod possible_intersection;
10 mod segment_intersection;
11 mod signed_area;
12 pub mod subdivide_segments;
13 pub mod sweep_event;
14
15 pub use helper::{BoundingBox, Float};
16
17 use self::connect_edges::connect_edges;
18 use self::fill_queue::fill_queue;
19 use self::subdivide_segments::subdivide;
20
21 #[derive(Clone, Copy, PartialEq, Eq, Debug)]
22 pub enum Operation {
23 Intersection,
24 Difference,
25 Union,
26 Xor,
27 }
28
29 pub trait BooleanOp<F, Rhs = Self>
30 where
31 F: Float,
32 {
boolean(&self, rhs: &Rhs, operation: Operation) -> MultiPolygon<F>33 fn boolean(&self, rhs: &Rhs, operation: Operation) -> MultiPolygon<F>;
34
intersection(&self, rhs: &Rhs) -> MultiPolygon<F>35 fn intersection(&self, rhs: &Rhs) -> MultiPolygon<F> {
36 self.boolean(rhs, Operation::Intersection)
37 }
38
difference(&self, rhs: &Rhs) -> MultiPolygon<F>39 fn difference(&self, rhs: &Rhs) -> MultiPolygon<F> {
40 self.boolean(rhs, Operation::Difference)
41 }
42
union(&self, rhs: &Rhs) -> MultiPolygon<F>43 fn union(&self, rhs: &Rhs) -> MultiPolygon<F> {
44 self.boolean(rhs, Operation::Union)
45 }
46
xor(&self, rhs: &Rhs) -> MultiPolygon<F>47 fn xor(&self, rhs: &Rhs) -> MultiPolygon<F> {
48 self.boolean(rhs, Operation::Xor)
49 }
50 }
51
52 impl<F> BooleanOp<F> for Polygon<F>
53 where
54 F: Float,
55 {
boolean(&self, rhs: &Polygon<F>, operation: Operation) -> MultiPolygon<F>56 fn boolean(&self, rhs: &Polygon<F>, operation: Operation) -> MultiPolygon<F> {
57 boolean_operation(&[self.clone()], &[rhs.clone()], operation)
58 }
59 }
60
61 impl<F> BooleanOp<F, MultiPolygon<F>> for Polygon<F>
62 where
63 F: Float,
64 {
boolean(&self, rhs: &MultiPolygon<F>, operation: Operation) -> MultiPolygon<F>65 fn boolean(&self, rhs: &MultiPolygon<F>, operation: Operation) -> MultiPolygon<F> {
66 boolean_operation(&[self.clone()], rhs.0.as_slice(), operation)
67 }
68 }
69
70 impl<F> BooleanOp<F> for MultiPolygon<F>
71 where
72 F: Float,
73 {
boolean(&self, rhs: &MultiPolygon<F>, operation: Operation) -> MultiPolygon<F>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
79 impl<F> BooleanOp<F, Polygon<F>> for MultiPolygon<F>
80 where
81 F: Float,
82 {
boolean(&self, rhs: &Polygon<F>, operation: Operation) -> MultiPolygon<F>83 fn boolean(&self, rhs: &Polygon<F>, operation: Operation) -> MultiPolygon<F> {
84 boolean_operation(self.0.as_slice(), &[rhs.clone()], operation)
85 }
86 }
87
boolean_operation<F>(subject: &[Polygon<F>], clipping: &[Polygon<F>], operation: Operation) -> MultiPolygon<F> where F: Float,88 fn boolean_operation<F>(subject: &[Polygon<F>], clipping: &[Polygon<F>], operation: Operation) -> MultiPolygon<F>
89 where
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
trivial_result<F>(subject: &[Polygon<F>], clipping: &[Polygon<F>], operation: Operation) -> MultiPolygon<F> where F: Float,132 fn trivial_result<F>(subject: &[Polygon<F>], clipping: &[Polygon<F>], operation: Operation) -> MultiPolygon<F>
133 where
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 }
142