Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[wip] First attempts at implementing Haversine distance #48

Closed
wants to merge 6 commits into from
+54 −18
Closed

[wip] First attempts at implementing Haversine distance #48

Changes from 1 commit
Commits
Show all changes
6 commits
Select commit Hold shift + click to select a range
3edf43f
[wip] First attempts at implementing Haversine distance
tmcw Jul 21, 2016
809d8ad
Split haversine distance, implement
tmcw Jul 24, 2016
e32e9d5
Fix doctest
tmcw Jul 24, 2016
53f64c9
Fix doctest
tmcw Jul 24, 2016
0be988f
Trying rounding again
tmcw Jul 24, 2016
e26beeb
Parametric version
tmcw Aug 21, 2016
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Next Next commit
[wip] First attempts at implementing Haversine distance
@tmcw
tmcw committed Aug 21, 2016
commit 3edf43feafd27d700a307702eb9610a9774fa1ea
16 changes: 16 additions & 0 deletions src/algorithm/distance.rs
View file
Original file line number Diff line number Diff line change
@@ -16,6 +16,7 @@ pub trait Distance<T, Rhs = Self>
/// assert!(dist < COORD_PRECISION)
/// ```
fn distance(&self, rhs: &Rhs) -> T;
fn haversine_distance(&self, rhs: &Rhs) -> T;
}

impl<T> Distance<T, Point<T>> for Point<T>
@@ -25,6 +26,15 @@ impl<T> Distance<T, Point<T>> for Point<T>
let (dx, dy) = (self.x() - p.x(), self.y() - p.y());
dx.hypot(dy)
}

// currently gives answer in meters
fn haversine_distance(&self, p: &Point<T>) -> T {
let R = 6373000;
let a = ((self.y() - p.y()).to_radians() / 2).sin().powi(2) +
(((self.x() - p.x()).to_radians() / 2).sin().powi(2) *
self.y().cos() * p.y().cos());
R * 2 * a.sqrt().atan2((1 - a).sqrt())
}
}

#[cfg(test)]
@@ -41,4 +51,10 @@ mod test {
let dist = Point::new(-72.1235, 42.3521).distance(&Point::new(72.1260, 70.612));
assert!(dist < 147. && dist > 146.);
}
#[test]
fn distance3_test() {
// Point::new(-72.1235, 42.3521).distance(&Point::new(72.1260, 70.612)) = 146.99163308930207
let dist = Point::new(-72.1235, 42.3521).haversine_distance(&Point::new(72.1260, 70.612));
assert!(dist < 147. && dist > 146.);
}
}
3 changes: 2 additions & 1 deletion src/algorithm/intersects.rs
View file
Original file line number Diff line number Diff line change
@@ -1,5 +1,5 @@
use num::Float;
use types::{LineString, Polygon, Bbox};
use types::{LineString, Polygon, Bbox, ToRadians};
use algorithm::contains::Contains;

/// Checks if the geometry A intersects the geometry B.
@@ -54,6 +54,7 @@ impl<T> Intersects<LineString<T>> for LineString<T>
}
}


