[help-3dldf] Re: Ellipsoids

[Hans Aberg]

On 2004/11/23 23:01, Laurence Finston at address@hidden wrote:

> Months ago I worked out a formula for the intersections of an ellipse and a
> circle in a plane using substitution, but it's quite long, so I'm not sure
> it's really correct.  I've never gotten around to testing it.  If it works, I
> believe I can use  it to find the intersections of two coplanar ellipses,
> because I could just transform one to a circle.  I have never seen this
> problem covered in a math book.  Currently, I use an iterative routine that
> traverses one of the ellipses, but it's quite slow--up to thirty seconds, at a
> guess.  

Have you tried to parametrize? Write each ellipse, i = 1, 2:
    x_i = A_i (cos t_i; sin t_i) + B_i
where x_i and B_i are two-dimensional vectors, and the A_i are 2x2 matrices.
Then equating the x_i, and either solve numerically, or write it (as you
hint) as
    (cos t_1; sin t_1) = A_1^(-1)(A_2 (cos t_2; sin t_2) + (B_1 - B_2))
After that, apply cos^(-1) to the top row, and sin^(-1) to the second, which
gives an equation with only t_2 in it, of the form
    a cos t_2 + b sin t_2 = c
Then rewrite the LHS as
    r cos(t_2 - theta)
where r := sqrt(a^2 + b^2), theta := tan^(-1)(b/a). (You get such formulas
by looking into a handbook, or in this particular case, by writing on polar
form (a + ib) = r e^(i theta), using the identity (a + ib) e^(ix) = r e^(i(x
+ theta)), looking at the real or imaginary part.) Then
    t_2 := theta +/- cos^(-1)(c/b)
And this also gets t_1. Then use this parametrization to compute the
intersection regions.

  Hans Aberg