1//! Determine whether a point is inside a path.
2
3use crate::geom::{CubicBezierSegment, LineSegment, QuadraticBezierSegment};
4use crate::math::Point;
5use crate::path::{FillRule, PathEvent};
6
7/// Returns whether the point is inside the path.
8pub fn hit_test_path<Iter>(point: &Point, path: Iter, fill_rule: FillRule, tolerance: f32) -> bool
9where
10 Iter: IntoIterator<Item = PathEvent>,
11{
12 let winding: i32 = path_winding_number_at_position(point, path, tolerance);
13
14 match fill_rule {
15 FillRule::EvenOdd => winding % 2 != 0,
16 FillRule::NonZero => winding != 0,
17 }
18}
19
20/// Compute the winding number of a given position with respect to the path.
21pub fn path_winding_number_at_position<Iter>(point: &Point, path: Iter, tolerance: f32) -> i32
22where
23 Iter: IntoIterator<Item = PathEvent>,
24{
25 // Loop over the edges and compute the winding number at that point by accumulating the
26 // winding of all edges intersecting the horizontal line passing through our point which are
27 // left of it.
28 let mut winding = 0;
29
30 for evt in path {
31 match evt {
32 PathEvent::Begin { .. } => {}
33 PathEvent::Line { from, to } => {
34 test_segment(
35 *point,
36 &LineSegment { from, to },
37 &mut winding,
38 );
39 }
40 PathEvent::End { last, first, .. } => {
41 test_segment(
42 *point,
43 &LineSegment {
44 from: last,
45 to: first,
46 },
47 &mut winding,
48 );
49 }
50 PathEvent::Quadratic { from, ctrl, to } => {
51 let segment = QuadraticBezierSegment { from, ctrl, to };
52 let (min, max) = segment.fast_bounding_range_y();
53 if min > point.y || max < point.y {
54 continue;
55 }
56 segment.for_each_flattened(tolerance, &mut |line| {
57 test_segment(*point, line, &mut winding);
58 });
59 }
60 PathEvent::Cubic {
61 from,
62 ctrl1,
63 ctrl2,
64 to,
65 } => {
66 let segment = CubicBezierSegment {
67 from,
68 ctrl1,
69 ctrl2,
70 to,
71 };
72 let (min, max) = segment.fast_bounding_range_y();
73 if min > point.y || max < point.y {
74 continue;
75 }
76 segment.for_each_flattened(tolerance, &mut |line| {
77 test_segment(*point, line, &mut winding);
78 });
79 }
80 }
81 }
82
83 winding
84}
85
86fn test_segment(
87 point: Point,
88 segment: &LineSegment<f32>,
89 winding: &mut i32,
90) {
91 let y0 = segment.from.y;
92 let y1 = segment.to.y;
93 let min_y = f32::min(y0, y1);
94 let max_y = f32::max(y0, y1);
95
96 if min_y > point.y
97 || max_y <= point.y
98 || f32::min(segment.from.x, segment.to.x) > point.x
99 {
100 return;
101 }
102
103 if y0 == y1 {
104 return;
105 }
106
107 let d = y1 - y0;
108
109
110 let t = (point.y - y0) / d;
111 let x = segment.sample(t).x;
112
113 if x > point.x {
114 return;
115 }
116
117 let w = if d > 0.0 { 1 } else { -1 };
118
119 *winding += w;
120}
121
122#[test]
123fn test_hit_test() {
124 use crate::math::point;
125 use crate::path::Path;
126
127 let mut builder = Path::builder();
128 builder.begin(point(0.0, 0.0));
129 builder.line_to(point(1.0, 0.0));
130 builder.line_to(point(1.0, 1.0));
131 builder.line_to(point(0.0, 1.0));
132 builder.end(true);
133 builder.begin(point(0.25, 0.25));
134 builder.line_to(point(0.75, 0.25));
135 builder.line_to(point(0.75, 0.75));
136 builder.line_to(point(0.20, 0.75));
137 builder.end(true);
138 let path = builder.build();
139
140 assert!(!hit_test_path(
141 &point(-1.0, 0.5),
142 path.iter(),
143 FillRule::EvenOdd,
144 0.1
145 ));
146 assert!(!hit_test_path(
147 &point(2.0, 0.5),
148 path.iter(),
149 FillRule::EvenOdd,
150 0.1
151 ));
152 std::println!(
153 "winding {:?}",
154 path_winding_number_at_position(&point(2.0, 0.0), path.iter(), 0.1)
155 );
156 assert!(!hit_test_path(
157 &point(2.0, 0.0),
158 path.iter(),
159 FillRule::EvenOdd,
160 0.1
161 ));
162 assert!(!hit_test_path(
163 &point(0.5, -1.0),
164 path.iter(),
165 FillRule::EvenOdd,
166 0.1
167 ));
168 assert!(!hit_test_path(
169 &point(0.5, 2.0),
170 path.iter(),
171 FillRule::EvenOdd,
172 0.1
173 ));
174
175 assert!(!hit_test_path(
176 &point(0.5, 0.5),
177 path.iter(),
178 FillRule::EvenOdd,
179 0.1
180 ));
181 assert!(hit_test_path(
182 &point(0.5, 0.5),
183 path.iter(),
184 FillRule::NonZero,
185 0.1
186 ));
187 assert!(hit_test_path(
188 &point(0.2, 0.5),
189 path.iter(),
190 FillRule::EvenOdd,
191 0.1
192 ));
193 assert!(hit_test_path(
194 &point(0.8, 0.5),
195 path.iter(),
196 FillRule::EvenOdd,
197 0.1
198 ));
199}
200
201#[test]
202fn hit_test_point_aligned() {
203 use crate::math::point;
204 use crate::path::polygon::Polygon;
205
206 let poly = Polygon {
207 points: &[
208 point(-10.0, 10.0),
209 point(10.0, 10.0),
210 point(10.0, 5.0),
211 point(10.0, -10.0),
212 point(-10.0, -10.0),
213 ],
214 closed: true,
215 };
216
217 assert!(hit_test_path(
218 &point(0.0, 5.0),
219 poly.path_events(),
220 FillRule::NonZero,
221 0.1
222 ));
223 assert!(!hit_test_path(
224 &point(15.0, 5.0),
225 poly.path_events(),
226 FillRule::NonZero,
227 0.1
228 ));
229}
230
231#[test]
232fn hit_test_double_square() {
233 use crate::math::point;
234 use crate::path::Path;
235
236 let mut builder = Path::builder();
237 builder.begin(point(0.0, 0.0));
238 builder.line_to(point(1.0, 0.0));
239 builder.line_to(point(1.0, 1.0));
240 builder.line_to(point(0.0, 1.0));
241 builder.line_to(point(0.0, 0.0));
242 builder.line_to(point(1.0, 0.0));
243 builder.line_to(point(1.0, 1.0));
244 builder.line_to(point(0.0, 1.0));
245 builder.end(true);
246 let path = builder.build();
247
248 assert_eq!(
249 path_winding_number_at_position(&point(0.5, 0.5), &path, 0.1),
250 -2
251 );
252}
253
254#[test]
255fn hit_test_double_count() {
256 use crate::math::point;
257 use crate::path::Path;
258
259 let mut builder = Path::builder();
260 builder.begin(point(0.0, 0.0));
261 builder.line_to(point(0.0, 1.0));
262 builder.line_to(point(1.0, 1.0));
263 builder.line_to(point(1.0, 2.0));
264 builder.line_to(point(1.0, 3.0));
265 builder.line_to(point(3.0, 3.0));
266 builder.line_to(point(3.0, 0.0));
267 builder.end(true);
268 let path = builder.build();
269
270 assert_eq!(
271 path_winding_number_at_position(&point(2.0, 1.0), &path, 0.1),
272 1
273 );
274 assert_eq!(
275 path_winding_number_at_position(&point(2.0, 2.0), &path, 0.1),
276 1
277 );
278}
279
280#[test]
281fn issue_882() {
282 use crate::math::point;
283 use crate::path::Path;
284 let mut pb = Path::builder();
285 pb.begin(point(0.0, 50.0));
286 pb.line_to(point(50.0, 50.0));
287 pb.line_to(point(50.0, 0.0));
288 pb.line_to(point(100.0, 0.0));
289 pb.line_to(point(100.0, 100.0));
290 pb.line_to(point(0.0, 100.0));
291 pb.line_to(point(0.0, 50.0));
292 pb.end(true);
293 let p = pb.build();
294
295 let x = point(55.0, 50.0);
296
297 assert!(hit_test_path(&x, p.iter(), FillRule::EvenOdd, 1.0))
298}