Distance for each intersected points of a line in increased order in 2D coordinate

Question

I am calculating the distance between A(x0,y0) and B(x1,y1) points in a 2D (x,y).

I have the following code which represents intersected points of each cell in the given two boundary points, A(x0,y0) and B(x1,y1).

def intersected_points(x0, x1, y0, y1):
    # slope 
    m = (y1 - y0 )/( x1 - x0)
    # Boundary of the selected points
    x_ceil = ceil( min (x0, x1 ))
    x_floor = floor( max(x0, x1))
    y_ceil = ceil( min(y0, y1))
    y_floor = floor( max(y0, y1))

    # calculate all intersected x coordinate
    ax = []
    for x in arange(x_ceil, x_floor + 1, 1):
          ax.append([ x, m * ( x - x0 ) + y0 ])
    # calculate all intersected y coordinate
    for y in arange(y_ceil, y_floor + 1, 1):
          ax.append([ ( y - y0 ) * ( 1./m ) + x0, y ])
    return ax

Sample values:

intersected_points(1.5, 4.4, 0.5, 4.1);

Output:

[
    [2.0, 1.1206896551724137],
    [3.0, 2.3620689655172411],
    [4.0, 3.6034482758620685],
    [1.9027777777777779, 1.0],
    [2.7083333333333335, 2.0],
    [3.5138888888888893, 3.0],
    [4.3194444444444446, 4.0]
]

The output I got is mixed and unsorted values, so, for each cell coordinates, where line crosses. BUT, The result I want to get should be something (including boundary points): (x0,y0), all intersected points, (x1,y1) where x0, y0 - intial, x1,y1 - final point. Other values are intersected line coordinates!

Answer 1

Here's a modified version of your code. It uses numpy a bit more, and it includes the end points in the sorted array of points.

import numpy as np

def intersected_points(x0, x1, y0, y1):
    # slope
    m = (y1 - y0) / (x1 - x0)
    # Boundary of the selected points
    x_ceil = np.ceil(min(x0, x1))
    x_floor = np.floor(max(x0, x1))
    y_ceil = np.ceil(min(y0, y1))
    y_floor = np.floor(max(y0, y1))

    # calculate all intersected x coordinate
    x = np.arange(x_ceil, x_floor + 1)
    y = m * (x - x0) + y0
    ax = zip(x, y)
    # calculate all intersected y coordinate
    y = np.arange(y_ceil, y_floor + 1)
    x = (y - y0) / m + x0
    ax.extend(zip(x, y))
    ax.append((x0, y0))
    ax.append((x1, y1))
    ax.sort()
    return np.array(ax)


if __name__ == "__main__":
    import matplotlib.pyplot as plt

    x0, y0 = 1.5, 0.5
    x1, y1 = 4.4, 4.1

    points = intersected_points(x0, x1, y0, y1)
    print points

    rect = plt.Rectangle((x0, y0), x1 - x0, y1 - y0,
                         facecolor="#60ff60", alpha=0.2)
    plt.gca().add_patch(rect)
    plt.plot([x0, x1], [y0, y1], 'b-')
    plt.plot(points[:, 0], points[:, 1], 'bo')
    plt.grid(True)
    plt.xticks(np.arange(np.floor(x0), np.ceil(x1)))
    plt.yticks(np.arange(np.floor(y0), np.ceil(y1)))
    plt.show()

It prints:

[[ 1.5         0.5       ]
 [ 1.90277778  1.        ]
 [ 2.          1.12068966]
 [ 2.70833333  2.        ]
 [ 3.          2.36206897]
 [ 3.51388889  3.        ]
 [ 4.          3.60344828]
 [ 4.31944444  4.        ]
 [ 4.4         4.1       ]]

and generates the plot: