Skip to content

Commit

Permalink
Merge #246
Browse files Browse the repository at this point in the history 
246: Introduce Line::{dx, dy, slope, determinant} methods. r=urschrei a=frewsxcv



Co-authored-by: Corey Farwell <coreyf@rwell.org>
  • Loading branch information
@bors @frewsxcv
bors[bot] and frewsxcv committed Jun 4, 2018
2 parents fbcabaa + f57665f commit 7a00054
Show file tree
Hide file tree
Showing 8 changed files with 90 additions and 53 deletions.
47 changes: 47 additions & 0 deletions geo-types/src/line.rs
View file
Original file line number Diff line number Diff line change
Expand Up @@ -36,6 +36,53 @@ where
end
}
}

/// Calculate the difference in ‘x’ components (Δx).
///
/// Equivalent to:
///
/// ```txt
/// line.end.x() - line.start.x()
/// ```
pub fn dx(&self) -> T {
self.end.x() - self.start.x()
}

/// Calculate the difference in ‘y’ components (Δy).
///
/// Equivalent to:
///
/// ```txt
/// line.end.y() - line.start.y()
/// ```
pub fn dy(&self) -> T {
self.end.y() - self.start.y()
}

/// Calculate the slope (Δy/Δx).
///
/// Equivalent to:
///
/// ```txt
/// line.dy() / line.dx()
/// ```
pub fn slope(&self) -> T {
self.dy() / self.dx()
}

/// Calculate the [determinant] of the line.
///
/// Equivalent to:
///
/// ```txt
/// line.start.x() * line.end.y() -
/// line.start.y() * line.end.x()
/// ```
///
/// [determinant]: https://en.wikipedia.org/wiki/Determinant
pub fn determinant(&self) -> T {
self.start.x() * self.end.y() - self.start.y() * self.end.x()
}
}

#[cfg(feature = "spade")]
Expand Down
8 changes: 4 additions & 4 deletions geo/src/algorithm/centroid.rs
View file
Original file line number Diff line number Diff line change
Expand Up @@ -37,7 +37,7 @@ where
}
let mut tmp = T::zero();
for line in linestring.lines() {
tmp = tmp + (line.start.x() * line.end.y() - line.end.x() * line.start.y());
tmp = tmp + line.determinant();
}
tmp / (T::one() + T::one())
}
Expand All @@ -55,7 +55,7 @@ where
let mut sum_x = T::zero();
let mut sum_y = T::zero();
for line in poly_ext.lines() {
let tmp = line.start.x() * line.end.y() - line.end.x() * line.start.y();
let tmp = line.determinant();
sum_x = sum_x + ((line.end.x() + line.start.x()) * tmp);
sum_y = sum_y + ((line.end.y() + line.start.y()) * tmp);
}
Expand All @@ -71,8 +71,8 @@ where

fn centroid(&self) -> Self::Output {
let two = T::one() + T::one();
let x = (self.start.x() + self.end.x()) / two;
let y = (self.start.y() + self.end.y()) / two;
let x = self.start.x() + self.dx() / two;
let y = self.start.y() + self.dy() / two;
Point::new(x, y)
}
}
Expand Down
4 changes: 2 additions & 2 deletions geo/src/algorithm/euclidean_distance.rs
View file
Original file line number Diff line number Diff line change
Expand Up @@ -4,6 +4,7 @@ use algorithm::polygon_distance_fast_path::*;
use num_traits::float::FloatConst;
use num_traits::{Float, Signed, ToPrimitive};
use {Line, LineString, MultiLineString, MultiPoint, MultiPolygon, Point, Polygon};
use algorithm::euclidean_length::EuclideanLength;

use spade::rtree::RTree;
use spade::SpadeFloat;
Expand Down Expand Up @@ -101,8 +102,7 @@ where
{
/// Minimum distance between two Points
fn euclidean_distance(&self, p: &Point<T>) -> T {
let (dx, dy) = (self.x() - p.x(), self.y() - p.y());
dx.hypot(dy)
Line::new(*self, *p).euclidean_length()
}
}

Expand Down
3 changes: 1 addition & 2 deletions geo/src/algorithm/euclidean_length.rs
View file
Original file line number Diff line number Diff line change
@@ -1,7 +1,6 @@
use num_traits::Float;

