Finding intersection between straight line and contour

Question

I am trying to find the intersection point of a straight(dashed red) with the contour-line highlighted in red(see plot). I used .get_paths in the second plot to isolate said contour line form the others(second plot).

I have looked at a contour intersection problem, How to find all the intersection points between two contour-set in an efficient way, and have tried to use it as a base but have not been able to reproduce anything useful.

http://postimg.org/image/hz01fouvn/

http://postimg.org/image/m6utofwb7/

Does any one have any ideas?

relevant functions to recreate plot,

#for contour 
def p_0(num,t) :
    esc_p = np.sum((((-1)**n)*(np.exp(t)**n)*((math.factorial(n)*((n+1)**0.5))**-1)) for n in range(1,num,1))
    return esc_p+1

tau = np.arange(-2,3,0.1)
r=[]

p1 = p_0(51,tau)
p2 = p_0(51,tau)

for i in p1:
    temp_r=i/p2
    r.append(temp_r)

x,y= np.meshgrid(tau,tau)
cs = plt.contour(x, y, np.log(r),50,colors='k')
whichContour =20
pa = CS.collections[whichContour].get_paths()[0]
v = pa.vertices
xx = v[:, 0]
yy = v[:, 1]
plt.plot(xx, yy, 'r-', label='Crossing contour')

#straight line 
p=0.75
logp = (np.log(p*np.exp(tau)))
plt.plot(tau,logp)

Current attempt,

import matplotlib
import numpy as np
import matplotlib.cm as cm
import matplotlib.mlab as mlab
import matplotlib.pyplot as plt
import math

def intercepting_line() :
matplotlib.rcParams['xtick.direction'] = 'out'
matplotlib.rcParams['ytick.direction'] = 'out'

#fake data

delta = 0.025
x = np.arange(-3.0, 3.0, delta)
y = np.arange(-2.0, 2.0, delta)
X, Y = np.meshgrid(x, y)
Z1 = mlab.bivariate_normal(X, Y, 1.0, 1.0, 0.0, 0.0)
Z2 = mlab.bivariate_normal(X, Y, 1.5, 0.5, 1, 1)
Z = 10.0 * (Z2 - Z1)

#plot
cs = plt.contour(X,Y,Z)
whichContour = 2 # change this to find the right contour lines

#get the vertices to calculate an intercept with a line
p = cs.collections[whichContour].get_paths()[0]
#see: http://matplotlib.org/api/path_api.html#module-matplotlib.path
v = p.vertices
xx = v[:, 0]
yy = v[:, 1]

#this shows the innermost ring now
plt.plot(xx, yy, 'r--', label='inner ring')

#fake line
x = np.arange(-2, 3.0, 0.1)
y=lambda x,m:(m*x)
y=y(x,0.9)
lineMesh = np.meshgrid(x,y)
plt.plot(x,y,'r' ,label='line')

#get the intercepts, two in this case 
x, y = find_intersections(v, lineMesh[1])
print x
print y
#plot the intercepting points
plt.plot(x[0], y[0], 'bo', label='first intercept')
#plt.plot(x[1], y[1], 'rs', label='second intercept')
plt.legend(shadow=True, fancybox=True, numpoints=1, loc='best')
plt.show()

#now we need to calculate the intercept of the vertices and whatever line
#this is pseudo code but works in case of two intercepting contour vertices

def find_intersections(A, B):
# min, max and all for arrays
amin = lambda x1, x2: np.where(x1<x2, x1, x2)
amax = lambda x1, x2: np.where(x1>x2, x1, x2)
aall = lambda abools: np.dstack(abools).all(axis=2)
slope = lambda line: (lambda d: d[:,1]/d[:,0])(np.diff(line, axis=0))

x11, x21 = np.meshgrid(A[:-1, 0], B[:-1, 0])
x12, x22 = np.meshgrid(A[1:, 0], B[1:, 0])
y11, y21 = np.meshgrid(A[:-1, 1], B[:-1, 1])
y12, y22 = np.meshgrid(A[1:, 1], B[1:, 1])
m1, m2 = np.meshgrid(slope(A), slope(B))
m1inv, m2inv = 1/m1, 1/m2

yi = (m1*(x21-x11-m2inv*y21) + y11)/(1 - m1*m2inv)
xi = (yi - y21)*m2inv + x21

