CODEWITHSUNDEEP
pythonnumpy
user2881553
user2881553

Reputation:

Efficient way of finding the intersections between polynomial curves?

The fitting by np.polyfit() returns me several polynomial expressions. I then plot the polynomial curves with matplotlib:

y_fit = np.arange(min(y), max(y), .1) # use more points for a smoother plot
x_fit = p[0](y_fit)
axes.plot(x_fit, y_fit, '-', color='green')

What I get is this

Polynomial Curves

They are actually the boundaries of a passage. I expect to see a closed blue polygon inside the green closed polygon. Using human intelligence, it is quite clear how to intersect them and remove the extra parts.

A simple and brutal method that I have tried is to solve pairwise coupled non-linear equation with fsolve(). However, this is quite infeasible, as I have a lot of polynomial curves, and thus solving them pairwise is too expensive. Also, it is clear that not all the intersections are important. (some intersections even hardly make sense!)

So is it possible for me to do this (get the crucial intersections only) efficiently?

Upvotes: 2

Views: 5023

Answers (1)

pv.
pv.

Reputation: 35125

You can find intersections of polynomial curves by finding roots:

import numpy as np

# fake data
x = np.linspace(0, 4, 20)
y1 = np.cos(x)
y2 = np.sin(x)

# polynomial fits
p1 = np.polynomial.Polynomial.fit(x, y1, 3)
p2 = np.polynomial.Polynomial.fit(x, y2, 3)

# find roots
x_0 = (p1 - p2).roots()
print(x_0)

# select roots in specific range only
x_0 = x_0[(x_0 > 0) & (x_0 < 4)]

# plot
xx = np.linspace(0, 4, 2000)

import matplotlib.pyplot as plt
plt.plot(x, y1, 'b.', x, y2, 'g.')
plt.plot(xx, p1(xx), xx, p2(xx))
plt.plot(x_0, p1(x_0), 'ko')
plt.show()

For polynomials obtained via np.polyfit, use np.roots.

Upvotes: 4

Related Questions