Найти пересечение точек на графе python, сгенерированных списком точек

Question

Я пытаюсь найти пересечение между двумя строками, которые были сгенерированы списком точек.

У меня было два списка точек, а затем я график их с помощью

import matplotlib.pyplot as plt 
import numpy as np 

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

Теперь я генерироваться график, который выглядит примерно так

Моя цель состоит в том, чтобы найти все точки, где это эти два графика пересекаются теперь (пересечения синей и зеленой линий). На первый взгляд может показаться, что точки будут просто точками, находящимися в обоих массивах a и b, но могут возникать некоторые пересечения, которые не встречаются в массивах при создании линий между точками.

Как мне найти все перекрестки?

Примечание: Я ищу решение, которое работает в Python 2.7

Answer 1

Если оба графика используют одни и те же значения X-оси (различные функции оцениваемые на одном массиве), вы можете сделать это вручную путем непосредственного вычисления пересечения каждой последовательной пары сегментов. Вы должны рассмотреть несколько случаев (если сегменты параллельны и т. Д.). Пересечение можно рассчитать с помощью уравнения линий на плоскости. Вы можете добавить этот метод для общего случая, взяв объединение значений по оси X и вычислив необходимые значения.

Простая (но, вероятно, менее эффективная, если вам приходится ее вычислять миллионы раз), заключается в том, чтобы полагаться на библиотеку shapely. Этот метод также работает, если пути не используют одни и те же значения оси X. Простой пример того, как это сделать.

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 

Это вернет

[(1.6666666666666667, 1.6666666666666665), (6.666666666666667, 6.666666666666667)] 

Answer 2

Вычитание значения обоих массивов и найти нули разностного массива.

Вы можете использовать scipy.signal.argrelmin, чтобы найти локальные минимумы абсолютного значения разностного массива.