python - 如何在多面体/多面体中找到整数点（坐标）？

Question

我正在使用 Python，但我不介意更改语言。我从我的研究中得到的只是计算一个区域内（晶格）点数量的工具，给出了包围它的平面的方程。其他工具用于优化多面体内部的给定函数（线性规划）。

单独找到格点怎么样？例如，一个函数

latticePoints( 'x < 5 & x > 0' ) = [ 1, 2, 3, 4]

另外，我正在寻找可以在多变量场景中工作的东西（x、y、z、...的约束）。

我目前正在尝试使用ppl解决这个问题。

Answer 1

使用 Python 包polytope，可以按如下方式计算一维多面体中的积分点d（此脚本基于我编写的测试：（polytope_test.py第 415--455 行）：

"""How to compute all points with integer coordinates inside a polytope."""
import numpy as np
import polytope.polytope as alg


def example():
    """Demonstrate the integral points computation."""
    # convex polytope
    vertices = np.array([[0.5, 1.5], [0.5, 1.5]])
    hull = alg.box2poly(vertices)
        # `hull` is an instance of the class `polytope.polytope.Polytope`,
        # which is for representing convex polytopes
    integral_points = alg.enumerate_integral_points(hull)
    print(hull)
    print('contains the integral points:')
    print(integral_points)
    #
    # nonconvex polytope
    vertices = np.array([[0.0, 0.0], [1.0, 1.0], [2.0, 1.0]])
    hull_1 = alg.qhull(vertices)  # convex hull of vertices in `vertices`
    hull_2 = alg.box2poly([[1.0, 2.0], [1.0, 2.0]])
    nonconvex = hull_1.union(hull_2)
        # `nonconvex` is an instance of the class `polytope.polytope.Region`,
        # which is for representing any polytope, including nonconvex ones,
        # and in this case can also be constructed with
        # `polytope.polytope.Region([hull_1, hull_2])`
    integral_points = alg.enumerate_integral_points(nonconvex)
    print('The polytope that is the union of the following polytopes:')
    print(nonconvex)
    print('contains the integral points:')
    print(integral_points)
    #
    # 3-dimensional polytope
    vertices = np.array([
        [0.0, 0.0, 0.0],
        [1.0, 0.0, 0.0],
        [0.0, 1.0, 0.0],
        [0.0, 0.0, 1.0]])
    hull = alg.qhull(vertices)
    integral_points = alg.enumerate_integral_points(hull)
    print(hull)
    print('contains the integral points:')
    print(integral_points)


if __name__ == '__main__':
    example()

目前，上述 Python 代码适用于 的开发版本polytope，可以使用包安装程序进行安装pip：

pip install git+git://github.com/tulip-control/polytope.git

或者通过克隆 GitHub 存储库，并从克隆的存储库安装：

git clone git@github.com:tulip-control/polytope
cd polytope
pip install .

上面的 Python 脚本输出：

Single polytope
  [[ 1.  0.] |    [[ 1.5]
   [ 0.  1.] x <=  [ 1.5]
   [-1. -0.] |     [-0.5]
   [-0. -1.]]|     [-0.5]]

contains the integral points:
[[1.]
 [1.]]
The polytope that is the union of the following polytopes:
     Polytope number 1:
     Single polytope
          [[-0.70711  0.70711] |    [[0.]
           [ 0.       1.     ] x <=  [1.]
           [ 0.44721 -0.89443]]|     [0.]]

     Polytope number 2:
     Single polytope
          [[ 1.  0.] |    [[ 2.]
          [ 0.  1.] x <=  [ 2.]
          [-1. -0.] |     [-1.]
          [-0. -1.]]|     [-1.]]



contains the integral points:
[[0. 1. 2. 1. 2.]
 [0. 1. 1. 2. 2.]]
Single polytope
  [[ 0.      -1.      -0.     ] |    [[0.     ]
   [-1.      -0.      -0.     ] x <=  [0.     ]
   [ 0.       0.      -1.     ] |     [0.     ]
   [ 0.57735  0.57735  0.57735]]|     [0.57735]]

contains the integral points:
[[0. 0. 1. 0.]
 [0. 0. 0. 1.]
 [0. 1. 0. 0.]]

Answer 2

Mathematica这里有一个很好的答案：

点 = {x, y} /。List@ToRules@ Reduce[x >= 4 y && x <= 4 y + 3 && 0 < x < 63 && 0 < y < 15, {x, y}, 整数]

---

         

---