Use QuickHull implementation for convex hull #89

urschrei · 2017-02-16T14:44:26Z

This supersedes #87, for a number of reasons:

It's a lot faster – (O n log (n)) on average
It's a far simpler implementation
it doesn't require those questionable Ord and Eq traits

There's also a more robust test provided.

Implementation based on: Barber, C. Bradford; Dobkin, David P.; Huhdanpaa, Hannu(1 December 1996) https://dx.doi.org/10.1145%2F235815.235821) Original paper here: http://www.cs.princeton.edu/~dpd/Papers/BarberDobkinHuhdanpaa.pdf

TeXitoi

Great work!

TeXitoi · 2017-02-17T13:45:11Z

src/algorithm/convexhull.rs

+    // this is a bit hairy
+    for point in &to_retain.difference(&to_remove)
+        .map(|&idx| points[idx])
+        .collect::<Vec<Point<T>>>() {


let iter = points.iter() .enumerate() .filter(|(idx, _)| ![mix_x_idx, max_x_idx].contains(idx)) .map(|(_, p)| *p); for point in iter {

And you don't need to_retain and to_remove (and much less allocations)

TeXitoi · 2017-02-17T13:46:39Z

src/algorithm/convexhull.rs

+    hull.push(p_a);
+    hull.push(p_b);
+    let mut left_set: Vec<Point<T>> = vec![];
+    let mut right_set: Vec<Point<T>> = vec![];


These type annotations should not be needed.

TeXitoi · 2017-02-17T13:49:17Z

src/algorithm/convexhull.rs

+    /// let res = poly.convex_hull();
+    /// assert_eq!(res.exterior, correct_hull);
+    /// ```
+    fn convex_hull(&self) -> Self where T: Float;


convex_hull must return a Polygon.

TeXitoi · 2017-02-17T13:52:11Z

src/algorithm/convexhull.rs

+    fn convex_hull(&self) -> Polygon<T> {
+        Polygon::new(LineString(quick_hull(&self.exterior.0)), vec![])
+    }
+}


Can be great if more geometries are supported (I think at MultiPolygon, LineString and MultiLineString in particular).

Seems like those can happen in follow up PRs, but would be good to have support for those other types

TeXitoi · 2017-02-17T13:59:18Z

src/algorithm/convexhull.rs

+    if points.len() < 4 {
+        return points.to_vec();
+    }
+    let mut hull: Vec<Point<T>> = vec![];


useless type annotation

TeXitoi · 2017-02-17T13:59:46Z

src/algorithm/convexhull.rs

+    }
+    let mut hull: Vec<Point<T>> = vec![];
+    let mut min_x_idx = <usize>::min_value();
+    let mut max_x_idx = <usize>::min_value();


simply use

let mut min_x_idx = 0; let mut max_x_idx = 0;

TeXitoi · 2017-02-17T14:00:46Z

src/algorithm/convexhull.rs

+    let mut max_x_idx = <usize>::min_value();
+    let mut min_x = Float::max_value();
+    let mut max_x = Float::min_value();
+    let to_retain: BTreeSet<usize> = (0..points.len() - 1).collect();


You can simply write

let to_retain: BTreeSet<_> = (0..points.len() - 1).collect();'

TeXitoi · 2017-02-17T14:00:56Z

src/algorithm/convexhull.rs

+    let mut min_x = Float::max_value();
+    let mut max_x = Float::min_value();
+    let to_retain: BTreeSet<usize> = (0..points.len() - 1).collect();
+    let mut to_remove: BTreeSet<usize> = BTreeSet::new();


useless type annotation

TeXitoi · 2017-02-17T14:58:25Z

src/algorithm/convexhull.rs

+    }
+    // recur
+    hull_set(p_a, &furthest_point, &mut left_ap, hull);
+    hull_set(&furthest_point, p_b, &mut left_pb, hull);


the hull.insert calls can have a squared effect because you push at the middle of a Vec (you then must shift n/2 elements). You can rewrite it just using hull.push:

// doing the first part let mut new_set: Vec<_> = set.iter().filter(|point| point_location(p_a, &furthest_point, point)).collect(); hull_set(p_a, &furthest_point, &mut new_set, hull); // inserting the current point hull.push(set[furthest_idx]); // doing the second part, reusing the memory allocated for the first part new_set.clear(); new_set.extends(set.iter().filter(|point| point_location(&furthest_point, p_b, point)); hull_set(&furthest_point, p_b, &mut new_set, hull);

