如何判断一个点是否在凸包内或外？

Question

如何判断一个点是否在凸包内或外？

4

我有一个numpy的点阵数组，并用(scipy.spatial.ConvexHull而不是scipy.spatial.Delaunay.convex_hull)计算了它们的ConvexHull，现在我想知道如果我将新的点添加到数组中，这个点是否在点云的凸包内。在numoy中做到这一点的最佳方法是什么？

我应该提到我看到了这个问题, 但它没有解决我的问题（因为它使用cipy.spatial.Delaunay.convex_hull来计算ConvexHull）。

- Am1rr3zA

可能是如何高效地找到一个点是否在点云的凸包内？的重复问题。 - kkuilla

@kkuilla 如果您仔细阅读我的问题，您会看到我放了那个问题的链接，并提到这个问题并没有解决我的问题。 - Am1rr3zA

是的，我在标记后注意到了这一点。你实际上是在说“它解决了我的问题”。我认为这可能是一个重复的问题，因为那个问题解决了你的问题。 - kkuilla

看起来其他问题的相当数量答案都回答了你的问题（例如 https://dev59.com/HGQn5IYBdhLWcg3wiXqd#16751168，它使用 scipy.spatial.ConvexHull），并且与您如何找到凸包无关。 - tacaswell

@tcaswell，请阅读特定答案下面的评论，您会发现错误。我之前已经读了那个答案很多次了。 - Am1rr3zA

一个快速的查看显示scipy.spatial.ConvexHull使用QHULL来解决问题，这更适合于高维凸包。如果你需要高维凸包，那么你可能应该这样说。否则，你可能不应该使用那个算法。确定一个点是否在N维凸包内似乎可能会很棘手。话虽如此，我认为射线跟踪（建议的方法）仍然有效，因为你只需要测试每个面，而在2D中，如果我没记错的话，一条边就是一个面。 - Nuclearman

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Cunningham · Accepted Answer

我知道这个问题有些旧了，但是如果有人像我一样遇到了这个问题，这里是答案：
我使用的是scipy 1.1.0和python 3.6

def isInHull(P,hull):
    '''
    Datermine if the list of points P lies inside the hull
    :return: list
    List of boolean where true means that the point is inside the convex hull
    '''
    A = hull.equations[:,0:-1]
    b = np.transpose(np.array([hull.equations[:,-1]]))
    isInHull = np.all((A @ np.transpose(P)) <= np.tile(-b,(1,len(P))),axis=0)

在这里，我们使用所有平面的方程来确定该点是否在凸包之外。我们从不建立Delaunay对象。此函数以P mxn作为输入，其中P是m个n维点的数组。使用凸包进行构造。

hull = ConvexHull(X)

在构建凸包的点云中，X是由p个点组成的pxn数组。