lyon_algorithms/
hit_test.rs

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 = 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}