我检查了 QHull 版本(从上面)和线性规划解决方案(例如看到这个问题)。到目前为止,使用 QHull 似乎是最好的选择,尽管我可能会错过一些scipy.spatial
LP 的优化。
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)
在哪里
%%time
in_hull_1 = asarray([pnt_in_cvex_hull_1(hull, pnt) for pnt in new_points], dtype=bool)
产生:
CPU times: user 268 ms, sys: 4 ms, total: 272 ms
Wall time: 268 ms
和
%%time
in_hull_2 = asarray([pnt_in_cvex_hull_2(hull_points, pnt) for pnt in new_points], dtype=bool)
生产
CPU times: user 3.83 s, sys: 16 ms, total: 3.85 s
Wall time: 3.85 s