eq.rs

use std::cmp::Ordering::Equal;
use std::cmp::Ordering;
use std::ops::{Add, Sub, Mul}; 
use std::collections::BTreeSet;

#[derive(Debug, Copy, Clone)]
struct Point {
	x: f64, 
	y: f64, 
}


impl PartialEq for Point {
	fn eq(&self, other: &Point) -> bool {
		if self.x.is_nan() & other.x.is_nan() & self.y.is_nan() & other.y.is_nan() {
			return true;
		}
		if self.x.is_nan() & other.x.is_nan() {
			return self.y == other.y; 
		}
		if self.y.is_nan() & other.y.is_nan() {
			return self.x == other.x;
		}
		(self.x == other.x) & (self.y == other.y)
	}
}


impl Eq for Point {}

impl PartialOrd for Point {
	fn partial_cmp(&self, other: &Point) -> Option<Ordering> {
		Some(self.cmp(other))
	}
}



impl Ord for Point {
    fn cmp(&self, other: &Point) -> Ordering {
        let c = self.x.partial_cmp(&other.x).unwrap();
        if c == Equal {
        	self.y.partial_cmp(&other.y).unwrap()
        } else {
        	c
        }
    }
}


impl Point {
	fn new(x: f64, y: f64) -> Point {
		if x.is_nan() | y.is_nan() {
			panic!("Coordinates cannot be NaN!");
		}
		Point {
			x: x,
			y: y,
		}
	}
	
	// Euclidean distance
	fn distance(&self, other: &Point) -> f64 {
		((self.x - other.x).powi(2) + (self.y - other.y).powi(2)).sqrt()
	}

    // Draw a horizontal line through this point, connect this point with the other, and measure the angle between these two lines. 
    fn angle(&self, other: &Point) -> f64 {
    	(other.y - self.y).atan2(other.x - self.x)
    }
}

impl Add for Point {
	type Output = Point; 
	fn add(self, rhs: Point) -> Point {
		Point::new(self.x + rhs.x, self.y + rhs.y)
	}
} 
impl Sub for Point {
	type Output = Point; 
	fn sub(self, rhs: Point) -> Point {
		Point::new(self.x - rhs.x, self.y - rhs.y)
	}
} 
// dot product 
impl Mul for Point {
	type Output = f64; 
	fn mul(self, rhs: Point) -> f64 {
		self.x * rhs.x + self.y * rhs.y
	}
}

#[test]
fn test_point() {
	use std::f64::consts::PI; 
	let p1 = Point::new(0.0, 0.0); 
	let p2 = Point::new(0.0, 1.0); 
	assert_eq!(p1.angle(&p2), PI/2.0);
	assert_eq!(p1.distance(&p2), 1.0);
	let p1 = Point::new(0.0, 0.0); 
	let p2 = Point::new(1.0, 1.0); 
	assert_eq!(p1.angle(&p2), PI/4.0);
	assert_eq!(p1.distance(&p2), 2.0f64.sqrt());
	let p1 = Point::new(0.0, 0.0); 
	let p2 = Point::new(1.0, -1.0); 
	assert_eq!(p1.angle(&p2), -PI/4.0);
	assert_eq!(p1.distance(&p2), 2.0f64.sqrt());
}

#[derive(PartialEq,Eq,Debug)]
struct Triangle {
	p0: Point, 
	p1: Point, 
	p2: Point,
}

impl Triangle {
	fn new(p0: Point, p1: Point, p2: Point) -> Triangle {
		// Sort by x-coordinate to make sure the first point is the leftmost and lowest.
		let mut v: Vec<Point> = vec![p0, p1, p2];
		v.sort();
		Triangle {
			p0: v[0], 
			p1: v[1], 
			p2: v[2],
		}
	}
	
	fn range_x(&self) -> (f64, f64) {
		(self.p0.x, self.p2.x)
	}
	fn range_y(&self) -> (f64, f64) {
		let mut v = vec![self.p0, self.p1, self.p2];
		v.sort_by(|a, b| {
			a.y.partial_cmp(&(b.y)).unwrap_or(Equal)
		});
		(v[0].y, v[2].y)
	}

