1

I'm trying to find the intersection between two lines that were generated by a list of points.

I had two list of points, and then I plotted them using

import matplotlib.pyplot as plt
import numpy as np

a = arrayOfPoints1
plt.plot(*zip(*a))
b = arrayOfPoints2
plt.plot(*zip(*b))
plt.show()

Now I've generated a graph that looks something like thisenter image description here

My goal is to find all the points where these two graphs intersect now (the blue and green line intersections). At first glance, it might seem like the points would just be the points that are in both array a and b, but there could be some intersections that occur that are not in the arrays when the lines between the points are generated.

How do I go about finding all the intersections?

Note: I'm looking for a solution that works in Python 2.7

user3370201
  • 59
  • 9

2 Answers2

1

If both graphs use the same X-axis values (different functions evaluated on the same array), you could do it manually by direct computation of the intersection of each consecutive pair of segments. You have to consider several cases (if the segments are parallel, etc). Intersection can be calculated with the equation of lines in the plane. You can addapt this method for the general case, by taking the union of both X-axis values and computing the needed values.

An easier (but probably less efficient if you have to compute it millions of times), is to rely on shapely library. This method also works if the paths do not use the same X-axis values. A simple example of how to do it below.

from shapely.geometry import LineString

l1 = LineString([(0,0), (10,10)])
l2 = LineString([(1,0), (5,10), (10,0)])

intersection = l1.intersection(l2)
intersect_points = [list(p.coords)[0] for p in intersection]
print intersect_points

This will return 

[(1.6666666666666667, 1.6666666666666665), (6.666666666666667, 6.666666666666667)]
eguaio
  • 3,754
  • 1
  • 24
  • 38
  • Could you explain what you mean by "direct computation of the intersection of each consecutive pair of segments"? I'm fairly new to graphing and math libraries in python so I'm not sure I fully grasp what you're suggesting. – user3370201 Dec 07 '15 at 07:06
  • Sure, I mean: http://stackoverflow.com/questions/3252194/numpy-and-line-intersections or http://stackoverflow.com/questions/20677795/find-the-point-of-intersecting-lines. You will need to do it for each pair of consecutive points. I highly recommend you to go with the `shapely` solution, though. Reliable and simple. – eguaio Dec 07 '15 at 07:12
-2

Subtract the values of both the arrays and find the zeros of the difference array.

You can use scipy.signal.argrelmin to find the local minima of the absolute value of the difference array.

Brad Solomon
  • 38,521
  • 31
  • 149
  • 235
Prakhar Godara
  • 21
  • 3