Re: [R] minimum distance between line segments
Hi, this sounds like a standard problem in Computational Geometry - I guess game developers have to deal with something like this all the time. You may want to look at a textbook or two. An article with the promising title "On fast computation of distance between line segments" can be found here: http://dx.doi.org/10.1016/0020-0190(85)90032-8 I found that one via Wikipedia: http://en.wikipedia.org/wiki/Proximity_problems Good hunting! Stephan Am 08.03.2011 22:55, schrieb Darcy Webber: 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. Thanks in advance, Darcy. __ 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. __ 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.
Re: [R] minimum distance between line segments
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 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
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 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 designate
Re: [R] minimum distance between line segments
On Fri, Mar 11, 2011 at 2:46 AM, Mike Marchywka 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.
Re: [R] minimum distance between line segments
> 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. I wasn't too happy before since I thought there was a good and simple way to approach this and no one came up with it, including me. On further thought, I seem to recall that a vector approach should be quite general without "special cases." For example, describe the segments as R=a*n^ + B where n^ is a unit vector in the direction of the line, B an initial point, a a scalar describing single coordinate along the line, and R the point on line corresponding to a. This should avoid issues with infinite slopes and other issues. You should be able to derive, for each segment, a set of n^, B, amin, and amax . calculating d=|R1-R2 | as a vector expression should be trivial and then you can minimize and constrain "a." Presumably d as a function of a1 and a2 will allow you to verify you can limit to amin and amax and let you see how to generalize to 3D etc. Since the segment is described originally by 4 numbers and this representation uses 6, you have some freedom in how to do this. The first thought is taking the initial point as B and then amin is zero and amax could be 1 if you don't actually bother to normalize "n^" and just take it as (dx,dy). And again in 2D nonparallel lines intersect so the distance between them is likely to be zero until you limit their extents. I haven't done this in so long I forgot about vectors but I hate special cases when there is a more concise and general way to approach a prblem :) As always with free advice on the internet, caveat emptor, but I'd be curious to see if anyone knows better. I think someone else suggested checking if they interesct first but again this is motivated by an attempt to avoid special cases and get a better understanding of what is going on. > > Thanks in advance, > Darcy. > > __ > 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. __ 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.
Re: [R] minimum distance between line segments
> To: r-h...@stat.math.ethz.ch > From: hwborch...@googlemail.com > Date: Wed, 9 Mar 2011 17:45:53 + > Subject: Re: [R] minimum distance between line segments > > Darcy Webber gmail.com> writes: > > > 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. > > > > Thanks in advance, > > Darcy. > > > > A correct approach could proceed as follows: > > (1) Find out whether two segments intersect > (e.g., compute the intersection point of the extended lines and compare > its x-coords with those of the segment endpoints); > if they do, the distance is 0, otherwise set it to Inf. > (2) For each endpoint, compute the intersection point of the perpendicular > line through this point with the other segment line; if this point lies > on the other segment, take the distance, otherwise compute the distance > to the other two endpoints. > (3) The minimum of all those distances is what you seek. > > I have done a fast implementation, but the code is so crude that I would > not like to post it here. If you are really in need I could send it to you. LOL, I sent a private reply suggesting essentially the opposite approach since I discovered pmax and pmin. That is, parameterize the location along lines ofinifinte length and minimize the distance WRT the two locations ( one for each line). You can do this by hand, find them to be perp or probably find an R routine to minimze the distnace. Then, with your array of positions along the lines, limit them with pmin or pmax. Infinite lines always cross unless parallel, so you will probably do a lot of clipping, but stuff like that would probably become apparent as you work through it. If things fail or you want to extend to 3D, you have some starting point for improvement. This is probably a common issue in some fields, like graphics, thought there may be something packaged but no idea. > > --Hans Werner > > (I am not aware of a pure plane geometry package in R --- is there any?) > > __ > 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. __ 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.
Re: [R] minimum distance between line segments
Darcy Webber gmail.com> writes: > 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. > > Thanks in advance, > Darcy. > A correct approach could proceed as follows: (1) Find out whether two segments intersect (e.g., compute the intersection point of the extended lines and compare its x-coords with those of the segment endpoints); if they do, the distance is 0, otherwise set it to Inf. (2) For each endpoint, compute the intersection point of the perpendicular line through this point with the other segment line; if this point lies on the other segment, take the distance, otherwise compute the distance to the other two endpoints. (3) The minimum of all those distances is what you seek. I have done a fast implementation, but the code is so crude that I would not like to post it here. If you are really in need I could send it to you. --Hans Werner (I am not aware of a pure plane geometry package in R --- is there any?) __ 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.
[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. Thanks in advance, Darcy. __ 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.