Determine if two lines intersect

Question

I've seen many postings here on stackoverflow, which are discussing this topic. I took a solution from stackoverflow, but I couldn't find the posting. It was to say: If two lines are intersecting, then the crossproduct produces for the left and the right side two different results. One positive and one negative. Otherwise both have the same sign. So far it is okay. The used formula is, where AB is one line and CD another.

dotproductleft = (B.x-A.x)(C.y-B.y)-(B.y-A.y)(C.x-B.x)

dotproductright = (B.x-A.x)(D.y-B.y)-(B.y-A.y)(D.x-B.x)

If I calculate this for the following given GPS coordinates I get an intersection, in a case where no intersection is possible.

A: x: 15.4433917 y: 47.0697272

B: x: 15.4433661 y: 47.0697722

C: x: 15.4434363 y: 47.0696776

D: x: 15.442966 y: 47.0700098

If I draw it on Google Maps Engine, I can see that there definitely no intersection between these lines.

The results for dotproductleft: -7.372399999828474E-10 and for dotproductright: 1.1921940000328E-8

It is working for other examples very well, but here I've seen that it is not working right. But I couldn't spot any error in the formula.

Answer 1

The lines which contain any line segment (e.g. AB and CD) will always intersect (unless they are parallel).

You want to check if the line segments intersect. This is easy to do by finding the point of intersection and checking if it lies on both line segments.

So, using your example, the two lines (on which line segments AB and CD lie on) intersect at P = (15.4434,47.0697). Now, if P lies on AB then the dot product of PA and PB is negative (since the angle between PA and PB is 180° and cos(180°)=-1).

If you compute the dot product of PA and PB, you will get a positive number (thus it does not lie on AB). However, the dot product of PC and PD gives you a negative number (thus it lies on CD).

Thus, you can check if the line segments intersect if the aforementioned dot products (with the point of intersection) are negative.