use ::{Line, LineString, MultiLineString};
use algorithm::euclidean_distance::EuclideanDistance;

/// Calculation of the length
Expand Down Expand Up @@ -30,7 +29,7 @@ where
T: Float,
{
fn euclidean_length(&self) -> T {
self.start.euclidean_distance(&self.end)
self.dx().hypot(self.dy())
}
}

Expand Down
35 changes: 15 additions & 20 deletions geo/src/algorithm/intersects.rs
View file
Original file line number Diff line number Diff line change
Expand Up @@ -29,17 +29,15 @@ where
T: Float,
{
fn intersects(&self, p: &Point<T>) -> bool {
let dx = self.end.x() - self.start.x();
let dy = self.end.y() - self.start.y();
let tx = if dx == T::zero() {
let tx = if self.dx() == T::zero() {
None
} else {
Some((p.x() - self.start.x()) / dx)
Some((p.x() - self.start.x()) / self.dx())
};
let ty = if dy == T::zero() {
let ty = if self.dy() == T::zero() {
None
} else {
Some((p.y() - self.start.y()) / dy)
Some((p.y() - self.start.y()) / self.dy())
};
match (tx, ty) {
(None, None) => {
Expand Down Expand Up @@ -78,14 +76,12 @@ where
fn intersects(&self, line: &Line<T>) -> bool {
// Using Cramer's Rule:
// https://en.wikipedia.org/wiki/Intersection_%28Euclidean_geometry%29#Two_line_segments
let (x1, y1, x2, y2) = (self.start.x(), self.start.y(), self.end.x(), self.end.y());
let (x3, y3, x4, y4) = (line.start.x(), line.start.y(), line.end.x(), line.end.y());
let a1 = x2 - x1;
let a2 = y2 - y1;
let b1 = x3 - x4; // == -(x4 - x3)
let b2 = y3 - y4; // == -(y4 - y3)
let c1 = x3 - x1;
let c2 = y3 - y1;
let a1 = self.dx();
let a2 = self.dy();
let b1 = -line.dx();
let b2 = -line.dy();
let c1 = line.start.x() - self.start.x();
let c2 = line.start.y() - self.start.y();

let d = a1 * b2 - a2 * b1;
if d == T::zero() {
Expand Down Expand Up @@ -149,15 +145,14 @@ where
}
for a in self.lines() {
for b in linestring.lines() {
let u_b = (b.end.y() - b.start.y()) * (a.end.x() - a.start.x())
- (b.end.x() - b.start.x()) * (a.end.y() - a.start.y());
let u_b = b.dy() * a.dx() - b.dx() * a.dy();
if u_b == T::zero() {
continue;
}
let ua_t = (b.end.x() - b.start.x()) * (a.start.y() - b.start.y())
- (b.end.y() - b.start.y()) * (a.start.x() - b.start.x());
let ub_t = (a.end.x() - a.start.x()) * (a.start.y() - b.start.y())
- (a.end.y() - a.start.y()) * (a.start.x() - b.start.x());
let ua_t = b.dx() * (a.start.y() - b.start.y())
- b.dy() * (a.start.x() - b.start.x());
let ub_t = a.dx() * (a.start.y() - b.start.y())
- a.dy() * (a.start.x() - b.start.x());
let u_a = ua_t / u_b;
let u_b = ub_t / u_b;
if (T::zero() <= u_a) && (u_a <= T::one()) && (T::zero() <= u_b)
Expand Down
42 changes: 19 additions & 23 deletions geo/src/algorithm/polygon_distance_fast_path.rs
View file
Original file line number Diff line number Diff line change
Expand Up @@ -139,7 +139,7 @@ where
if pprev.x() > p.x() {
if pprev.y() >= p.y() && pnext.y() >= p.y() {
if *slope > T::zero() {
slope_prev = (pprev.y() - p.y()) / (pprev.x() - p.x());
slope_prev = Line::new(*p, pprev).slope();
if clockwise && *slope <= slope_prev || !clockwise && *slope >= slope_prev {
cos = -cos;
sin = -sin;
Expand All @@ -156,8 +156,8 @@ where
sin = -sin;
}
} else {
slope_prev = (pprev.y() - p.y()) / (pprev.x() - p.x());
slope_next = (pnext.y() - p.y()) / (pnext.x() - p.x());
slope_prev = Line::new(*p, pprev).slope();
slope_next = Line::new(*p, pnext).slope();
if clockwise {
if *slope <= slope_prev {
cos = -cos;
Expand Down Expand Up @@ -192,8 +192,8 @@ where
sin = -sin;
}
} else {
slope_prev = (p.y() - pprev.y()) / (p.x() - pprev.x());
slope_next = (p.y() - pnext.y()) / (p.x() - pnext.x());
slope_prev = Line::new(*p, pprev).slope();
slope_next = Line::new(*p, pnext).slope();
if clockwise {
if *slope <= slope_prev {
sin = -sin;
Expand All @@ -208,7 +208,7 @@ where
}
} else if pprev.y() <= p.y() && pnext.y() <= p.y() {
if *slope > T::zero() {
slope_next = (p.y() - pnext.y()) / (p.x() - pnext.x());
slope_next = Line::new(*p, pnext).slope();
if *slope >= slope_next {
cos = -cos;
sin = -sin;
Expand Down Expand Up @@ -274,9 +274,9 @@ where
let slope = if vertical || p.y() == u.y() {
T::zero()
} else if u.x() > p.x() {
(u.y() - p.y()) / (u.x() - p.x())
Line::new(*p, *u).slope()
} else {
(p.y() - u.y()) / (p.x() - u.x())
Line::new(*u, *p).slope()
};
let upx;
let upy;
Expand Down Expand Up @@ -402,9 +402,9 @@ fn triangle_area<T>(a: &Point<T>, b: &Point<T>, c: &Point<T>) -> T
where
T: Float,
{
(T::from(0.5).unwrap()
* (a.x() * b.y() - a.y() * b.x() + a.y() * c.x() - a.x() * c.y() + b.x() * c.y()
- c.x() * b.y()))
(Line::new(*a, *b).determinant() +
Line::new(*b, *c).determinant() +
Line::new(*c, *a).determinant()) / (T::one() + T::one())
}

/// Does abc turn left?
Expand Down Expand Up @@ -491,13 +491,11 @@ where
}
false => {
state.vertical = false;
if state.p1.x() > state.p1next.x() {
state.slope =
(state.p1.y() - state.p1next.y()) / (state.p1.x() - state.p1next.x());
state.slope = if state.p1.x() > state.p1next.x() {
Line::new(state.p1next, state.p1).slope()
} else {
state.slope =
(state.p1next.y() - state.p1.y()) / (state.p1next.x() - state.p1.x());
}
Line::new(state.p1, state.p1next).slope()
};
}
}
}
Expand All @@ -510,13 +508,11 @@ where
}
false => {
state.vertical = false;
if state.q2.x() > state.q2next.x() {
state.slope =
(state.q2.y() - state.q2next.y()) / (state.q2.x() - state.q2next.x());
state.slope = if state.q2.x() > state.q2next.x() {
Line::new(state.q2next, state.q2).slope()
} else {
state.slope =
(state.q2next.y() - state.q2.y()) / (state.q2next.x() - state.q2.x());
}
Line::new(state.q2, state.q2next).slope()
};
}
}
}
Expand Down
2 changes: 1 addition & 1 deletion geo/src/algorithm/simplify.rs
View file
Original file line number Diff line number Diff line change
@@ -1,5 +1,5 @@
use num_traits::Float;
use ::{LineString, MultiLineString, MultiPolygon, Point, Polygon};
use ::{LineString, MultiLineString, MultiPolygon, Point, Polygon, Line};
use algorithm::euclidean_distance::EuclideanDistance;

// perpendicular distance from a point to a line
Expand Down
2 changes: 1 addition & 1 deletion geo/src/algorithm/winding_order.rs
View file
Original file line number Diff line number Diff line change
Expand Up @@ -8,7 +8,7 @@ pub(crate) fn twice_signed_ring_area<T>(linestring: &LineString<T>) -> T where T
}
let mut tmp = T::zero();
for line in linestring.lines() {
tmp = tmp + (line.start.x() * line.end.y() - line.end.x() * line.start.y());
tmp = tmp + line.determinant();
}

tmp
Expand Down

0 comments on commit 7a00054

Please sign in to comment.