Find all points below a line on a map

Question

In order to draw a path between two points on a map with many points (almost two thousand), I use the following function:

def path_between_cities(self, cities_with_coordinates, from_to):

        from matplotlib.lines import Line2D     

        # coordinates from chosen path
        x = [int(from_to[0][2]), int(from_to[1][2])]
        y = [int(from_to[0][1]), int(from_to[1][1])]

        #create line
        line = Line2D(x,y,linestyle='-',color='k')

        # create axis
        x_ = np.array((0,2000))
        y_ = np.array((0,6000))

        plt.plot(x_,y_, 'o')

        for item in cities_with_coordinates:
            name = item[0]
            y_coord = int(item[1])
            x_coord = int(item[2])
            plt.plot([x_coord], [y_coord], marker='o', markersize=1, color='blue')
            plt.axes().add_line(line)

        plt.axis('scaled')
        plt.show()

My goal is to extract all points (coordinates) which are found below the drawn line.

I know that you can do this using the cross product of vectors

Given a large number of vectors, what would be the most efficient way of achieving this in the context above?

Answer 1

Each cross product operation is still O(1). You can run the below function for all the points and see which of them are below, bringing it to a linear time check.

def ccw(a,b,c):
    """ Returns 1 if c is above directed line ab else returns -1"""
    return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y)
    #a and b are the vertices and c is the test point.

Unless you have some other information about the points, you would have to check each point to see if it below a particular line.