I think I need to retract the part about 3 iterations... not true if, e.g., the segments intersect and the angle is small.
-----Original Message----- From: r-help-boun...@r-project.org [mailto:r-help-boun...@r-project.org] On Behalf Of rex.dw...@syngenta.com Sent: Friday, March 11, 2011 2:37 PM To: tlum...@uw.edu; marchy...@hotmail.com Cc: r-help@r-project.org; darcy.web...@gmail.com Subject: Re: [R] minimum distance between line segments I like Thomas's idea as a quick practical solution. Here is one more little variation just in case you really do have millions of these distances. Pick point P1 on line segment L1 (e.g., an endpoint). Pick 101 evenly spaced points on line segment L2. Find the nearest to P1 and call it P2. Now go back to L1 and pick a new P1. Alternate until the distance stops dropping. I think it is probably a theorem that three iterations suffice. So, you could get by with 303 distance calculations instead of 10,201. This might also be interesting to some because it defines a function that returns a function. line = function(p1,p2) function(a) (1-a)*p1 + a*p2 # returns a function mapping any a in [0,1] to a point between p1 and p2. line1 = line(c(pi,12),c(7,-3)) # one line line2 = line(c(0.1,5),c(3,7*sqrt(2))) #another line print(line1(1)) # one endpoint print(line1(0)) # the other print(line1(0.5)) # midpoint d2 = function(p1,p2) sum((p1-p2)^2) # parameter a for the point on some.line nearest to some.point. nearest = function(some.point,some.line) { seq = (0:100)/100; return(seq[which.min(sapply(seq, function(a) d2(some.point,some.line(a))))]) } plot.seg = function (some.line,...) lines(rbind(some.line(0),some.line(1)),...) a = 0 b = nearest(line1(a),line2) a = nearest(line2(b),line1) b = nearest(line1(a),line2) plot(c(-5,15),c(-5,15),asp=1,type="n",main=sqrt(d2(line1(a),line2(b)))) plot.seg(line1,col="black") plot.seg(line2,col="blue") plot.seg(line(line1(a),line2(b)),col="red") -----Original Message----- From: r-help-boun...@r-project.org [mailto:r-help-boun...@r-project.org] On Behalf Of Thomas Lumley Sent: Thursday, March 10, 2011 2:54 PM To: Mike Marchywka Cc: r-help@r-project.org; darcy.web...@gmail.com Subject: Re: [R] minimum distance between line segments On Fri, Mar 11, 2011 at 2:46 AM, Mike Marchywka <marchy...@hotmail.com> wrote: > ---------------------------------------- >> Date: Wed, 9 Mar 2011 10:55:46 +1300 >> From: darcy.web...@gmail.com >> To: r-help@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 ______________________________________________ R-help@r-project.org mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting-guide.html and provide commented, minimal, self-contained, reproducible code. message may contain confidential information. If you are not the designated recipient, please notify the sender immediately, and delete the original and any copies. Any use of the message by you is prohibited. ______________________________________________ R-help@r-project.org mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting-guide.html and provide commented, minimal, self-contained, reproducible code. message may contain confidential information. If you are not the designated recipient, please notify the sender immediately, and delete the original and any copies. Any use of the message by you is prohibited. ______________________________________________ R-help@r-project.org mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting-guide.html and provide commented, minimal, self-contained, reproducible code.
