I have an ellipsoid whose center, raddi and rotation are known. Also, I know the location of two points A and B which can be anywhere inside an ellipsoid. I want to know the distance between C and D. Any Idea how to implement this in fast and efficient way. Thank you.
On
Let $\mathbf v={B-A\over \lVert B-A\rVert}$. The the line through points $A$ and $B$ can be parameterized as $A+t\mathbf v$. Since $\lVert\mathbf v\rVert=1$, the parameter $t$ measures distance along this line. Now, substitute this into the equation of the ellipsoid, obtaining a quadratic equation in $t$. Writing this equation as $at^2+bt+c=0$, its solutions are the standard ${-b\pm\sqrt{b^2-4ac}\over2a}$, per the quadratic formula. The length of the chord is of course the distance between the points represented by these solutions, but since we’ve arranged for $t$ to measure distances along the line, the chord length is also equal to the absolute value of the difference between the roots of the quadratic, namely $${\sqrt{b^2-4ac}\over\lvert a\rvert}.\tag1$$ You will need to determine the coefficients of this quadratic equation yourself from whatever equation it is that you have for the ellipsoid.
For instance, the equation of any quadric in $\mathbb R^n$ can be written in matrix/vector form as $$(\mathbf x-\mathbf p)^TQ(\mathbf x-\mathbf p)=0,$$ where $Q$ is a symmetric $n\times n$ matrix and $\mathbf p$ corresponds to a translation from the origin (in the case of an ellipsoid, its center). Substituting the parameterization of the line into this, expanding by linearity and rearranging, we obtain the quadratic equation $$(\mathbf v^TQ\mathbf v)t^2+2\mathbf v^TQ(A-\mathbf p)t + (A-\mathbf p)^TQ(A-\mathbf p)=0.\tag2$$
Since you know the center $\mathbf p$, rotation $R$ and semiaxis lengths $\lambda$, $\mu$, $\tau$† of the ellipsoid, you can simplify this quite a bit. If you apply the inverse of the transformation that rotates and translates the ellipsoid from standard position, i.e., set $A'=R^{-1}(A-\mathbf p)$, $B'=R^{-1}(B-\mathbf p)$ and $\mathbf v' = {B'-A'\over\lVert B'-A'\rVert} = R^{-1}\mathbf v$, then in this new coordinate system equation (2) becomes $$(\mathbf v'^TQ'\mathbf v')t^2+2(\mathbf v'^TQ'A')t+A'^TQ'A'=0$$ with $Q'=\operatorname{diag}(1/\lambda^2,1/\mu^2,1/\tau^2)$, making the chord length $${2\sqrt{(\mathbf v'^TQ'\mathbf A')^2-(\mathbf v'^TQ'\mathbf v')(\mathbf A'^TQ'\mathbf A')}\over\lvert\mathbf v'^TQ'\mathbf v'\rvert}.\tag3$$ Expanding by coordinates, we have $$\mathbf v'^TQ'\mathbf v' = {v_x'^2\over\lambda^2}+{v_y'^2\over\mu^2}+{v_z'^2\over\tau^2} \\ \mathbf v'^TQ'\mathbf A' = {v_x'a_x'\over\lambda^2}+{v_y'a_y'\over\mu^2}+{v_z'a_z'\over\tau^2} \\ \mathbf A'^TQ'\mathbf A' = {a_x'^2\over\lambda^2}+{a_y'^2\over\mu^2}+{a_z'^2\over\tau^2}.$$ I’ll leave working the rest out to you. If I were coding this, though, I’d compute it in stages as was done above instead of trying to expand (1) into a closed-form expression in terms of the coordinates of $A$ and $B$. Recall, too, that for a rotation matrix $R^{-1}=R^T$.
† These are usually named $a$, $b$ and $c$, but I’ve already used those names for the coefficients of the quadratic equation.
On
Hint:
Let the implicit equation of the ellipse be
$$ax^2+2bxy+cy^2+2dx+2ey+f=0$$ and the parametric line by the two given points be
$$x=x_0+t\,x_{01},\\y=y_0+t\,y_{01}.$$
You can normalize the linear coefficients with
$$x=x_0+t\frac{x_{01}}{\sqrt{x_{01}^2+y_{01}^2}},\\y=y_0+t\frac{y_{01}}{\sqrt{x_{01}^2+y_{01}^2}}$$ and $t$ now represents the abscissa along the line.
Plugging the expression of $x,y$ in the first, and expanding, you get a quadratic equation in $t$. The distance between the two points is just the difference between the two roots.
This generalizes to 3D, with an ellipsoid.
Let $F_1$ and $F_2$ the foci of the ellipse with $F_1(-c,0)$ and $F_2(c,0)$. The centre of the ellipse is, for simplicity, $C(0,0)$. The equation of the ellipse is: $$\frac{x^2}{a^2}+\frac{y^2}{b^2}=1$$ with $a,b$ that have to be known. For the line $AB$, instead: $m=\frac{y_A-y_B}{x_A-x_B}$ and the equation is: $$y-y_A=\frac{y_A-y_B}{x_A-x_B}(x-x_A)$$The points $C$ and $D$ are generated by: $$\left\{\begin{matrix} \frac{x^2}{a^2}+\frac{y^2}{b^2}=1 \\y-y_A=\frac{y_A-y_B}{x_A-x_B}(x-x_A) \end{matrix}\right.$$
Substituing $y=y_A+\frac{y_A-y_B}{x_A-x_B}(x-x_A)=mx+q$ and taking the discriminant, I obtain: $$x=\frac{\frac{2mq}{b^2}\pm\sqrt{\frac{4m^2q^2}{b^4}-4\frac{q^2}{b^2a^2}-4\frac{m^2q^2}{b^4}+4\frac{1}{a^2}+4\frac{m^2}{b^2}}}{2\left ( \frac{1}{a^2}+\frac{m^2}{b^2} \right )}=\frac{\frac{2mq}{b^2}\pm\sqrt{-\frac{q^2}{b^2a^2}+\frac{1}{a^2}+\frac{m^2}{b^2}}}{2\left ( \frac{1}{a^2}+\frac{m^2}{b^2} \right )}$$ So, $\Delta x$ is: $\Delta x=\frac{2\cdot \sqrt{-\frac{q^2}{b^2a^2}+\frac{1}{a^2}+\frac{m^2}{b^2}}}{2\left ( \frac{1}{a^2}+\frac{m^2}{b^2} \right )}=\frac{\sqrt{-\frac{q^2}{b^2a^2}+\frac{1}{a^2}+\frac{m^2}{b^2}}}{{\left ( \frac{1}{a^2}+\frac{m^2}{b^2} \right )}}$. For $\Delta y$, instead, I obtain: $\Delta y=m\cdot\Delta x=m\cdot \left ( \frac{\sqrt{-\frac{q^2}{b^2a^2}+\frac{1}{a^2}+\frac{m^2}{b^2}}}{{\left ( \frac{1}{a^2}+\frac{m^2}{b^2} \right )}} \right )$. By the Pythagorean theorem, I have: $$l_{CD}=\sqrt{(\Delta x)^2+(\Delta y)^2}=\sqrt{\left (\frac{\sqrt{-\frac{q^2}{b^2a^2}+\frac{1}{a^2}+\frac{m^2}{b^2}}}{{\left ( \frac{1}{a^2}+\frac{m^2}{b^2} \right )}}\right )^2+m^2\cdot \left ( \frac{\sqrt{-\frac{q^2}{b^2a^2}+\frac{1}{a^2}+\frac{m^2}{b^2}}}{{\left ( \frac{1}{a^2}+\frac{m^2}{b^2} \right )}} \right )^2}=\left (\frac{\sqrt{-\frac{q^2}{b^2a^2}+\frac{1}{a^2}+\frac{m^2}{b^2}}}{{\left ( \frac{1}{a^2}+\frac{m^2}{b^2} \right )}}\right )\cdot\sqrt{m^2+1}$$ In this eqution, you have to substitute $m=\frac{y_A-y_b}{x_A-x_B}$ and $q=y_A+-x_A\cdot\frac{y_A-y_b}{x_A-x_B}$.
Note that $y=mx+q$ does not represents all the possible lines in the Cartesian plane: the only special case is the line $x=k$ with $-a\leq k\leq a$. For this, I have: $$\left\{\begin{matrix} \frac{x^2}{a^2}+\frac{y^2}{b^2}=1 \\x=k \end{matrix}\right.$$
So: $l_{CD}=\Delta y=2\cdot\frac{b}{a}\cdot\sqrt{a^2-k^2}=2\cdot\frac{b}{a}\cdot\sqrt{(a+k)(a-k)}$
More calculations are required when the ellipse is shifted or rotated.