查找一个点是否在一个凸点内部，而不计算船体本身
testingP点是否在由一组点X构成的凸包内部的最简单方法是什么？
我想要一个在高维空间（也就是多达40个维度）工作的algorithm，它没有明确计算凸包本身。 有任何想法吗？
这个问题可以通过find线性规划的一个可行点来解决。 如果你对完整的细节感兴趣，而不是把一个LP插入到一个现有的求解器中，我推荐阅读Boyd和Vandenberghe关于凸优化的书 。
设A = (X[1] X[2] ... X[n]) ，即第一v1 ，第二个v2等
解决以下LP问题，
minimize (over x): 1 st Ax = P x^T * [1] = 1 x[i] >= 0 \forall i
哪里
-
x^T是x的转置 -
[1]是全1vector。
如果问题在凸包中，问题就有了解决方法。
该点位于其他点的凸包外部，当且仅当从它到这些其他点的所有vector的方向小于圆周/球/超球体的一半时。
你不必计算凸包本身，因为在多维空间中看起来相当麻烦。 有一个众所周知的凸包的属性 ：
（ [v1, v2, .., vn] ）的凸包内的任意vector（点） v可以表示为sum(ki*vi) ，其中0 <= ki <= 1且sum(ki) = 1 。 相应地，凸包外的任何点都不会有这样的表示。
在m维空间中，这将给我们带有n未知数的m线性方程组。
编辑
在一般情况下，我不确定这个新问题的复杂性，但对于m = 2 ，似乎是线性的。 也许，在这方面有更多经验的人会纠正我。
我有16个维度相同的问题。 由于即使是qhull也不能正常工作，因为需要生成太多的面孔，所以我通过testing开发了我自己的方法，在新点和参考数据（我称之为“HyperHull”）之间是否可以find分离的超平面。 。
find一个分离超平面的问题可以转化为一个凸二次规划问题（参见： SVM ）。 我在python中使用cvxopt执行了less于170行的代码（包括I / O）。 即使存在这样的问题，该algorithm在任何维度上都可以不加修改地工作，即维数越高，壳体上的点的数量就越高（参见多面体中的随机点的凸包 ）。 由于船体没有明确的构造，只是被检查过，无论是否在一个点内，与快速船体相比，该algorithm在高维上具有很大的优势。
这个algorithm可以“自然”并行化，加速应该等于处理器的数量。
你是否愿意接受一个启发式的答案，应该通常工作，但不能保证？ 如果你是那么你可以尝试这个随机的想法。
假设f（x）是P乘以X中事物数量的距离的立方，减去到X中所有点的距离的立方和。随机地开始，并使用爬山algorithm来最大化f（x）对于距离P很远的球体中的x而言。除了退化情况，如果P不在凸包中，这应该有一个非常好的find超平面的法线的概率，P是在，X中的所有东西都在另一边。
尽pipe原来的post是三年前的，也许这个答案仍然有帮助。 吉尔伯特 – 约翰逊 – 基尔希（GJK）algorithmfind了两个凸多面体之间的最短距离，每个凸多面体都被定义为一组发生器的凸包，值得注意的是，凸包本身不需要计算。 在一个特殊的情况下，被问到的情况是，其中一个多面体只是一个点。 为什么不尝试使用GJKalgorithm来计算P和点X的凸包之间的距离？ 如果这个距离是0，那么P在X内（或至less在其边界上）。 Octave / Matlab中的GJK实现，名为ClosestPointInConvexPolytopeGJK.m，以及支持代码，可在http://www.99main.com/~centore/MunsellAndKubelkaMunkToolbox/MunsellAndKubelkaMunkToolbox.html中获得; 。 GJKalgorithm的简单描述可在Sect。 2的论文，在~centore/ColourSciencePapers/GJKinConstrainedLeastSquares.pdf 。 我已经使用GJKalgorithm来处理31维空间中的一些非常小的集合X，并且取得了很好的效果。 GJK的performance如何与其他人所推荐的线性规划方法相比较是不确定的（尽pipe任何比较都是有趣的）。 GJK方法确实避免计算凸包，或用线性不等式来表示壳体，这两者都可能是耗时的。 希望这个答案有帮助。
