如何查找给定 3D 形状中的所有点

Question

考虑 3D 空间，我们只研究整数点 。然后我们得到 3 个基向量（当然是非正交的），通过它们我们可以获得 3D 弯曲立方体（用英语怎么说？）。问题是：如何找出这个弯曲立方体内的所有点？我想找到一种方法来扫描目标空间附近的所有点。但我不知道怎么办。

最近我有一些解决方案的想法。解点 必须满足一个方程 where ) for i=1,2,3 （x_i can=0 是我的另一个考虑因素，这很好）。所以问题总结就是找到解决方案 其中 A 和 b 都是整数矩阵， 的第一行是 ，第二行 ...

然后我不知道下一步该做什么。一个超级天真的解决方案是选择一个非常大的空间B，并检查B中的每个点b，看是否存在满足Ax=b的x。

有更好的方法吗？

Answer 1

像 {a1,a2,a3} 这样的基不定义平行六面体，而是定义完整的 3D 空间。它只是与典型正交系统不同的“坐标系统”。

任意点 P(px,py,pz) 都可以表示为基向量的组合：

P= u1·a1 + u2·a2 + u3·a3

通过将每个向量展开为其 x、y、z 分量，该向量方程以矩阵形式

[P]=[A]·[u]

表示。

[u]

是一个列矩阵。

要找到点

Pi

的 [ui] 向量，您必须反转（即得到 [A^-1]）矩阵 [A]，然后 [ui]=[A^-1]·[Pi ]

问题是，如果所有

u1,u2,u3

>= 0

，我们可以认为一个点位于轴“内部”

因此，要检查您的点集合（笛卡尔系统中给出的坐标），您需要计算每个点的 [ui] 分量

Pi

并检查某个分量是否为 < 0。

注意：
如果所有 ux,uy,uz 属于 [0,1] 范围，则意味着

P

位于平行六面体（6 个面，边平行于轴）内，其顶点由 start (0,0,0) 和 end 定义(aix,aiy,aiz) 点。
不要与“归一化长度”（长度=1）混淆：如果所有a1，a2，a3向量的长度=1，那么你就有一个“统一基础”