Finding Intersection Between Straight Line And Contour

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 contou

Solution 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:

Solution 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.

Solution 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 * p4xx= 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)

Solution 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 pointsfor pt inzip(*line(*p1, *p2)):
    if cv2.pointPolygonTest(conts[0], pt, False) == 0:  # If the point is on the contourreturn 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)