0

I'm trying to realize a multi trilateration in c++. I have three ranges with which I want to determine a certain point in 3d space. I've already looked up for solutions and found a usable python code snipped. Then I have rewritten the whole snipped in c++ but the results are kind of odd and of the expected results. Their must be some common mistakes which I just don't see (maybe it's too obvious lol). The test data is from here, and I know that this linear way of solving the gps trillat problem is not even remotely accurate but that's not important for my purpose. The resulting vector is: -3.39803e+29, 3.39803e+29, -3.39803e+29 which cannot be true.

/* Recursive function for finding determinant of matrix.
  n(rows) is current dimension of A[][]. */
double clacDeterminant(double **A, int rows)
{
  double D = 0; // Initialize result

  //  Base case : if matrix contains single element
  if (rows == 1)
      return A[0][0];

  int sign = 1;  // To store sign multiplier

  // Iterate for each element of first row
  for (int f = 0; f < rows; f++)
  {
      // Getting Cofactor of A[0][f]
      double **temp = getCofactor(A, 0, f, rows);
      D += sign * A[0][f] * clacDeterminant(A, rows - 1);

      // terms are to be added with alternate sign
      sign = -sign;
  }

  return D;
}

// Function to get adjoint of A[N][N] in adj[N][N].
double** calcAdjoint(double **A, int matrixArows)
{
  double** adj = allocate2Ddouble(matrixArows, posMTrillatASize);
  int sign = 0;

  for (int i=0; i<matrixArows; i++)
  {
      for (int j=0; j<posMTrillatASize; j++)
      {
          // Get cofactor of A[i][j]
          double **temp = getCofactor(A, i, j, posMTrillatASize);

          // sign of adj[j][i] positive if sum of row
          // and column indexes is even.
          sign = ((i+j)%2==0)? 1: -1;

          // Interchanging rows and columns to get the
          // transpose of the cofactor matrix
          adj[i][j] = (sign)*(clacDeterminant(A, posMTrillatASize-1));
      }
  }
  return adj;
}

// by https://www.programiz.com/cpp-programming/examples/matrix-multiplication-function modified by L.K.
// method assumes that matrices have same dim sizes
double** multiplyMatrices(double **matrixA, double **matrixB, int matrixArows)
{
  double** outputMatrix = allocate2Ddouble(matrixArows, posMTrillatASize);
  int i, j, k;

  // Initializing elements of matrix mult to 0.
  for(i = 0; i < matrixArows; ++i)
  {
    for(j = 0; j < posMTrillatASize; ++j)
    {
      outputMatrix[i][j] = 0;
    }
  }

  // Multiplying matrix matrixA and matrixB and storing in array mult.
  for(i = 0; i < matrixArows; ++i)
  {
    for(j = 0; j < posMTrillatASize; ++j)
    {
      for(k=0; k<posMTrillatASize; ++k)
      {
        outputMatrix[i][j] += matrixA[i][k] * matrixB[k][j];
      }
    }
  }
  return outputMatrix;
}

double* multiplyMatrixByVector(double **matrixA, double vectorB[])
{
  double vectorRes[posMTrillatASize];
  memset(vectorRes, 0, posMTrillatASize*sizeof(double));

  for (int i=0;i<posMTrillatASize;i++)
  {
      for (int j=0;j<posMTrillatASize;j++)
      {
          vectorRes[i]+= (matrixA[i][j]*vectorB[j]);
      }
  }

  return vectorRes;
}

double** transpose2DimMatrix(double **inputArr, int matrixArows, int transpose2DimMatrix)
{
  double **outputArr = allocate2Ddouble(transpose2DimMatrix, matrixArows);
  for (int i = 0; i < matrixArows; ++i)
  {
    for (int j = 0; j < transpose2DimMatrix; ++j)
    {
      outputArr[j][i] = inputArr[i][j];
    }
  }
  return outputArr;
}

