Java：转换为3d空间的两个椭圆段的交点 11 月，2 周 Questions & Answers 606 我将直线和椭圆（而非平面和椭球）的段转换为三维空间，并需要计算两个给定段是否相交以及在哪里相交 我正在使用Java，但还没有找到一个库来解决我的问题，也没有找到一些可以用于我自己实现的算法
# 1 楼答案 对于直线相交测试，有几种方法可以解决。经典的方法是使用线性代数（即求解线性矩阵系统），但从软件开发的角度来看，我更喜欢几何代数的方法，以普莱克坐标的形式，它只需要实现向量代数运算（即叉积和点积），这比求解线性系统的矩阵运算更容易编码 为了比较起见，我将两者都展示出来，然后你决定： 线性代数方式 给定线段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 见： https://en.m.wikipedia.org/wiki/Generalized_inverse 幸运的是，Java中的任何矩阵包都应该能够非常轻松地计算上述计算，而且可能也非常高效 如果将A与其伪逆A^+相乘等于单位矩阵I，即（A^+==I，则存在唯一答案（交集），您可以通过计算以下乘积得到它： x=A^+B 当然，如果你首先不能计算伪逆，例如，因为（A^ta）是奇异的（即行列式为零），那么就不存在交集 因为我们处理的是线段，所以当x0和x1都在区间[01]内时，交点在点p（x0）或Q（x1）处 其他解决方法 为了避免处理矩阵代数，我们可以尝试使用向量代数和代换法求解系统： 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） 我还不能提供上述结果的几何直观 采摘器协调方式 给定线段p受点P1和P2限制，线段Q受点Q1和Q2限制 线p的Pucker坐标由一对3d向量（Pd，Pm）给出： Pd=P2-P1 Pm=P1 x P2 式中，Pm是P1和P2的叉积。可以用完全相同的方法计算线Q的采摘器坐标（Qd，Qm） 线p和Q只有在共面时才能相交。第P线和第Q线为共平面iif： Pd•Qm+Qd•Pm=0 其中（•）是点积。由于机器的精度有限，稳健测试不应检查零，而应检查少量。如果Pd x Qd=0，那么直线是平行的（这里0是零向量）。对于instamce，应该再次进行稳健测试，以确定（Pd x Qd）的平方长度很小 如果两条线不平行，那么它们是共面的，它们的交点（用普莱克的术语称为“相交”）将是点： x=（（Pm•N）Qd-（Qm•N）Pd-（Pm•Qd）N）/（Pd x Qd）•N 其中N是任何坐标轴向量（即，（1,0,0）或（0,1,0）或（0,0,1）），如at（Pd x Qd）•N为非零 如果p和Q都不通过原点，那么它们的采摘器坐标Pm和Qm将分别为非零，并且以下sinpler公式将起作用 x=Pm x Qm/Pd•Qm 有关Pucker坐标的介绍，请参见： https://en.m.wikipedia.org/wiki/Plücker_coordinates http://www.realtimerendering.com/resources/RTNews/html/rtnv11n1.html#art3 关于一般的求交公式，请参见“推论6”： http://web.cs.iastate.edu/~cs577/handouts/plucker-coordinates.pdf 将椭圆转换为前后旋转的圆 我们总是可以把椭圆变成圆。椭圆有两个“半径”，称为半轴，你可以把它们想象成两个正交向量，一个大的称为大半轴，一个小的称为小半轴。可以对两个半轴向量应用非均匀缩放变换，使其大小相等，从而得到一个圆 我们定义一个椭圆“E”，它的中心O是一个3d点，它的两个半轴A1和A2也是3d向量。椭圆平面的法向量N可以通过其半轴N=A1 x A2的叉积来计算，然后将其归一化为单位长度 现在假设有一个线性函数M，你可以用它把椭圆E变换成一个圆C，半径等于短半轴，把它应用到椭圆的半轴A1和A2，以及椭圆的中心O 请注意，Elipse的圆心O和椭圆的法向量N不会因M而改变。因此M（N）=N和M（O）=O。这意味着圆位于同一平面上，并且与椭圆具有相同的位置C。线性函数M有一个对应的反函数M^-1，所以我们可以将圆的向量变换回原始椭圆E 当然，我们也可以使用函数M来变换直线p和Q的端点，将它们发送到“圆空间”，我们可以使用M^-1将它们发送回“椭圆空间” 利用M，我们可以计算圆空间中的直线p和Q与椭圆E的交点。现在我们可以把重点放在直线和圆的交点上 线平面相交 给定一个具有法向量N和距离D的平面： N•x+D=0 对于平面中的每个点x。然后，与线P的交点与Pucker坐标（Pd，Pm）由下式给出： x=（nx 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线在圆的平面内，那么下面的单次检查将给出答案： https://stackoverflow.com/a/1079478/9147444 如何计算线性函数M 计算M的简单方法如下。使用椭圆的法向量N以及半轴A1和A2创建一个3x3矩阵U。这样，U将向量A1、A2和N作为列 然后缩放长半轴A1，使其与短半轴A2具有相同的长度。然后创建矩阵V auch，该矩阵V将新向量A1、A2和N作为列 然后我们定义线性矩阵系统： RU=V 其中R是一个3x3（非均匀）标度旋转矩阵 我们可以通过将方程的两边乘以U的倒数来求解R，U的倒数用U^-1表示 ru^-1=vu^-1 因为U^-1是我们得到的单位矩阵： R=vu^+ 利用R定义仿射变换 M（x）=R（x-O）+O 我们可以使用M将点转换为圆空间，例如O、P1、P2、Q1和Q2。但是如果我们需要变换向量，比如A1，A2，N，Pd和Qd。我们需要e简单的M： M（x）=rx 因为A1、A2和N是R的特征向量，所以R不是奇异的，并且有一个逆。我们将逆M定义为： M^-1（x）=R^-1（x-O）+O 对于向量： M^-1（x）=R^-1 x 更新：椭圆-椭圆相交 两个相交的非共面三维椭圆的交点位于其平面相交形成的线上。所以你首先找到包含椭圆的平面相交形成的线（如果平面不相交，也就是说，它们是平行的，那么两个椭圆都不相交） 交线属于两个平面，因此它垂直于两条法线。方向向量V是平面法线的叉积： V=N1×N2 为了完全确定直线，我们还需要在直线上找到一个点。我们可以通过解平面的线性方程来实现。给定2x3矩阵N=[N1^T N2^T]，法线N1和N2为行，2x1列向量b=[N1•C1，N2•C2]，其中C1和C2是椭圆的中心，我们可以形成线性矩阵系统： nx=b 其中X是满足两个平面方程的点。由于满足系统的直线上有无限多个点，因此系统被低估。我们仍然可以通过使用矩阵N的伪逆（用N^+表示）找到更接近原点的特定解 X=N^+b 直线方程是 L（t）=X+tV 对于一些标量t 然后可以应用前面描述的方法来测试线-椭圆相交，即将椭圆缩放为一个圆，并与共面线相交。如果两个椭圆在同一点与直线相交，则它们相交 现在，椭圆实际上位于同一平面上的情况更加复杂。你可以在Eberly博士的优秀著作《几何工具》（Geometric Tools，也可在网上找到）中看到他的方法： https://www.geometrictools.com/Documentation/IntersectionOfEllipses.pdf ，也可以检查开源的C++源代码： https://www.geometrictools.com/GTEngine/Include/Mathematics/GteIntrEllipse2Ellipse2.h
# 1 楼答案
对于直线相交测试，有几种方法可以解决。经典的方法是使用线性代数（即求解线性矩阵系统），但从软件开发的角度来看，我更喜欢几何代数的方法，以普莱克坐标的形式，它只需要实现向量代数运算（即叉积和点积），这比求解线性系统的矩阵运算更容易编码
为了比较起见，我将两者都展示出来，然后你决定：
线性代数方式
给定线段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
见： https://en.m.wikipedia.org/wiki/Generalized_inverse
幸运的是，Java中的任何矩阵包都应该能够非常轻松地计算上述计算，而且可能也非常高效
如果将A与其伪逆A^+相乘等于单位矩阵I，即（A^+==I，则存在唯一答案（交集），您可以通过计算以下乘积得到它：
x=A^+B
当然，如果你首先不能计算伪逆，例如，因为（A^ta）是奇异的（即行列式为零），那么就不存在交集
因为我们处理的是线段，所以当x0和x1都在区间[01]内时，交点在点p（x0）或Q（x1）处
其他解决方法
为了避免处理矩阵代数，我们可以尝试使用向量代数和代换法求解系统：
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）
我还不能提供上述结果的几何直观
采摘器协调方式
给定线段p受点P1和P2限制，线段Q受点Q1和Q2限制
线p的Pucker坐标由一对3d向量（Pd，Pm）给出：
Pd=P2-P1
Pm=P1 x P2
式中，Pm是P1和P2的叉积。可以用完全相同的方法计算线Q的采摘器坐标（Qd，Qm）
线p和Q只有在共面时才能相交。第P线和第Q线为共平面iif：
Pd•Qm+Qd•Pm=0
其中（•）是点积。由于机器的精度有限，稳健测试不应检查零，而应检查少量。如果Pd x Qd=0，那么直线是平行的（这里0是零向量）。对于instamce，应该再次进行稳健测试，以确定（Pd x Qd）的平方长度很小
如果两条线不平行，那么它们是共面的，它们的交点（用普莱克的术语称为“相交”）将是点：
x=（（Pm•N）Qd-（Qm•N）Pd-（Pm•Qd）N）/（Pd x Qd）•N
其中N是任何坐标轴向量（即，（1,0,0）或（0,1,0）或（0,0,1）），如at（Pd x Qd）•N为非零
如果p和Q都不通过原点，那么它们的采摘器坐标Pm和Qm将分别为非零，并且以下sinpler公式将起作用
x=Pm x Qm/Pd•Qm
有关Pucker坐标的介绍，请参见：
https://en.m.wikipedia.org/wiki/Plücker_coordinates
http://www.realtimerendering.com/resources/RTNews/html/rtnv11n1.html#art3
关于一般的求交公式，请参见“推论6”：
http://web.cs.iastate.edu/~cs577/handouts/plucker-coordinates.pdf
将椭圆转换为前后旋转的圆
我们总是可以把椭圆变成圆。椭圆有两个“半径”，称为半轴，你可以把它们想象成两个正交向量，一个大的称为大半轴，一个小的称为小半轴。可以对两个半轴向量应用非均匀缩放变换，使其大小相等，从而得到一个圆
我们定义一个椭圆“E”，它的中心O是一个3d点，它的两个半轴A1和A2也是3d向量。椭圆平面的法向量N可以通过其半轴N=A1 x A2的叉积来计算，然后将其归一化为单位长度
现在假设有一个线性函数M，你可以用它把椭圆E变换成一个圆C，半径等于短半轴，把它应用到椭圆的半轴A1和A2，以及椭圆的中心O
请注意，Elipse的圆心O和椭圆的法向量N不会因M而改变。因此M（N）=N和M（O）=O。这意味着圆位于同一平面上，并且与椭圆具有相同的位置C。线性函数M有一个对应的反函数M^-1，所以我们可以将圆的向量变换回原始椭圆E
当然，我们也可以使用函数M来变换直线p和Q的端点，将它们发送到“圆空间”，我们可以使用M^-1将它们发送回“椭圆空间”
利用M，我们可以计算圆空间中的直线p和Q与椭圆E的交点。现在我们可以把重点放在直线和圆的交点上
线平面相交
给定一个具有法向量N和距离D的平面：
N•x+D=0
对于平面中的每个点x。然后，与线P的交点与Pucker坐标（Pd，Pm）由下式给出：
x=（nx 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线在圆的平面内，那么下面的单次检查将给出答案：
https://stackoverflow.com/a/1079478/9147444
如何计算线性函数M
计算M的简单方法如下。使用椭圆的法向量N以及半轴A1和A2创建一个3x3矩阵U。这样，U将向量A1、A2和N作为列
然后缩放长半轴A1，使其与短半轴A2具有相同的长度。然后创建矩阵V auch，该矩阵V将新向量A1、A2和N作为列
然后我们定义线性矩阵系统：
RU=V
其中R是一个3x3（非均匀）标度旋转矩阵
我们可以通过将方程的两边乘以U的倒数来求解R，U的倒数用U^-1表示
ru^-1=vu^-1
因为U^-1是我们得到的单位矩阵：
R=vu^+
利用R定义仿射变换
M（x）=R（x-O）+O
我们可以使用M将点转换为圆空间，例如O、P1、P2、Q1和Q2。但是如果我们需要变换向量，比如A1，A2，N，Pd和Qd。我们需要e简单的M：
M（x）=rx
因为A1、A2和N是R的特征向量，所以R不是奇异的，并且有一个逆。我们将逆M定义为：
M^-1（x）=R^-1（x-O）+O
对于向量：
M^-1（x）=R^-1 x
更新：椭圆-椭圆相交
两个相交的非共面三维椭圆的交点位于其平面相交形成的线上。所以你首先找到包含椭圆的平面相交形成的线（如果平面不相交，也就是说，它们是平行的，那么两个椭圆都不相交）
交线属于两个平面，因此它垂直于两条法线。方向向量V是平面法线的叉积：
V=N1×N2
为了完全确定直线，我们还需要在直线上找到一个点。我们可以通过解平面的线性方程来实现。给定2x3矩阵N=[N1^T N2^T]，法线N1和N2为行，2x1列向量b=[N1•C1，N2•C2]，其中C1和C2是椭圆的中心，我们可以形成线性矩阵系统：
nx=b
其中X是满足两个平面方程的点。由于满足系统的直线上有无限多个点，因此系统被低估。我们仍然可以通过使用矩阵N的伪逆（用N^+表示）找到更接近原点的特定解
X=N^+b
直线方程是
L（t）=X+tV
对于一些标量t
然后可以应用前面描述的方法来测试线-椭圆相交，即将椭圆缩放为一个圆，并与共面线相交。如果两个椭圆在同一点与直线相交，则它们相交
现在，椭圆实际上位于同一平面上的情况更加复杂。你可以在Eberly博士的优秀著作《几何工具》（Geometric Tools，也可在网上找到）中看到他的方法：
https://www.geometrictools.com/Documentation/IntersectionOfEllipses.pdf
，也可以检查开源的C++源代码：
https://www.geometrictools.com/GTEngine/Include/Mathematics/GteIntrEllipse2Ellipse2.h