<HTML><BODY><span style="font-size: 14px;">Hello,</span><br><br><span style="font-size: 14px;">I am having trouble with solving line intersection problem. I would solve it using standard functions which may already exist in Python library. <br>Let me explain it below:</span><br><span style="font-size: 14px;">I have sets of lines A(x,y) and B(x,y) and one map as a matrix form, also with its resolution dx, dy which can be changed.</span><br><span style="font-size: 14px;">I wanted to calculate all intersected points of line with the map depending on dx, dy value. I already did it, but two problems:</span><br><span style="font-size: 14px;">1) When some coordinate value (x or y) are zero, the program returns wrong answer. For example, distance is zero, but it is not zero in fact.</span><br><span style="font-size: 14px;">2) How can I optimize my code (using Python standard library), if possible.</span><br><br><span style="font-size: 14px;">Or is there standard Python library for that purpose???</span><br><br><span style="font-size: 14px;">import numpy as np</span><br><br><span style="font-size: 14px;">def intrsctd_pnts(map, dx, dy, A, B, line_number):</span><br><br><span style="font-size: 14px;"> height, width = np.shape(map)</span><br><br><span style="font-size: 14px;"> # slope of each line</span><br><span style="font-size: 14px;"> m = (B[:, 1] - A[:, 1]) / (B[:, 0] - A[:, 0])</span><br><span style="font-size: 14px;"> b = A[:, 1] - m * A[:, 0]</span><br><br><span style="font-size: 14px;"> lx_min = np.minimum(A[:,0], B[:,0])</span><br><span style="font-size: 14px;"> lx_max = np.maximum(A[:,0], B[:,0])</span><br><span style="font-size: 14px;"> ly_min = np.minimum(A[:,1], B[:,1])</span><br><span style="font-size: 14px;"> ly_max = np.maximum(A[:,1], B[:,1])</span><br><br><span style="font-size: 14px;"> lx_floor = np.ceil(lx_min /dx)*dx</span><br><span style="font-size: 14px;"> lx_ceil = np.floor(lx_max /dx)*dx</span><br><span style="font-size: 14px;"> ly_floor = np.ceil(ly_min /dy)*dy</span><br><span style="font-size: 14px;"> ly_ceil = np.floor(ly_max /dy)*dy</span><br><br><span style="font-size: 14px;"> distance = []</span><br><span style="font-size: 14px;"> i_pixel = []</span><br><span style="font-size: 14px;"> intersect_point = []</span><br><span style="font-size: 14px;"> for i in range(line_number):</span><br><span style="font-size: 14px;"> AB = []</span><br><span style="font-size: 14px;"> # calculate all intersected x coordinates</span><br><span style="font-size: 14px;"> x = np.arange(lx_floor[i], lx_ceil[i]+dx, dx)</span><br><span style="font-size: 14px;"> y = m[i] * x + b[i]</span><br><span style="font-size: 14px;"> AB = zip(x, y)</span><br><span style="font-size: 14px;"> # calculate all intersected y coordinates</span><br><span style="font-size: 14px;"> y = np.arange(ly_floor[i], ly_ceil[i]+dy, dy)</span><br><span style="font-size: 14px;"> x = (y - b[i]) / m[i]</span><br><span style="font-size: 14px;"> AB.extend(zip(x, y))</span><br><span style="font-size: 14px;"> AB.append((A[i,0], A[i,1]))</span><br><span style="font-size: 14px;"> AB.append((B[i,0], B[i,1]))</span><br><span style="font-size: 14px;"> AB.sort()</span><br><span style="font-size: 14px;"> AB = np.asarray(AB)</span><br><span style="font-size: 14px;"> intersect_point.append(AB)</span><br><span style="font-size: 14px;"> # compute distance between two points</span><br><span style="font-size: 14px;"> dist_x = np.diff(AB[:,0])</span><br><span style="font-size: 14px;"> dist_y = np.diff(AB[:,1])</span><br><span style="font-size: 14px;"> distance.append( np.sqrt((dist_x)**2 + (dist_y)**2) )</span><br><br><span style="font-size: 14px;"> # FIND pixel value where line intersects that pixel</span><br><span style="font-size: 14px;"> col = (np.floor( min(AB[:,0]) / dx)).astype(int)</span><br><span style="font-size: 14px;"> row = (np.floor( min(AB[:,1]) / dy)).astype(int)</span><br><br><span style="font-size: 14px;"> # FIND <span style="font-size: 14px;" data-mce-style="font-size: 14px;">pixel</span> to which this lines belong</span><br><span style="font-size: 14px;"> i_pixel.append(col + width*row)</span><br><br><span style="font-size: 14px;"> return distance, i_pixel, intersect_point</span><br><br><br><span style="font-size: 14px;">def main():</span><br><span style="font-size: 14px;"> # INPUTS:</span><br><span style="font-size: 14px;"> map = np.array( [ [ 4.5, 4.5, 4.5, 3.4],</span><br><span style="font-size: 14px;"> [ 3.9, 4.5, 5.2, 4.5],</span><br><span style="font-size: 14px;"> [ 3.9, 3.9, 2.5, 2.2],</span><br><span style="font-size: 14px;"> [ 3.4, 3.9, 2.9, 2.2],</span><br><span style="font-size: 14px;"> [ 2.5, 3.4, 2.2, 1.4],</span><br><span style="font-size: 14px;"> [ 2.5, 2.2, 2.5, 1.2] )</span><br><span style="font-size: 14px;"> dx = dy = 0.5</span><br><span style="font-size: 14px;"> A = np.array( [ [ 0. , 0. ], </span><br><span style="font-size: 14px;"> [ 1.9 , 0.] ])</span><br> <br><span style="font-size: 14px;"> B = np.array( [ [ 1.1 , 2.3],</span><br><span style="font-size: 14px;"> [ 1.3 , 1.3] ])</span><br><br><span style="font-size: 14px;"> line_number = len(A) # or len(B)</span><br> <br><span style="font-size: 14px;"> distance, pixels, int_points = intrsctd_pnts(map, dx, dy, A, B, line_number)</span><br> <br><span style="font-size: 14px;"> ## distance should not be zero</span><br><br><span style="font-size: 14px;">if __name__ == '__main__':</span><br><span style="font-size: 14px;"> main()</span><br><br><br></BODY></HTML>