// Function to calculate and store inverse, returns 0 if false
// matrix is singular by https://www.geeksforgeeks.org/adjoint-inverse-matrix/
double** calcInverse(double **A, int matrixArows)
{
  double** inverse = allocate2Ddouble(matrixArows, posMTrillatASize);
  // Find determinant of A[][]
  int det = clacDeterminant(A, posMTrillatASize);
  if (det == 0)
  {
      cout << "Singular matrix, can't find its inverse";
      return 0;
  }

  // Find adjoint
  double **adj = calcAdjoint(A, matrixArows);

  // Find Inverse using formula "inverse(A) = adj(A)/det(A)"
  for (int i=0; i<matrixArows; i++)
      for (int j=0; j<posMTrillatASize; j++)
          inverse[i][j] = adj[i][j]/double(det);

  return inverse;
}

double* leastSquareReg(double **matrixA, double vectorB[], int matrixArows, int matrixAcol)
{
  double **matrixATransposed = transpose2DimMatrix(matrixA, matrixArows, matrixAcol);
  double **matrixATransposedA = multiplyMatrices(matrixATransposed, matrixA, matrixAcol);
  double **matrixATransposedAInverse = calcInverse(matrixATransposedA, matrixArows);
  double **matrixATransposedAAdd = multiplyMatrices(matrixATransposedAInverse, matrixATransposed, matrixArows);
  double *finalX = multiplyMatrixByVector(matrixATransposedAAdd, vectorB);

  return finalX;
}

ecefPos trillatPosFromRange(satLocation finalSatPos, satRanges finalSatRanges)
{
  std::map<int, ecefPos>::iterator it_;
  std::map<int, double>::iterator finalSatRangesMap;
  int matrixArows, matrixAcol = 0;
  double x, y, z;
  double Am, Bm, Cm, Dm;
  double range;
  int nSat = finalSatPos.locations.size();
  ecefPos finalPos = { 0.0, 0.0, 0.0 };

  matrixAcol = posMTrillatASize;
  matrixArows = nSat;

  double **matrixA = allocate2Ddouble(nSat, 3);
  double vectorB[posMTrillatASize] = {};

  int i = 0;
  for (it_ = finalSatPos.locations.begin(); it_ != finalSatPos.locations.end(); it_++)
  {
    // look up for pseudo range with same sat id
    finalSatRangesMap = finalSatRanges.ranges.find(it_->first);
    range = finalSatRangesMap->second;

    if (it_ != finalSatPos.locations.end())
    {
      x = it_->second.x;
      y = it_->second.y;
      z = it_->second.z;
      Am = -2*x;
      Bm = -2*y;
      Cm = -2*z;
      Dm = EARTH_RADIUS_KM*EARTH_RADIUS_KM + (pow(x,2)+pow(y,2)+pow(z,2)) - pow(range,2);

      matrixA[i][0] = Am;
      matrixA[i][1] = Bm;
      matrixA[i][2] = Cm;
      vectorB[i] = Dm;
      i++;

    } else
    {
      std::cout << "could not find sat pos for user pos trilateration" << std::endl;
    }
  }

  // least square regression
  double *finalECEF = leastSquareReg(matrixA, vectorB, matrixArows, matrixAcol);

  finalPos.x = finalECEF[0];
  finalPos.y = finalECEF[1];
  finalPos.z = finalECEF[2];

  for (int i = 0; i < 5; ++i)
  {
    std::cout << finalECEF[i] << std::endl;
  }
  return finalPos;
}
  • That's quite a lot of code. "Strange" numbers are usually a hint of uninitialized variables or undefined/unspecified behaviour. UB could be caused by out-of-bounds-accesses. I'd start debugging in `allocate2Ddouble`. – Lukas-T Nov 03 '20 at 09:59
  • How are you compiling? For uninitialized variable the compiler should give a warning. Try with flags -Wall -Wextra. – Stef Nov 03 '20 at 10:58
  • @Stef I tried it with flags but there were no warnings besides unused vars. – Peter Hackman Nov 04 '20 at 08:43
  • @churill if I had an out bound acces wouldn't my program just crash? at least that's what it has always been like for me – Peter Hackman Nov 04 '20 at 08:43
  • @PeterHackman No, at least in theory, undefined behaviour means, _anything_ can happen. Yes, in practice you usually get a segmentation fault. But sometimes you don't and just get strange values. – Lukas-T Nov 04 '20 at 09:56
  • @PeterHackman Consider the code `int a[10]; int b = 3; a[10] = 4;`. You might get a segmentation fault; or maybe the program runs fine, but now `b` is equal to 4. – Stef Nov 04 '20 at 10:27

0 Answers0