假设我们知道一个多面体的顶点，并且想要得到它的半空间表示 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

题中给出的半空间表示表示相同的多胞形

该题使用了两个不同的软件包，并且这些中的每一个都给出了不同的半空间表示。正如下面的代码所检查的，这两个半空间 representations 表示相同的多胞形。代码还表明它们等于上面使用获得的答案 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 version 0.2.3。

软件包 polytope 可以从 Python Package Index (PyPI) using the package installer pip:

安装

pip install polytope

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

Assume we know the vertices of a polytope, and want to get its halfspace representation A * x <= b

python

algorithm

matlab

computational-geometry

polyhedra

从顶点表示到半空间表示

题中给出的半空间表示表示相同的多胞形