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 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228
use super::{base_math::parametric_from_point, Vector2};
use crate::core::traits::Real;
/// Holds the result of finding the intersect between two line segments.
#[derive(Debug, Copy, Clone)]
pub enum LineLineIntr<T>
where
T: Real,
{
/// No intersect, segments are parallel and not collinear.
NoIntersect,
/// There is a true intersect between the line segments.
TrueIntersect {
/// Parametric value for intersect on first segment.
seg1_t: T,
/// Parametric value for intersect on second segment.
seg2_t: T,
},
/// Segments overlap each other (are collinear) by some amount.
Overlapping {
/// Parametric value for start of coincidence along second segment.
seg2_t0: T,
/// Parametric value for end of coincidence along second segment.
seg2_t1: T,
},
/// There is an intersect between the lines but one or both of the segments must be extended.
FalseIntersect {
/// Parametric value for intersect on first segment.
seg1_t: T,
/// Parametric value for intersect on second segment.
seg2_t: T,
},
}
/// Finds the intersects between two lines segments.
///
/// This function returns the parametric solution(s) using the general line segment equation
/// `P(t) = p0 + t * (p1 - p0)`. Where `t` then goes from 0 to 1. For `t < 0` or `t > 1` the result
/// is on the same line but not within the line segment.
///
/// `epsilon` is used for fuzzy float comparisons.
///
/// # Explanation on result cases `LineLineIntr`
/// ## `NoIntersect`
/// Either of the following cases:
/// * Lines are (or almost, using `epsilon` to determine) parallel
/// * Both line segments are points and distinct from each other
/// * One line segment is a point and distinct from the other line segment
///
/// ## `TrueIntersect`
/// Either of the following cases:
/// * Line segments are not parallel and intersect at one point
/// * Both line segments are points and lie over each other (using `epsilon` for position compare)
/// * One line segment is a point and lies in other line segment (again using `epsilon`)
///
/// ## `FalseIntersect`
/// Either of the following cases:
/// * Line segments are not parallel and at least one must be extended to intersect (that is for
/// `0 <= t <= 1` for both segments there is no intersect)
///
/// ## `Overlapping`
/// Either of the following cases:
/// * The lines are collinear and overlap, the segments may fully, partially or not overlap at all
/// (determined by parametric t values returned)
///
/// # Examples
///
/// ```
/// # use cavalier_contours::core::traits::*;
/// # use cavalier_contours::core::math::*;
/// # use cavalier_contours::core::math::LineLineIntr::TrueIntersect;
/// // A line segment tangent-intersecting a circle with one of the line segments end points.
/// let v1 = Vector2::new(0.0, 0.0);
/// let v2 = Vector2::new(1.0, 0.0);
/// let u1 = Vector2::new(0.5, -1.0);
/// let u2 = Vector2::new(0.5, 1.0);
/// if let LineLineIntr::TrueIntersect {
/// seg1_t: t1,
/// seg2_t: t2,
/// } = line_line_intr(v1, v2, u1, u2, 1e-5)
/// {
/// assert_eq!(t1, 0.5);
/// assert_eq!(t2, 0.5);
/// } else {
/// unreachable!("expected true intersection between line segments");
/// }
///```
/// Line segments are defined by `v1->v2` and `u1->u2`.
/// Handles the cases where the lines may be parallel, collinear, or single points.
pub fn line_line_intr<T>(
v1: Vector2<T>,
v2: Vector2<T>,
u1: Vector2<T>,
u2: Vector2<T>,
epsilon: T,
) -> LineLineIntr<T>
where
T: Real,
{
// This implementation works by processing the segments in parametric equation form and using
// perpendicular products
// http://geomalgorithms.com/a05-_intersect-1.html
// http://mathworld.wolfram.com/PerpDotProduct.html
use LineLineIntr::*;
let v = v2 - v1;
let u = u2 - u1;
let v_pdot_u = v.perp_dot(u);
let w = v1 - u1;
let eps = epsilon;
// segment lengths are used to scale parametric t value for fuzzy comparing
// this ensures when comparing parametric values the epsilon value is applied with numbers at a
// length/position scale, e.g., a difference in parametric t value of 0.1 represents a much
// greater position difference for a segment with a length of 1,000,000 vs. a segment with a
// length of 0.01, multiplying by the length first ensures that is accounted for to use with the
// epsilon value
let seg1_length = (v2 - v1).length();
let seg2_length = (u2 - u1).length();
// threshold check here to avoid almost parallel lines resulting in very distant intersection
if !v_pdot_u.fuzzy_eq_zero_eps(eps) {
// segments not parallel or collinear
let seg1_t = u.perp_dot(w) / v_pdot_u;
let seg2_t = v.perp_dot(w) / v_pdot_u;
if !(seg1_t * seg1_length).fuzzy_in_range_eps(T::zero(), seg1_length, eps)
|| !(seg2_t * seg2_length).fuzzy_in_range_eps(T::zero(), seg2_length, eps)
{
return FalseIntersect { seg1_t, seg2_t };
}
return TrueIntersect { seg1_t, seg2_t };
}
// segments are parallel and possibly collinear
let v_pdot_w = v.perp_dot(w);
let u_pdot_w = u.perp_dot(w);
// threshold check here, we consider almost parallel lines to be parallel
if !v_pdot_w.fuzzy_eq_zero_eps(eps) || !u_pdot_w.fuzzy_eq_zero_eps(eps) {
// parallel and not collinear so no intersect
return NoIntersect;
}
// either collinear or degenerate (segments are single points)
let v_is_point = v1.fuzzy_eq_eps(v2, eps);
let u_is_point = u1.fuzzy_eq_eps(u2, eps);
if v_is_point && u_is_point {
// both segments are points
if v1.fuzzy_eq_eps(u1, eps) {
// same point
return TrueIntersect {
seg1_t: T::zero(),
seg2_t: T::zero(),
};
}
// distinct points
return NoIntersect;
}
if v_is_point {
// v is point and u is not a point
let seg2_t = parametric_from_point(u1, u2, v1, eps);
if (seg2_t * seg2_length).fuzzy_in_range_eps(T::zero(), seg2_length, eps) {
return TrueIntersect {
seg1_t: T::zero(),
seg2_t,
};
}
return NoIntersect;
}
if u_is_point {
// u is point and v is not a point
let seg1_t = parametric_from_point(v1, v2, u1, eps);
if (seg1_t * seg1_length).fuzzy_in_range_eps(T::zero(), seg1_length, eps) {
return TrueIntersect {
seg1_t,
seg2_t: T::zero(),
};
}
return NoIntersect;
}
// neither segment is a point, check if they overlap
let w2 = v2 - u1;
let (mut seg2_t0, mut seg2_t1) = if u.x.fuzzy_eq_zero_eps(eps) {
(w.y / u.y, w2.y / u.y)
} else {
(w.x / u.x, w2.x / u.x)
};
if seg2_t0 > seg2_t1 {
std::mem::swap(&mut seg2_t0, &mut seg2_t1);
}
// using threshold check here to make intersect "sticky" to prefer considering it an intersect
if !(seg2_t0 * seg2_length).fuzzy_lt_eps(seg2_length, eps)
|| !(seg2_t1 * seg2_length).fuzzy_gt_eps(T::zero(), eps)
{
return NoIntersect;
}
seg2_t0 = num_traits::real::Real::max(seg2_t0, T::zero());
seg2_t1 = num_traits::real::Real::min(seg2_t1, T::one());
if ((seg2_t1 - seg2_t0) * seg2_length).fuzzy_eq_zero_eps(eps) {
// intersect is a single point (segments line up end to end)
// determine if seg1_t is 0.0 or 1.0
let seg1_t = if v1.fuzzy_eq_eps(u1, eps) || v1.fuzzy_eq_eps(u2, eps) {
// v1 touches which is start of seg1
T::zero()
} else {
T::one()
};
return TrueIntersect {
seg1_t,
seg2_t: seg2_t0,
};
}
Overlapping { seg2_t0, seg2_t1 }
}