impl<T> Intersects<LineString<T>> for Polygon<T>
where T: Float
{
16 changes: 16 additions & 0 deletions src/traits.rs
View file
Original file line number Diff line number Diff line change
@@ -2,6 +2,22 @@ pub use ::Geometry;

use num::Float;

pub trait ToRadians {
fn to_radians(self) -> Self;
}

impl ToRadians for f32 {
fn to_radians(self) -> f32 {
self.to_radians()
}
}

impl ToRadians for f64 {
fn to_radians(self) -> f64 {
self.to_radians()
}
}

pub trait ToGeo<T: Float>
{
fn to_geo(&self) -> Geometry<T>;
34 changes: 18 additions & 16 deletions src/types.rs
View file
Original file line number Diff line number Diff line change
@@ -5,19 +5,21 @@ use std::ops::Sub;

use num::{Float, ToPrimitive};

pub use traits::ToGeo;

pub static COORD_PRECISION: f32 = 1e-1; // 0.1m

#[derive(PartialEq, Clone, Copy, Debug)]
pub struct Coordinate<T>
where T: Float
where T: Float + ToRadians
{
pub x: T,
pub y: T,
}

#[derive(PartialEq, Clone, Copy, Debug)]
pub struct Bbox<T>
where T: Float
where T: Float + ToRadians
{
pub xmin: T,
pub xmax: T,
@@ -26,10 +28,10 @@ pub struct Bbox<T>
}

#[derive(PartialEq, Clone, Copy, Debug)]
pub struct Point<T> (pub Coordinate<T>) where T: Float;
pub struct Point<T> (pub Coordinate<T>) where T: Float + ToRadians;

impl<T> Point<T>
where T: Float + ToPrimitive
where T: Float + ToPrimitive + ToRadians
{
/// Creates a new point.
///
@@ -172,7 +174,7 @@ impl<T> Point<T>
}

impl<T> Neg for Point<T>
where T: Float + Neg<Output = T> + ToPrimitive
where T: Float + Neg<Output = T> + ToPrimitive + ToRadians
{
type Output = Point<T>;

@@ -192,7 +194,7 @@ impl<T> Neg for Point<T>
}

impl<T> Add for Point<T>
where T: Float + ToPrimitive
where T: Float + ToPrimitive + ToRadians
{
type Output = Point<T>;

@@ -212,7 +214,7 @@ impl<T> Add for Point<T>
}

impl<T> Sub for Point<T>
where T: Float + ToPrimitive
where T: Float + ToPrimitive + ToRadians
{
type Output = Point<T>;

@@ -232,7 +234,7 @@ impl<T> Sub for Point<T>
}

impl<T> Add for Bbox<T>
where T: Float + ToPrimitive
where T: Float + ToPrimitive + ToRadians
{
type Output = Bbox<T>;

@@ -261,7 +263,7 @@ impl<T> Add for Bbox<T>
}

impl<T> AddAssign for Bbox<T>
where T: Float + ToPrimitive
where T: Float + ToPrimitive + ToRadians
{
/// Add a boundingox to the given boundingbox.
///
@@ -287,26 +289,26 @@ impl<T> AddAssign for Bbox<T>


#[derive(PartialEq, Clone, Debug)]
pub struct MultiPoint<T>(pub Vec<Point<T>>) where T: Float;
pub struct MultiPoint<T>(pub Vec<Point<T>>) where T: Float + ToRadians;

#[derive(PartialEq, Clone, Debug)]
pub struct LineString<T>(pub Vec<Point<T>>) where T: Float;
pub struct LineString<T>(pub Vec<Point<T>>) where T: Float + ToRadians;

#[derive(PartialEq, Clone, Debug)]
pub struct MultiLineString<T>(pub Vec<LineString<T>>) where T: Float;
pub struct MultiLineString<T>(pub Vec<LineString<T>>) where T: Float + ToRadians;

#[derive(PartialEq, Clone, Debug)]
pub struct Polygon<T>(pub LineString<T>, pub Vec<LineString<T>>) where T: Float;
pub struct Polygon<T>(pub LineString<T>, pub Vec<LineString<T>>) where T: Float + ToRadians;

#[derive(PartialEq, Clone, Debug)]
pub struct MultiPolygon<T>(pub Vec<Polygon<T>>) where T: Float;
pub struct MultiPolygon<T>(pub Vec<Polygon<T>>) where T: Float + ToRadians;

#[derive(PartialEq, Clone, Debug)]
pub struct GeometryCollection<T>(pub Vec<Geometry<T>>) where T: Float;
pub struct GeometryCollection<T>(pub Vec<Geometry<T>>) where T: Float + ToRadians;

#[derive(PartialEq, Clone, Debug)]
pub enum Geometry<T>
where T: Float
where T: Float + ToRadians
{
Point(Point<T>),
LineString(LineString<T>),