ellipse intersection (was Re: compute intensive scheme)

Aubrey Jaffer <agj@alum.mit.edu> writes:
> Now try to find the intersection of two arbitrary ellipses.
[...]
> Here is how to set up the general intersection of two ellipses; each
> ellipse being those points whose sum of the distances to the two centers
> is a constant (d1, d3).  Please post if you find a solution.

Would this approach work: shrink/stretch/rotate the coord-space until one of
the ellipses is a circle and the other is aligned to the x/y axes. Then solv
e
the circle/ellipse intersection problem. Then transform back into the origin
al
space.

--
Cheers,                                        The Rhythm is around me,
The Rhythm has control.
Ray Blaak                                      The Rhythm is inside me,
rAYblaaK@STRIPCAPStelus.net                    The Rhythm has my soul.

In article <ud5xsvco3.fsf_-_@STRIPCAPStelus.net>,
Ray Blaak <rAYblaaK@STRIPCAPStelus.net> wrote:

> Aubrey Jaffer <agj@alum.mit.edu> writes: 
> [...] 
>
> Would this approach work: shrink/stretch/rotate the coord-space until one 
of
> the ellipses is a circle and the other is aligned to the x/y axes. Then so
lve
> the circle/ellipse intersection problem. Then transform back into the orig
inal
> space.

If you do that, I suspect the second one isn't an ellipse any more,
unless their axes were parallel (or orthoginal) at the start.

--
Bruce |  41.1670S | \  spoken |          -+-
Hoult | 174.8263E | /\ here.  | ----------O----------

Bruce Hoult <bruce@hoult.org> writes:
> In article <ud5xsvco3.fsf_-_@STRIPCAPStelus.net>,
>  Ray Blaak <rAYblaaK@STRIPCAPStelus.net> wrote: 
>
> If you do that, I suspect the second one isn't an ellipse any more,
> unless their axes were parallel (or orthoginal) at the start.

I thought of that, am thinking that it would still be. A different one of
course, but still an ellipse.

I haven't proved it algebraically, but intuitively an arbitrary ellipse can 
be
viewed as a (somewhat rotated) X. Stretching and shrinking can change the X 
so
that the crossing is no long perpendicular, but a new perpendicular X can
always be drawn within the new bounds, showing it is still an ellipse.

Of course, my intuition can be completely wrong too.

--
Cheers,                                        The Rhythm is around me,
The Rhythm has control.
Ray Blaak                                      The Rhythm is inside me,
rAYblaaK@STRIPCAPStelus.net                    The Rhythm has my soul.

Ray> Would this approach work: shrink/stretch/rotate the coord-space until
Ray> one of the ellipses is a circle and the other is aligned to the x/y axe
s.
Ray> Then solve the circle/ellipse intersection problem. Then transform back
Ray> into the original space.

Ellipses can be stretched along their axes or rotated and they are still
ellipses.  But you can't stretch them at an angle to the axes, and still
maintain an ellipse.

So you can center then rotationall align one of the ellipses to the
coordinate system, but when you try to shrink it to a circle, you
distort the other one out of being an ellipse.

Ray Blaak <rAYblaaK@STRIPCAPStelus.net> writes:

> Aubrey Jaffer <agj@alum.mit.edu> writes: 
> [...] 
>
> Would this approach work: shrink/stretch/rotate the coord-space
> until one of the ellipses is a circle and the other is aligned to
> the x/y axes. Then solve the circle/ellipse intersection
> problem. Then transform back into the original space.

Even if it does, the necessary transfroms (rotations and scaling) may
not be expressible algebraically in terms of the given parameters;
pushing the solution out of the original problem domain.

I tried intersecting a circle with one foci-specified ellipse.  After
running 3 hours it appears that puppy won't be coming home.

But non-isometric scaling doesn't play well with ellipses specified by
foci.  A given transform which takes points from the original ellipse
to a circle will not correctly transform the foci, since they must
both map the same center point.

