algorithm - 找到球体中所有晶格​​点的最佳方法

Question

给定一堆任意向量(存储在矩阵 A 中)和半径 r，我想找到落在半径 r 的球体内的那些向量的所有整数值线性组合。然后我会将必要的坐标存储在矩阵 V 中。因此，例如，如果线性组合

K=[0; 1; 0]

落在我的球体内，即类似

if norm(A*K) <= r then
   V(:,1)=K
end

等等

A 中的向量肯定是给定格的最简单可能基础，并且最大向量的长度为 1。不确定这是否以任何有用的方式限制了向量，但我怀疑它可能。 - 他们不会像不太理想的基础那样具有相似的方向。

我已经尝试了几种方法，但没有一种看起来特别令人满意。我似乎找不到一个很好的模式来遍历格子。

我目前的方法是从中间开始(即所有 0 的线性组合)并一个一个地遍历必要的坐标。它涉及存储一堆额外的向量来跟踪，所以我可以遍历坐标的所有八分圆(在 3D 情况下)并一个一个地找到它们。这个实现看起来非常复杂而且不是很灵活(特别是它似乎不容易推广到任意数量的维度 - 尽管这对于当前目的来说并不是绝对必要的，但它是一个不错的选择)

是否有一种很好的*方法来找到所有需要的点？

(*理想情况下既高效又优雅**。如果真的有必要，在球体外部有几个额外的点并不重要，但最好不要更多。我确实需要球体内的所有向量.-如果它有很大的不同，我对 3D 情况最感兴趣。

**我很确定我当前的实现两者都不是。)

---

我发现的类似问题:

Find all points in sphere of radius r around arbitrary coordinate - 这实际上是一个比我正在寻找的更普遍的情况。我只处理周期性晶格，我的球体始终以 0 为中心，与晶格上的一点重合。但我没有点列表，而是一个向量矩阵，我可以用它生成所有点。

How to efficiently enumerate all points of sphere in n-dimensional grid - 完全规则的超立方晶格和曼哈顿距离的情况。我正在寻找完全任意的格子和欧氏距离(或者，为了提高效率，显然是它的平方)。

Answer 1

顺便说一句，在没有证明任何断言的情况下，我认为 1) 如果向量集不是最大秩，则解的数量是无限的； 2) 如果集合是最大秩的，则向量生成的线性变换的图像是目标空间的一个子空间(例如，平面)，它与球体相交在一个较低维的球体中； 3)由此可以将问题简化为1-1线性变换(k维空间上的kxk矩阵)； 4) 由于矩阵是可逆的，您可以将球体“拉回”到包含格点的空间中的椭球体，作为奖励，您可以获得椭球体的良好几何描述(主轴定理)； 5) 你的问题现在变成了确定椭圆体内的格点。

后一个问题与高斯考虑的一个老问题(计算椭圆内的格点)有关，他推导出了一个很好的近似值。确定一个椭圆(oid)内的格点可能不是那么整洁的问题，但它可能一次减少一个维度(椭圆体和平面的横截面是另一个椭圆体)。