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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
|
use super::{LineSegment, TripletOrientation, Vec2};
use alga::general::{ClosedMul, ClosedSub};
use nalgebra::Scalar;
use num_traits::Zero;
pub struct Polygon<T: Scalar + Copy> {
pub corners: Vec<Vec2<T>>,
}
impl<T: Scalar + Copy> Polygon<T> {
pub fn new(corners: Vec<Vec2<T>>) -> Self {
Self { corners }
}
/// Check whether a point is inside a polygon or not. If a point lies on an edge, it also
/// counts as inside the polygon.
pub fn contains(&self, point: Vec2<T>) -> bool
where
T: Scalar + Copy + ClosedSub + ClosedMul + PartialOrd + Zero,
{
// Must be at least a triangle to contain anything
if self.corners.len() < 3 {
return false;
}
// Get the maximum x for the horizontal lines for "Infinity".
let mut max_x = self.corners[0].x;
for corner in self.corners.iter() {
/* Handle the edge case where the point is on a polygon corner, so we don't have to
* worry about it later.
*/
if point == *corner {
return true;
}
max_x = super::partial_max(corner.x, max_x);
}
// The horizontally "infinite" point of the test point.
let line_to_infinity = LineSegment::new(point, Vec2::new(max_x, point.y));
// The number of times the point line to infinity pierced through the polygon hull.
let mut num_pierced = 0;
/* Find edges that should be ignored. These are all edges, where the straight line passes
* right through a corner of the edge. It might still be counted as piercing the polygon,
* if the next corners lie below and the previous corner lies above the line or vice
* versa, but not if both points lie above it or below. The corners are exempted from the
* run through the edges. The edges that should be ignored are saved by their starting
* corner's index.
*/
let mut ignore_edge = vec![false; self.corners.len()];
for i in 0..self.corners.len() {
if point.y == self.corners[i].y {
// The previous corner index
let prev_i = (i + self.corners.len() - 1) % self.corners.len();
// Make sure the edges containing this corner will be ignored.
ignore_edge[i] = true;
ignore_edge[prev_i] = true;
/* Make sure we don't count a pierce double because of consecutive collinear
* points. (Although the polygon really should be sanitised, but you know)
*/
if self.corners[prev_i].y == point.y {
continue;
}
/* Ignore coming collinear points, since we are only interested in when the
* y-coordinate finally changes
*/
let mut j = (i + 1) % self.corners.len();
while i != j {
if self.corners[j].y != point.y {
if (self.corners[prev_i].y < point.y && self.corners[j].y > point.y)
|| (self.corners[prev_i].y > point.y && self.corners[j].y < point.y)
{
/* Only count as pierced when it would be right of the point, otherwise
* it would be like checking to the left of the line that is drawn to
* infinity, which is incorrect
*/
if self.corners[i].x >= point.x {
//println!("Pierced through corner {:?}", self.corners[i]);
num_pierced += 1;
}
}
break;
}
j = (j + 1) % self.corners.len();
}
}
}
// Find the points where the x-line may actually collide with a proper line.. ^^
for (i, edge_start) in self.corners.iter().enumerate() {
if ignore_edge[i] {
continue;
}
let next = (i + 1) % self.corners.len();
let current_edge = LineSegment::new(*edge_start, self.corners[next]);
if LineSegment::intersect(¤t_edge, &line_to_infinity) {
num_pierced += 1;
//println!("Pierced through edge: {:?}", ¤t_edge);
/* Check for the edge case, where the point might lie right on an edge of the
* polygon.
*/
if super::triplet_orientation(*edge_start, current_edge.end, point)
== TripletOrientation::Collinear
{
// The point should be right on an edge.
// XXX: Should this not just be an assertion? It seems that this always has to
// be the case when reaching this part.
return current_edge.contains_collinear(point);
}
}
}
//println!("Num pierced is: {}", num_pierced);
num_pierced % 2 == 1
}
/// Join this polygon with another, ensuring the area of the two stays the same, minus the
/// overlap.
///
/// # Panics
/// If the two polygons do not intersect, it is impossible to unite them into a single polygon,
/// in which case this function is bound to fail.
// TODO: Create a function that only tries to join the polygons.
pub fn unite(&mut self, mut _other: Polygon<T>) {
unimplemented!()
}
}
#[cfg(test)]
mod test {
use super::*;
#[test]
fn polygon_contains() {
let polygon = Polygon::new(vec![
Vec2::new(0., 0.),
Vec2::new(-1., 1.),
Vec2::new(0., 2.),
Vec2::new(1., 3.),
Vec2::new(3., 1.5),
Vec2::new(2., 0.),
Vec2::new(1., 1.),
]);
assert!(!polygon.contains(Vec2::new(1., -2.)));
assert!(!polygon.contains(Vec2::new(-1., 0.5)));
assert!(polygon.contains(Vec2::new(0., 0.5)));
assert!(polygon.contains(Vec2::new(0.5, 1.)));
assert!(polygon.contains(Vec2::new(0.5, 1.5)));
assert!(!polygon.contains(Vec2::new(-2., 1.9)));
assert!(!polygon.contains(Vec2::new(0., 3.)));
assert!(polygon.contains(Vec2::new(1., 3.)));
}
}
|
