在 C++ 中找到一对椭圆的公切线的首选方法

Question

我想在 C++ 中做到这一点。我有两个想法可以做到这一点：

1. 将椭圆对视为两个不同参数的参数方程，我可以根据这两个参数得到两个方程。这对方程是非线性的，都是余切函数，正弦和余弦。Geant4，这是我主要使用的，只有多项式
2. 使用几何库来解决这个问题。我查看了 Boost 几何，但文档不连贯（对我而言）。话虽如此，它似乎更针对计算几何。也许我要求它做 Y，而它本来只打算做 X。

怎么做呢？在 python 中它非常简单，我可以在睡梦中完成。任何见解将不胜感激。自从我开始学习 C++，感觉选择要使用的库本身就是一场巨大的战斗。

Answer 1

我有几个建议。您可以尝试 LibreCAD，它有一个求解两个椭圆公切线的求解器，但我对 API 一无所知。求解器求解四次方程，如果您天真地尝试找到两个椭圆的公切线，您就会得到四次方程。

如果你想自己动手：有了一点理论（“圆锥曲线的范围”），你所要求的可以用线性代数（即找到 3x3 矩阵的逆）加上求解二次方程和一个三次方程来完成。它是这样的：

您可以以矩阵方程的形式表示任何圆锥曲线（例如椭圆）

        [m00 m01 m02] [x]
[x,y,z] [m10 m11 m12] [y] = 0
        [m20 m21 m22] [z]

其中矩阵M是对称的并且[x,y,z]是齐次坐标；只是想想z=1。我们可以写短格式作为方程X M X^T = 0，其中X^T是的转置X。

平面中的线可以写成表格lx+my+nz=0，所以有“线坐标” (l,m,n)。

上述圆锥的切线组可以用这种符号非常简单地表达。让A是矩阵的逆矩阵M。那么圆锥曲线的切线集是

        [a00 a01 a02] (l)
(l,m,n) [a10 a11 a12] (m) = 0
        [a20 a21 a22] (n)

现在假设我们有第二个带有矩阵 的二次曲线N，它N有逆B。公切线将满足上述方程和方程

        [b00 b01 b02] (l)
(l,m,n) [b10 b11 b12] (m) = 0
        [b20 b21 b22] (n)

事实上，我们可以将后一个方程中的矩阵标量乘以t，它仍然成立：

          [b00 b01 b02] (l)
(l,m,n) t [b10 b11 b12] (m) = 0
          [b20 b21 b22] (n)

将第一个圆锥的切线方程与上述第二个圆锥的方程相加，我们得到矩阵方程L (A + tB) L^T = 0。因此，两个圆锥曲线的任何公共切线都是“范围”内每个圆锥曲线的公共切线A + tB。

现在来做一个大的简化想法：我们可以在那个范围内找到一些非常特殊的圆锥曲线，“退化”圆锥曲线，它们只是点对。由于公切线必须通过所有圆锥曲线，因此它们必须通过退化圆锥曲线。但是很容易找到通过退化圆锥曲线的线，因为这些圆锥曲线只是点对！

您可以通过求解三次方程来找到退化圆锥曲线，det(A + tB) = 0其中det()是 3x3 矩阵的行列式。三次方可以通过卡尔达诺公式或变体以封闭形式求解，或者如果您需要，也可以通过数值求解。一旦找到t使退化圆锥曲线的值，就可以将方程分解L (A + tB) L^T = 0为两个线性因子。每个线性因子xl + ym + zn = 0定义齐次坐标[x,y,z]或笛卡尔坐标中的一个点(x/z,y/z)。您应该以这种方式获得三个点对（6 个点）。将线穿过某些点对将为您提供四条（最多）切线。

下面是一个简单的例子（其中两个椭圆的中心都在原点）：找到共同的切线x^2+2y^2=3和x^2+14y^2=7。矩阵形式的圆锥是

        [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]

切线由下式给出

        [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)

注意我将逆矩阵乘以一个标量只是为了使条目成为整数而不是有理数。您不必这样做，但它使手工计算更容易。将第二个矩阵乘以一个额外的标量t给出

        [6+14t 0    0   ] (l)
(l,m,n) [0     3+t  0   ] (m) = 0
        [0     0   -2-2t] (n)

当 时(6+14t)(3+t)(-2-2t)=0，即当时，圆锥曲线是退化的t=-3/7, -3, -1。当t=-3/7我们得到

18/7 m^2 - 8/7 n^2 = 2/7 (9 m^2 - 4 n^2) = 2/7 (3m - 2n)(3m + 2n) = 0

这对应于具有齐次坐标[x,y,z] = [0,3,-2]和的点，[0,3,2]换句话说，对应于具有笛卡尔坐标(0,-3/2)和 的点(0,3/2)。

当t=-3我们得到-36l^2 + 4n^2 = (6l+2n)(-6l+2n) = 0、 点[6,0,2]和[-6,0,2]或 在笛卡尔坐标(3,0)和 中(-3,0)。最后，当t=1我们得到-8l^2 + 2m^2 = 2(2l+m)(-2l+m) = 0对应的点时[2,1,0]，[-2,1,0]哪些是无穷远处的点。

暂时避开无穷远的点，只是因为它们更难处理，我们通过以下一对点得到四条线：

{(0,-3/2),(-3,0)}, {(0,-3/2),(3,0)}, {(0,3/2),(-3,0)}, {(0,3/2),(3,0)}

这给了我们两个椭圆的四个公共切线。

可以从图中看到，该公切线也穿过在无穷远处的点[2,1,0]和[-2,1,0]，即，平行线对具有斜率1/2和-1/2。

是不是很美？