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
|
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;
}
/* What's happening here:
*
* This algorithm creates a horizontal line for the point that should be checked. It goes
* to infinity (since infinite lines are not possible, it just goes to the maximum x value
* of all corner points). Then, the times the line crosses a polygon edge is counted. If
* the times it hit a polygon edge is uneven, it must have been inside, otherwise outside.
*
* There is an edge case however (pun not intended); When the line from the point is collinear
* to a polygon edge. it might hit this edge once and no other (it's at the top y or bottom y
* of the polygon), but may still not be inside the polygon. In this case, it's checked
* whether the point is in between the corner points of this polygon edge or not. If it is
* in between, it is still inside the polygon, otherwise outside.
*/
// Get the maximum x for the horizontal lines for "Infinity".
let mut max_x = self.corners[0].x;
for corner in self.corners.iter().skip(1) {
max_x = super::partial_max(corner.x, max_x);
}
println!("Max x is {:?}", max_x);
// The horizontally "infinite" point of the test point.
let line_to_infinity = LineSegment::new(point, Vec2::new(max_x, point.y));
// Check for intersection for all the polygon edges.
let mut num_intersects = 0;
for i in 0..self.corners.len() {
// Wrap around for the edge that returns to the start.
let j = (i + 1) % self.corners.len();
let current_edge = LineSegment::new(self.corners[i], self.corners[j]);
if LineSegment::intersect(¤t_edge, &line_to_infinity) {
/* Check for the edge case, where the point might lie right on an edge of the
* polygon.
*/
if super::triplet_orientation(current_edge.start, current_edge.end, point)
== TripletOrientation::Collinear
{
// The point is right on an edge
if current_edge.contains_collinear(point) {
return true;
}
} else {
num_intersects += 1;
}
}
}
num_intersects % 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.)));
}
}
|
