Re: determining if two line segments overlap

"gh14tq5@xxxxxxxxx" wrote:
>
> Hi,
>
> What is the best way to determine if two line segments overlap in the
> x-y plane. More specifically, suppose I know the coordinates of the
> endpoints of each line, e.g., p1a = (x1a,y1a), p2a = (x2a,y2a) and
> p1b=(x1b,y1b), p2b=(x2b,y2b). In my particular problem, I also know
> that if the line segments touch, then, either the two line segments are
> on the same ray or they share a common end point. In other words, the
> can't form a cross like figure. Also, neither line segment can be of
> zero length.
>
> At the moment, I'm doing the following procedure. First, I compute the
> midpoints of each segment : m1 = (p1a+p1b)/2 and m2 = (p2a+p2b)/2.
> Next, I compute the vector between the midpoints u = (m2-m1)/|m2-m1| and
> the length of the vector R=|u| as well as the unit vector of one of the
> segments (say the first) v = (p1b-p1a)/|p1b-p1a|. The lengths of the
> segments are d1=|p1b-p1a| and d2=|p2b-p2a|. With this information, I do
> the following comparison (Fortran notation),
>
> if ( abs(u cross v) .le. R*eps .and. R .le. (d1+d2)/2.) then
> there is an overlap
>
> I'm mainly worried about issues arising due to the computers finite
> numerical precision. For example, it's possible that even if the both
> segments lie on the same ray, abs(u cross v) may not be exactly zero due
> to precision errors, so I introduced the variable eps as a fudge factor,
> but I've never been quite sure exactly what value to set it at. I've
> been using 1e-6 (double precision, x86) which seems to be work, but I'm
> always a little worried about it. Also, if the overlap is very, very
> small, I'm a little worried that the second comparison R .le. (d1+d2)/2.
> may be subject to numerical errors.
>
> I would consider two segments that touch only at an endpoint but that
> lie on the same ray to be overlapping, but two segments that touch only
> at an endpoint but do not lie on the same ray to be not overlapping. So,
> two segments that touch but lie on different rays could pass the second
> test and also the first test (possibly I think depending on eps) if one
> segment is very, very short and the other segment is very very long.
> This would be a mistaken overlap indication.
>
> Any advice?
>
> Thanks in advance,
> John

There is an algorithm for this in my (as yet unpublished) CiSE column
"Feeling No Pain in the Argand Plane". It was an illustration of how
you can simplify 2-dimensional vectorial computations with complex
arithmetic.

http://galileo.phys.virginia.edu/classes/551.jvn.fall01/complex1.pdf


--
Julian V. Noble
Professor Emeritus of Physics
jvn@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
^^^^^^^^^^^^^^^^^^
http://galileo.phys.virginia.edu/~jvn/

"For there was never yet philosopher that could endure the
toothache patiently."

-- Wm. Shakespeare, Much Ado about Nothing. Act v. Sc. 1.
.

Relevant Pages

  • Re: determining if two line segments overlap
    ... >that if the line segments touch, then, either the two line segments are ... > on the same ray or they share a common end point. ... >segments lie on the same ray, absmay not be exactly zero due ... Also, if the overlap is very, very ...
    (sci.math.num-analysis)
  • determining if two line segments overlap
    ... What is the best way to determine if two line segments overlap in the ... on the same ray or they share a common end point. ... segments lie on the same ray, absmay not be exactly zero due ...
    (sci.math.num-analysis)
  • Re: pwelch PSD estimator syntax, please someone?
    ... if you use 8 segments to estimate the spectrum in a 1024 sample ... This also leads to the fact that the number of overlap points, M, is given ... I sometimes feel MATLAB Help documentation really comes examples ...
    (comp.soft-sys.matlab)
  • RE: Any way to automate set intersection discovery?
    ... what data are you using to determine the overlap? ... would then generate a series of queries that append data to that table, ... to tbl_n to get the records that fall in segments ... a single command or query that would give me tables for each section, ...
    (microsoft.public.access.queries)
  • Re: Click on Map area to chose filter for Query
    ... books show some standard methods for determining whether or not a point ... is in a region bounded by line segments. ... boundary then it must lie outside the region. ... code would need to loop through each ProvinceID. ...
    (comp.databases.ms-access)