Preferred means for finding common tangent to a pair of ellipses in C ++
I want to do this in C ++. I have two ideas that I can do this:
- Given a pair of ellipses as parametric equations of two different parameters, I can get two equations in two parameters. This pair of equations is non-linear, both functions are cotangents, sines and cosines. Geant4, which I work with in the first place, only has Polynomial
- Use this geometry to solve this problem. I looked at Boost geometry but the documentation is incoherent (for me). Having said that, it seems to be more focused on computational geometry. Perhaps I am asking it to do Y when it was only meant for X.
How can I do that? It's so easy in python, I could do it in my sleep. Any insight would be much appreciated. Since I took C ++, it seems to me that choosing a library to use is a huge battle in itself.
source to share
I have several suggestions. You can try LibreCAD, which has a solver for common tangents to two ellipses, but I don't know anything about the API. The solver solves quark equations, which is what happens if you naively try to find common tangents for two ellipses.
If you want to collapse on your own: with a bit of theory ("bony ranges") what you are asking for can be done with linear algebra (namely, to find inversions of 3x3 matrices) and also to solve quadratures and a single cubic equation ... It works like this:
You can express any conic (like an ellipse) as a matrix equation
[m00 m01 m02] [x]
[x,y,z] [m10 m11 m12] [y] = 0
[m20 m21 m22] [z]
where the matrix is M
symmetric and [x,y,z]
are homogeneous coordinates; just think z=1
. We can write this equation in short form as X M X^T = 0
, where X^T
is transposition X
.
Lines in the plane can be written in the form lx+my+nz=0
and therefore have "linear coordinates" (l,m,n)
.
The set of tangent lines to the indicated conic can be very simply expressed in these notation. Let be the A
inverse matrix M
. The set of tangent lines to a conic then
[a00 a01 a02] (l)
(l,m,n) [a10 a11 a12] (m) = 0
[a20 a21 a22] (n)
Now suppose we have a second conic with a matrix N
and that N
has an inverse B
. The general tangent will satisfy the above equation, and the equation
[b00 b01 b02] (l)
(l,m,n) [b10 b11 b12] (m) = 0
[b20 b21 b22] (n)
Indeed, we can scalarly multiply the matrix in the last equation by t
, and it will still take place:
[b00 b01 b02] (l)
(l,m,n) t [b10 b11 b12] (m) = 0
[b20 b21 b22] (n)
Adding the equation of the tangents to the first conic to the above equation for the second conic, we get the matrix equation L (A + tB) L^T = 0
. Thus, any common tangent to two conics is a common tangent to each conic in the "range" A + tB
.
Now for a big oversimplification idea: we can find some very special conics in this range, "degenerate" conics, which are just pairs of points. Since common tangents must pass through all conics, they must pass through degenerate conics. But it is easy to find lines through degenerate conics, since such conics are just pairs of points!
You will find degenerate conics by solving the cubic equation det(A + tB) = 0
, where det()
is the determinant of 3x3 matrices. The dice can be solved closed by Cardano's formula or variation, or it can be solved numerically if that's what you want. When you find the value t
that degenerate conics make, you can expand the equation L (A + tB) L^T = 0
into two linear factors. Each linear factor xl + ym + zn = 0
defines a point in uniform coordinates [x,y,z]
or in Cartesian coordinates (x/z,y/z)
. Thus, you should get three points-pairs (six points). Taking lines through some of these pairs of points will give you your four (at most) tangent lines.
Here's a simple example (where the centers of two ellipses are at the origin): find the common tangents to x^2+2y^2=3
and x^2+14y^2=7
. Conic in matrix form
[1 0 0] [x] [1 0 0] [x]
[x,y,z] [0 2 0] [y] = 0, [x,y,z] [0 14 0] [y] = 0
[0 0 -3] [z] [0 0 -7] [z]
Tangents are given by the expression
[6 0 0] (l) [14 0 0] (l)
(l,m,n) [0 3 0] (m) = 0, (l,m,n) [ 0 1 0] (m) = 0
[0 0 -2] (n) [ 0 0 -2] (n)
Note. I have multiplied the inverse matrices by a scalar to make integers rather than rational numbers. You don't need to do this, but it makes calculating the hands easier. Multiplying the second matrix by an additional scalar t
gives
[6+14t 0 0 ] (l)
(l,m,n) [0 3+t 0 ] (m) = 0
[0 0 -2-2t] (n)
The conic is degenerate at (6+14t)(3+t)(-2-2t)=0
, i.e. at t=-3/7, -3, -1
. When t=-3/7
we get
18/7 m^2 - 8/7 n^2 = 2/7 (9 m^2 - 4 n^2) = 2/7 (3m - 2n)(3m + 2n) = 0
This corresponds to points with uniform coordinates [x,y,z] = [0,3,-2]
and [0,3,2]
, in other words, points with Cartesian coordinates (0,-3/2)
and (0,3/2)
.
When t=-3
we get -36l^2 + 4n^2 = (6l+2n)(-6l+2n) = 0
, points [6,0,2]
and [-6,0,2]
or in Cartesian coordinates (3,0)
and (-3,0)
. Finally, at t=1
we obtain the -8l^2 + 2m^2 = 2(2l+m)(-2l+m) = 0
corresponding points [2,1,0]
and [-2,1,0]
, which are points at infinity.
Avoiding infinite dots now, simply because they are a little harder to work with, we end up with four lines through the following pairs of dots:
{(0,-3/2),(-3,0)}, {(0,-3/2),(3,0)}, {(0,3/2),(-3,0)}, {(0,3/2),(3,0)}
which gives us four common touches to two ellipses.
It can be seen from the figure that common tangents also pass through infinite points [2,1,0]
and [-2,1,0]
, i.e. that pairs of parallel lines have a slope 1/2
and -1/2
.
Isn't it pretty?
source to share