<p>我查看了QHull版本(从上面开始)和线性规划解决方案(例如,参见<a href="https://stackoverflow.com/questions/8261260/how-to-fastest-check-if-point-3d-is-inside-convex-hull-given-by-set-of-point">this question</a>)。到目前为止,使用QHull似乎是最好的选择,尽管我可能会错过一些关于<code>scipy.spatial</code>LP的优化。在</p>
<pre><code>import numpy
import numpy.random
from numpy import zeros, ones, arange, asarray, concatenate
from scipy.optimize import linprog
from scipy.spatial import ConvexHull
def pnt_in_cvex_hull_1(hull, pnt):
'''
Checks if `pnt` is inside the convex hull.
`hull` a QHull ConvexHull object
`pnt` point array of shape (3,)
'''
new_hull = ConvexHull(concatenate((hull.points, [pnt])))
if numpy.array_equal(new_hull.vertices, hull.vertices):
return True
return False
def pnt_in_cvex_hull_2(hull_points, pnt):
'''
Given a set of points that defines a convex hull, uses simplex LP to determine
whether point lies within hull.
`hull_points` (N, 3) array of points defining the hull
`pnt` point array of shape (3,)
'''
N = hull_points.shape[0]
c = ones(N)
A_eq = concatenate((hull_points, ones((N,1))), 1).T # rows are x, y, z, 1
b_eq = concatenate((pnt, (1,)))
result = linprog(c, A_eq=A_eq, b_eq=b_eq)
if result.success and c.dot(result.x) == 1.:
return True
return False
points = numpy.random.rand(8, 3)
hull = ConvexHull(points, incremental=True)
hull_points = hull.points[hull.vertices, :]
new_points = 1. * numpy.random.rand(1000, 3)
</code></pre>
<p>在哪里</p>
^{pr2}$
<p>产生:</p>
<pre><code>CPU times: user 268 ms, sys: 4 ms, total: 272 ms
Wall time: 268 ms
</code></pre>
<p>以及</p>
<pre><code>%%time
in_hull_2 = asarray([pnt_in_cvex_hull_2(hull_points, pnt) for pnt in new_points], dtype=bool)
</code></pre>
<p>生产</p>
<pre><code>CPU times: user 3.83 s, sys: 16 ms, total: 3.85 s
Wall time: 3.85 s
</code></pre>