Path: news.mathworks.com!not-for-mail
From: "Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid>
Newsgroups: comp.soft-sys.matlab
Subject: Re: Self intersection of a 2d curve
Date: Sun, 24 Feb 2008 20:58:05 +0000 (UTC)
Organization: The MathWorks, Inc.
Lines: 34
Message-ID: <fpslot$iub$1@fred.mathworks.com>
References: <e0c27f69-1502-4b74-883b-92b8f0afae57@n75g2000hsh.googlegroups.com>
Reply-To: "Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid>
NNTP-Posting-Host: webapp-02-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1203886685 19403 172.30.248.37 (24 Feb 2008 20:58:05 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Sun, 24 Feb 2008 20:58:05 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 1187260
Xref: news.mathworks.com comp.soft-sys.matlab:453427


Inf <infinitysquared@gmail.com> wrote in message 
<e0c27f69-1502-4b74-883b-92b8f0afae57@n75g2000hsh.googlegroups.c
om>...
> Dear All,
> 
> I have a curve in 2d that is piecewise linear, consisting
> of lines joining the points (x1,y1), (x2,y2),(x3,y3),...
> 
> I would like to obtain estimates of the coordinates
> of the points where this curve intersects with itself.
> 
> Any help is appreciated.
> 
> Inf.
-------
  With linear segments, you can get exact values rather than merely estimates.  
For any pair of line segments, you need to know whether they intersect and if 
so where that intersection is located.  If P1 = (X1,Y1) and P2 = (X2,Y2) are the 
endpoints of one segment and P3 = (X3,Y3) and P4 = (X4,Y4) are the 
endpoints of the another segment, then they intersect if det
([X1,Y1,1,X2,Y2,1,X3,Y3,1]) and det([X1,Y1,1,X2,Y2,1,X4,Y4,1]) are of 
opposite sign, and similarly det([X1,Y1,1,X3,Y3,1,X4,Y4,1]) and det
([X2,Y2,1,X3,Y3,1,X4,Y4,1]) are of opposite sign.  The point of intersection 
would be the solution, (X,Y), to the equations

(Y2-Y1)*X - (X2-X1)*Y = X1*Y2-X2*Y1
(Y4-Y3)*X - (X4-X3)*Y = X3*Y4-X3*Y4

  So you should apply these tests to all possible pairs of line segment 
endpoints, or at least those where you suspect an intersection may occur.

Roger Stafford