use super::Point;
use crate::encoding_context::EncodingContext;
use std::ops::Range;
#[derive(Default)]
pub(crate) struct Segments {
pub(crate) x: [f32; 4],
pub(crate) y: [f32; 4],
pub(crate) dx: [f32; 4],
pub(crate) dy: [f32; 4],
pub(crate) len2: [f32; 4],
}
pub(super) struct Polyline {
blocks: Vec<Segments>,
len: usize,
distance_blocks: SegmentDistanceFn,
}
impl Polyline {
pub(super) fn new(ctx: &EncodingContext, points: &[Point<f32>]) -> Self {
let len = points.len().saturating_sub(1);
let mut blocks = Vec::<Segments>::with_capacity(len.div_ceil(4));
for (i, &[a, b]) in points.array_windows::<2>().enumerate() {
if i % 4 == 0 {
blocks.push(Segments::default());
}
let block = blocks.last_mut().unwrap();
let lane = i % 4;
let (dx, dy) = (b.x - a.x, b.y - a.y);
block.x[lane] = a.x;
block.y[lane] = a.y;
block.dx[lane] = dx;
block.dy[lane] = dy;
block.len2[lane] = dx * dx + dy * dy;
}
Self {
blocks,
len,
distance_blocks: ctx.spline_distance,
}
}
pub(super) fn distance(&self, p: Point<f32>) -> f32 {
self.distance_range(p, 0..self.len)
}
pub(super) fn distance_range(&self, p: Point<f32>, segments: Range<usize>) -> f32 {
assert!(segments.start <= segments.end && segments.end <= self.len);
let mut best = f32::INFINITY;
let prefix = segments.start.next_multiple_of(4).min(segments.end);
for i in segments.start..prefix {
best = best.min(self.scalar(p, i));
}
let end = segments.end / 4 * 4;
if prefix < end {
let blocks = &self.blocks[prefix / 4..end / 4];
best = best.min((self.distance_blocks)(p, blocks));
}
for i in prefix.max(end)..segments.end {
best = best.min(self.scalar(p, i));
}
best
}
fn scalar(&self, p: Point<f32>, index: usize) -> f32 {
self.blocks[index / 4].distance(p, index % 4)
}
}
impl Segments {
#[inline]
fn distance(&self, p: Point<f32>, lane: usize) -> f32 {
let (x, y, dx, dy, len2) = (
self.x[lane],
self.y[lane],
self.dx[lane],
self.dy[lane],
self.len2[lane],
);
let t = if len2 > 1e-12 {
(((p.x - x) * dx + (p.y - y) * dy) / len2).clamp(0.0, 1.0)
} else {
0.0
};
let (ex, ey) = (p.x - (x + t * dx), p.y - (y + t * dy));
ex * ex + ey * ey
}
}
pub(crate) type SegmentDistanceFn = fn(Point<f32>, &[Segments]) -> f32;
pub(crate) fn select_segment_distance_fn() -> SegmentDistanceFn {
#[cfg(all(target_arch = "aarch64", feature = "neon"))]
return |point, blocks| unsafe { crate::neon::spline_distance_neon(point, blocks) };
#[cfg(all(target_arch = "x86_64", feature = "avx"))]
if std::is_x86_feature_detected!("avx2") && std::is_x86_feature_detected!("fma") {
return |point, blocks| unsafe { crate::avx::spline_distance_avx2(point, blocks) };
}
#[allow(unreachable_code)]
segment_distance_scalar
}
fn segment_distance_scalar(p: Point<f32>, blocks: &[Segments]) -> f32 {
let mut best = f32::INFINITY;
for block in blocks {
for lane in 0..4 {
best = best.min(block.distance(p, lane));
}
}
best
}
#[cfg(test)]
mod tests {
use super::*;
fn reference(p: Point<f32>, points: &[Point<f32>]) -> f32 {
let mut best = f32::INFINITY;
for &[a, b] in points.array_windows::<2>() {
let (dx, dy) = (b.x - a.x, b.y - a.y);
let len2 = dx * dx + dy * dy;
let t = if len2 > 1e-12 {
(((p.x - a.x) * dx + (p.y - a.y) * dy) / len2).clamp(0.0, 1.0)
} else {
0.0
};
let (ex, ey) = (p.x - (a.x + t * dx), p.y - (a.y + t * dy));
best = best.min(ex * ex + ey * ey);
}
best
}
#[test]
fn prepared_distances_match_segment_reference_for_every_alignment() {
let kernels = EncodingContext::default();
let points: Vec<_> = (0..if cfg!(miri) { 17 } else { 71 })
.map(|i| {
let i = i / 2;
Point::new((i * 19 % 31) as f32 * 0.7, (i * 7 % 13) as f32 * 0.1234)
})
.collect();
for (scale, offset) in [(1.0, 0.0), (1e-7, 0.0), (1000.0, 1e7)] {
let points: Vec<_> = points
.iter()
.map(|p| Point::new(p.x * scale + offset, p.y * scale + offset))
.collect();
let line = Polyline::new(&kernels, &points);
for p in [
Point::new(-1.0, -0.0),
Point::new(14.3 * scale + offset, 8.9 * scale + offset),
points[24.min(points.len() - 1)],
Point::new(1e7, -1e5),
] {
for start in 0..points.len() {
for end in start..points.len() {
assert_eq!(
line.distance_range(p, start..end).to_bits(),
reference(p, &points[start..=end]).to_bits(),
"scale {scale}, offset {offset}, range {start}..{end}"
);
}
}
}
}
assert_eq!(
Polyline::new(&kernels, &[]).distance(points[0]),
f32::INFINITY
);
}
}