Thread Subject: Self intersection of a 2d curve

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.

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

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.

Inf <infinitysquared@gmail.com> wrote in message <e2ed79c7-49c3-4457-
a498-d7d5a34b2af6@u69g2000hse.googlegroups.com>...
> 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.
--------
  Yes, that would work.

  The determinant expressions I gave you are capable of greater accuracy,
because each is proportional to the orthogonal distance from an endpoint of
one segment to the extended line along the other segment. For example, det
([X1,Y1,1,X2,Y2,1,X3,Y3,1]) is equal to the signed orthogonal distance from
point P3 to the line through P1 and P2 multiplied by the length of segment
P1P2 - or what is equivalent, twice the signed (counterclockwise) area of
triangle P1P2P3.

  This accuracy difference would become evident in the case of vertical or
nearly vertical segments. However, you could probably achieve almost the
same accuracy improvement with your method by modifying it to use either
x-values or y-values of an intersection depending on whether the absolute
value of the slope of the segment being tested is less than or greater than 1,
respectively.

Roger Stafford

In article
<e0c27f69-1502-4b74-883b-92b8f0afae57@n75g2000hsh.googlegroups.com>,
 Inf <infinitysquared@gmail.com> wrote:

> 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.


I just added the ability to find self-intersections to my
intersections.m, available on the FEX:

<http://www.mathworks.com/matlabcentral/fileexchange/loadFile.do?objectId
=11837&objectType=FILE>

(watch for wrapped URL)

--
Doug Schwarz
dmschwarz&ieee,org
Make obvious changes to get real email address.