logo
 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
73
74

use super::{LineIntersection, LineIntersector};
use crate::algorithm::kernels::{Kernel, Orientation, RobustKernel};
use crate::bounding_rect::BoundingRect;
use crate::contains::Contains;
use crate::intersects::Intersects;
use crate::num_traits::Zero;
use crate::{Coordinate, GeoFloat, Line, Rect};

/// 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::algorithm::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: Coordinate<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
    }
}