xconds = (amin(x11, x12) < xi, xi <= amax(x11, x12),
          amin(x21, x22) < xi, xi <= amax(x21, x22) )
yconds = (amin(y11, y12) < yi, yi <= amax(y11, y12),
          amin(y21, y22) < yi, yi <= amax(y21, y22) )

return xi[aall(xconds)], yi[aall(yconds)]

At the moment it finds intersecting points but only where the line is uniform, the main reason why I cannot find a solution here is that I dont understand the original authors train of thinking here,

yi = (m1*(x21-x11-m2inv*y21) + y11)/(1 - m1*m2inv)
xi = (yi - y21)*m2inv + x21     

Answer 1

Use shapely can find the intersection point, than use the point as the init guess value for fsolve() to find the real solution:

#for contour 
def p_0(num,t) :
    esc_p = np.sum((((-1)**n)*(np.exp(t)**n)*((math.factorial(n)*((n+1)**0.5))**-1)) for n in range(1,num,1))
    return esc_p+1

tau = np.arange(-2,3,0.1)

x,y= np.meshgrid(tau,tau)
cs = plt.contour(x, y, np.log(p_0(51, y)/p_0(51, x)),[0.2],colors='k')

p=0.75
logp = (np.log(p*np.exp(tau)))
plt.plot(tau,logp)

from shapely.geometry import LineString
v1 = cs.collections[0].get_paths()[0].vertices

ls1 = LineString(v1)
ls2 = LineString(np.c_[tau, logp])
points = ls1.intersection(ls2)
x, y = points.x, points.y

from scipy import optimize

def f(p):
    x, y = p
    e1 = np.log(0.75*np.exp(x)) - y
    e2 = np.log(p_0(51, y)/p_0(51, x)) - 0.2
    return e1, e2

x2, y2 = optimize.fsolve(f, (x, y))

plt.plot(x, y, "ro")
plt.plot(x2, y2, "gx")

print x, y
print x2, y2

Here is the output:

0.273616328952 -0.0140657435002
0.275317387697 -0.0123646847549

and the plot:

Answer 2

See your contour lines as polylines and plug the vertex coordinates into the implicit line equation (F(P) = a.X + b.Y + c = 0). Every change of sign is an intersection, computed by solving 2x2 linear equations. You need no sophisticated solver.

If you need to detect the contour lines simultaneously, it is not much more complicated: consider the section of the terrain by a vertical plane through the line. You will obtain altitudes by linear interpolation along the edges of the grid tiles that are crossed. Finding the intersections with the grid is closely related to the Bresenham line drawing algorithm.

Then what you get is a profile, i.e. a function of a single variable. Locating the intersections with the horizontal planes (iso-values) is also done by detecting changes of sign.

Answer 3

This is a way that I used to solve this problem

def straight_intersection(straight1, straight2):
    p1x = straight1[0][0]
    p1y = straight1[0][1]
    p2x = straight1[1][0]
    p2y = straight1[1][1]
    p3x = straight2[0][0]
    p3y = straight2[0][1]
    p4x = straight2[1][0]
    p4y = straight2[1][1]
    x = p1y * p2x * p3x - p1y * p2x * p4x - p1x * p2y * p4x + p1x * p2y * p3x - p2x * p3x * p4y + p2x * p3y * p4x + p1x * p3x * p4y - p1x * p3y * p4x
    x = x / (p2x * p3y - p2x * p4y - p1x * p3y + p1x * p4y + p4x * p2y - p4x * p1y - p3x * p2y + p3x * p1y)
    y = ((p2y - p1y) * x + p1y * p2x - p1x * p2y) / (p2x - p1x)
    return (x, y)

Answer 4

While this question is old now, i want to share my answer for this problem for future generations to come. Actually, there is two more solutions i found to this problem that is relatively efficient.

First solution is using pointPolygonTest in opencv recursively like that.

# Enumerate the line segment points between 2 points
for pt in zip(*line(*p1, *p2)):
    if cv2.pointPolygonTest(conts[0], pt, False) == 0:  # If the point is on the contour
        return pt

Second solution, you can simply draw the contour and line and make a np.logical_and() to get the answer

blank = np.zeros((1000, 1000))
blank_contour = drawContour(blank.copy(), cnt[0], 0, 1, 1)
blank_line = cv2.line(blank.copy(), line[0], line[1], 1, 1)
intersections = np.logical_and(blank_contour, black_line)

points = np.where(intersections == 1)