Add extreme point-finding #114
Conversation
urschrei
force-pushed
the
find_extreme_points
branch
from
f42d3a4 to
32d789d
Compare
|
Argh, I've just realised that the indices are only valid for input geometries that are convex. Because the convex-hull algorithm alters vertex order and may remove vertices, the returned struct contains indices that are wrong if the input geometry wasn't convex to begin with. It's trivial to use this work as the basis for a trait that returns the extreme points (which is useful functionality imo), and it's necessary to have the extreme indices of a convex geometry as part of the polygon-to-polygon distance functionality, but maybe it shouldn't be a public API? |
since this trait can't return the indices of a non-convex polygon, there's no need to specify what to do with an input polygon This makes the trait publicly useless, since there's no simple way of guaranteeing the convex property of the input geometry. However, the trait is still useful as a helper for returning extreme points, as an internal helper for returning extreme indices for polygon-to-polygon distance there's no simple way to restrict a trait's visibility until 1.18, so we're currently back to the drawing board
Like ExtremeIndices, but for points
|
I think it's fine leaving it public, as long as the limitations of the algorithm are documented, I think it's fine. r=me if this is good to go |
The input Polygon is now checked for convexity. This functionality adds considerable complexity to the trait, but I feel like it's worth it.
|
OK, the I'm using a wrapping index lookup to get the two previous points. I don't think I can over / underflow it, and it's guaranteed to always receive a valid index, since it's only called by I've also added an |
[ci skip]
src/algorithm/extremes.rs
Outdated
| } | ||
|
|
||
| // positive implies a -> b -> c is counter-clockwise, negative implies clockwise | ||
| pub fn cross_prod<T>(p_a: &Point<T>, p_b: &Point<T>, p_c: &Point<T>) -> T |
There was a problem hiding this comment.
Did you mean for this to be public?
|
LGTM. r=me if it's ready |
|
r=frewsxcv |
|
bors r+ |
114: Add extreme point-finding r=frewsxcv This PR allows the calculation of the indices containing the extreme (min and max) `x` and `y` values of a geometry (any geometry for which we can build a convex hull). There are some subtleties: The algorithm is simple, and runs in `O(n)` time, but only works on convex geometries, which it expects to be oriented counter-clockwise. Since convex-hull processing using QuickHull is `O(n log n)` on average, that's the lower bound if the geometry needs to be processed first. However, if you know your geometries are convex and oriented, you can specify this, and get `O(n)` processing. There's also a binary-search algorithm available, which cuts processing time to `O(log n)`, but I haven't been able to make it work. It's [available in a previous commit](urschrei@4f71b24#diff-6128c8bf9f8def540989e4f8abf862c7L85) along with a link to the source, if anyone wants to have a look at it and figure out where the problem is – it incorrectly returns minimum `x`. The current algorithm is implemented using a wrapper function that allows the algorithms to be easily swapped out. I've also defaulted to returning indices, not points, because this functionality is primarily intended as a helper for other algorithms.
Build succeeded |
This PR allows the calculation of the indices containing the extreme (min and max)
xandyvalues of a geometry (any geometry for which we can build a convex hull). There are some subtleties:The algorithm is simple, and runs in
O(n)time, but only works on convex geometries, which it expects to be oriented counter-clockwise. Since convex-hull processing using QuickHull isO(n log n)on average, that's the lower bound if the geometry needs to be processed first. However, if you know your geometries are convex and oriented, you can specify this, and getO(n)processing.There's also a binary-search algorithm available, which cuts processing time to
O(log n), but I haven't been able to make it work. It's available in a previous commit along with a link to the source, if anyone wants to have a look at it and figure out where the problem is – it incorrectly returns minimumx. The current algorithm is implemented using a wrapper function that allows the algorithms to be easily swapped out.I've also defaulted to returning indices, not points, because this functionality is primarily intended as a helper for other algorithms.