0

I have two arrays as follows:

X1 = np.array([[x11, x12, x13 ... x1n],[y11, y12, y13, ... , y1n]])

X2 = np.array([[x21, x22, x23 ... x2n],[y21, y22, y23, ... , y2n]])

I would like to basically conceptualize these as piecewise linear functions and come up with an intersection point intercept:

intercept = (x_int, y_int)

Every search I do regarding array intersection gives entirely unrelated results, since the intersection of two arrays also has the meaning of finding elements common to both arrays (rather than an intersection point).

I also found this interesting post, but it seems too complex for my application. If I had to implement this, I think I could since it would involve repeated calculations of line equations and intersections of points between line equations. However I'm first trying to check if some robust implementation already exists in a well-tested library, since my poor attempt might take hours/days to achieve and then not necessarily be applicable for any dataset.

Has this already been implemented in python?

hpaulj
  • 221,503
  • 14
  • 230
  • 353
user32882
  • 5,094
  • 5
  • 43
  • 82
  • If you can convert your Numpy arrays to functions, maybe this is useful? https://scipy-cookbook.readthedocs.io/items/Intersection.html – Antje Mar 18 '19 at 16:11
  • This post is also helpful https://stackoverflow.com/questions/43016174/finding-the-intersection-point-between-line-and-piecewise-linear-curves – user32882 Mar 18 '19 at 16:30
  • Your phrasing seems to suggest the existence of a single intersection point; but that cannot be assumed for the general case. As for strategies to tackle this, it really depends on the expected size of the arrays. If they are small or assumptions can be made, such as x always sorted and increasing, simple solutions may apply. But if these are arbitrary piecewise curves, a separate broad-phase collision algorithm to avoid O(n^2) performance is almost mandatory. – Eelco Hoogendoorn Mar 18 '19 at 21:03
  • It doesnt have to be one intersection point. It can be an array of intersection points – user32882 Mar 19 '19 at 06:17

1 Answers1

0

Step 1: work with the union of x1 and x2.
Step 2: linearly interpolate to find y1 and y2 for each point in the union.
Step 3: find where y1 - y2 changes sign.
Step 4: solve the linear equations for the intersection. 

import numpy as np

def intersect_piecewise(X1, X2):
    x = np.union1d(X1[0], X2[0])
    y1 = np.interp(x, X1[0], X1[1])
    y2 = np.interp(x, X2[0], X2[1])
    dy = y1 - y2

    ind = (dy[:-1] * dy[1:] < 0).nonzero()[0]
    x1, x2 = x[ind], x[ind+1]
    dy1, dy2 = dy[ind], dy[ind+1]
    y11, y12 = y1[ind], y1[ind+1]
    y21, y22 = y2[ind], y2[ind+1]

    x_int = x1 - (x2 - x1) * dy1 / (dy2 - dy1)
    y_int = y11 + (y12 - y11) * (x_int - x1) / (x2 - x1)
    return x_int, y_int

the equations you need to solve are
(x_int - x1) / (x2 - x1) = (0 - dy1) / (dy2 - dy1)
= (y_int - y11) / (y12 - y11) = (y_int - y21) / (y22 - y21)

Edit: Let's try it out

import matplotlib.pyplot as plt

x = np.linspace(-2, 2, 17)
X1 = np.stack((x[::2], x[::2]**2))
X2 = np.stack((x[1::2], 4 - x[1::2]**2))
x_int, y_int = intersect_piecewise(X1, X2)

plt.plot(X1[0], X1[1], 'bo-', X2[0], X2[1], 'bo-', x_int, y_int, 'rs')

Plot of intersection

Subhaneil Lahiri
  • 408
  • 3
  • 10