Convex hull: Difference between revisions
Content added Content deleted
(Add Rust implementation) |
|||
Line 2,169: | Line 2,169: | ||
Points of convex hull in clockwise order: |
Points of convex hull in clockwise order: |
||
-3/-9 -9/-3 -3/15 5/19 12/17 17/5 19/-8 -3/-9</pre> |
-3/-9 -9/-3 -3/15 5/19 12/17 17/5 19/-8 -3/-9</pre> |
||
=={{header|Rust}}== |
|||
Calculates convex hull from list of points (f32, f32). This can be executed entirely in the Rust Playground. |
|||
<lang Rust> |
|||
#[derive(Debug, Clone)] |
|||
struct Point { |
|||
x: f32, |
|||
y: f32 |
|||
} |
|||
fn calculate_convex_hull(points: &Vec<Point>) -> Vec<Point> { |
|||
//There must be at least 3 points |
|||
if points.len() < 3 { return points.clone(); } |
|||
let mut hull = vec![]; |
|||
//Find the left most point in the polygon |
|||
let (left_most_idx, _) = points.iter() |
|||
.enumerate() |
|||
.min_by(|lhs, rhs| lhs.1.x.partial_cmp(&rhs.1.x).unwrap()) |
|||
.expect("No left most point"); |
|||
let mut p = left_most_idx; |
|||
let mut q = 0_usize; |
|||
loop { |
|||
//The left most point must be part of the hull |
|||
hull.push(points[p].clone()); |
|||
q = (p + 1) % points.len(); |
|||
for i in 0..points.len() { |
|||
if orientation(&points[p], &points[i], &points[q]) == 2 { |
|||
q = i; |
|||
} |
|||
} |
|||
p = q; |
|||
//Break from loop once we reach the first point again |
|||
if p == left_most_idx { break; } |
|||
} |
|||
return hull; |
|||
} |
|||
//Calculate orientation for 3 points |
|||
//0 -> Straight line |
|||
//1 -> Clockwise |
|||
//2 -> Counterclockwise |
|||
fn orientation(p: &Point, q: &Point, r: &Point) -> usize { |
|||
let val = (q.y - p.y) * (r.x - q.x) - |
|||
(q.x - p.x) * (r.y - q.y); |
|||
if val == 0. { return 0 }; |
|||
if val > 0. { return 1; } else { return 2; } |
|||
} |
|||
fn main(){ |
|||
let points = vec![pt(16,3), pt(12,17), pt(0,6), pt(-4,-6), pt(16,6), pt(16,-7), pt(16,-3), pt(17,-4), pt(5,19), pt(19,-8), pt(3,16), pt(12,13), pt(3,-4), pt(17,5), pt(-3,15), pt(-3,-9), pt(0,11), pt(-9,-3), pt(-4,-2), pt(12,10)]; |
|||
let hull = calculate_convex_hull(&points); |
|||
hull.iter() |
|||
.for_each(|pt| println!("{:?}", pt)); |
|||
} |
|||
fn pt(x: i32, y: i32) -> Point { |
|||
return Point {x:x as f32, y:y as f32}; |
|||
} |
|||
</lang> |
|||
=={{header|Scala}}== |
=={{header|Scala}}== |
||
Scala Implementation to find Convex hull of given points collection. Functional Paradigm followed |
Scala Implementation to find Convex hull of given points collection. Functional Paradigm followed |