我将线段和椭圆(非平面和椭圆体)的片段转换为3d空间,并且需要计算两个给定的片段是否相交以及在哪里。
我正在使用Java但尚未找到解决我问题的库,也没有遇到过我可以用于自己实现的算法。
对于线 - 线交叉测试,有几种方法可以解决。经典的方法是使用线性代数(即求解线性矩阵系统),但从软件开发的角度来看,我更像是几何 - 代数方式,以Plucker坐标的形式,它只需要实现向量代数运算(即,交叉产品和点积产品比编码线性系统的矩阵运算更简单。
为了比较,我将展示两者,然后你决定:
线性代数方法
给定由点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 ^ 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)是单数(即行列式为零),则不存在交集。
由于我们处理段,如果x0和x1都在区间[0 1]中,则交点位于点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)
我还不能提供上述结果的几何直觉。
Plucker坐标方式
给定由点P1和P2限制的线段P和由点Q1和Q2限制的线段Q.
P行的Plucker坐标由一对3d矢量(Pd,Pm)给出:
Pd = P2-P1
Pm = P1×P2
其中Pm是P1和P2的交叉积。线Q的Plucker坐标(Qd,Qm)可以完全相同的方式计算。
如果它们是共面的,则线P和Q只能相交。如果出现以下情况,P和Q线是共面的:
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×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×A2的叉积计算,然后将其归一化以具有单位长度。
现在假设有一个线性函数M可用于将椭圆E转换(缩放)成圆C,半径等于次半轴,通过将其应用于椭圆的半轴A1和A2以及椭圆的中心O.
请注意,eliipse的中心O和椭圆的法向量N不会被M改变。因此M(N)= N且M(O)= O.这意味着圆位于同一平面并且具有与C相同的位置C.椭圆。线性函数M具有相应的反函数M ^ -1,因此我们可以转换回圆的矢量以获得原始椭圆E.
当然,我们也可以使用函数M转换线P和Q的端点,将它们发送到“圆空间”,然后我们可以使用M ^ -1将它们发送回“椭圆空间”。
使用M我们可以计算线P和Q与圆形空间中的椭圆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×A2)/ | A1×A2 |
D = -N•O
线圆和点圆交点
现在有了x,圆点检查很简单:
| O - x | <= | A2 |
只有当x在圆边界时才等于平等。
如果P行在圆圈的平面上,那么下面的sinple检查会给你答案:
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 Y = B.
其中R是3×3(非均匀)缩放 - 旋转矩阵。
我们可以通过将等式的两边乘以U的倒数来求解R,其由U ^ -1表示
R y ^^ -1 = b y ^ -1
由于U U ^ -1是我们得到的单位矩阵:
P = B Y ^ +
使用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
更新:椭圆 - 椭圆交点
两个相交的非共面三维椭圆在它们的平面之间的交点形成的线上具有它们的交叉点。所以你首先找到由包含椭圆的平面的交点形成的线(如果平面不相交,即它们是平行的,那么椭圆都不相交)。
交叉线属于两个平面,因此它垂直于两个法线。方向向量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