[R] minimum distance between line segments

[Thomas Lumley]

On Fri, Mar 11, 2011 at 2:46 AM, Mike Marchywka <marchywka at hotmail.com> wrote:

> ----------------------------------------
>> Date: Wed, 9 Mar 2011 10:55:46 +1300
>> From: darcy.webber at gmail.com
>> To: r-help at r-project.org
>> Subject: [R] minimum distance between line segments
>>
>> Dear R helpers,
>>
>> I think that this may be a bit of a math question as the more I
>> consider it, the harder it seems. I am trying to come up with a way to
>> work out the minimum distance between line segments. For instance,
>> consider 20 random line segments:
>>
>> x1 <- runif(20)
>> y1 <- runif(20)
>> x2 <- runif(20)
>> y2 <- runif(20)
>>
>> plot(x1, y1, type = "n")
>> segments(x1, y1, x2, y2)
>>
>> Inititally I thought the solution to this problem was to work out the
>> distance between midpoints (it quickly became apparent that this is
>> totally wrong when looking at the plot). So, I thought that perhaps
>> finding the minimum distance between each of the lines endpoints AND
>> their midpoints would be a good proxy for this, so I set up a loop
>> that uses pythagoras to work out these 9 distances and find the
>> minimum. But, this solution is obviously flawed as well (sometimes
>> lines actually intersect, sometimes the minimum distances are less
>> etc). Any help/dection on this one would be much appreciated.
>

There are two possibilities:

If the segments cross, the minimum distance is where they cross, obviously.

If they don't cross, the minimum distance is from one of the four
endpoints to the closest point on the other segment.  The closest
point on the other segment is either the nearest endpoint of the other
segment or the closest point on the infinite line that extends the
other segment.

That gives a small set of possibilities to work with.

If you're not doing this for millions of segments and you don't need
very high accuracy, however, taking lots of points from each segment
and computing pairwise distances by brute force is likely to be easier

peri<-function(xstart,ystart,xend,yend){
	
	line1x<-seq(xstart[1],xend[1],length=98)
	line1y<-seq(ystart[1],yend[1],length=98)
	
	line2x<-seq(xstart[2],xend[2],length=100)
	line2y<-seq(ystart[2],yend[2],length=100)

   distsq<-outer(1:98,1:100, function(i,j)
(line1x[i]-line2x[j])^2+(line1y[i]-line2y[j])^2)
	
	closest<-which(distsq==min(distsq),arr.ind=TRUE)
	
	rbind(c(line1x[closest[1]],line1y[closest[1]]),c(line2x[closest[2]],line2y[closest[2]]))
	
	}

   -thomas


-- 
Thomas Lumley
Professor of Biostatistics
University of Auckland