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

Question

为了在地图上有很多点(大约两千点(的两点之间绘制路径，我使用以下函数：

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

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

我知道你可以使用向量的叉积来做到这一点

考虑到大量的矢量，在上述情况下，实现这一目标的最有效方法是什么？

Answer 1

每个叉积运算仍然是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.

除非你有关于这些点的其他信息，否则你必须检查每个点，看看它是否在一条特定的线下面。