bevy_shape/
polygon.rs

1use alloc::{collections::BTreeMap, vec::Vec};
2use bevy_math::{ops, Vec2};
3use core::cmp::Ordering;
4
5#[derive(Debug, Clone, Copy)]
6enum Endpoint {
7    Left,
8    Right,
9}
10
11/// An event in the [`EventQueue`] is either the left or right vertex of an edge of the polygon.
12///
13/// Events are ordered so that any event `e1` which is to the left of another event `e2` is less than that event.
14/// If `e1.position().x == e2.position().x` the events are ordered from bottom to top.
15///
16/// This is the order expected by the [`SweepLine`].
17#[derive(Debug, Clone, Copy)]
18struct SweepLineEvent {
19    segment: Segment,
20    /// Type of the vertex (left or right)
21    endpoint: Endpoint,
22}
23
24impl SweepLineEvent {
25    const fn position(&self) -> Vec2 {
26        match self.endpoint {
27            Endpoint::Left => self.segment.left,
28            Endpoint::Right => self.segment.right,
29        }
30    }
31}
32
33impl PartialEq for SweepLineEvent {
34    fn eq(&self, other: &Self) -> bool {
35        self.position() == other.position()
36    }
37}
38
39impl Eq for SweepLineEvent {}
40
41impl PartialOrd for SweepLineEvent {
42    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
43        Some(self.cmp(other))
44    }
45}
46
47impl Ord for SweepLineEvent {
48    fn cmp(&self, other: &Self) -> Ordering {
49        xy_order(self.position(), other.position())
50    }
51}
52
53/// Orders 2D points according to the order expected by the sweep line and event queue from -X to +X and then -Y to Y.
54fn xy_order(a: Vec2, b: Vec2) -> Ordering {
55    a.x.total_cmp(&b.x).then_with(|| a.y.total_cmp(&b.y))
56}
57
58/// The event queue holds an ordered list of all events the [`SweepLine`] will encounter when checking the current polygon.
59#[derive(Debug, Clone)]
60struct EventQueue {
61    events: Vec<SweepLineEvent>,
62}
63impl EventQueue {
64    /// Initialize a new `EventQueue` with all events from the polygon represented by `vertices`.
65    ///
66    /// The events in the event queue will be ordered.
67    fn new(vertices: &[Vec2]) -> Self {
68        if vertices.is_empty() {
69            return Self { events: Vec::new() };
70        }
71
72        let mut events = Vec::with_capacity(vertices.len() * 2);
73        for i in 0..vertices.len() {
74            let v1 = vertices[i];
75            let v2 = *vertices.get(i + 1).unwrap_or(&vertices[0]);
76            let (left, right) = if xy_order(v1, v2) == Ordering::Less {
77                (v1, v2)
78            } else {
79                (v2, v1)
80            };
81
82            let segment = Segment {
83                edge_index: i,
84                left,
85                right,
86            };
87            events.push(SweepLineEvent {
88                segment,
89                endpoint: Endpoint::Left,
90            });
91            events.push(SweepLineEvent {
92                segment,
93                endpoint: Endpoint::Right,
94            });
95        }
96
97        events.sort();
98
99        Self { events }
100    }
101}
102
103/// Represents a segment or rather an edge of the polygon in the [`SweepLine`].
104///
105/// Segments are ordered from bottom to top based on their left vertices if possible.
106/// If their y values are identical, the segments are ordered based on the y values of their right vertices.
107#[derive(Debug, Clone, Copy)]
108struct Segment {
109    edge_index: usize,
110    left: Vec2,
111    right: Vec2,
112}
113
114impl PartialEq for Segment {
115    fn eq(&self, other: &Self) -> bool {
116        self.edge_index == other.edge_index
117    }
118}
119
120impl Eq for Segment {}
121
122impl PartialOrd for Segment {
123    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
124        Some(self.cmp(other))
125    }
126}
127
128impl Ord for Segment {
129    fn cmp(&self, other: &Self) -> Ordering {
130        self.left
131            .y
132            .total_cmp(&other.left.y)
133            .then_with(|| self.right.y.total_cmp(&other.right.y))
134    }
135}
136
137/// Holds information about which segment is above and which is below a given [`Segment`]
138#[derive(Debug, Clone, Copy)]
139struct SegmentOrder {
140    above: Option<usize>,
141    below: Option<usize>,
142}
143
144/// A sweep line allows for an efficient search for intersections between [segments](`Segment`).
145///
146/// It can be thought of as a vertical line sweeping from -X to +X across the polygon that keeps track of the order of the segments
147/// the sweep line is intersecting at any given moment.
148#[derive(Debug, Clone)]
149struct SweepLine<'a> {
150    vertices: &'a [Vec2],
151    tree: BTreeMap<Segment, SegmentOrder>,
152}
153
154impl<'a> SweepLine<'a> {
155    const fn new(vertices: &'a [Vec2]) -> Self {
156        Self {
157            vertices,
158            tree: BTreeMap::new(),
159        }
160    }
161
162    /// Determine whether the given edges of the polygon intersect.
163    fn intersects(&self, edge1: Option<usize>, edge2: Option<usize>) -> bool {
164        let Some(edge1) = edge1 else {
165            return false;
166        };
167        let Some(edge2) = edge2 else {
168            return false;
169        };
170
171        // All adjacent edges intersect at their shared vertex
172        // but these intersections do not count so we ignore them here.
173        // Likewise a segment will always intersect itself / an identical edge.
174        if edge1 == edge2
175            || (edge1 + 1) % self.vertices.len() == edge2
176            || (edge2 + 1) % self.vertices.len() == edge1
177        {
178            return false;
179        }
180
181        let s11 = self.vertices[edge1];
182        let s12 = *self.vertices.get(edge1 + 1).unwrap_or(&self.vertices[0]);
183        let s21 = self.vertices[edge2];
184        let s22 = *self.vertices.get(edge2 + 1).unwrap_or(&self.vertices[0]);
185
186        // When both points of the second edge are on the same side of the first edge, no intersection is possible.
187        if point_side(s11, s12, s21) * point_side(s11, s12, s22) > 0.0 {
188            return false;
189        }
190        if point_side(s21, s22, s11) * point_side(s21, s22, s12) > 0.0 {
191            return false;
192        }
193
194        true
195    }
196
197    /// Add a new segment to the sweep line
198    fn add(&mut self, s: Segment) -> SegmentOrder {
199        let above = if let Some((next_s, next_ord)) = self.tree.range_mut(s..).next() {
200            next_ord.below.replace(s.edge_index);
201            Some(next_s.edge_index)
202        } else {
203            None
204        };
205        let below = if let Some((prev_s, prev_ord)) = self.tree.range_mut(..s).next_back() {
206            prev_ord.above.replace(s.edge_index);
207            Some(prev_s.edge_index)
208        } else {
209            None
210        };
211
212        let s_ord = SegmentOrder { above, below };
213        self.tree.insert(s, s_ord);
214        s_ord
215    }
216
217    /// Get the segment order for the given segment.
218    ///
219    /// If `s` has not been added to the [`SweepLine`] `None` will be returned.
220    fn find(&self, s: &Segment) -> Option<&SegmentOrder> {
221        self.tree.get(s)
222    }
223
224    /// Remove `s` from the [`SweepLine`].
225    fn remove(&mut self, s: &Segment) {
226        let Some(s_ord) = self.tree.get(s).copied() else {
227            return;
228        };
229
230        if let Some((_, above_ord)) = self.tree.range_mut(s..).next() {
231            above_ord.below = s_ord.below;
232        }
233        if let Some((_, below_ord)) = self.tree.range_mut(..s).next_back() {
234            below_ord.above = s_ord.above;
235        }
236
237        self.tree.remove(s);
238    }
239}
240
241/// Test what side of the line through `p1` and `p2` `q` is.
242///
243/// The result will be `0` if the `q` is on the segment, negative for one side and positive for the other.
244#[inline]
245const fn point_side(p1: Vec2, p2: Vec2, q: Vec2) -> f32 {
246    (p2.x - p1.x) * (q.y - p1.y) - (q.x - p1.x) * (p2.y - p1.y)
247}
248
249/// Tests whether the `vertices` describe a simple polygon.
250/// The last vertex must not be equal to the first vertex.
251///
252/// A polygon is simple if it is not self intersecting and not self tangent.
253/// As such, no two edges of the polygon may cross each other and each vertex must not lie on another edge.
254///
255/// Any 'polygon' with less than three vertices is simple.
256///
257/// The algorithm used is the Shamos-Hoey algorithm, a version of the Bentley-Ottman algorithm adapted to only detect whether any intersections exist.
258/// This function will run in O(n * log n)
259pub fn is_polygon_simple(vertices: &[Vec2]) -> bool {
260    if vertices.len() < 3 {
261        return true;
262    }
263    if vertices.len() == 3 {
264        let [a, b, c] = [vertices[0], vertices[1], vertices[2]];
265        let triangle_area =
266            ops::abs(a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y)) / 2.0;
267        return triangle_area > 0.0;
268    }
269
270    let event_queue = EventQueue::new(vertices);
271    let mut sweep_line = SweepLine::new(vertices);
272
273    for e in event_queue.events {
274        match e.endpoint {
275            Endpoint::Left => {
276                let s = sweep_line.add(e.segment);
277                if sweep_line.intersects(Some(e.segment.edge_index), s.above)
278                    || sweep_line.intersects(Some(e.segment.edge_index), s.below)
279                {
280                    return false;
281                }
282            }
283            Endpoint::Right => {
284                if let Some(s) = sweep_line.find(&e.segment) {
285                    if sweep_line.intersects(s.above, s.below) {
286                        return false;
287                    }
288                    sweep_line.remove(&e.segment);
289                }
290            }
291        }
292    }
293
294    true
295}
296
297#[cfg(test)]
298mod tests {
299    use super::*;
300    use bevy_math::Vec2;
301
302    #[test]
303    fn complex_polygon() {
304        // A square with one side punching through the opposite side.
305        let verts = [Vec2::ZERO, Vec2::X, Vec2::ONE, Vec2::Y, Vec2::new(2.0, 0.5)];
306        assert!(!is_polygon_simple(&verts));
307
308        // A square with a vertex from one side touching the opposite side.
309        let verts = [Vec2::ZERO, Vec2::X, Vec2::ONE, Vec2::Y, Vec2::new(1.0, 0.5)];
310        assert!(!is_polygon_simple(&verts));
311
312        // A square with one side touching the opposite side.
313        let verts = [
314            Vec2::ZERO,
315            Vec2::X,
316            Vec2::ONE,
317            Vec2::Y,
318            Vec2::new(1.0, 0.6),
319            Vec2::new(1.0, 0.4),
320        ];
321        assert!(!is_polygon_simple(&verts));
322
323        // Four points lying on a line
324        let verts = [Vec2::ONE, Vec2::new(3., 2.), Vec2::new(5., 3.), Vec2::NEG_X];
325        assert!(!is_polygon_simple(&verts));
326
327        // Three points lying on a line
328        let verts = [Vec2::ONE, Vec2::new(3., 2.), Vec2::NEG_X];
329        assert!(!is_polygon_simple(&verts));
330
331        // Two identical points and one other point
332        let verts = [Vec2::ONE, Vec2::ONE, Vec2::NEG_X];
333        assert!(!is_polygon_simple(&verts));
334
335        // Two triangles with one shared side
336        let verts = [Vec2::ZERO, Vec2::X, Vec2::Y, Vec2::ONE, Vec2::X, Vec2::Y];
337        assert!(!is_polygon_simple(&verts));
338    }
339
340    #[test]
341    fn simple_polygon() {
342        // A square
343        let verts = [Vec2::ZERO, Vec2::X, Vec2::ONE, Vec2::Y];
344        assert!(is_polygon_simple(&verts));
345
346        let verts = [];
347        assert!(is_polygon_simple(&verts));
348    }
349}
bevy_shape/polygon.rs

bevy_shape/
polygon.rs
