How to determine if two 2D line segments are overlap?

Question

I'm working on a task (with python3) which needs to check if 2 line segments are overlap and can return the 2 end points. The line segment has coordinates in (x1, y1, x2, y2) form, which (x1,y1) and (x2,y2) is the coordinates of its end points. The 2 lines are pretty close to each other, but might not be parallel. You can see the picture to understand which case is called overlap. I think the overlap definition can be said "if the projection of one point lies between 2 endpoints of the other line" Example:

overlap1 = numpy.array([[1,4,5,5], [7,7,3,5]])
overlap2 = numpy.array([[8,1,12,2], [9,2,11,3]])

non_overlap = numpy.array([[1,2,5,3], [6,3,9,4]])

My goal is to find the 2 furthest points of 4 points if they are overlap, as the red circle shows in the image. Currently my idea is:

1. calculate distance from all points (AB, AC, AD, BC, BD, CD) and check to find the max distance, called max_len
2. Calculate: test = len_AB + len_CD - max_len
3. If test > 0, they are overlap, otherwise they aren't

This alg works pretty good to check the overlap condition but difficult to return the 2 most end points.

What do you think about this problem? Thank you.

Answer 1

Consider the next code for calculation of relative position of projection of point (xp, yp) onto (x1y1-x2y2) line segment. It uses dot (scalar) product.

Returns None when segment is really a point

Returns parameter 0..1 when projection lies inside segment

Returns values off this interval if projection lies on the line beyond segment. So negative values and > 1 are for your red circled points.

(picture with another point names)

def proj(x1, y1, x2, y2, xp, yp):
    x12 = x2 - x1
    y12 = y2 - y1
    dotp = x12 * (xp - x1) + y12 * (yp - y1)
    dot12 = x12 * x12 + y12 * y12
    if dot12:
        return dotp / dot12
    else:
        return None

Answer 2

Thank you for reading my question. I think it's a more about math than programming problem, but after a while, I have found a good simple algorithm to deal with it. My solution is heavily based on numpy array in python for efficient calculation. I'm not sure if there's a better way with more math approach, but hopefully this solution is still helpful in the future.

The idea is to find distance from all point combination (there are 6 distance from 4 points). I create an numpy array of that combination, find the Euclidean distance, find the maximum distance from that, and check the overlap by condition: len_AB + len_CD - max(distance).

import numpy as np
def check_overlap(line1, line2):
    combination = np.array([line1,
                         line2,
                         [line1[0], line1[1], line2[0], line2[1]],
                         [line1[0], line1[1], line2[2], line2[3]],
                         [line1[2], line1[3], line2[0], line2[1]],
                         [line1[2], line1[3], line2[2], line2[3]]])
    distance = np.sqrt((combination[:,0] - combination[:,2])**2 + (combination[:,1] - combination[:,3])**2)
    max = np.amax(distance)
    overlap = distance[0] + distance[1] - max
    endpoint = combination[np.argmax(distance)]
    return (overlap >= 0), endpoint

Answer 3

It looks like you are just using x coordinates, so if A<C<B<D or A<C<D<B ir overlaps, otherwise it does not (such as A<B<C<D)