Thread Subject: only 2 line intersection

Hello!

I wonder if there is a built in functionality for getting a boolean value if two lines intersect.

Example an array = [2 3 1 5;2 4 4 4]
Where the first row is the x-cord and the second the y-cord.

Im not interested on finding the intersection point but only on getting the boolean value.

Thanks

*Tried File exchange could not find anything

"Allonii Andersson" <allonii@hotmail.com> wrote in message <golnib$ffp$1@fred.mathworks.com>...
> Hello!
>
> I wonder if there is a built in functionality for getting a boolean value if two lines intersect.
>
> Example an array = [2 3 1 5;2 4 4 4]
> Where the first row is the x-cord and the second the y-cord.
>
> Im not interested on finding the intersection point but only on getting the boolean value.
>
> Thanks
>
> *Tried File exchange could not find anything

You might need to explain what you are after a little more clearly. How does one form a line from the x and y coordinates you have listed? Is it by forming the three line segments which connect the 4 points, or something else?

> You might need to explain what you are after a little more clearly. How does one >form a line from the x and y coordinates you have listed? Is it by forming the three >line segments which connect the 4 points, or something else?

Sorry for that, the [2 3 1 5;2 4 4 4] forms
2 3 2 5
2 4 4 4

the first row are the x-cords and the second the y-cords as mentioned before.

the first two colums form a line and the two last colums form another line.

Line1 = from (2,2) to (3,4)
Line2 = from (2,4) to (5,4)

I want to check if these two lines intersect.

Thanks

"Allonii Andersson" <allonii@hotmail.com> wrote in message <golq11$2gi$1@fred.mathworks.com>...
> > You might need to explain what you are after a little more clearly. How does one >form a line from the x and y coordinates you have listed? Is it by forming the three >line segments which connect the 4 points, or something else?
>
> Sorry for that, the [2 3 1 5;2 4 4 4] forms
> 2 3 2 5
> 2 4 4 4
>
> the first row are the x-cords and the second the y-cords as mentioned before.
>
> the first two colums form a line and the two last colums form another line.
>
> Line1 = from (2,2) to (3,4)
> Line2 = from (2,4) to (5,4)
>
> I want to check if these two lines intersect.
>
> Thanks

Are these lines, rays, or line segments? See, for instance,
http://www.mathleague.com/help/geometry/basicterms.htm
http://mathworld.wolfram.com/Line.html

Lines intersect when they are not running parallel.

hth
Jos

"Allonii Andersson" <allonii@hotmail.com> wrote in message <golq11$2gi$1@fred.mathworks.com>...
> > You might need to explain what you are after a little more clearly. How does one >form a line from the x and y coordinates you have listed? Is it by forming the three >line segments which connect the 4 points, or something else?
>
> Sorry for that, the [2 3 1 5;2 4 4 4] forms
> 2 3 2 5
> 2 4 4 4
>
> the first row are the x-cords and the second the y-cords as mentioned before.
>
> the first two colums form a line and the two last colums form another line.
>
> Line1 = from (2,2) to (3,4)
> Line2 = from (2,4) to (5,4)
>
> I want to check if these two lines intersect.
>
> Thanks

The method described will fail if the lines are colinear. You would need a check for that circumstance if it is possible.
Assume that the lines are extended to infinity in both directions. Then they must meet at some point. By my quick algebra, the x coord of this intersection is
X = (x(1)*m21-x(3)*m43-y(1)+y(3))/(m21-m43);
where m21 is the slope of the first line
m21 = (y(2)-y(1))/(x(2)-x(1));
m43 is obviously the slope of the second line.

If the shorter lines are to intersect, then (assuming x(1)<x(2) and x(3)<x(4))
x(1)<X<x(2) and x(3)<X<x(4).
in code this could be
c = [x(1) X x(2)];
[ind ind] = sort(c);
if(ind(2)~=2), intersect = false; return;
c = [x(3) X x(4)];
[ind ind] = sort(c);
if(ind(2)~=2), intersect = false; return;
% Now check the Y coordinates
Y = m43*(X-x(3))+y(3);
c = [y(1) Y y(2)];
[ind ind] = sort(c);
if(ind(2)~=2), intersect = false; return;
c = [y(3) Y y(4)];
[ind ind] = sort(c);
if(ind(2)~=2), intersect = false; return;
% If gotten this far there must be an intersection
intersect = true;

Again, you will need some error checking because divide-by 0 is certainly possible.
Hth
Darren

