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

Question

我想在 C++ 中执行此操作。我有两个想法可以做到这一点：

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

人们会怎么做呢？在 python 中，它是如此简单，我可以在睡梦中完成。任何见解将不胜感激。自从我接触了 C++，感觉选择要使用的库本身就是一场巨大的战斗。

Answer 1

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

如果你想自己动手：有了一点理论知识 ("ranges of conics")，你所要求的可以用线性代数（即求 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 的形式 "line coordinates" (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。因此，两个二次曲线的任何公切线都是 "range" A + tB.

中每个二次曲线的公切线

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

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

举个简单的例子（两个椭圆的圆心都在原点）：求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.

是不是很漂亮？

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

Preferred means for finding common tangent to a pair of ellipses in C++

c++

geometry

solver