Re: determining if two line segments overlap
- From: spellucci@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx (Peter Spellucci)
- Date: Tue, 13 Dec 2005 14:10:07 +0000 (UTC)
In article <dnmf9s$c4u$1@xxxxxxxxxxxxxxxxxx>,
"gh14tq5@xxxxxxxxx" <gh14tq5@xxxxxxxxx> writes:
>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
try this:
first step: extend the line segments to twosided infinite lines:
line1: (x,y)=(x1a,y1a)+t*(x1b-x1a,y1b-y1a) t real
line2: (x,y)=(x2a,y2a)+s*(x2b-x2a,y2b-y2a) s real
your finite segments are given by the conditions 0<=t<=1 and 0<=s<=1.
if the two direction vectors
are parallel, i.e.
((x1b-x1a)*(y2b-y2a)-(x2b-x2a)*(y1b-y1a))=0
then there will be no overlap possible at all .
if not the difference vector of the initial points is also parallel to these.
i.e. also
((x1b-x1a)*(y2a-y1a)-(y1b-y1a)*(x2a-x1a))=0.
in this exceptional case the two extended infinite lines coincide.
an overlap will occur if and only if one of the end points of one segment can
be expressed as as a point of the other segment with the parameter in [0,1]
this gives at most four equations in one variable each.
otherwise, if the two direction vectors are not parallel, then the two
extended lines will intersect:
set line1=line2 and solve for t and s. this is solve
the two equations in the two unknowns t,s :
[x1b-x1a -x2b+x2a][t ] = [ x2a-x1a]
[y1b-y1a -y2b+y2a][s ] [ y2a-y1a]
for t and s. if 0<t<=1 and 0<=s<=1 then this pair t,s gives the
coordinates of the intersection point of the two finite segments,
otherwise the two finite segments do not overlap.
in the sense of linear optimization algorithms you have the feasibility problem:
the above system of two linear equations in two unknowns t,s plus the
conditions
0<=t<=1, 0<=s<=1
but using an LP feasibility phase for doing this is a kind overshoot.
hth
peter
.
- References:
- determining if two line segments overlap
- From: gh14tq5@xxxxxxxxx
- determining if two line segments overlap
- Prev by Date: Announcement: Experimental Chaos Conference
- Next by Date: Re: Least Squares fit to Legendre Polynomial
- Previous by thread: determining if two line segments overlap
- Next by thread: Re: determining if two line segments overlap
- Index(es):
Relevant Pages
|
