[help-3dldf] Re: button-hole problem

[Peter Vanroose]

 --- Laurence Finston <address@hidden> wrote: 
>  Martijn van Manen has given me some material about finding the
> intersections of two ellipes algebraically, but he uses some
> mathematical concepts that I don't understand.

Let me try to explain these concepts in a few words:

An ellipse (or actually any conic section) in the XY plane has an
equation Q(x,y)=0 where Q is a quadratic expression in x and y.

Suppose the two ellipses are given by the equations Q1(x,y)=0 and
Q2(x,y)=0.

Any linear combination of Q1 and Q2 is still quadratic, hence
represents an (other) conic section.
For example: Q3(x,y) := 3 * Q1(x,y) - 7 * Q2(x,y) = 0.

Interestingly, any linear combination of Q1 and Q2 also passes through
the four intersection points of Q1=0 and Q2=0.
So, in order to find those intersection points, one may as well try to
intersect any two linear combinations of Q1 and Q2.

Now from those linear combinations Q3:=k*Q1+l*Q2, there are three
choices for (k,l) such that Q3 is degenerate.
This means that Q3(x,y) can be written as the product of two linear
factors:
Q3(x,y) = (a*x+b*y+c)*(d*x+e*y+f) for some numbers a,b,c,d,e,f.

Geometrically, this means that Q3=0 is actually "two straight lines",
hence the term "degenerate".

Now the intersection problem reduces to find two of those three
degenerate conic sections amongst k*Q1+l*Q2=0.
Fortunately, there is an algebraic expression for verifying that a
quadratic equation is the product of two linear factors (similar to the
discriminant formula for solving quadratic equations in one unknown).
Hence two pairs of numbers (k1,l1) and (k2,l2) can be found relatively
easily, which gives us two degenerate conic sections Q3:=k1*Q1+l1*Q2
and Q4:=k2*Q1+l2*Q2.

Suppose Q3=L1*L2 and Q4=L3*L4, where L1,L2,L3,L4 are linear (i.e., L1=0
is a straight line etc.)
The intersection of Q1 and Q2 equals the intersection of Q3 and Q4,
which are the four points L1^L3, L1^L4, L2^L3 and L2^L4, where "^"
stands for the intersection point of the two lines. Intersecting lines
is of course easy.

Note that the numbers k and l might be complex numbers. This is e.g.
the case when intersecting two circles. B.t.w., all circles pass
through the two points (at infinity) with direction x=1,y=j and
x=1,y=-j. Hence, when intersecting two circles, one of the component
lines L1 will be the line at infinity, and there will be at most two
"real" intersection points.



--      Peter.