1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
//! 2D polygon primitive (allocation-backed).
//!
//! This module is only available when `std` or `alloc` is enabled.
use crate::vec2::Vec2;
#[cfg(feature = "std")]
use std::vec::Vec;
#[cfg(all(not(feature = "std"), feature = "alloc"))]
use alloc::vec::Vec;
/// A simple 2D polygon defined by an ordered list of vertices.
///
/// - The polygon may be convex or concave.
/// - Self-intersecting polygons are not rejected, but `contains_point` is defined by the even-odd rule.
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[derive(Clone, Debug, PartialEq)]
pub struct Polygon2<Unit: Copy = (), Space: Copy = ()> {
vertices: Vec<Vec2<Unit, Space>>,
}
impl<Unit: Copy, Space: Copy> Polygon2<Unit, Space> {
/// Creates a polygon from the given vertices.
///
/// The polygon uses the vertex order as-is; it is the caller’s responsibility to ensure the
/// vertices represent the intended shape.
#[inline]
pub fn new(vertices: Vec<Vec2<Unit, Space>>) -> Self {
Self { vertices }
}
#[inline]
pub fn vertices(&self) -> &[Vec2<Unit, Space>] {
&self.vertices
}
#[inline]
pub fn into_vertices(self) -> Vec<Vec2<Unit, Space>> {
self.vertices
}
/// Returns true if the polygon contains `p`.
///
/// Uses the **even-odd** (ray casting) rule. Points on the boundary are considered **inside**.
///
/// Degenerate polygons (fewer than 3 vertices) return false.
pub fn contains_point(&self, p: Vec2<Unit, Space>) -> bool {
let n = self.vertices.len();
if n < 3 {
return false;
}
// Treat boundary as inside.
for i in 0..n {
let a = self.vertices[i];
let b = self.vertices[(i + 1) % n];
if point_on_segment(p, a, b, boundary_eps()) {
return true;
}
}
// Even-odd rule with horizontal ray to +X.
let mut inside = false;
let py = p.y;
let px = p.x;
for i in 0..n {
let a = self.vertices[i];
let b = self.vertices[(i + 1) % n];
// Check if edge crosses the horizontal line at y=py (strictly).
let ay = a.y;
let by = b.y;
let intersects = (ay > py) != (by > py);
if !intersects {
continue;
}
// Compute x coordinate where the segment crosses y=py.
let t = (py - ay) / (by - ay);
let x_int = a.x + (b.x - a.x) * t;
if px < x_int {
inside = !inside;
}
}
inside
}
}
#[inline]
fn boundary_eps() -> f32 {
if cfg!(feature = "libm") { 1e-5 } else { 1e-6 }
}
#[inline]
fn point_on_segment<Unit: Copy, Space: Copy>(p: Vec2<Unit, Space>, a: Vec2<Unit, Space>, b: Vec2<Unit, Space>, eps: f32) -> bool {
let ap = p - a;
let ab = b - a;
// Collinearity via cross product.
if ap.cross(ab).abs() > eps {
return false;
}
// Projection bounds via dot product.
let dot = ap.dot(ab);
if dot < -eps {
return false;
}
let ab_len_sq = ab.length_squared();
if dot > ab_len_sq + eps {
return false;
}
true
}