java - Java：两个椭圆段的交点转换为 3d 空间

对于线-线相交测试有几种解决方法。经典的方式是使用线性代数（即求解线性矩阵系统），但从软件开发的角度来看，我更喜欢几何代数方式，采用 Plucker Coordinates 的形式，它只需要实现向量代数运算（即，叉积和点积），它们比用于求解线性系统的矩阵运算更易于编码。

为了比较，我将两者都显示，然后您决定：

线性代数方式

给定由点 P1 和 P2 限制的线段 P 和由点 Q1 和 Q2 限制的线段 Q。

线的参数形式由下式给出：

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^TA)^-1 A^T

见： https ://en.m.wikipedia.org/wiki/Generalized_inverse

幸运的是，Java 中的任何矩阵包都应该能够非常轻松地并且可能非常高效地计算上述计算。

如果将 A 与其伪逆 A^+ 相乘等于单位矩阵 I，即 (AA^+) == I，则存在唯一答案（交集），您可以得到它计算以下乘积：

x = A^+ B

当然，如果您一开始就无法计算伪逆，例如，因为 (A^TA) 是奇异的（即行列式为零），则不存在交集。

由于我们正在处理线段，因此交点在点 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)

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

拔取器坐标方式

给定由点 P1 和 P2 限制的线段 P 和由点 Q1 和 Q2 限制的线段 Q。

线 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 定义一个椭圆“E”，它是一个 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 的端点，将它们发送到“圆形空间”，我们可以使用 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 以使 V 具有新的向量 A1 和 A2 以及 N 作为列。

然后我们定义线性矩阵系统：

RU = V

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

我们可以通过将等式两边乘以 U 的倒数来求解 R，用 U^-1 表示

RUU^-1 = VU^-1

由于 UU^-1 是我们得到的单位矩阵：

R = VU^+

使用 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 是椭圆的中心，我们可以形成线性矩阵系统：

NX = 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

java - Java：两个椭圆段的交点转换为 3d 空间

问题描述

解决方案

推荐阅读