#!/usr/bin/env python3 # -*- coding: utf-8 -*- def edge_intersection(x1: int, y1: int, x2: int, y2: int, x3: int, y3: int, x4: int, y4: int) -> list: """Intersection point of two line segments in 2 dimensions params: ---------- x1, y1, x2, y2 -> coordinates of line a, p1 ->(x1, y1), p2 ->(x2, y2), x3, y3, x4, y4 -> coordinates of line b, p3 ->(x3, y3), p4 ->(x4, y4) Return: ---------- list A list contains x and y coordinates of the intersection point, but return an empty list if no intersection point. """ # None of lines' length could be 0. if ((x1 == x2 and y1 == y2) or (x3 == x4 and y3 == y4)): return [] # The denominators for the equations for ua and ub are the same. den = ((y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1)) # Lines are parallel when denominator equals to 0, # No intersection point if den == 0: return [] # Avoid the divide overflow ua = ((x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3)) / (den + 1e-16) ub = ((x2 - x1) * (y1 - y3) - (y2 - y1) * (x1 - x3)) / (den + 1e-16) # if ua and ub lie between 0 and 1. # Whichever one lies within that range then the corresponding line segment contains the intersection point. # If both lie within the range of 0 to 1 then the intersection point is within both line segments. if (ua < 0 or ua > 1 or ub < 0 or ub > 1): return [] # Return a list with the x and y coordinates of the intersection x = x1 + ua * (x2 - x1) y = y1 + ua * (y2 - y1) return [x, y] if __name__ == "__main__": line_a = [494, 117, 1051, 123] line_b = [1011, 133, 1011, 74] intersection_point = edge_intersection(*line_a, *line_b) print(intersection_point)