Re: [R] minimum distance between line segments

From: Mike Marchywka <marchywka_at_hotmail.com>
Date: Wed, 09 Mar 2011 15:31:27 -0500



> To: r-help_at_stat.math.ethz.ch
> From: hwborchers_at_googlemail.com
> Date: Wed, 9 Mar 2011 17:45:53 +0000
> 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_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.
                                               



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. Received on Wed 09 Mar 2011 - 22:01:34 GMT

Archive maintained by Robert King, hosted by the discipline of statistics at the University of Newcastle, Australia.
Archive generated by hypermail 2.2.0, at Wed 09 Mar 2011 - 22:10:20 GMT.

Mailing list information is available at https://stat.ethz.ch/mailman/listinfo/r-help. Please read the posting guide before posting to the list.

list of date sections of archive