Запись для проверки, находится ли точка в пространстве корпуса, с использованием scipy.optimize.minimize.
Основано на ответе пользователя 1071736.
Если вы вычислите выпуклую оболочку, все будет намного быстрее, поэтому я добавил пару строк для людей, которые хотят это сделать. Я переключился с сканирования Грэма (только 2D) на алгоритм scipy qhull.
документация scipy.optimize.minimize:
https://docs.scipy.org/doc/scipy/reference/optimize.nonlin.html
import numpy as np
import scipy.optimize
import matplotlib.pyplot as plt
from scipy.spatial import ConvexHull
def hull_test(P, X, use_hull=True, verbose=True, hull_tolerance=1e-5, return_hull=True):
if use_hull:
hull = ConvexHull(X)
X = X[hull.vertices]
n_points = len(X)
def F(x, X, P):
return np.linalg.norm( np.dot( x.T, X ) - P )
bnds = [[0, None]]*n_points # coefficients for each point must be > 0
cons = ( {'type': 'eq', 'fun': lambda x: np.sum(x)-1} ) # Sum of coefficients must equal 1
x0 = np.ones((n_points,1))/n_points # starting coefficients
result = scipy.optimize.minimize(F, x0, args=(X, P), bounds=bnds, constraints=cons)
if result.fun < hull_tolerance:
hull_result = True
else:
hull_result = False
if verbose:
print( '# boundary points:', n_points)
print( 'x.T * X - P:', F(result.x,X,P) )
if hull_result:
print( 'Point P is in the hull space of X')
else:
print( 'Point P is NOT in the hull space of X')
if return_hull:
return hull_result, X
else:
return hull_result
Проверка некоторых образцов данных:
n_dim = 3
n_points = 20
np.random.seed(0)
P = np.random.random(size=(1,n_dim))
X = np.random.random(size=(n_points,n_dim))
_, X_hull = hull_test(P, X, use_hull=True, hull_tolerance=1e-5, return_hull=True)
Выход:
# boundary points: 14
x.T * X - P: 2.13984259782e-06
Point P is in the hull space of X
Визуализируйте это:
rows = max(1,n_dim-1)
cols = rows
plt.figure(figsize=(rows*3,cols*3))
for row in range(rows):
for col in range(row, cols):
col += 1
plt.subplot(cols,rows,row*rows+col)
plt.scatter(P[:,row],P[:,col],label='P',s=300)
plt.scatter(X[:,row],X[:,col],label='X',alpha=0.5)
plt.scatter(X_hull[:,row],X_hull[:,col],label='X_hull')
plt.xlabel('x{}'.format(row))
plt.ylabel('x{}'.format(col))
plt.tight_layout()
