使用 Python 包polytope
,可以从多面体的顶点计算凸多面体的半空间表示,如下所示:
从顶点表示到半空间表示
"""How to compute the halfspace representation of a convex polytope.
The polytope is given in vertex representation,
and this script shows how to convert the vertex representation
to a halfspace representation.
"""
import numpy as np
import polytope
vertices = np.array([[2, -2], [2, 2], [-10, 2], [-10, -2]])
poly = polytope.qhull(vertices) # convex hull
# `poly` is an instance of the class `polytope.polytope.Polytope`,
# which is for representing convex polytopes.
# Nonconvex polytopes can be represented too,
# using the class `polytope.polytope.Region`.
print('Halfspace representation of convex polytope:')
print('matrix `A`:')
print(poly.A)
print('vector `b`:')
print(poly.b)
# print(poly) # another way of printing
# a polytope's halfspace representation
问题中给出的半空间表示代表相同的多面体
该问题使用了两个不同的软件包,每个软件包都给出了不同的半空间表示。正如下面的代码所检查的,这两个半空间表示表示相同的多面体。该代码还显示它们等于上面使用 Python 包获得的答案polytope
。
"""Showing that the question's halfspace representations are the same polytope.
Any polytope has infinitely many minimal halfspace representations.
The representations below happen to be minimal, and equal up to scaling and
permutation of rows of `A` and elements of `b`.
"""
import numpy as np
import polytope
# halfspace representation computed using `polytope`
# from the vertex representation given in the question
vertices = np.array([[2, -2], [2, 2], [-10, 2], [-10, -2]])
poly = polytope.qhull(vertices)
# first halfspace representation given in the question
A = np.array([
[-0.00000000e+00, -1.00000000e+00],
[-1.00000000e+00, -0.00000000e+00],
[4.93432455e-17, 1.00000000e+00],
[1.00000000e+00, -0.00000000e+00]])
b = np.array([2., 10., 2., 2.])
question_poly_1 = polytope.Polytope(A, b)
# second halfspace representation given in the question
A = np.array([
[0.0, -0.4472],
[0.4472, -0.0000],
[0.0, 0.4472],
[-0.0995, -0.0000]])
b = np.array([0.8944, 0.8944, 0.8944, 0.9950])
question_poly_2 = polytope.Polytope(A, b)
# check that all the above halfspace representations
# represent the same polytope
assert poly == question_poly_1, (poly, question_poly_1)
assert poly == question_poly_2, (poly, question_poly_2)
上面的 Python 代码适用于polytope
0.2.3 版本。
polytope
可以使用包安装程序从Python包索引 (PyPI)安装包pip
:
pip install polytope