Вот простое решение, которое требует только SciPy:
def in_hull(p, hull):
"""
Test if points in `p` are in `hull`
`p` should be a `NxK` coordinates of `N` points in `K` dimensions
`hull` is either a scipy.spatial.Delaunay object or the `MxK` array of the
coordinates of `M` points in `K`dimensions for which Delaunay triangulation
will be computed
"""
from scipy.spatial import Delaunay
if not isinstance(hull,Delaunay):
hull = Delaunay(hull)
return hull.find_simplex(p)>=0
возвращает булево массив, в котором True значения указывают точки, лежащие в данной выпуклой оболочки. Он может быть использован, как это:
tested = np.random.rand(20,3)
cloud = np.random.rand(50,3)
print in_hull(tested,cloud)
Если Matplotlib установлена, вы можете также использовать следующую функцию, которая вызывает первый и участки результаты. Для данных 2D только, заданных Nx2 массивов:
def plot_in_hull(p, hull):
"""
plot relative to `in_hull` for 2d data
"""
import matplotlib.pyplot as plt
from matplotlib.collections import PolyCollection, LineCollection
from scipy.spatial import Delaunay
if not isinstance(hull,Delaunay):
hull = Delaunay(hull)
# plot triangulation
poly = PolyCollection(hull.points[hull.vertices], facecolors='w', edgecolors='b')
plt.clf()
plt.title('in hull')
plt.gca().add_collection(poly)
plt.plot(hull.points[:,0], hull.points[:,1], 'o', hold=1)
# plot the convex hull
edges = set()
edge_points = []
def add_edge(i, j):
"""Add a line between the i-th and j-th points, if not in the list already"""
if (i, j) in edges or (j, i) in edges:
# already added
return
edges.add((i, j))
edge_points.append(hull.points[ [i, j] ])
for ia, ib in hull.convex_hull:
add_edge(ia, ib)
lines = LineCollection(edge_points, color='g')
plt.gca().add_collection(lines)
plt.show()
# plot tested points `p` - black are inside hull, red outside
inside = in_hull(p,hull)
plt.plot(p[ inside,0],p[ inside,1],'.k')
plt.plot(p[-inside,0],p[-inside,1],'.r')
Я хочу узнать, если произвольная точка находится в выпуклой оболочке точечного облака или вне ее. :) – AME
так вы удовлетворены ответом? – octoback
Ваш ответ для внутри или снаружи корпуса неверен в том, что выше и ниже не является достаточным испытанием. Например, если точка находится за пределами корпуса, но, скажем, на полпути по 45-градусной диагонали, тогда ваш тест не удастся. Вместо этого суммируйте углы между контрольной точкой и всеми точками выпуклой оболочки: если она внутри углов будет суммироваться до 2pi, а если она снаружи, они будут суммироваться до 0 (или у меня могут быть некоторые детали этого неправильного, но вот основная идея). – tom10