代码之家 › 专栏 › 技术社区 › 8-Bit Borges

在地图上的一条线下查找所有点

cross-product computational-geometry matplotlib python

8-Bit Borges · 技术社区 · 6 年前

为了在多个点(近2000个)的地图上绘制两点之间的路径,我使用以下函数:

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()

我的目标是提取在绘制线下方的所有点(坐标)。

我知道你可以用 cross product of vectors

考虑到大量的向量,在上面的上下文中实现这一点的最有效的方法是什么?

1 回复 | 直到 6 年前

gaganso 6 年前

O(1)

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.