[BlindMath] Do Two line segments intersect?

[ckgoodwin85 at gmail.com]

Hi,

I have this working in Excel now.  

If line segment 1, l1, is made up of points p1 and p2, and line segment s2 is made up of points p3 and p4, then:

If P3 lies somewhere on s1 then D1 is 0.

If p4 lies somewhere on l1 then d2 is 0.

If p1 lies somewhere on s2 then d3 is 0.

If p2 lies somewhere on s2 then d4 is 0.

These conditions can combine, so for example:

If p1 and p3 are the same then both d1 and d3 are 0.

And if d1 has opposite sign to d2 and d3 has opposite sign to d4 then the segments cross.

Anything else and they don’t intersect.

That gives me all I need to determine if my line segments touch or cross.

I’ll implement this in my C++ application next.    And if it works, I’ll be able to tell if my user is inside or outside a polygon.

Lots of rare cases to consider but I’m on my way.

And as you say, floating point arithmetic to consider as well.

Many thanks for your help, Chris 

 

From: ckgoodwin85 at gmail.com <ckgoodwin85 at gmail.com> 
Sent: Thursday, January 18, 2024 6:47 PM
To: 'Blind Math list for those interested in mathematics' <blindmath at nfbnet.org>
Subject: RE: [BlindMath] Do Two line segments intersect?

 

Repeat of my reply to Jonathan, this time to the group…

 

Hi Jonathan,

 

Many thanks for your help.  I think you have told me the crucial info I need.

 

I understand now how the 4 determinants are written.  A top left, top right, bottom left and bottom right.

And a determinant is

AB

CD

Expanded to

AD-BC

 

So the top left determinant has

A = Ax-Cx

B=Bx-Cx

C=Ay-Cy

D=By-Cy

So I just have to use this approach to write out all 4 determinants.

That is great.  Many thanks.

 

As for floating point.  Yes.  I was watching a variable earlier this evening which had a value that should have been 2.5 but was shown as 2.49999999999999.

I’ll tackle this once I’ve sorted the determinants and have that working with test data.  I think it means I can’t use ‘=’ and only ‘<’ and ‘>’.

I may not be able to get to this again before the weekend but I’m confident I’m on the right track thanks to your help.

Best, Chris

 

From: Jonathan Fine <jfine2358 at gmail.com <mailto:jfine2358 at gmail.com> > 
Sent: Wednesday, January 17, 2024 9:24 PM
To: Blind Math list for those interested in mathematics <blindmath at nfbnet.org <mailto:blindmath at nfbnet.org> >
Cc: ckgoodwin85 at gmail.com <mailto:ckgoodwin85 at gmail.com> 
Subject: Re: [BlindMath] Do Two line segments intersect?

 

Hi Chris

 

I'm happy to be your sighted assistant for this. I'll learn something from it.

 

Here's a start, from my phone.

 

To understand the algorithm you will need to know what it is that the determinant calculates.

 

To implement the algorithm you will need to know how to compute a determinant. 

 

You might also need to know something about the hazards of floating point arithmetic. 

 

All the above are equally true for sighted and blind.

 

You quoted some determinants from stack overflow. Unfortunately they've been written as ASCII art, and you've misread them.

 

In ASCII art the basic 2x2 determinant is

 

| a b |

| c d |

 

It's value is (a*d - b*c).

 

The quote from stack overflow you should read as columns, not rows.

 

All this might not be enough to help you. Please let me know how you get on, and I'll respond further tomorrow. 

 

Best wishes

 

Jonathan