[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 


More information about the R-sig-Geo mailing list