and correct the beginning of the function and the insertion in quick_hull accordingly.

let mut new_set: Vec<_> = set.iter().filter(|point| point_location(p_a, &furthest_point, point)).collect(); gives me a reference, but I need the Point…

= note: expected type `&mut std::vec::Vec<types::Point<T>>` = note: found type `&mut std::vec::Vec<&types::Point<T>>`

add .cloned() after .iter()

I'm trying to adapt this and #89 (comment), but it's failing to compile for me in about three different ways – can you send me a PR against https://github.com/urschrei/rust-geo/tree/convex_hull_quick?

frewsxcv · 2017-02-17T14:50:45Z

src/algorithm/convexhull.rs

+    // this is a bit hairy
+    for point in &to_retain.difference(&to_remove)
+        .map(|&idx| points[idx])
+        .collect::<Vec<Point<T>>>() {


Can this collect call be removed? Seems like we could just iterate over the Points in the Iterator

Removing the collect() gives me a trait bound error:

the trait std::iter::Iterator is not implemented for &std::iter::Map<std::collections::btree_set::Difference<'_, usize>, [closure@convexhull.rs:73:14: 73:32 points:_]>

you have to remove the & after the for point in

frewsxcv · 2017-02-17T14:59:38Z

src/algorithm/convexhull.rs

+    }
+    // recur
+    hull_set(p_a, &furthest_point, &mut left_ap, hull);
+    hull_set(&furthest_point, p_b, &mut left_pb, hull);


Seems like these calls could be done concurrently? If so, something we can do later in a future PR. Though we don't really depend on any parallelism libraries like rayon yet, hmm.

Yep, I've been messing about with Rayon to try to parallelise this. It'll be in a follow-up, if only for discussion, because we're not doing it anywhere yet…

I think you must have a very big polygon for parallelism being interesting.

frewsxcv · 2017-02-17T15:00:52Z

src/algorithm/convexhull.rs

+    fn convex_hull(&self) -> Polygon<T> {
+        Polygon::new(LineString(quick_hull(&self.exterior.0)), vec![])
+    }
+}


Seems like those can happen in follow up PRs, but would be good to have support for those other types

urschrei · 2017-02-18T21:40:02Z

I've covered the nits, but:

