[R-sig-Geo] GRASS with R and distances between polygon edges
Barry Rowlingson
b.rowlingson at lancaster.ac.uk
Mon Oct 30 18:22:14 CET 2006
> For many polygons each having possibly many points defining the edges,
> it's a time consuming search. I am not aware of any GIS software or R
> packages that do this comprehensively. One alternative is to use
> buffering by some set of fixed distances. Or, write a program/function
> to do the search: for each polygon, find the minimum distance between
> all of its vertices and all of the vertices of each other polygon.
> However, this algorithm does not work well with two polygons like this:
>
> |---------------------|
> | |
> |---------------------|
>
> /\
> / \
> /____\
>
> A buffering approach would do better.
I think if you compute the minimum distances from each vertex of polygon
A to each segment of polygon B, then do the same for each vertex of
polygon B to each segment of polygon A you should get the exact answer.
At least, for non-overlapping polygons. This is because you cant arrange
two non-intersecting line segments such that their closest approach
isn't at one of the four ends. For any point within one of the line
segments, going one way along the line must get you either closer or
further to the other line segment. I think thats intuitively obvious now
I've intuited it enough times...
To find the nearest point-line segment, parameterise the line segment so
the ends are at p=0 and 1, do a bit of vector math, work out the p for
the closest point, if 0<p then p=0, and p>1 then p=1, work out the
distance from your vertex to the point p. Keep the minimum.
You have to repeat with B's vertices against A's segments since in the
rectangle-triangle case either could be A or B and the nearest point is
where the triangle's vertex is close to the rectangles segment.
It doesnt work for overlapping polygons since the nearest approach of
two overlapping line segments is partway between the segments. But its
fairly easy to detect overlapping line segments in one go and then
distance=0.
Barry
More information about the R-sig-Geo
mailing list