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
use super::{LineIntersection, LineIntersector};
use crate::kernels::{Kernel, Orientation, RobustKernel};
use crate::{BoundingRect, Contains, Intersects};
use crate::{Coord, GeoFloat, Line, Rect};
use num_traits::Zero;
/// A robust version of [LineIntersector](traits.LineIntersector).
#[derive(Clone)]
pub(crate) struct RobustLineIntersector;
impl RobustLineIntersector {
pub fn new() -> RobustLineIntersector {
RobustLineIntersector
}
}
impl<F: GeoFloat> LineIntersector<F> for RobustLineIntersector {
fn compute_intersection(&mut self, p: Line<F>, q: Line<F>) -> Option<LineIntersection<F>> {
crate::line_intersection::line_intersection(p, q)
}
}
impl RobustLineIntersector {
/// Computes the "edge distance" of an intersection point p along a segment.
///
/// The edge distance is a metric of the point along the edge.
/// The metric used is a robust and easy to compute metric function.
/// It is _not_ equivalent to the usual Euclidean metric.
/// It relies on the fact that either the x or the y ordinates of the
/// points in the edge are unique, depending on whether the edge is longer in
/// the horizontal or vertical direction.
///
/// NOTE: This function may produce incorrect distances for inputs where p is not precisely
/// on p1-p2 (E.g. p = (139,9) p1 = (139,10), p2 = (280,1) produces distance 0.0, which is
/// incorrect.
///
/// My hypothesis is that the function is safe to use for points which are the
/// result of _rounding_ points which lie on the line,
/// but not safe to use for _truncated_ points.
pub fn compute_edge_distance<F: GeoFloat>(intersection: Coord<F>, line: Line<F>) -> F {
let dx = (line.end.x - line.start.x).abs();
let dy = (line.end.y - line.start.y).abs();
let mut dist: F;
if intersection == line.start {
dist = F::zero();
} else if intersection == line.end {
if dx > dy {
dist = dx;
} else {
dist = dy;
}
} else {
let intersection_dx = (intersection.x - line.start.x).abs();
let intersection_dy = (intersection.y - line.start.y).abs();
if dx > dy {
dist = intersection_dx;
} else {
dist = intersection_dy;
}
// hack to ensure that non-endpoints always have a non-zero distance
if dist == F::zero() && intersection != line.start {
dist = intersection_dx.max(intersection_dy);
}
}
debug_assert!(
!(dist == F::zero() && intersection != line.start),
"Bad distance calculation"
);
dist
}
}