Implement Polygon-Polygon distance #219
Conversation
|
(Oh, it also adds |
This implementation uses brute-force with an R*-tree for non-convex polygons, but has a "fast path" for convex polygons, based on Pirzadeh (1999)
We can also avoid allocating two extra points here
urschrei
force-pushed
the
new_polygon_distance
branch
from
ac4d1cd to
928e4dc
Compare
| // Return minimum distance between a Point and a Line segment | ||
| // This is a helper for Point-to-LineString and Point-to-Polygon distance | ||
| /// Minimum distance between a Point and a Line segment | ||
| /// This is a helper for Point-to-LineString and Point-to-Polygon distance |
There was a problem hiding this comment.
even though this won't get rendered might want to either update the next line to /// or revert the /// changes on the previous lines for consistency
| match get_position(p, &poly.exterior) { | ||
| PositionPoint::Inside => true, | ||
| PositionPoint::OnBoundary | PositionPoint::Outside => false, | ||
| } |
There was a problem hiding this comment.
is this the same as doing:
poly.exterior.contains(p)https://docs.rs/geo/0.8.3/geo/algorithm/contains/trait.Contains.html
There was a problem hiding this comment.
contains() evaluates differently because of boundary detection IIRC…(it certainly starts failing the tests when I change it)
| punit = unitvector(m, poly, p, idx); | ||
| } else { | ||
| match clockwise { | ||
| true => { |
There was a problem hiding this comment.
if ... {
} else {
match clockwise {
true => ...,
false => ...,
}
}can be reduced to
if ... {
...
} else if clockwise {
...
} else {
...
}| vertical = true; | ||
| } else { | ||
| vertical = false; | ||
| } |
There was a problem hiding this comment.
let vertical = p.x() == u.x();| } else { | ||
| slope = (p.y() - u.y()) / (p.x() - u.x()); | ||
| } | ||
| } |
There was a problem hiding this comment.
let slope = if vertical || p.y() == u.y() {
T::zero()
} else if u.x() > p.x() {
(u.y() - p.y()) / (u.x() - p.x())
} else {
(p.y() - u.y()) / (p.x() - u.x())
};
|
bors r=frewsxcv |
219: Implement Polygon-Polygon distance r=frewsxcv a=urschrei Uses the standard approach (brute force + R*-tree) for non-convex polygons, but for convex polygons, uses a novel implementation of the rotating calipers technique, based on [Pirzadeh (1999), pp24—30](http://digitool.library.mcgill.ca/R/?func=dbin-jump-full&object_id=21623&local_base=GEN01-MCG02), which is around 10x faster. Co-authored-by: Stephan Hügel <urschrei@gmail.com>
Build succeeded |
|
(did I say 10x? I just ran a benchmark, and the fast path is actually 100x faster) |
| fn euclidean_distance(&self, other: &Polygon<T>) -> T { | ||
| self.start | ||
| .euclidean_distance(other) | ||
| .min(self.end.euclidean_distance(other)) |
There was a problem hiding this comment.
Q: does it mean that the distance from a Line to a Polygon is evaluated as either the distance from the starting point to the polygon, or the ending point to the polygon, depending on which one is closer?
What about this kind of situation for example:
Here, each endpoint of the line is much further to the polygon than the actual Line<>Polygon proper distance.
There was a problem hiding this comment.
Oof yes this is terrible.
|
As for // Brute-force pseudocode
impl EuclideanDistance<T, MultiPolygon<T>> for Line<T> {
fn euclidean_distance(&self, other: &MultiPolygon<T>) -> T {
let mut distance = T::max_value();
for polygon in other {
let dist = self.euclidean_distance(polygon);
distance = dist.min(distance);
}
distance
}
} |
|
I think that's a pretty reasonable implementation. I can't see an obviously simpler way to do it, and it's linear complexity (I think), so should be fine – it's always possible that there's a sub-linear approach, but I can't recall one off-hand. |
|
Just submitted a PR for that — only difference with above is I tried to follow the existing style. See #227 |
226: Polygon-Line euclidean distance fix r=urschrei a=urschrei See here: #219 (review) WIP until I add tests for a Line contained in a Polygon interior ring and intersection Co-authored-by: Stephan Hügel <stephan.hugel.12@ucl.ac.uk>
Uses the standard approach (brute force + R*-tree) for non-convex polygons, but for convex polygons, uses a novel implementation of the rotating calipers technique, based on Pirzadeh (1999), pp24—30, which is around 10x faster.