[R] minimum distance between line segments

[Mike Marchywka]

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


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