Java：两个椭圆段的交点转换为 3d space
Java: Intersection of two ellipse segments transformed into 3d space
我有线段和椭圆（不是平面和椭圆体）转换成3d space并且需要计算两个给定的线段是否相交和在哪里。
我正在使用 Java，但还没有找到可以解决我的问题的库，也没有遇到一些可以用于我自己的实现的算法。
对于线与线相交的测试，有几种方法可以解决。经典方法是使用线性代数（即求解线性矩阵系统），但从软件开发的角度来看，我更喜欢几何代数方法，以 Plucker 坐标的形式，它只需要实现向量代数运算（即，叉积和点积），它们比求解线性系统的矩阵运算更易于编码。
为了比较，我会展示两者，然后你决定：
线性代数方式
给定线段P由点P1和P2限定，线段Q由点Q1和Q2限定。
直线的参数形式由下式给出：
P(t) = P1 + t (P2 - P1)
Q(t) = Q1 + t (Q2 - Q1)
其中t为区间[0 1]中的实数。
如果两条线相交，则以下等式成立：
P(t0) = Q(t1)
前提是t0和t1这两个未知数存在。展开上面的等式我们得到：
t0 (P2 - P1) - t1 (Q2 - Q1) = Q1 - P1
我们可以用矩阵代数表示上述方程来求解t0和t1：
A x = B
其中A是一个3x2矩阵，第一列坐标为向量(P2 - P1)，第二列为向量坐标(Q2 - Q1)； x 是未知数 t0 和 t1 的 2x1 列向量，B 是坐标为向量 (Q1 - P1) 的 3x1 列向量。
经典的系统可以解决计算矩阵 A 的伪逆，表示为 A^+:
A^+ = (A^T A)^-1 A^T[=17=]
参见：
https://en.m.wikipedia.org/wiki/Generalized_inverse
幸运的是，Java 中的任何矩阵包都应该能够非常轻松且高效地计算上述计算。
如果 A 与其伪逆 A^+ 相乘等于单位矩阵 I，即 (A A^+) == I，则有一个唯一的答案（交集），你可以通过计算得到它以下产品：
x = A^+ B
当然，如果您不能首先计算伪逆，例如，因为 (A^T A) 是奇异的（即行列式为零），则不存在交集。
由于我们处理的是线段，因此交点位于点 P(x0) 或 Q(x1)，当且仅当 x0 和 x1 都在区间 [0 1] 内。
其他解决方法
为了避免处理矩阵代数，我们可以尝试使用向量代数和代入法求解系统：
t0 (P2 - P1) - t1 (Q2 - Q1) = Q1 - P1
t0 = a + t1 b
t1 = C • (Q1 - (1 - a) P1 - a P2) / |C|^2
其中：
a = (P2 - P1) • (Q1 - P1) / |P2 - P1|^2
b = (P2 - P1) • (Q2 - Q1) / |P2 - P1|^2
C = b (P2 - P1) - (Q2 - Q1)
我还不能提供上述结果的几何直觉。
Plucker 坐标方式
给定线段P由点P1和P2限定，线段Q由点Q1和Q2限定。
线 P 的 Plucker 坐标由一对 3d 向量 (Pd, Pm) 给出：
Pd = P2 - P1
Pm = P1 x P2
其中 Pm 是 P1 和 P2 的叉积。 Q线的Plucker Coordinates(Qd, Qm)可以用完全相同的方法计算。
直线P和Q只有在共面时才能相交。 Thr 行 P 和 Q 是共线 iif:
Pd • Qm + Qd • Pm = 0
其中 (•) 是点积。由于机器的精度有限，因此稳健的测试不应检查零，而应检查较小的数字。如果 Pd x Qd = 0 则线是平行的（这里 0 是零向量）。同样，一个稳健的测试应该是例如 (Pd x Qd) 的平方长度很小。
如果直线不平行则它们共面并且它们的交点（在 Plucker 的行话中称为 "meet"）将是点：
x = ((Pm • N) Qd - (Qm • N) Pd - (Pm • Qd) N) / (Pd x Qd) • N
其中N是任何坐标轴向量（即（1,0,0）或（0,1,0）或（0,0,1）），使得（Pd x Qd）•N是非零。
如果P和Q都不通过原点，则它们的Plucker坐标Pm和Qm分别为非零，下面的sinpler公式将起作用
x = Pm x Qm / Pd • Qm
有关 Plucker 坐标的介绍，请参阅：
https://en.m.wikipedia.org/wiki/Plücker_coordinates
http://www.realtimerendering.com/resources/RTNews/html/rtnv11n1.html#art3
有关一般交集公式，请参阅 "Corollary 6" of:
http://web.cs.iastate.edu/~cs577/handouts/plucker-coordinates.pdf
来回变换椭圆为圆
我们总能把椭圆变成圆形。一个椭圆有两条"radius"，叫做半轴，你可以在脑海中想象成两个正交的向量，一个大的叫长半轴，一个小的叫短半轴。你可以对两个半轴向量应用非均匀缩放变换，使它们大小相等，所以你得到一个圆。
我们定义一个椭圆"E"，它的中心O是一个3d点，它的两个半轴A1和A2也是3d向量。椭圆平面的法向量 N 可以通过其半轴 N = A1 x A2 的叉积计算，然后将其归一化为具有单位长度。
现在假设有一个线性函数 M，您可以通过将其应用于椭圆的半轴，将其用于将椭圆 E 变换（缩放）为半径等于短半轴的圆 C A1 和 A2 到椭圆的中心 O。
注意到椭圆的圆心O和椭圆的法向量N并没有被M改变。所以M(N) = N和M(O) = O。这意味着圆在同一平面上并且具有与椭圆相同的位置 C。线性函数M有一个对应的反函数M^-1，所以我们可以将圆的向量反变换得到原来的椭圆E。
当然我们也可以使用函数 M 转换线 P 和 Q 的端点，将它们发送到 "circle space"，我们可以使用 M^-1 将它们发送回 "ellipse space"。
使用 M 我们可以计算直线 P 和 Q 与圆 space 中的椭圆 E 的交点。所以现在我们可以关注线圆交点。
线面交点
给定一个法向量为 N 且距离为 D 的平面，使得：
N•x + D = 0
对于平面中的每个点 x。然后 P 线与 Plucker 坐标 (Pd, Pm) 的交点由下式给出：
x = (N x Pm - D Pd) / N • Pd
这仅在直线 P 不在平面内时有效，即：
(N • P1 + D) != 0 和 (N • P2 + D) != 0
对于我们的椭圆 E，我们有：
N = (A1 x A2)/|A1 x A2|
D = -N • O
线圆点圆交点
有了x，圆内点检查就简单了：
|O-x| <= |A2|
只有当x在圆边界时等式才成立。
如果直线 P 在圆的平面内，那么下面的简单检查会给你答案：
如何计算线性函数M
计算 M 的简单方法如下。使用椭圆的法向量 N 和半轴 A1 和 A2 创建一个 3x3 矩阵 U。使得 U 具有向量 A1、A2 和 N 作为列。
然后将长半轴A1缩放到与短半轴A2等长。然后创建矩阵 V，使 V 具有新向量 A1、A2 和 N 作为列。
然后我们定义线性矩阵系统：
R U = V
其中 R 是 3x3（非均匀）缩放旋转矩阵。
我们可以通过等式两边乘以U的倒数来求解R，用U^-1表示
R U U^-1 = V U^-1
因为 U U^-1 是我们得到的单位矩阵：
R = VU^+
我们使用 R 定义仿射变换
M(x) = R (x - O) + O
我们可以用M把点变成圆space，比如O、P1、P2、Q1、Q2。但是如果我们需要对A1、A2、N、Pd、Qd等向量进行变换。我们需要使用更简单的 M:
M(x) = R x
因为A1、A2、N是R的特征向量，所以R不是奇异向量，有逆向量。我们将逆 M 定义为：
M^-1(x) = R^-1 (x - O) + O
对于向量：
M^-1(x) = R^-1 x
更新：椭圆-椭圆交集
两个相交的非共面 3d 椭圆的交点位于它们的平面相交形成的线上。所以你首先要找到由包含椭圆的平面相交形成的线（如果平面不相交，即它们是平行的，那么椭圆都不相交）。
交线属于两个平面，因此垂直于两个法线。方向向量V是平面法线的叉积：
V = N1 × N2
要完全确定直线我们还需要找到直线上的一个点。我们可以解决平面的线性方程。给定以法线 N1 和 N2 为行的 2x3 矩阵 N = [N1^T N2^T]，以及 2x1 列向量 b = [N1 • C1, N2 • C2]，其中 C1 和 C2 是椭圆的中心，我们可以形成线性矩阵系统：
N X = b
其中X是满足两个平面方程的点。该系统是欠定的，因为在满足该系统的直线上有无数个点。我们仍然可以通过使用矩阵N的伪逆来找到更接近原点的特解，记为N^+。
X = N^+ b
直线方程为
L(t) = X + t V
对于一些标量 t。
然后就可以应用前面介绍的方法来测试线椭圆相交，即把椭圆缩放成圆并与共面线相交。如果两个椭圆在同一点与直线相交，则它们相交。
现在，椭圆实际上位于同一平面上的情况更加复杂。您可以在埃伯利博士的优秀著作 "Geometric Tools"（也可在线获取）中查看所采用的方法：
https://www.geometrictools.com/Documentation/IntersectionOfEllipses.pdf
另外可以查看开源的C++源码：
https://www.geometrictools.com/GTEngine/Include/Mathematics/GteIntrEllipse2Ellipse2.h
我有线段和椭圆（不是平面和椭圆体）转换成3d space并且需要计算两个给定的线段是否相交和在哪里。
我正在使用 Java，但还没有找到可以解决我的问题的库，也没有遇到一些可以用于我自己的实现的算法。
对于线与线相交的测试，有几种方法可以解决。经典方法是使用线性代数（即求解线性矩阵系统），但从软件开发的角度来看，我更喜欢几何代数方法，以 Plucker 坐标的形式，它只需要实现向量代数运算（即，叉积和点积），它们比求解线性系统的矩阵运算更易于编码。
为了比较，我会展示两者，然后你决定：
线性代数方式
给定线段P由点P1和P2限定，线段Q由点Q1和Q2限定。
直线的参数形式由下式给出：
P(t) = P1 + t (P2 - P1)
Q(t) = Q1 + t (Q2 - Q1)
其中t为区间[0 1]中的实数。
如果两条线相交，则以下等式成立：
P(t0) = Q(t1)
前提是t0和t1这两个未知数存在。展开上面的等式我们得到：
t0 (P2 - P1) - t1 (Q2 - Q1) = Q1 - P1
我们可以用矩阵代数表示上述方程来求解t0和t1：
A x = B
其中A是一个3x2矩阵，第一列坐标为向量(P2 - P1)，第二列为向量坐标(Q2 - Q1)； x 是未知数 t0 和 t1 的 2x1 列向量，B 是坐标为向量 (Q1 - P1) 的 3x1 列向量。
经典的系统可以解决计算矩阵 A 的伪逆，表示为 A^+:
A^+ = (A^T A)^-1 A^T[=17=]
参见： https://en.m.wikipedia.org/wiki/Generalized_inverse
幸运的是，Java 中的任何矩阵包都应该能够非常轻松且高效地计算上述计算。
如果 A 与其伪逆 A^+ 相乘等于单位矩阵 I，即 (A A^+) == I，则有一个唯一的答案（交集），你可以通过计算得到它以下产品：
x = A^+ B
当然，如果您不能首先计算伪逆，例如，因为 (A^T A) 是奇异的（即行列式为零），则不存在交集。
由于我们处理的是线段，因此交点位于点 P(x0) 或 Q(x1)，当且仅当 x0 和 x1 都在区间 [0 1] 内。
其他解决方法
为了避免处理矩阵代数，我们可以尝试使用向量代数和代入法求解系统：
t0 (P2 - P1) - t1 (Q2 - Q1) = Q1 - P1
t0 = a + t1 b
t1 = C • (Q1 - (1 - a) P1 - a P2) / |C|^2
其中：
a = (P2 - P1) • (Q1 - P1) / |P2 - P1|^2
b = (P2 - P1) • (Q2 - Q1) / |P2 - P1|^2
C = b (P2 - P1) - (Q2 - Q1)
我还不能提供上述结果的几何直觉。
Plucker 坐标方式
给定线段P由点P1和P2限定，线段Q由点Q1和Q2限定。
线 P 的 Plucker 坐标由一对 3d 向量 (Pd, Pm) 给出：
Pd = P2 - P1
Pm = P1 x P2
其中 Pm 是 P1 和 P2 的叉积。 Q线的Plucker Coordinates(Qd, Qm)可以用完全相同的方法计算。
直线P和Q只有在共面时才能相交。 Thr 行 P 和 Q 是共线 iif:
Pd • Qm + Qd • Pm = 0
其中 (•) 是点积。由于机器的精度有限，因此稳健的测试不应检查零，而应检查较小的数字。如果 Pd x Qd = 0 则线是平行的（这里 0 是零向量）。同样，一个稳健的测试应该是例如 (Pd x Qd) 的平方长度很小。
如果直线不平行则它们共面并且它们的交点（在 Plucker 的行话中称为 "meet"）将是点：
x = ((Pm • N) Qd - (Qm • N) Pd - (Pm • Qd) N) / (Pd x Qd) • N
其中N是任何坐标轴向量（即（1,0,0）或（0,1,0）或（0,0,1）），使得（Pd x Qd）•N是非零。
如果P和Q都不通过原点，则它们的Plucker坐标Pm和Qm分别为非零，下面的sinpler公式将起作用
x = Pm x Qm / Pd • Qm
有关 Plucker 坐标的介绍，请参阅：
https://en.m.wikipedia.org/wiki/Plücker_coordinates
http://www.realtimerendering.com/resources/RTNews/html/rtnv11n1.html#art3
有关一般交集公式，请参阅 "Corollary 6" of:
http://web.cs.iastate.edu/~cs577/handouts/plucker-coordinates.pdf
来回变换椭圆为圆
我们总能把椭圆变成圆形。一个椭圆有两条"radius"，叫做半轴，你可以在脑海中想象成两个正交的向量，一个大的叫长半轴，一个小的叫短半轴。你可以对两个半轴向量应用非均匀缩放变换，使它们大小相等，所以你得到一个圆。
我们定义一个椭圆"E"，它的中心O是一个3d点，它的两个半轴A1和A2也是3d向量。椭圆平面的法向量 N 可以通过其半轴 N = A1 x A2 的叉积计算，然后将其归一化为具有单位长度。
现在假设有一个线性函数 M，您可以通过将其应用于椭圆的半轴，将其用于将椭圆 E 变换（缩放）为半径等于短半轴的圆 C A1 和 A2 到椭圆的中心 O。
注意到椭圆的圆心O和椭圆的法向量N并没有被M改变。所以M(N) = N和M(O) = O。这意味着圆在同一平面上并且具有与椭圆相同的位置 C。线性函数M有一个对应的反函数M^-1，所以我们可以将圆的向量反变换得到原来的椭圆E。
当然我们也可以使用函数 M 转换线 P 和 Q 的端点，将它们发送到 "circle space"，我们可以使用 M^-1 将它们发送回 "ellipse space"。
使用 M 我们可以计算直线 P 和 Q 与圆 space 中的椭圆 E 的交点。所以现在我们可以关注线圆交点。
线面交点
给定一个法向量为 N 且距离为 D 的平面，使得：
N•x + D = 0
对于平面中的每个点 x。然后 P 线与 Plucker 坐标 (Pd, Pm) 的交点由下式给出：
x = (N x Pm - D Pd) / N • Pd
这仅在直线 P 不在平面内时有效，即：
(N • P1 + D) != 0 和 (N • P2 + D) != 0
对于我们的椭圆 E，我们有：
N = (A1 x A2)/|A1 x A2|
D = -N • O
线圆点圆交点
有了x，圆内点检查就简单了：
|O-x| <= |A2|
只有当x在圆边界时等式才成立。
如果直线 P 在圆的平面内，那么下面的简单检查会给你答案：
如何计算线性函数M
计算 M 的简单方法如下。使用椭圆的法向量 N 和半轴 A1 和 A2 创建一个 3x3 矩阵 U。使得 U 具有向量 A1、A2 和 N 作为列。
然后将长半轴A1缩放到与短半轴A2等长。然后创建矩阵 V，使 V 具有新向量 A1、A2 和 N 作为列。
然后我们定义线性矩阵系统：
R U = V
其中 R 是 3x3（非均匀）缩放旋转矩阵。
我们可以通过等式两边乘以U的倒数来求解R，用U^-1表示
R U U^-1 = V U^-1
因为 U U^-1 是我们得到的单位矩阵：
R = VU^+
我们使用 R 定义仿射变换
M(x) = R (x - O) + O
我们可以用M把点变成圆space，比如O、P1、P2、Q1、Q2。但是如果我们需要对A1、A2、N、Pd、Qd等向量进行变换。我们需要使用更简单的 M:
M(x) = R x
因为A1、A2、N是R的特征向量，所以R不是奇异向量，有逆向量。我们将逆 M 定义为：
M^-1(x) = R^-1 (x - O) + O
对于向量：
M^-1(x) = R^-1 x
更新：椭圆-椭圆交集
两个相交的非共面 3d 椭圆的交点位于它们的平面相交形成的线上。所以你首先要找到由包含椭圆的平面相交形成的线（如果平面不相交，即它们是平行的，那么椭圆都不相交）。
交线属于两个平面，因此垂直于两个法线。方向向量V是平面法线的叉积：
V = N1 × N2
要完全确定直线我们还需要找到直线上的一个点。我们可以解决平面的线性方程。给定以法线 N1 和 N2 为行的 2x3 矩阵 N = [N1^T N2^T]，以及 2x1 列向量 b = [N1 • C1, N2 • C2]，其中 C1 和 C2 是椭圆的中心，我们可以形成线性矩阵系统：
N X = b
其中X是满足两个平面方程的点。该系统是欠定的，因为在满足该系统的直线上有无数个点。我们仍然可以通过使用矩阵N的伪逆来找到更接近原点的特解，记为N^+。
X = N^+ b
直线方程为
L(t) = X + t V
对于一些标量 t。
然后就可以应用前面介绍的方法来测试线椭圆相交，即把椭圆缩放成圆并与共面线相交。如果两个椭圆在同一点与直线相交，则它们相交。
现在，椭圆实际上位于同一平面上的情况更加复杂。您可以在埃伯利博士的优秀著作 "Geometric Tools"（也可在线获取）中查看所采用的方法：
https://www.geometrictools.com/Documentation/IntersectionOfEllipses.pdf
另外可以查看开源的C++源码：
https://www.geometrictools.com/GTEngine/Include/Mathematics/GteIntrEllipse2Ellipse2.h