"Darren Rowland" <darrenjremovethisrowland@hotmail.com> wrote in message <golsld$r82$1@fred.mathworks.com>...
> "Allonii Andersson" <allonii@hotmail.com> wrote in message <golq11$2gi$1@fred.mathworks.com>...
> > > You might need to explain what you are after a little more clearly. How does one >form a line from the x and y coordinates you have listed? Is it by forming the three >line segments which connect the 4 points, or something else?
> >
> > Sorry for that, the [2 3 1 5;2 4 4 4] forms
> > 2 3 2 5
> > 2 4 4 4
> >
> > the first row are the x-cords and the second the y-cords as mentioned before.
> >
> > the first two colums form a line and the two last colums form another line.
> >
> > Line1 = from (2,2) to (3,4)
> > Line2 = from (2,4) to (5,4)
> >
> > I want to check if these two lines intersect.
> >
> > Thanks
>
> The method described will fail if the lines are colinear. You would need a check for that circumstance if it is possible.
> Assume that the lines are extended to infinity in both directions. Then they must meet at some point. By my quick algebra, the x coord of this intersection is
> X = (x(1)*m21-x(3)*m43-y(1)+y(3))/(m21-m43);
> where m21 is the slope of the first line
> m21 = (y(2)-y(1))/(x(2)-x(1));
> m43 is obviously the slope of the second line.
>
> If the shorter lines are to intersect, then (assuming x(1)<x(2) and x(3)<x(4))
> x(1)<X<x(2) and x(3)<X<x(4).
> in code this could be
> c = [x(1) X x(2)];
> [ind ind] = sort(c);
> if(ind(2)~=2), intersect = false; return;
> c = [x(3) X x(4)];
> [ind ind] = sort(c);
> if(ind(2)~=2), intersect = false; return;
> % Now check the Y coordinates
> Y = m43*(X-x(3))+y(3);
> c = [y(1) Y y(2)];
> [ind ind] = sort(c);
> if(ind(2)~=2), intersect = false; return;
> c = [y(3) Y y(4)];
> [ind ind] = sort(c);
> if(ind(2)~=2), intersect = false; return;
> % If gotten this far there must be an intersection
> intersect = true;
>
> Again, you will need some error checking because divide-by 0 is certainly possible.
> Hth
> Darren


Thanks Darren this really helpt me.

Allonii

"Allonii Andersson" <allonii@hotmail.com> wrote in message <golq11$2gi$1@fred.mathworks.com>...
> > You might need to explain what you are after a little more clearly. How does one >form a line from the x and y coordinates you have listed? Is it by forming the three >line segments which connect the 4 points, or something else?
>
> Sorry for that, the [2 3 1 5;2 4 4 4] forms
> 2 3 2 5
> 2 4 4 4
>
> the first row are the x-cords and the second the y-cords as mentioned before.
>
> the first two colums form a line and the two last colums form another line.
>
> Line1 = from (2,2) to (3,4)
> Line2 = from (2,4) to (5,4)
>
> I want to check if these two lines intersect.
>
> Thanks

If all that you care about is if the lines drawn
through these points in a least squares sense
intersect at any point, then the solution is trivial.

They intersect if the correlation coefficient is
non-zero. Any non-zero correlation at all and
they MUST intersect at some point (perhaps
way out towards infinity, but they will intersect.)

If your question is really if the piecewise linear
curves drawn through these pairs of points
intersect, then the answer is completely
different. For that, you would use a tool
designed to solve that problem. Such a tool
is on the file exchange. There are several such
tools I believe, but one that I would trust is
found here:

http://www.mathworks.com/matlabcentral/fileexchange/11837

HTH,
John

"Allonii Andersson" <allonii@hotmail.com> wrote in message <golq11$2gi$1@fred.mathworks.com>...
> .......
> Line1 = from (2,2) to (3,4)
> Line2 = from (2,4) to (5,4)
>
> I want to check if these two lines intersect.
> .......

  The two line segments connecting the points P1 = (x1,y1) with P2 = (x2,y2) and P3 = (x3,y3) with P4 = (x4,y4), respectively, will intersect if and only if

 det([1,1,1;x1,x2,x3;y1,y2,y3])*det([1,1,1;x1,x2,x4;y1,y2,y4]) <= 0 and
 det([1,1,1;x1,x3,x4;y1,y3,y4])*det([1,1,1;x2,x3,x4;y2,y3,y4]) <= 0

  This is equivalent to requiring that P3 and P4 lie on opposite sides of the infinite line through P1P2 and that at the same time P1 and P2 lie on opposite sides of the infinite line P3P4. The signs of the above determinants determine this information and must be opposite in each case.

Roger Stafford

> The two line segments connecting the points P1 = (x1,y1) with P2 = (x2,y2) and P3 = (x3,y3) with P4 = (x4,y4), respectively, will intersect if and only if
>
> det([1,1,1;x1,x2,x3;y1,y2,y3])*det([1,1,1;x1,x2,x4;y1,y2,y4]) <= 0 and
> det([1,1,1;x1,x3,x4;y1,y3,y4])*det([1,1,1;x2,x3,x4;y2,y3,y4]) <= 0
>
> This is equivalent to requiring that P3 and P4 lie on opposite sides of the infinite line through P1P2 and that at the same time P1 and P2 lie on opposite sides of the infinite line P3P4. The signs of the above determinants determine this information and must be opposite in each case.
>
> Roger Stafford

Very nice insight Roger, as always ;)