Гиперплоскость, определяемая n точками

У меня есть следующая проблема:

Учитывая n точек в пространстве, я ищу гиперплоскость, которая проходит через них.

Самый простой пример такой задачи - это две точки (x_1=0, x_2=0) и (1,-1), и я хотел бы получить 1*x_1+1*x_2=0.

Мои точки будут n-кортежами 32-битных целых чисел. Коэффициенты a_i искомой гиперплоскости a_1 x_1 + a_2 x_2 + ... = c также должны быть 32-битными целыми числами. В случае, если гиперплоскость не может быть определена таким образом, я хотел бы доложите об этом.

Мой проект закодирован на языке c++.

Я, вероятно, смог бы закодировать это сам, но я предполагаю, что это будет довольно много работы. Кроме того, я подозреваю, что это достаточно общая проблема, чтобы могла существовать библиотека с открытым исходным кодом, которая решила бы мою проблему. Кто-нибудь знает о библиотеке, которая могла бы решить мою проблему?

Заранее спасибо!

3 4
c++ linear-algebra

3 ответа:

На самом деле это не очень трудно, учитывая, что данные точки линейно независимы.

Пусть u^i в Z^n-ваши узлы, а затем определите 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 будет вашей правой стороной равенства гиперплоскости.

3

Я сам им не пользовался, ноLinBox выглядит так, как вы хотите.

2

Все, что вам нужно сделать, это решить систему линейных уравнений: 

X*A = C

Где A = (a_1, ..., a_n)^T, C= (c, ..., c)^T. Они оба n по 1 вектору. И X является m по n матрице 

x^1_1  ...  x^1_n
x^2_1  ...  x^2_n
  .     .     .
  .     .     .
  .     .     .
x^m_1  ...  x^m_n
Где каждая строка-это Координата точки. Предположим, что существуют m точки (независимо от того, являются ли они линейно зависимыми или нет) и m<=n.

Чтобы решить линейные уравнения, попробуйте 2 случая: C = (1, ..., 1)^T, и C = (0, ..., 0)^T.

Тогда вы можете использовать все, что угодно алгоритмы, такие как исключение Гаусса или Гаусса-Жордана, чтобы искать A = (a_1, ..., a_n)^T. Если m<n и / или точки линейно зависимы, у вас будут свободные переменные в A, в противном случае A определяется однозначно. По определенному A можно сказать, что все элементы A являются целыми числами.

-1