How to determine based on pairs of coordinates if there is an intersection between the two?

Question

I have two line segments that are represented by two x,y coordinates, like so:

[(x1,y1),(x2,y2)] //start & end of first line
[(x3,y3),(x4,y4)] //start & end of second line

What is the most efficient way to determine if there is an intersection in these lines?

Answer 1

There is an intersection iff

(((X3-X1) * (Y2-Y1)-(Y3-Y1) * (X2-X1)) * ((X4-X1) * (Y2-Y1)-(Y4-Y1) * (X2-X1)) <= 0)

and

(((X1-X3) * (Y4-Y3)-(Y1-Y3) * (X4-X3)) * ((X2-X3) * (Y4-Y3)-(Y2-Y3) * (X4-X3)) <= 0)

Answer 2

Take the triangle formed by the first vector/line and endpoint of the line you're checking for a collision, and take its area via determinant. Compare its area to the area of the triangle formed with the other endpoint. If they are both positive/negative, then there is no intersection. If their signs are different, then there MIGHT be an intersection.

If their signs are different, do the same thing as above, except using the endpoints of the original vector instead of the endpoints of the line. (And using the whole line instead of the original vector).

If their signs are different, then there is definitely an intersection, and if they are the same, then there is no intersection.

Useful links: Taking the determinant of a triangle: Here

Evaluating a determinant: Here

Let me know if anything doesn't make sense!