	// Barycentric Technique, check whether point is in triangle, see http://blackpawn.com/texts/pointinpoly/
	fn contains(&self, p: Point) -> bool {
		let v0 = self.p2 - self.p0; 
		let v1 = self.p1 - self.p0; 
		let v2 = p - self.p0; 
		let dot00 = v0 * v0; 
		let dot01 = v0 * v1;
		let dot02 = v0 * v2;
		let dot11 = v1 * v1;
		let dot12 = v1 * v2;
		let inv_denom = 1.0f64 / (dot00 * dot11 - dot01 * dot01);
		let u = (dot11 * dot02 - dot01 * dot12) * inv_denom;
		let v = (dot00 * dot12 - dot01 * dot02) * inv_denom;
		(u >= 0.0) & (v >= 0.0) & (u + v <= 1.0)
	}
}


#[macro_export]
macro_rules! btreeset {
    ($($x: expr),*) => {{
         let mut set = ::std::collections::BTreeSet::new();
         $( set.insert($x); )*
         set
    }}
}

fn convex_hull_naive(points: &BTreeSet<Point>) -> Vec<Point> {
	let minus_one = |p: &Point| {
		points.difference(&(btreeset!(p.clone()))).cloned().collect::<BTreeSet<Point>>()
	};
	let mut p_internal_set: BTreeSet<Point> = BTreeSet::new();
	for p_i in points {
		let minus_i = minus_one(&p_i);
		for p_j in &minus_i {
			let minus_j = minus_one(&p_j);
			for p_k in &minus_j {
				let minus_k = minus_one(&p_k);
				for p_m in &minus_k {
					if Triangle::new(p_i.clone(), p_j.clone(), p_k.clone()).contains(p_m.clone()) {
						p_internal_set.insert(p_m.clone());
					}
				}
			}
		}
	}
	let mut hull = points.difference(&p_internal_set).cloned().collect::<Vec<Point>>();
	hull.sort();
	let head = hull[0].clone();
	let angle_to_head = |p: &Point| {
		if p == head {
			0.0
		} else {
			head.angle(p)
		}
	};
	return vec!(Point::new(1.0, 1.0));
}


#[test]
fn test_triangle() {
	use std::f64::consts::PI; 
	let p2 = Point::new(0.0, 0.0); 
	let p1 = Point::new(0.0, 1.0); 
	let p0 = Point::new(1.0, 1.0);
	let t = Triangle::new(p0, p1, p2); 
	assert_eq!(t.range_x(), (0.0, 1.0));
	assert_eq!(t.range_y(), (0.0, 1.0));
	assert_eq!(t.p0, p2);
	assert_eq!(t.p1, p1);
	assert_eq!(t.p2, p0);
	// triangle should contain its vertices
	assert!(t.contains(p0));
	assert!(t.contains(p1));
	assert!(t.contains(p2));
	// triangle should contain points on any side
	assert!(t.contains(Point::new(0.5, 0.5)));
	assert!(t.contains(Point::new(0.3, 0.3)));
	assert!(t.contains(Point::new(0.2, 0.2)));
	assert!(t.contains(Point::new(0.1, 0.1)));
	assert!(t.contains(Point::new(0.0, 0.1)));
	assert!(t.contains(Point::new(0.0, 0.2)));
	assert!(t.contains(Point::new(0.1, 1.0)));
	assert!(t.contains(Point::new(0.2, 1.0)));
	assert!(!t.contains(Point::new(0.2, 1.1)));
	// strictly inside the triangle
	assert!(t.contains(Point::new(0.5, 0.51)));
	assert!(t.contains(Point::new(0.51, 0.51)));
	assert!(t.contains(Point::new(0.51, 0.52)));
	let p2 = Point::new(0.0, 0.0); 
	let p1 = Point::new(0.5, 1.0); 
	let p0 = Point::new(1.0, 0.5);
	let t = Triangle::new(p0, p1, p2); 
	assert_eq!(t.range_x(), (0.0, 1.0));
	assert_eq!(t.range_y(), (0.0, 1.0));
	assert_eq!(t.p0, p2);
	assert_eq!(t.p1, p1);
	assert_eq!(t.p2, p0);
}

err

cargo build
   Compiling algorithms_in_a_nutshell v0.1.0 (file:///Users/kaiyin/Documents/workspace-eclipse-neon/algorithms_in_a_nutshell)
error[E0277]: the trait bound `&convex_hull::Point: std::cmp::PartialEq<convex_hull::Point>` is not satisfied
   --> src/convex_hull.rs:190:6
    |
190 |  		if p == head {
    |  		   ^^^^^^^^^ trait `&convex_hull::Point: std::cmp::PartialEq<convex_hull::Point>` not satisfied
    |
    = help: the following implementations were found:
    = help:   <convex_hull::Point as std::cmp::PartialEq>

error: aborting due to previous error

error: Could not compile `algorithms_in_a_nutshell`.

To learn more, run the command again with --verbose.