如何在多边形/多面体中找到整数点(坐标)？

Question

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

单独找出点阵怎么样？例如，这类函数

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

另外，我正在寻找在多变量场景中工作的东西(约束在x，y，z，.)。

我目前正试图使用ppl来解决这个问题。

Answer 1

数学这里中有一个很好的答案

点= {x，y} /。列表@ToRules@ Reducex >= 4 y&x <= 4 y+3&0

​

​

Answer 2

使用package polytope，可以按如下方式计算d-dimensional多点内的积分点(此脚本基于我编写的一个测试：(第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.]]