parry3d/utils/
point_in_poly2d.rs

1use crate::math::Real;
2use na::Point2;
3use num::Zero;
4
5/// Tests if the given point is inside a convex polygon with arbitrary orientation.
6///
7/// This function uses a faster algorithm than [`point_in_poly2d`] but only works for
8/// convex polygons. It checks if the point is on the same side of all edges of the polygon.
9///
10/// The polygon is assumed to be closed, i.e., first and last point of the polygon are implicitly
11/// assumed to be connected by an edge.
12///
13/// # Arguments
14///
15/// * `pt` - The point to test
16/// * `poly` - A slice of points defining the convex polygon vertices in any order (clockwise or counter-clockwise)
17///
18/// # Returns
19///
20/// `true` if the point is inside or on the boundary of the polygon, `false` otherwise.
21///
22/// # Examples
23///
24/// ## Point Inside a Square
25///
26/// ```
27/// # #[cfg(all(feature = "dim2", feature = "f32"))] {
28/// use parry2d::utils::point_in_convex_poly2d;
29/// use parry2d::na::Point2;
30///
31/// let square = vec![
32///     Point2::origin(),
33///     Point2::new(2.0, 0.0),
34///     Point2::new(2.0, 2.0),
35///     Point2::new(0.0, 2.0),
36/// ];
37///
38/// let inside = Point2::new(1.0, 1.0);
39/// let outside = Point2::new(3.0, 1.0);
40///
41/// assert!(point_in_convex_poly2d(&inside, &square));
42/// assert!(!point_in_convex_poly2d(&outside, &square));
43/// # }
44/// ```
45///
46/// ## Point on the Boundary
47///
48/// ```
49/// # #[cfg(all(feature = "dim2", feature = "f32"))] {
50/// use parry2d::utils::point_in_convex_poly2d;
51/// use parry2d::na::Point2;
52///
53/// let triangle = vec![
54///     Point2::origin(),
55///     Point2::new(2.0, 0.0),
56///     Point2::new(1.0, 2.0),
57/// ];
58///
59/// let on_edge = Point2::new(1.0, 0.0);
60/// assert!(point_in_convex_poly2d(&on_edge, &triangle));
61/// # }
62/// ```
63///
64/// ## Empty Polygon
65///
66/// ```
67/// # #[cfg(all(feature = "dim2", feature = "f32"))] {
68/// use parry2d::utils::point_in_convex_poly2d;
69/// use parry2d::na::Point2;
70///
71/// let empty: Vec<Point2<f32>> = vec![];
72/// let point = Point2::new(1.0, 1.0);
73///
74/// // An empty polygon contains no points
75/// assert!(!point_in_convex_poly2d(&point, &empty));
76/// # }
77/// ```
78pub fn point_in_convex_poly2d(pt: &Point2<Real>, poly: &[Point2<Real>]) -> bool {
79    if poly.is_empty() {
80        false
81    } else {
82        let mut sign = 0.0;
83
84        for i1 in 0..poly.len() {
85            let i2 = (i1 + 1) % poly.len();
86            let seg_dir = poly[i2] - poly[i1];
87            let dpt = pt - poly[i1];
88            let perp = dpt.perp(&seg_dir);
89
90            if sign.is_zero() {
91                sign = perp;
92            } else if sign * perp < 0.0 {
93                return false;
94            }
95        }
96
97        true
98    }
99}
100
101/// Tests if the given point is inside an arbitrary closed polygon with arbitrary orientation,
102/// using a winding number algorithm.
103///
104/// This function works with both convex and concave polygons, and even self-intersecting
105/// polygons. It uses a winding number algorithm to determine if a point is inside.
106///
107/// The polygon is assumed to be closed, i.e., first and last point of the polygon are implicitly
108/// assumed to be connected by an edge.
109///
110/// This handles concave polygons. For a faster function dedicated to convex polygons, see [`point_in_convex_poly2d`].
111///
112/// # Arguments
113///
114/// * `pt` - The point to test
115/// * `poly` - A slice of points defining the polygon vertices in order (clockwise or counter-clockwise)
116///
117/// # Returns
118///
119/// `true` if the point is inside the polygon, `false` otherwise.
120///
121/// # Examples
122///
123/// ## Convex Polygon (Square)
124///
125/// ```
126/// # #[cfg(all(feature = "dim2", feature = "f32"))] {
127/// use parry2d::utils::point_in_poly2d;
128/// use parry2d::na::Point2;
129///
130/// let square = vec![
131///     Point2::origin(),
132///     Point2::new(2.0, 0.0),
133///     Point2::new(2.0, 2.0),
134///     Point2::new(0.0, 2.0),
135/// ];
136///
137/// let inside = Point2::new(1.0, 1.0);
138/// let outside = Point2::new(3.0, 1.0);
139///
140/// assert!(point_in_poly2d(&inside, &square));
141/// assert!(!point_in_poly2d(&outside, &square));
142/// # }
143/// ```
144///
145/// ## Concave Polygon (L-Shape)
146///
147/// ```
148/// # #[cfg(all(feature = "dim2", feature = "f32"))] {
149/// use parry2d::utils::point_in_poly2d;
150/// use parry2d::na::Point2;
151///
152/// // L-shaped polygon (concave)
153/// let l_shape = vec![
154///     Point2::origin(),
155///     Point2::new(2.0, 0.0),
156///     Point2::new(2.0, 1.0),
157///     Point2::new(1.0, 1.0),
158///     Point2::new(1.0, 2.0),
159///     Point2::new(0.0, 2.0),
160/// ];
161///
162/// let inside_corner = Point2::new(0.5, 0.5);
163/// let outside_corner = Point2::new(1.5, 1.5);
164///
165/// assert!(point_in_poly2d(&inside_corner, &l_shape));
166/// assert!(!point_in_poly2d(&outside_corner, &l_shape));
167/// # }
168/// ```
169///
170/// ## Complex Polygon with Holes
171///
172/// ```
173/// # #[cfg(all(feature = "dim2", feature = "f32"))] {
174/// use parry2d::utils::point_in_poly2d;
175/// use parry2d::na::Point2;
176///
177/// // A star shape (self-intersecting creates a complex winding pattern)
178/// let star = vec![
179///     Point2::new(0.0, 1.0),
180///     Point2::new(0.5, 0.5),
181///     Point2::new(1.0, 1.0),
182///     Point2::new(0.7, 0.3),
183///     Point2::new(1.0, -0.5),
184///     Point2::origin(),
185///     Point2::new(-1.0, -0.5),
186///     Point2::new(-0.7, 0.3),
187///     Point2::new(-1.0, 1.0),
188///     Point2::new(-0.5, 0.5),
189/// ];
190///
191/// let center = Point2::new(0.0, 0.5);
192/// assert!(point_in_poly2d(&center, &star));
193/// # }
194/// ```
195///
196/// ## Empty Polygon
197///
198/// ```
199/// # #[cfg(all(feature = "dim2", feature = "f32"))] {
200/// use parry2d::utils::point_in_poly2d;
201/// use parry2d::na::Point2;
202///
203/// let empty: Vec<Point2<f32>> = vec![];
204/// let point = Point2::new(1.0, 1.0);
205///
206/// // An empty polygon contains no points
207/// assert!(!point_in_poly2d(&point, &empty));
208/// # }
209/// ```
210pub fn point_in_poly2d(pt: &Point2<Real>, poly: &[Point2<Real>]) -> bool {
211    if poly.is_empty() {
212        return false;
213    }
214
215    let mut winding = 0i32;
216
217    for (i, a) in poly.iter().enumerate() {
218        let b = poly[(i + 1) % poly.len()];
219        let seg_dir = b - a;
220        let dpt = pt - a;
221        let perp = dpt.perp(&seg_dir);
222        winding += match (dpt.y >= 0.0, b.y > pt.y) {
223            (true, true) if perp < 0.0 => 1,
224            (false, false) if perp > 0.0 => 1,
225            _ => 0,
226        };
227    }
228
229    winding % 2 == 1
230}
231
232#[cfg(test)]
233mod tests {
234    use super::*;
235
236    #[test]
237    fn point_in_poly2d_self_intersecting() {
238        let poly = [
239            [-1.0, -1.0],
240            [0.0, -1.0],
241            [0.0, 1.0],
242            [-2.0, 1.0],
243            [-2.0, -2.0],
244            [1.0, -2.0],
245            [1.0, 2.0],
246            [-1.0, 2.0],
247        ]
248        .map(Point2::from);
249        assert!(!point_in_poly2d(&[-0.5, -0.5].into(), &poly));
250        assert!(point_in_poly2d(&[0.5, -0.5].into(), &poly));
251    }
252
253    #[test]
254    fn point_in_poly2d_concave() {
255        let poly = [
256            [615.4741821289063, 279.4120788574219],
257            [617.95947265625, 281.8973693847656],
258            [624.1727294921875, 288.73193359375],
259            [626.6580200195313, 292.4598693847656],
260            [634.7352294921875, 302.40106201171875],
261            [637.8418579101563, 306.7503356933594],
262            [642.8124389648438, 312.96356201171875],
263            [652.7536010742188, 330.98193359375],
264            [654.6176147460938, 334.7098693847656],
265            [661.4521484375, 349.0003356933594],
266            [666.4227294921875, 360.18414306640625],
267            [670.1506958007813, 367.6400451660156],
268            [675.1212768554688, 381.30914306640625],
269            [678.2279052734375, 391.2503356933594],
270            [681.33447265625, 402.43414306640625],
271            [683.81982421875, 414.23931884765625],
272            [685.0624389648438, 422.3165283203125],
273            [685.6837768554688, 431.0150146484375],
274            [686.3051147460938, 442.8201904296875],
275            [685.6837768554688, 454.0040283203125],
276            [683.81982421875, 460.83856201171875],
277            [679.4705200195313, 470.77972412109375],
278            [674.4999389648438, 480.720947265625],
279            [670.1506958007813, 486.93414306640625],
280            [662.073486328125, 497.49664306640625],
281            [659.5881958007813, 499.36065673828125],
282            [653.3749389648438, 503.70989990234375],
283            [647.7830200195313, 506.1951904296875],
284            [642.8124389648438, 507.43780517578125],
285            [631.6286010742188, 508.05914306640625],
286            [621.0661010742188, 508.05914306640625],
287            [605.5330200195313, 508.05914306640625],
288            [596.2131958007813, 508.05914306640625],
289            [586.893310546875, 508.05914306640625],
290            [578.8161010742188, 508.05914306640625],
291            [571.3602294921875, 506.1951904296875],
292            [559.5551147460938, 499.36065673828125],
293            [557.0697631835938, 497.49664306640625],
294            [542.1580200195313, 484.4488525390625],
295            [534.7021484375, 476.37164306640625],
296            [532.8381958007813, 473.8863525390625],
297            [527.2462768554688, 466.43048095703125],
298            [522.2756958007813, 450.89739990234375],
299            [521.6543579101563, 444.06280517578125],
300            [521.0330200195313, 431.6363525390625],
301            [521.6543579101563, 422.93780517578125],
302            [523.518310546875, 409.26873779296875],
303            [527.2462768554688, 397.46356201171875],
304            [532.8381958007813, 385.6584167480469],
305            [540.9154052734375, 373.23193359375],
306            [547.1286010742188, 365.77606201171875],
307            [559.5551147460938, 354.59222412109375],
308            [573.2241821289063, 342.165771484375],
309            [575.70947265625, 339.68048095703125],
310            [584.4080200195313, 331.603271484375],
311            [597.455810546875, 317.3128356933594],
312            [601.8051147460938, 311.7209167480469],
313            [607.39697265625, 303.6437072753906],
314            [611.7462768554688, 296.1878356933594],
315            [614.2315673828125, 288.1106262207031],
316            [615.4741821289063, 280.65472412109375],
317            [615.4741821289063, 279.4120788574219],
318        ]
319        .map(Point2::from);
320        let pt = Point2::from([596.0181884765625, 427.9162902832031]);
321        assert!(point_in_poly2d(&pt, &poly));
322    }
323
324    #[test]
325    #[cfg(all(feature = "dim2", feature = "alloc"))]
326    fn point_in_poly2d_concave_exact_vertex_bug() {
327        let poly = crate::shape::Ball::new(1.0).to_polyline(10);
328        assert!(point_in_poly2d(&Point2::origin(), &poly));
329        assert!(point_in_poly2d(&Point2::new(-0.25, 0.0), &poly));
330        assert!(point_in_poly2d(&Point2::new(0.25, 0.0), &poly));
331        assert!(point_in_poly2d(&Point2::new(0.0, -0.25), &poly));
332        assert!(point_in_poly2d(&Point2::new(0.0, 0.25), &poly));
333        assert!(!point_in_poly2d(&Point2::new(-2.0, 0.0), &poly));
334        assert!(!point_in_poly2d(&Point2::new(2.0, 0.0), &poly));
335        assert!(!point_in_poly2d(&Point2::new(0.0, -2.0), &poly));
336        assert!(!point_in_poly2d(&Point2::new(0.0, 2.0), &poly));
337    }
338}
parry3d/utils/point_in_poly2d.rs

parry3d/utils/
point_in_poly2d.rs
