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

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