如何确定哪些点在多边形内部，哪些不在（大量点）？
我有一大堆数据点（超过100,000个），它们存储在一个二维的numpy数组里。这个数组的第一列是x坐标，第二列是y坐标。此外，我还有几个一维数组，里面存储了每个数据点的额外信息。现在我想从这些一维数组中创建图表，只包含在特定多边形内的数据点。
我想出了一个解决方案，但这个方案既不优雅也不快：
#XY is the 2D array.
#A is one of the 1D arrays.
#poly is a matplotlib.patches.Polygon
mask = np.array([bool(poly.get_path().contains_point(i)) for i in XY])
matplotlib.pylab.hist(A[mask], 100)
matplotlib.pylab.show()
你能帮我改进一下这个代码吗？我试着用np.vectorize来替代列表推导式，但没能成功。
2 个回答
我对你使用的库不太熟悉，不过我有一个合理的算法思路可以分享。我会用简单的Python代码来说明这个算法的实现方法，之后你可以根据自己的需要进行改进和使用你们的库。需要说明的是，我并不认为这是最好的方法，但我想尽快给出我的想法，所以就开始吧。
这个想法来源于在算法中使用两个向量的叉积来找到一组点的凸包，比如说 Graham扫描算法。假设我们有两个点p1和p2，它们分别定义了从原点(0,0)到(x1, y1)和(x2, y2)的向量p1和p2。这两个向量的叉积p1 x p2会得到一个新的向量p3，这个向量与p1和p2都垂直，且它的大小等于由这两个向量形成的平行四边形的面积。
一个非常有用的结果是，下面这个矩阵的行列式
/ x1, x2 \
\ y1, y2 /
...计算结果是x1*y2 - x2*y1，它给出了向量p3的大小，符号则表示p3是“向外”还是“向内”。这里的关键点是，如果这个值是正的，那么p2在p1的“左边”；如果是负的，那么p2就在p1的“右边”。
希望这个ASCII艺术示例能帮助你理解：
. p2(4, 5)
/
/
/
/_ _ _ _ _. p1(5, 0)
x1*y2 - x2*y1 = 5*4 - 0*5 = 20，所以p2在p1的“左边”。
接下来讲讲这对我们有什么用！如果我们有一个多边形的顶点列表和图中其他点的集合，那么对于多边形的每一条边，我们可以得到该边的向量。同时，我们也可以得到从起始顶点到图中所有其他点的向量。通过测试这些向量是在边的左边还是右边，我们可以逐步排除一些点。最终没有被排除的点就是在多边形内部的点。接下来我们来看看一些代码，让这一切更清晰！
首先，获取多边形的顶点列表，按照你绘制时的顺序（逆时针方向），例如一个五边形可能是：
poly = [(1, 1), (4, 2), (5, 5), (3, 8), (0, 4)]
然后获取一个包含图中所有其他点的集合，我们会逐渐从这个集合中移除无效的点，直到最后留下的点正好是多边形内部的点。
points = set(['(3, 0), (10, -2), (3,3), ...])
主要的代码其实写得很简洁，尽管我花了不少时间来解释它的工作原理。to_right函数接收两个元组表示的向量，如果v2在v1的右边，就返回True。接下来的循环会遍历多边形的所有边，如果某个点在任何边的右边，就将其从工作集合中移除。
def to_right(v1, v2):
return (v1[0]*v2[1] - v1[1]*v2[0]) < 0
for i in range(len(poly)):
v1 = poly[i-1]
v2 = poly[i]
for p in points:
if(to_right(v2-v1, p-v1)):
points.remove(p)
补充说明：之所以在右边的点会被移除而不是左边，是因为多边形顶点的指定顺序。如果顶点是顺时针排列的，你就需要移除左边的点。目前我没有特别好的解决方案来处理这个问题。
总之，希望我说的这些内容是正确的，并且对某些人有帮助，即使不是提问者。这个算法的渐进复杂度是O(mn)，其中n是图中的点数，m是多边形的顶点数，因为在最坏的情况下，所有点都在多边形内部，我们需要检查每个点与每条边的关系，而没有点被移除。
使用 matplotlib.nxutils.points_inside_poly，这个方法可以很高效地判断一个点是否在多边形内部。
关于这个有40年历史的算法的例子和更多解释，可以查看 matplotlib的常见问题解答。
更新： 请注意，从matplotlib的1.2.0版本开始，points_inside_poly这个方法已经不再推荐使用了。请改用 matplotlib.path.Path.contains_points。