-
-
Save kindlychung/a286e8f6ae217f86b5825a186dd4567b to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Compiling algorithms_in_a_nutshell v0.1.0 (file:///Users/kaiyin/Documents/workspace-eclipse-neon/algorithms_in_a_nutshell) | |
error[E0308]: mismatched types | |
--> src/convex_hull.rs:167:10 | |
| | |
167 | set | |
| ^^^ expected struct `convex_hull::Point`, found reference | |
... | |
175 | let minus_i = points.difference(&(btreeset!(p_i))); | |
| -------------- in this macro invocation | |
| | |
= note: expected type `std::collections::BTreeSet<convex_hull::Point>` | |
= note: found type `std::collections::BTreeSet<&convex_hull::Point>` | |
error[E0308]: mismatched types | |
--> src/convex_hull.rs:167:10 | |
| | |
167 | set | |
| ^^^ expected struct `convex_hull::Point`, found reference | |
... | |
177 | let minus_j = points.difference(&(btreeset!(p_j))); | |
| -------------- in this macro invocation | |
| | |
= note: expected type `std::collections::BTreeSet<convex_hull::Point>` | |
= note: found type `std::collections::BTreeSet<&convex_hull::Point>` | |
error[E0277]: the trait bound `&std::collections::btree_set::Difference<'_, convex_hull::Point>: std::iter::Iterator` is not satisfied | |
--> src/convex_hull.rs:178:4 | |
| | |
178 | for p_k in &minus_j { | |
| ^ trait `&std::collections::btree_set::Difference<'_, convex_hull::Point>: std::iter::Iterator` not satisfied | |
| | |
= note: `&std::collections::btree_set::Difference<'_, convex_hull::Point>` is not an iterator; maybe try calling `.iter()` or a similar method | |
= note: required by `std::iter::IntoIterator::into_iter` | |
error: aborting due to 3 previous errors | |
Build failed, waiting for other jobs to finish... | |
error[E0308]: mismatched types | |
--> src/convex_hull.rs:167:10 | |
| | |
167 | set | |
| ^^^ expected struct `convex_hull::Point`, found reference | |
... | |
175 | let minus_i = points.difference(&(btreeset!(p_i))); | |
| -------------- in this macro invocation | |
| | |
= note: expected type `std::collections::BTreeSet<convex_hull::Point>` | |
= note: found type `std::collections::BTreeSet<&convex_hull::Point>` | |
error[E0308]: mismatched types | |
--> src/convex_hull.rs:167:10 | |
| | |
167 | set | |
| ^^^ expected struct `convex_hull::Point`, found reference | |
... | |
177 | let minus_j = points.difference(&(btreeset!(p_j))); | |
| -------------- in this macro invocation | |
| | |
= note: expected type `std::collections::BTreeSet<convex_hull::Point>` | |
= note: found type `std::collections::BTreeSet<&convex_hull::Point>` | |
error[E0277]: the trait bound `&std::collections::btree_set::Difference<'_, convex_hull::Point>: std::iter::Iterator` is not satisfied | |
--> src/convex_hull.rs:178:4 | |
| | |
178 | for p_k in &minus_j { | |
| ^ trait `&std::collections::btree_set::Difference<'_, convex_hull::Point>: std::iter::Iterator` not satisfied | |
| | |
= note: `&std::collections::btree_set::Difference<'_, convex_hull::Point>` is not an iterator; maybe try calling `.iter()` or a similar method | |
= note: required by `std::iter::IntoIterator::into_iter` | |
error: aborting due to 3 previous errors | |
error: Could not compile `algorithms_in_a_nutshell`. | |
To learn more, run the command again with --verbose. |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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_by(|a, b| { | |
if a.x == b.x { | |
a.y.partial_cmp(&b.y).unwrap_or(Equal) | |
} else { | |
a.x.partial_cmp(&b.x).unwrap_or(Equal) | |
} | |
}); | |
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> { | |
// set of all points | |
let p_internal_set: BTreeSet<Point> = BTreeSet::new(); | |
for p_i in points { | |
let minus_i = points.difference(&(btreeset!(p_i))); | |
for p_j in minus_i { | |
let minus_j = points.difference(&(btreeset!(p_j))); | |
for p_k in &minus_j { | |
} | |
} | |
} | |
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); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment