c++ - 由 n 个点定义的超平面

Question

我有以下问题:

给定空间中的 n 个点，我正在搜索穿过它们的超平面。

此类问题的最简单示例是两点 (x_1=0,x_2=0) 和 (1,-1)，我想返回 1*x_1+1*x_2=0。

我的点将是 32 位整数的 n 元组。所需超平面 a_1 x_1 + a_2 x_2 + ... = c 的系数 a_i 也必须是 32 位整数。如果不能以这种方式定义超平面，我想报告这一点。

我的项目是用 C++ 编写的。

我可能可以自己编写代码，但我预计这需要大量工作。此外，我的直觉是，这是一个足够普遍的问题，可能会有一个开源库可以解决我的问题。有人知道可以解决我的问题的库吗？

提前致谢!

Answer 1

实际上这并不难，因为给定的点是线性无关的。

设 Z^n 中的 u^i 为节点，然后将 v^i 定义为 (u^i_0, ..., u^i_{n-1},-1)。

现在创建一个矩阵A

( v^0_0     v^0_1 ...     v^0_n     )
( v^1_0     v^1_1 ...     v^1_n     )
    .         .             .
    .         .             .
    .         .             .
( v^{n-2}_0 v^{n-2}_1 ... v^{n-2}_n )

你要解决的是 A * x == 0。

现在继续进行高斯消元。确保您仍然让系数为整数。因此，您不必执行 r_k -= r_ki * r_i/r_ii，而是执行 r_k = r_ki * r_i - r_ii * r_k。在每个步骤之后，将处理后的行除以其最大公约数。这通常可以避免溢出。如果您遇到溢出，只需为矩阵运算本身使用更大的类型。

最后，您将得到一个矩阵，其中最多有两列具有多个条目。您的解决方案将仅取决于这两行值的选择，例如它看起来像

1 1 1 0 0 0
2 0 0 1 0 0
0 1 0 0 1 0
1 1 0 0 0 1

将任何值分配给 x_0 和 x_1(在本例中)，您就完成了。x 的最后一个值将是超平面等式的右侧。