scipy.spatial.

HalfspaceIntersection

class scipy.spatial.HalfspaceIntersection(halfspaces, interior_point, incremental=False, qhull_options=None)

N 维空间中的半空间交集。

在 0.19.0 版本中添加。

参数:

halfspaces浮点数数组，形状 (nineq, ndim+1)

形式为 Ax + b <= 0 的堆叠不等式，格式为 [A; b]

interior_point浮点数数组，形状 (ndim,)

明显位于半空间定义区域内的点。 也称为可行点，可以通过线性规划获得。

incrementalbool，可选

允许增量添加新的半空间。 这会占用一些额外的资源。

qhull_optionsstr，可选

要传递给 Qhull 的其他选项。 有关详细信息，请参阅 Qhull 手册。（默认值：ndim > 4 时为“Qx”，否则为“”）始终启用选项“H”。

引发:

QhullError

当 Qhull 遇到错误情况时引发，例如当未启用解决选项时的几何退化。

ValueError

如果给定的输入数组不兼容则引发。

说明

交集是使用 Qhull 库计算的。 这重现了 Qhull 的“qhalf”功能。

参考文献

[Qhull]

http://www.qhull.org/

[1]

S. Boyd, L. Vandenberghe, Convex Optimization，可在 http://stanford.edu/~boyd/cvxbook/ 获取

示例

在你的浏览器中尝试一下！

形成某些多边形的平面的半空间交集

>>> from scipy.spatial import HalfspaceIntersection
>>> import numpy as np
>>> halfspaces = np.array([[-1, 0., 0.],
...                        [0., -1., 0.],
...                        [2., 1., -4.],
...                        [-0.5, 1., -2.]])
>>> feasible_point = np.array([0.5, 0.5])
>>> hs = HalfspaceIntersection(halfspaces, feasible_point)

将半空间绘制为填充区域和交点

>>> import matplotlib.pyplot as plt
>>> fig = plt.figure()
>>> ax = fig.add_subplot(1, 1, 1, aspect='equal')
>>> xlim, ylim = (-1, 3), (-1, 3)
>>> ax.set_xlim(xlim)
>>> ax.set_ylim(ylim)
>>> x = np.linspace(-1, 3, 100)
>>> symbols = ['-', '+', 'x', '*']
>>> signs = [0, 0, -1, -1]
>>> fmt = {"color": None, "edgecolor": "b", "alpha": 0.5}
>>> for h, sym, sign in zip(halfspaces, symbols, signs):
...     hlist = h.tolist()
...     fmt["hatch"] = sym
...     if h[1]== 0:
...         ax.axvline(-h[2]/h[0], label='{}x+{}y+{}=0'.format(*hlist))
...         xi = np.linspace(xlim[sign], -h[2]/h[0], 100)
...         ax.fill_between(xi, ylim[0], ylim[1], **fmt)
...     else:
...         ax.plot(x, (-h[2]-h[0]*x)/h[1], label='{}x+{}y+{}=0'.format(*hlist))
...         ax.fill_between(x, (-h[2]-h[0]*x)/h[1], ylim[sign], **fmt)
>>> x, y = zip(*hs.intersections)
>>> ax.plot(x, y, 'o', markersize=8)

默认情况下，qhull 不提供计算内部点的方法。 这可以使用线性规划轻松计算。 考虑形式为 \(Ax + b \leq 0\) 的半空间，求解线性规划

\[ \begin{align}\begin{aligned}max \: y\\s.t. Ax + y ||A_i|| \leq -b\end{aligned}\end{align} \]

其中 \(A_i\) 是 A 的行，即每个平面的法线。

将产生一个位于凸多面体内最远的点 x。 准确地说，它是内接于多面体的最大半径为 y 的超球的中心。 这个点被称为多面体的切比雪夫中心（参见 [1] 4.3.1，pp148-149）。 Qhull 输出的方程始终是标准化的。

>>> from scipy.optimize import linprog
>>> from matplotlib.patches import Circle
>>> norm_vector = np.reshape(np.linalg.norm(halfspaces[:, :-1], axis=1),
...     (halfspaces.shape[0], 1))
>>> c = np.zeros((halfspaces.shape[1],))
>>> c[-1] = -1
>>> A = np.hstack((halfspaces[:, :-1], norm_vector))
>>> b = - halfspaces[:, -1:]
>>> res = linprog(c, A_ub=A, b_ub=b, bounds=(None, None))
>>> x = res.x[:-1]
>>> y = res.x[-1]
>>> circle = Circle(x, radius=y, alpha=0.3)
>>> ax.add_patch(circle)
>>> plt.legend(bbox_to_anchor=(1.6, 1.0))
>>> plt.show()

返回在新标签页中打开

属性:

halfspaces双精度浮点数数组，形状 (nineq, ndim+1)

输入半空间。

interior_point : 浮点数数组，形状 (ndim,)

输入内部点。

intersections双精度浮点数数组，形状 (ninter, ndim)

所有半空间的交点。

dual_points双精度浮点数数组，形状 (nineq, ndim)

输入半空间的对偶点。

dual_facets整数列表的列表

形成对偶凸包的（不一定是单纯）面的点的索引。

dual_vertices整数数组，形状 (nvertices,)

形成对偶凸包顶点的半空间的索引。 对于二维凸包，顶点按逆时针顺序排列。 对于其他维度，它们按输入顺序排列。

dual_equations双精度浮点数数组，形状 (nfacet, ndim+1)

[法线，偏移量] 形成对偶面的超平面方程（更多信息请参见 Qhull 文档）。

dual_area浮点数

对偶凸包的面积

dual_volume浮点数

对偶凸包的体积

方法

add_halfspaces(halfspaces[, restart])	处理一组额外的新半空间。
close()	完成增量处理。