6aa0115 has exposed what looks like either an off-by-one or a logic error somewhere; very simple Polygons have their initial point duplicated by the algorithm (see the change at f31f07e), but more complex Polygons such as poly1.rs and poly2.rs don't; the result matches Shapely's (and thus GEOS's), though in a different order.
The vector-insert-avoiding change suggested by @TeXitoi is a crucial enhancement, but I can't seem to get all the way there.

fix bug + optimizations

urschrei · 2017-02-19T17:22:14Z

Amazing work, thanks @TeXitoi!
I should be able to impl this for MultiPoint, LineString, and MultiLineString, but we're missing a method to get the exterior ring for a MultiPolygon at the moment.

TeXitoi · 2017-02-19T17:32:21Z

For multipolygon, just aggregate all the exterior points of the outer polygons in a Vec. You need to give a mutable slice, so creating the Vec is needed.

TeXitoi

I can't really approve as I'm now a contributor, but that's to remove my request changes.

TODO: add some tests for them

- MultiPoint - LineString - MultiLineString - MultiPolygon

TeXitoi · 2017-02-20T16:21:17Z

src/algorithm/convexhull.rs

+{
+    fn convex_hull(&self) -> Polygon<T> {
+        let mut aggregated: Vec<Point<T>> = self.0.iter()
+            .flat_map(|elem| elem.exterior.0.clone())


.flat_map(|elem| elem.exterior.0.iter().cloned()

TeXitoi · 2017-02-20T16:21:48Z

src/algorithm/convexhull.rs

+{
+    fn convex_hull(&self) -> Polygon<T> {
+        let mut aggregated: Vec<Point<T>> = self.0.iter()
+            .flat_map(|elem| elem.0.clone())


frewsxcv

Looks great, nice job :)

frewsxcv · 2017-03-01T02:19:20Z

@urschrei Anything else here or is this good to merge?

urschrei · 2017-03-01T09:16:23Z

Good to go here. Thanks!

frewsxcv · 2017-03-02T01:59:01Z

bors r+

89: Use QuickHull implementation for convex hull

ghost · 2017-03-02T02:16:18Z

Build succeeded

continuous-integration/travis-ci/push

urschrei added 3 commits February 16, 2017 14:42

Implement Convex Hull using QuickHull

dab9fde

Implementation based on: Barber, C. Bradford; Dobkin, David P.; Huhdanpaa, Hannu(1 December 1996) https://dx.doi.org/10.1145%2F235815.235821) Original paper here: http://www.cs.princeton.edu/~dpd/Papers/BarberDobkinHuhdanpaa.pdf

Account for fewer than 4 points in exterior Polygon ring

6ff25eb

Better variable names and comment

92c3d23

TeXitoi requested changes Feb 17, 2017

View reviewed changes

TeXitoi reviewed Feb 17, 2017

View reviewed changes

frewsxcv reviewed Feb 17, 2017

View reviewed changes

urschrei and others added 5 commits February 17, 2017 15:17

Fixing nits

0ff8cc4

Simplify point iteration

77a87c3

Avoid allocating BTreeSets

6aa0115

Fix doc test

f31f07e

A convex hull is always a Polygon

7af53a2

TeXitoi and others added 6 commits February 19, 2017 01:11

fix duplicated point

d38c316

Add test

7104c0a

only use push

78808b4

remove a lot of allocations and slice::remove calls

c9deae0

no index and no alloc in quick_hull (only use the given mut slice)

515cfce

Merge pull request #1 from TeXitoi/convex_hull_quick

24bfc11

fix bug + optimizations

TeXitoi approved these changes Feb 19, 2017

View reviewed changes

urschrei and others added 2 commits February 20, 2017 12:37

Impl convex hull for all supporting types

3fc929c

TODO: add some tests for them

Add convex_hull tests for:

600e520

- MultiPoint - LineString - MultiLineString - MultiPolygon

TeXitoi reviewed Feb 20, 2017

View reviewed changes

Fix flat_map() on MultiLineString and MultiPolygon

e53a92e

frewsxcv approved these changes Feb 22, 2017

View reviewed changes

ghost pushed a commit that referenced this pull request Mar 2, 2017

Merge #89

46276e6

89: Use QuickHull implementation for convex hull

ghost merged commit e53a92e into georust:master Mar 2, 2017

urschrei deleted the convex_hull_quick branch March 14, 2017 18:12

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Use QuickHull implementation for convex hull #89

Use QuickHull implementation for convex hull #89

urschrei commented Feb 16, 2017

TeXitoi left a comment

TeXitoi Feb 17, 2017

TeXitoi Feb 17, 2017

TeXitoi Feb 17, 2017

TeXitoi Feb 17, 2017

frewsxcv Feb 17, 2017

TeXitoi Feb 17, 2017

TeXitoi Feb 17, 2017

TeXitoi Feb 17, 2017

TeXitoi Feb 17, 2017

TeXitoi Feb 17, 2017

urschrei Feb 17, 2017

TeXitoi Feb 17, 2017

urschrei Feb 17, 2017

TeXitoi Feb 19, 2017

frewsxcv Feb 17, 2017

urschrei Feb 17, 2017

TeXitoi Feb 17, 2017

frewsxcv Feb 17, 2017

urschrei Feb 17, 2017

TeXitoi Feb 17, 2017

frewsxcv Feb 17, 2017

urschrei commented Feb 18, 2017

urschrei commented Feb 19, 2017

TeXitoi commented Feb 19, 2017

TeXitoi left a comment

TeXitoi Feb 20, 2017

TeXitoi Feb 20, 2017

frewsxcv left a comment

frewsxcv commented Mar 1, 2017

urschrei commented Mar 1, 2017

frewsxcv commented Mar 2, 2017

ghost commented Mar 2, 2017

Use QuickHull implementation for convex hull #89

Use QuickHull implementation for convex hull #89

Conversation

urschrei commented Feb 16, 2017

TeXitoi left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

urschrei commented Feb 18, 2017

urschrei commented Feb 19, 2017

TeXitoi commented Feb 19, 2017

TeXitoi left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

frewsxcv left a comment

Choose a reason for hiding this comment

frewsxcv commented Mar 1, 2017

urschrei commented Mar 1, 2017

frewsxcv commented Mar 2, 2017

ghost commented Mar 2, 2017

Build succeeded