Python function for line intersection??

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

Python function for line intersection??

Happyman-2
Hello,

I am having trouble with solving line intersection problem. I would solve it using standard functions which may already exist in Python library.
Let me explain it below:

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.
I wanted to calculate all intersected points of line with the map depending on dx, dy value. I already did it, but two problems:
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.
2) How can I optimize my code (using Python standard library), if possible.

Or is there standard Python library for that purpose???

import numpy as np

def intrsctd_pnts(map, dx, dy, A, B, line_number):

    height, width = np.shape(map)

    # slope of each line
    m = (B[:, 1] - A[:, 1]) / (B[:, 0] - A[:, 0])
    b = A[:, 1] - m * A[:, 0]

    lx_min = np.minimum(A[:,0], B[:,0])
    lx_max = np.maximum(A[:,0], B[:,0])
    ly_min = np.minimum(A[:,1], B[:,1])
    ly_max = np.maximum(A[:,1], B[:,1])

    lx_floor = np.ceil(lx_min /dx)*dx
    lx_ceil = np.floor(lx_max /dx)*dx
    ly_floor = np.ceil(ly_min /dy)*dy
    ly_ceil = np.floor(ly_max /dy)*dy

    distance = []
    i_pixel = []
    intersect_point = []
    for i in range(line_number):
        AB = []
        # calculate all intersected x coordinates
        x = np.arange(lx_floor[i], lx_ceil[i]+dx, dx)
        y = m[i] * x + b[i]
        AB = zip(x, y)
        # calculate all intersected y coordinates
        y = np.arange(ly_floor[i], ly_ceil[i]+dy, dy)
        x = (y - b[i]) / m[i]
        AB.extend(zip(x, y))
        AB.append((A[i,0], A[i,1]))
        AB.append((B[i,0], B[i,1]))
        AB.sort()
        AB = np.asarray(AB)
        intersect_point.append(AB)
        # compute distance between two points
        dist_x = np.diff(AB[:,0])
        dist_y = np.diff(AB[:,1])
        distance.append( np.sqrt((dist_x)**2 + (dist_y)**2) )

        # FIND pixel value where line intersects that pixel
        col = (np.floor( min(AB[:,0]) / dx)).astype(int)
        row = (np.floor( min(AB[:,1]) / dy)).astype(int)

        # FIND pixel to which this lines belong
        i_pixel.append(col + width*row)

    return distance, i_pixel, intersect_point


def main():
    # INPUTS:
    map = np.array( [ [ 4.5,  4.5,  4.5,  3.4],
                               [ 3.9,  4.5,  5.2,  4.5],
                               [ 3.9,  3.9,  2.5,  2.2],
                               [ 3.4,  3.9,  2.9,  2.2],
                               [ 2.5,  3.4,  2.2,  1.4],
                               [ 2.5,  2.2,  2.5,  1.2] )
    dx = dy = 0.5
    A = np.array( [ [ 0. , 0. ],
                           [ 1.9 , 0.] ])
 
    B = np.array( [ [ 1.1 , 2.3],
                           [ 1.3 , 1.3] ])

    line_number = len(A)  # or len(B)
 
    distance, pixels, int_points = intrsctd_pnts(map, dx, dy, A, B, line_number)
 
   ##  distance should not be zero

if __name__ == '__main__':
    main()



_______________________________________________
NumPy-Discussion mailing list
[hidden email]
http://mail.scipy.org/mailman/listinfo/numpy-discussion
Reply | Threaded
Open this post in threaded view
|

Re: Python function for line intersection??

Stéfan van der Walt
On Tue, Oct 8, 2013 at 3:15 PM, Happyman <[hidden email]> wrote:
>     # slope of each line
>     m = (B[:, 1] - A[:, 1]) / (B[:, 0] - A[:, 0])
>     b = A[:, 1] - m * A[:, 0]

Calculating the slope of a line leads to difficulties, e.g. when
dealing with vertical lines.  Rather, parameterize lines as shown
here:

http://paulbourke.net/geometry/pointlineplane/

Stéfan
_______________________________________________
NumPy-Discussion mailing list
[hidden email]
http://mail.scipy.org/mailman/listinfo/numpy-discussion