Feature: Full Spherical Distance Determination Algorithm (FSDDA)

[nguy8tri]

Description

This algorithm directly fits a circle with all points, eliminating the need for iterative solvation. However, the process is not as easy:

Algorithm

1. Compute the Plane of the Points (SVD)
   a. Compute the Centroid of the Points (this will be a plane point, so now we just need a normal vector)
   b. Subtract the centroid from all points and produce the outer product using each point against itself. Add all matrices together (the result is symmetric).
   c. Solve for the eigenvector associated with the lowest eigenvalue. This will be easier since you have a 3D matrix, and you simply need to solve a cubic equation (Cardano's method). This is the plane vector. If the other eigenvalues are distinct, their eigenvectors can form a basis for the plane, which you will need in the next step.
2. Compute the Points in 2D space on the plane
   a. Project all points onto the plane. This is found by subtracting each point with any point on the plane, finding the projection of that point on the plane's normal vector, then subtracting the point by the normal vector times the length of the projection.
   b. Express all points in the basis vectors of the plane. Use the centroid as the center of the coordinate system, subtract that from each vector, then find the projection distance of the results onto the basis to get the "x, y" of each point
3. Find the circle
   a. Using your 2D points, fit them to a circle using any method. Probably least squares, using the general formula of a circle (hint, use the pseudo inverse)
   b. Project the center and radius vectors back into 3D space using the center of the coordinate system as well as the basis vectors.

Resources

1. Fitting a Plane to Points
2. Finding the Eigenvalues and Eigenvectors of a 3x3 symmetric matrix

[nguy8tri]

We need to research each component of this a little bit more. SVD and least squares are very sensitive to noise :(.

[j4lando]

I believe the RANSAC algorithm begins with SVD as an initial guess.

[lsakunes]

I might be misunderstanding something about this so please fact check, but I think even for a spherical body, when you take a picture of the horizon from the altitude we're at, we don't get a circular horizon. The tutorial paper claims it's just a general conic, so an ellipse, parabola, or hyperbola (depending on FOV and altitude). Our FOV is quite wide, so I think it takes us even further away from a circular approximation. Again, I don't know for sure, but the tutorial paper made a big point of going through the math to prove it's not, and it looked quite convincing.

(Sorry I commented this on the wrong thing initially)

[nguy8tri]

@lsakunes You are right, if we're talking about fitting on the image plane itself. However, SDDA and FSDDA both project the points into 3D onto the unit sphere, and no matter what orientation you are looking at earth, those points must form a circle. The geometry explanation that Josh gave a while back shows why this is the case.

[lsakunes]

Oh, I see. Thank you for the clarification.