use super::convert::{Vertex, VertexSource};
use super::outline::{Contour, Outline, Stroke};
use super::{Path, PathCode};
use crate::{Affine2D, Point};
fn crossings<I: VertexSource>(points: &[Point], path: &mut I) -> Vec<bool> {
let n = points.len();
let mut inside = vec![false; n];
let mut yflag0 = vec![false; n];
let mut subpath = vec![false; n];
let finite = |p: &Point| p.is_finite();
path.rewind();
let mut pending_move: Option<Point> = None;
loop {
let start = match pending_move.take() {
Some(p) => p,
None => match path.next() {
None => break,
Some(v) if v.code == PathCode::ClosePoly => continue,
Some(v) => v.point,
},
};
let (mut v0, mut v1) = (start, start);
for (i, p) in points.iter().enumerate() {
if p.y.is_finite() {
yflag0[i] = v0.y >= p.y;
subpath[i] = false;
}
}
let mut stream_ended = false;
loop {
let (next, subpath_ended) = match path.next() {
None => {
stream_ended = true;
(start, true)
}
Some(Vertex {
code: PathCode::ClosePoly,
..
}) => (start, true),
Some(Vertex {
code: PathCode::MoveTo,
point,
}) => {
pending_move = Some(point);
break;
}
Some(v) => (v.point, false),
};
for (i, p) in points.iter().enumerate().filter(|(_, p)| finite(p)) {
let yflag1 = v1.y >= p.y;
if yflag0[i] != yflag1 && crosses(v0, v1, *p, yflag1) {
subpath[i] = !subpath[i];
}
yflag0[i] = yflag1;
}
v0 = v1;
v1 = next;
if subpath_ended {
break;
}
}
let mut all_inside = true;
for (i, p) in points.iter().enumerate().filter(|(_, p)| finite(p)) {
let yflag1 = v1.y >= p.y;
if yflag0[i] != yflag1 && crosses(v0, v1, *p, yflag1) {
subpath[i] = !subpath[i];
}
inside[i] |= subpath[i];
all_inside &= inside[i];
}
if all_inside || stream_ended {
break;
}
}
inside
}
fn crosses(v0: Point, v1: Point, t: Point, yflag1: bool) -> bool {
((v1.y - t.y) * (v0.x - v1.x) >= (v1.x - t.x) * (v0.y - v1.y)) == yflag1
}
impl Path {
fn containment_stream(&self, transform: &Affine2D) -> impl VertexSource + '_ {
self.iter_vertices()
.transform(*transform)
.remove_nans(true, self.codes.is_some())
.flatten_curves(true)
}
pub fn contains_point(&self, point: Point, transform: Option<&Affine2D>, radius: f64) -> bool {
self.contains_points(&[point], transform, radius)[0]
}
pub fn contains_points(
&self,
points: &[Point],
transform: Option<&Affine2D>,
radius: f64,
) -> Vec<bool> {
if self.len() < 3 {
return vec![false; points.len()];
}
let stream = self.containment_stream(transform.unwrap_or(&Affine2D::IDENTITY));
if radius == 0.0 {
let mut stream = stream;
crossings(points, &mut stream)
} else {
crossings(points, &mut Outline::new(stream, Contour::new(radius)))
}
}
pub fn contains_path(&self, other: &Self, transform: Option<&Affine2D>) -> bool {
if self.len() < 3 {
return false;
}
let points: Vec<Point> = other
.containment_stream(transform.unwrap_or(&Affine2D::IDENTITY))
.map(|v| v.point)
.collect();
self.contains_points(&points, None, 0.0)
.into_iter()
.all(|inside| inside)
}
pub fn stroke_contains_point(&self, point: Point, transform: &Affine2D, radius: f64) -> bool {
let stream = self.containment_stream(transform);
crossings(
&[point],
&mut Outline::new(stream, Stroke::new(radius * 2.0)),
)[0]
}
}
#[cfg(test)]
mod tests {
use super::*;
fn p(x: f64, y: f64) -> Point {
Point::new(x, y)
}
fn clockwise_square() -> Path {
Path::polygon([p(0.0, 0.0), p(0.0, 1.0), p(1.0, 1.0), p(1.0, 0.0)])
}
#[test]
fn crossing_rule() {
let sq = Path::unit_rectangle();
assert_eq!(
sq.contains_points(&[p(0.5, 0.5), p(1.5, 0.5), p(f64::NAN, 0.5)], None, 0.0),
vec![true, false, false]
);
assert!(
!Path::polyline(vec![p(0.0, 0.0), p(1.0, 1.0)]).contains_point(p(0.5, 0.5), None, 0.0)
);
}
#[test]
fn radius_sign_follows_orientation() {
let outside = p(1.1, 0.5);
let inside = p(0.9, 0.5);
assert!(Path::unit_rectangle().contains_point(outside, None, 0.5));
assert!(!Path::unit_rectangle().contains_point(inside, None, -0.5));
assert!(!clockwise_square().contains_point(inside, None, 0.5));
assert!(clockwise_square().contains_point(outside, None, -0.5));
}
#[test]
fn holes_do_not_exclude_points() {
let donut = Path::compound([
&Path::polygon([p(0.0, 0.0), p(4.0, 0.0), p(4.0, 4.0), p(0.0, 4.0)]),
&Path::polygon([p(1.0, 1.0), p(1.0, 3.0), p(3.0, 3.0), p(3.0, 1.0)]),
]);
assert!(donut.contains_point(p(2.0, 2.0), None, 0.0));
}
#[test]
fn subpaths_ended_by_a_move_stay_open() {
let path = Path::new(
vec![
p(0.0, 0.0),
p(2.0, 0.0),
p(2.0, 2.0),
p(0.0, 2.0),
p(5.0, 5.0),
p(6.0, 5.0),
],
vec![
PathCode::MoveTo,
PathCode::LineTo,
PathCode::LineTo,
PathCode::LineTo,
PathCode::MoveTo,
PathCode::LineTo,
],
)
.expect("valid");
assert!(path.contains_point(p(-1.0, 1.0), None, 0.0));
}
#[test]
fn containment_of_paths() {
let small = Path::polygon([p(0.25, 0.25), p(0.75, 0.25), p(0.75, 0.75), p(0.25, 0.75)]);
assert!(Path::unit_rectangle().contains_path(&small, None));
assert!(!small.contains_path(&Path::unit_rectangle(), None));
let shifted = Affine2D::translation(2.0, 0.0);
assert!(!Path::unit_rectangle().contains_path(&small, Some(&shifted)));
assert!(Path::unit_rectangle().contains_path(&Path::default(), None));
}
#[test]
fn stroke_hit_test() {
let line = Path::polyline(vec![p(0.0, 0.0), p(10.0, 0.0)]);
let id = Affine2D::IDENTITY;
assert!(line.stroke_contains_point(p(5.0, 0.4), &id, 0.5));
assert!(!line.stroke_contains_point(p(5.0, 0.6), &id, 0.5));
assert!(!line.stroke_contains_point(p(10.2, 0.0), &id, 0.5));
}
}