java - Java:将两个椭圆段的交集转换为3d空间

Question

我将线段和椭圆段（非平面和椭圆体）转换为3d空间，并且需要计算两个给定的段是否相交以及在何处相交。

我正在使用Java，但是还没有找到可以解决我的问题的库，也没有遇到可以用于自己的实现的算法。

Answer 1

对于线-线相交测试，有几种解决方法。经典方式是使用线性代数（即求解线性矩阵系统），但是从软件开发的角度来看，我更喜欢采用Plucker坐标形式的Geometric-Algebra方式，该方式仅需要实现矢量代数运算（即，叉积和点积），比矩阵运算更容易编码，以解决线性系统问题。

为了进行比较，我将同时展示两者，然后您决定：

线性代数方式

给定线段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：

x = B

其中，A是一个3x2矩阵，第一列的向量（P2-P1）坐标，第二列的向量（Q2-Q1）坐标； x是未知数t0和t1的2x1列向量，B是3x1列向量，坐标为向量（Q1-P1）。

经典地，该系统可以通过计算矩阵A的伪逆来求解，用A ^ +表示：

A ^ + =（A ^ T A）^-1 A ^ T

看到：
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）

我还不能提供上述结果的几何直觉。

采摘坐标方式

给定线段P受点P1和P2限制，线段Q受点Q1和Q2限制。

P线的Plucker坐标由一对3d向量（Pd，Pm）给出：

Pd = P2-P1

Pm = P1 x P2

其中Pm是P1和P2的叉积。可以以完全相同的方式来计算线Q的Plucker坐标（Qd，Qm）。

P和Q线只有在共面的情况下才能相交。 Thr行P和Q是共同的iif：

Pd•Qm + Qd•Pm = 0

其中（•）是点积。由于机器具有有限的精度，因此可靠的测试应检查零而不是零。如果Pd x Qd = 0，则线是平行的（此处0是零向量）。同样，应该进行可靠的测试，以确保（Pd x Qd）的平方长度很小。

如果这些线不平行，则它们是共面的，并且它们的交点（在Plucker的行话中称为“相遇”）将是重点：

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

有关一般的交集公式，请参见以下内容的“推论6”：

http://web.cs.iastate.edu/~cs577/handouts/plucker-coordinates.pdf

将椭圆变换为前后圆

我们总是可以将椭圆变成圆形。椭圆具有两个称为半轴的“半径”，您可以在脑海中将它们可视化为两个正交向量，一个大称为主要半轴，一个小的称为次要半轴。您可以对两个半轴向量应用非均匀的缩放变换，以使其大小相等，因此得到一个圆。

我们通过其中心O（一个3d点）以及两个半轴A1和A2（它们也是3d向量）定义一个椭圆“ E”。可以通过椭圆半平面的叉积N = A1 x A2求出椭圆平面的法向矢量N，然后将其规格化为单位长度。

现在，假设有一个线性函数M，您可以将其应用到椭圆的半轴A1和A2上，并将其转换（缩放）为半径等于次半轴的圆C，半径等于次半轴。椭圆的中心O。

注意，椭圆的中心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。然后，用Plucker坐标（Pd，Pm）与线P的交点为：

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在圆的平面内，则以下正弦检查将为您提供答案：

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作为列。

然后定义线性矩阵系统：

R U = V

其中R是3x3（非均匀）缩放旋转矩阵。

我们可以通过将方程式的两边都乘以U的倒数（由U ^ -1表示）来求解R

R U U ^ -1 = V U ^ -1

由于U U ^ -1是单位矩阵，我们得到：

R = V U ^ +

使用R定义仿射变换

M（x）= R（x-O）+ O

我们可以使用M将点变换为圆形空间，例如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

为了完全确定线，我们还需要在线上找到一个点。我们可以解决平面的线性方程。给定2x3矩阵N = [N1 ^ T N2 ^ T]，以法线N1和N2为行，并且2x1列向量b = [N1•C1，N2•C2]，其中C1和C2是椭圆的中心，我们可以形成线性矩阵系统：

N X = b

X是满足两个平面方程的某个点。由于线中有无数个点使系统满意，所以该系统尚不确定。通过使用矩阵N的伪逆，用N ^ +表示，我们仍然可以找到更接近原点的特定解。

X = N ^ + b

线方程为

L（t）= X + t V

对于一些标量t。

然后，您可以应用前面所述的方法来测试线-椭圆相交，即将椭圆缩放为一个圆形并与共面线相交。如果两个椭圆都在同一点相交，则它们相交。

现在，椭圆实际上位于同一平面上的情况更加复杂。您可以在Eberly博士的出色著作《几何工具》（也可在线获得）中采用以下方法：

https://www.geometrictools.com/Documentation/IntersectionOfEllipses.pdf

您也可以检查开源的C ++源代码：

https://www.geometrictools.com/GTEngine/Include/Mathematics/GteIntrEllipse2Ellipse2.h