#!/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)