[R] minimum distance between line segments

[Stephan Kolassa]

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 at 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.
>