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