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

Add extreme point-finding #114

Merged
merged 17 commits into from
Apr 17, 2017
Merged

Add extreme point-finding #114

Changes from 1 commit
Commits
Show all changes
17 commits
Select commit Hold shift + click to select a range
d03e58b
First pass at extreme-finding algorithms
urschrei Mar 24, 2017
d50468a
Remove binary search implementation for now
urschrei Apr 9, 2017
d89d144
Return indices, not points
urschrei Apr 9, 2017
4f5df74
Simplify matching, remove allocations, add another test
urschrei Apr 10, 2017
392f38a
Add MultiPolygon and MultiPoint impls
urschrei Apr 10, 2017
32d789d
Better docs
urschrei Apr 10, 2017
582e2b1
Merge branch 'master' into find_extreme_points
frewsxcv Apr 15, 2017
f2f2218
We're returning indices, so make that clear
urschrei Apr 14, 2017
9e6cf9b
Rename trait
urschrei Apr 14, 2017
8c959bd
Fix comment
urschrei Apr 15, 2017
c29a01e
Better function names
urschrei Apr 15, 2017
1ec7e71
Simplify ExtremeIndices trait
urschrei Apr 15, 2017
867c679
Implement ExtremePoints trait
urschrei Apr 16, 2017
7d9b73a
Add convexity check to ExtremeIndices trait
urschrei Apr 16, 2017
81ef980
Better comments
urschrei Apr 17, 2017
6a81d83
cross product doesn't need to be pub
urschrei Apr 17, 2017
a969dab
Make points raw
urschrei Apr 17, 2017
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
Prev Previous commit
Next Next commit
Add MultiPolygon and MultiPoint impls
  • Loading branch information
@urschrei
urschrei committed Apr 10, 2017
commit 392f38aecdb22016600c5892c82e820d168cddc6
22 changes: 20 additions & 2 deletions src/algorithm/extremes.rs
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -1,5 +1,5 @@
use num_traits::Float;
use types::{Point, LineString, Polygon};
use types::{Point, LineString, Polygon, MultiPoint, MultiPolygon};
use algorithm::convexhull::ConvexHull;
use algorithm::orient::{Orient, Direction};
use types::Extremes;
Expand Down Expand Up @@ -73,7 +73,7 @@ fn find_extremes<T, F>(func: F, polygon: &Polygon<T>, convex: bool, oriented: bo

// find a convex, counter-clockwise oriented polygon's maximum vertex in a specified direction
// u: a direction vector. We're using a point to represent this, which is a hack but works fine
// this is O(n), because polymax() can't yet calculate minimum x
// this is O(n) if the polygon is convex.
fn polymax_naive<T>(u: &Point<T>, poly: &Polygon<T>) -> Result<usize, ()>
where T: Float
{
Expand Down Expand Up @@ -126,6 +126,24 @@ impl<T> ExtremePoints<T> for Polygon<T>
}
}

impl<T> ExtremePoints<T> for MultiPolygon<T>
where T: Float
{
fn extreme_points(&self, convex: bool, oriented: bool) -> Extremes {
// we can disregard the input because convex-hull processing always orients
find_extremes(polymax_naive, &self.convex_hull(), true, true)
}
}

impl<T> ExtremePoints<T> for MultiPoint<T>
where T: Float
{
fn extreme_points(&self, convex: bool, oriented: bool) -> Extremes {
// we can disregard the input because convex-hull processing always orients
find_extremes(polymax_naive, &self.convex_hull(), true, true)
}
}

#[cfg(test)]
mod test {
use types::Point;
Expand Down