A simpler formulation of the ellipse (or any conic section) is the
implicit form:

a*x*x + b*y*x + c*y*y + d*x + e*y + f = 0

It turns out that your last rotation (aligning the other to the x/y
axis) is not needed.  Intersecting the implicit form with a circle
solves in a couple of minutes:

e0 : a*x*x + b*y*x + c*y*y + d*x + e*y + f = 0;

2                    2
e0: 0 = f + d x + a x  + (e + b x) y + c y

e1 : x*x + y*y = r;

2    2
e1: 0 = - r + x  + y

e2 : eliminate([e0, e1], y);

2       2               2  2                                     2
e2: 0 = f  + (- e  + 2 c f) r + c  r  + (2 d f + (2 c d - 2 b e) r) x + (d  
+

2                       2              2      2
e  + (2 a - 2 c) f + (- b  + 2 a c - 2 c ) r) x  + ((2 a - 2 c) d +

3     2    2            2   4
2 b e) x  + (a  + b  - 2 a c + c ) x

-=-=-=-=-=-

The (doubly-exponential) pressure to reduce the number of unknowns
when using symbolic mathematics programs is a barrier to use,
requiring sophisticated mathematical reasoning.

It may be too much to hope to detect rotational simplifications; but
can gratuitous offsets and scaling be automatically detected (and
substituted)?

I assume that you are using some variant of a Groebner basis based
algorithm to do the elimination.

If not, you should probably look at
one of the books by Cox Little and O'Shea.  The undergraduate text
should contain enough info to help you, it is easy to read, but can be
a bit tedious.  IIRC it contained a chapter on automatic theorem
proving in euclidean geometry, which is very close to your
problem.)

If you are, have you tried a different term order?

"Deinst@world.std.com" <Deinst@world.std.com> writes:

> I assume that you are using some variant of a Groebner basis based
> algorithm to do the elimination.

JACAL's elimination code predates my contact with the Groebner bases
literature.  It combines equations using pseudo-remainder-sequences
and term-reordering.

> If not, you should probably look at one of the books by Cox, Little,
> and O'Shea.  The undergraduate text should contain enough info to
> help you, it is easy to read, but can be a bit tedious.

I have read up to chapter 4 (a while ago).

> IIRC it contained a chapter on automatic theorem proving in
> euclidean geometry, which is very close to your problem.)

I chose the ellipse intersection problem because it is a standard one
for computer algebra systems.

> If you are, have you tried a different term order?

Yes; other orders run more slowly.  My experience with JACAL gives me
some insight into how to order the variables for quick results.
Coding that optimization into JACAL would be useful.

Bruce Hoult <bruce@hoult.org> writes:

> In article <ud5xsvco3.fsf_-_@STRIPCAPStelus.net>,
>  Ray Blaak <rAYblaaK@STRIPCAPStelus.net> wrote:
> 
>
> If you do that, I suspect the second one isn't an ellipse any more,
> unless their axes were parallel (or orthoginal) at the start.

It turns out that we can solve the problem using only rotation and
translation (which none should argue corrupts an ellipse).

The pair of ellipses is rotated and translated so that one is
axis-aligned and centered at the origin.

We then intersect the other (rotated and translated) ellipse with the
axis-aligned ellipse.  The derivation took JACAL only 3.min:


e0 : a*x*x + b*y*x + c*y*y + d*x + e*y + f = 0;

2                    2
e0: 0 = f + d x + a x  + (e + b x) y + c y

e1 : eliminate([e0, (x*k)^2+y^2=r], y);

2       2               2  2                                     2
e1: 0 = f  + (- e  + 2 c f) r + c  r  + (2 d f + (2 c d - 2 b e) r) x + (d  
+

2           2       2              2  2      2
2 a f + (e  - 2 c f) k  + (- b  + 2 a c - 2 c  k ) r) x  + (2 a d +

2   3     2     2           2    2  4   4
(- 2 c d + 2 b e) k ) x  + (a  + (b  - 2 a c) k  + c  k ) x