15

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!

Community
  • 1
  • 1
Sergiy
  • 1,029
  • 1
  • 12
  • 19
  • 2
    This should be trivial, no? 1) Using the endpoints, solve for the `slope` and `y-intercept` of each line segment. 2) Solve for the intersection once you know the equation of each line 3) Check that this intersection lies along both lines (and not outside the segment) – Cory Kramer Mar 15 '14 at 00:04
  • As Cyber said this should be pretty trivial. Take a look here and see if you understand http://stackoverflow.com/questions/4543506/algorithm-for-intersection-of-2-lines – Michael Aquilina Mar 15 '14 at 00:06
  • 1
    shapely can do this very quickly, https://pypi.python.org/pypi/Shapely – HYRY Mar 15 '14 at 12:25
  • Shapely is exactly the wheel I did not want to reinvent. Great package. Thanks! – Sergiy Mar 17 '14 at 16:52

1 Answers1

26

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.

Sergiy
  • 1,029
  • 1
  • 12
  • 19
  • FYI for those installing Shapely: You only need to install the C API dependency libgeos-c1. See: http://stackoverflow.com/q/17777613/892482 – Bort Sep 30 '16 at 19:28