Path: news.mathworks.com!newsfeed-00.mathworks.com!newscon02.news.prodigy.net!prodigy.net!border1.nntp.dca.giganews.com!nntp.giganews.com!postnews.google.com!u69g2000hse.googlegroups.com!not-for-mail
From: Inf <infinitysquared@gmail.com>
Newsgroups: comp.soft-sys.matlab
Subject: Re: Self intersection of a 2d curve
Date: Mon, 25 Feb 2008 10:09:34 -0800 (PST)
Organization: http://groups.google.com
Lines: 46
Message-ID: <e2ed79c7-49c3-4457-a498-d7d5a34b2af6@u69g2000hse.googlegroups.com>
References: <e0c27f69-1502-4b74-883b-92b8f0afae57@n75g2000hsh.googlegroups.com> 
NNTP-Posting-Host: 139.184.30.136
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
X-Trace: posting.google.com 1203962974 10794 127.0.0.1 (25 Feb 2008 18:09:34 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: Mon, 25 Feb 2008 18:09:34 +0000 (UTC)
Complaints-To: groups-abuse@google.com
Injection-Info: u69g2000hse.googlegroups.com; posting-host=139.184.30.136; 
User-Agent: G2/1.0
X-HTTP-UserAgent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-GB; rv:1.8.1.12) 
X-HTTP-Via: 1.1 proxy6.uscs.susx.ac.uk:8080 (squid/2.6.STABLE18)
Bytes: 3003
Xref: news.mathworks.com comp.soft-sys.matlab:453546


On 24 Feb, 20:58, "Roger Stafford"
<ellieandrogerxy...@mindspring.com.invalid> wrote:
> Inf<infinitysqua...@gmail.com> wrote in message
>
> <e0c27f69-1502-4b74-883b-92b8f0afa...@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

Many thanks Roger.

I stumbled onto something like this.
I used a slightly different procedure, where I determined the point
of
intersection of the two lines, then checked to see if the x coord
lies in the range of covering both line segments.

Inf.