假设我们知道多面体的顶点，并希望得到它的半空间表示 A * x <= b

Question

我想得到半空间表示A*x <= b，给定多面体的顶点为python或Matlab。

假设vertices = [2 -2; 2 2; -10 2; -10 -2];是顶点，我使用了两个不同的库，给出了两个不一样的答案，不确定为什么会给出不同的答案。

• 使用https://github.com/stephane-caron/pypoman，

  from numpy import array
  from pypoman import compute_polytope_halfspaces
  vertices = map(array, [[2,-2],[2, 2], [-10, 2], [-10, -2]])
  A, b = compute_polytope_halfspaces(vertices)
  print(A)
  print(b)
  

  输出：

  A =      [[ -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 = [  2.  10.   2.   2.]
  

• 使用多参数工具箱3(http://people.ee.ethz.ch/~mpt/3/((Matlab(

  vertices = [2 -2; 2 2; -10 2; -10 -2];
  Xc = Polyhedron(vertices);
  

  输出：

  >> Xc.A
  ans =
  0   -0.4472
  0.4472   -0.0000
  0    0.4472
  -0.0995   -0.0000
  >> Xc.b
  ans =
  0.8944
  0.8944
  0.8944
  0.9950
  

任何有助于理解为什么会发生这种情况的事情都非常感谢

Answer 1

使用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包CCD_ 4。

"""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。

可以使用包安装程序pip:从Python包索引(PyPI(安装包polytope

pip install polytope