I'm currently writing software which analyses STEP files to hunt for engineered parts with particular shapes. The software uses Open Cascade which presents me with topological and geometrical objects in a BREP representation. When this gives me explicit cylindrical and toroidal surfaces, and explicit circles, ellipses and lines, I can accomplish my task fairly easily. The problem arises when shapes that I know are meant to be circles or ellipses–and were probably drawn with that intent in whatever CAD software produced the STEP file–are represented in the BREP format as spline curves of various degree, which approximate the desired shapes perfectly well visually, and for manufacturing, but which lose the original design intent.
Curves (or "edges") in the BREP format are parameterized, and I can get positions, tangents, curvature and centre of curvature at any parameter value. So actually, detecting straight lines is easy–I just look for zero curvature along the length–and similarly for circular arcs, where I can just look for constant curvature at a number of sampled parameter values. My question is, given the same information, how can I detect elliptical arcs (they might not be complete ellipses) that are not circular? What should I be looking for? Ideally, I want the center of the ellipse (or the two foci) and the major and minor radii, but the crucial output would be the center itself.
Googling just turns up a mountain of results about doing the opposite, i.e. approximating conics using splines (as the CAD software does to begin with). Nobody seems to want to reverse the process!
Suppose you have the set of points $\{ P_i(x_i, y_i, z_i) \}$ of the original curve.
First step is to ensure that these points lie on one plane. This should be straight forward. Next you want to find the $2D$ coordinates of $\{ P_i \}$ in a reference frame attached to the plane in which the points lie. Let the unit normal vector to the plane be $n$, then one can find (in infinite ways) two vectors $u_1, u_2$ such that $u_1, u_2, n$ form an orthonormal triple, i.e. they constitute a coordinate frame. Define
$R = [u_1, u_2, n ] $
If the coordinate frame has its origin at $P_1$ then
$P = R Q + P_1$
So that $Q = R^T (P - P_1) $ is the coordinate vector in the coordinate frame specified by $P_1$ and $ R$. The $Q$ vector always has its third coordinate equal to zero. So we are only concerned with the first two entries of the vector $Q$.
Now take five points $P$'s and find the corresponding $Q's$, you will have five ordered pairs $(x_i, y_i), i = 1, 2, 3, 4, 5 $
Using the determinant definition of an ellipse, for any point $(x, y)$ on the ellipse the following is true:
$\begin{vmatrix} x^2 && xy & y^2 && x && y && 1 \\ x_1^2 && x_1y_1 & y_1^2 && x_1 && y_1 && 1 \\ x_2^2 && x_2y_2 & y_2^2 && x_2 && y_2 && 1 \\ x_3^2 && x_3y_3 & y_3^2 && x_3 && y_3 && 1 \\ x_4^2 && x_4y_4 & y_4^2 && x_4 && y_4 && 1 \\ x_5^2 && x_5y_5 & y_5^2 && x_5 && y_5 && 1 \end{vmatrix} = 0 $
If the edge points $\{ P_i \}$ truly describe an ellipse, then any of these points $P$ when transformed as above, generates an ordered pair $(x,y)$ that satisfies the above determinant equation. You don't have to compute the whole determinant for each $(x,y)$, you can compute the coefficients of $x^2, xy, y^2, x, y, 1$ (by computing the cofactors of the above determinant) so that you have ready the equation of the ellipse
$A x^2 + B xy + + C y^2 + D x + E y + F = 0 $
This is much simpler to evaluate for each ordered pair $(x,y)$.