How do I find the intersection of two line segments?

Question

Suppose we have two finite line segments defined each by two points (in two space). I would like to find a way to get the intersection point of those two lines. Eventually, I would like to extend this to work on sets of connected line segments.

I have found a good solution here: Python - matplotlib: find intersection of lineplots. However, this relies on scipy, which I believe requires BLAS, which for separate reasons I would like to avoid.

matplotlib has a module called Path, which has an intersects_path() function (http://matplotlib.org/api/path_api.html#matplotlib.path.Path.intersects_path) which returns true or false for the existence of an intersection, but not the specific location, which I require.

Does anyone know of a clean approach to this?

Any solution I am coming up with is lengthy, and if a solution already exists I would really prefer not to re-invent the wheel.

Thanks!

Answer 1

For the sake of completion, I thought I would post the final solution which I used.

Using Shapely (https://pypi.python.org/pypi/Shapely) the code can look as simple as this:

from shapely.geometry import LineString

line1 = LineString([(0,0), (1,0), (1,1)])
line2 = LineString([(0,1), (1,1)])

print(line1.intersection(line2))

Returns:

POINT (1 1)

The nice thing about this is that it will handle single point intersection, and intersection of segments seamlessly, and the same technique can be applied to much more complicated objects.