[BlindMath] Do Two line segments intersect?

[ckgoodwin85 at gmail.com]

Hi,

I am writing a mapping application and I need to find out if two line
segments intersect.

Segment 1 has points A and B

Segment 2 has points C and D.

 

Following a section on:

https://stackoverflow.com/questions/3838329/how-can-i-check-if-two-segments-
intersect

 

It states:

Suppose the two segments have endpoints A,B and C,D. The numerically robust
way to determine intersection is to check the sign of the four determinants:

| Ax-Cx  Bx-Cx |    | Ax-Dx  Bx-Dx |

| Ay-Cy  By-Cy |    | Ay-Dy  By-Dy |

 

| Cx-Ax  Dx-Ax |    | Cx-Bx  Dx-Bx |

| Cy-Ay  Dy-Ay |    | Cy-By  Dy-By |

For intersection, each determinant on the left must have the opposite sign
of the one to the right, but there need not be any relationship between the
two lines. You are basically checking each point of a segment against the
other segment to make sure they lie on opposite sides of the line defined by
the other segment.

End quote.

 

This isn't that clear.  I am not familiar with determinants other than they
are like a matrix.  I don't get what is meant by left and right in this
case.

I have interpreted the first one :

| Ax-Cx  Bx-Cx |    | Ax-Dx  Bx-Dx |

As

(Ax-Cx)*(Bx-Cx) - (Ax-Dx)*(Bx-Dx)

 

Is that the right way to read it?

I have mocked this up in a spreadsheet and it is tantalisingly close in
giving me something useful.  For example, when the two segments clearly
cross each other, all 4 of my interpretations of the calculations equal
zero.

I get a variety of behaviour though when one point from segment 1 is on top
of a point from segment 2.  Also strange result when the two segments
exactly or partially overlap.

 

So this is vaguely an accessibility question because I'm trying to interpret
a web page but is actually a plea for help on getting a working algorithm.

Many thanks for anyone who finds this of interest and can help.

Best, Chris