几何图元的交集是许多计算机图形学和建模应用中的基本构造（[弗利等，1996]，[O'Rourke的，1998]）。这里我们看看最简单的2D和3D线性图元的算法：线，线段和平面。
线和交点
为了计算二维和三维的直线和线段的交点，最好使用直线的参数方程表示法。在算法2中讨论了其他表示法，关于
点到线的
距离。这里显示了如何从其他表示转换为参数表示。
在任何维度上，由两个点P 0 和P 1定义的线的参数方程可以表示为：
，
参数s是一个实数，
是一个行方向向量。使用这个表示
，
以及何时
，P（s）是有限段P 0 P 1上的点，其中s是P（s）沿着段的距离的分数。即s = d（P 0，P（s））/ d（P 0，P 1）。此外，如果s <0，则P（s）在P 0侧的段之外，并且如果 s > 1，则P（s）在P 1侧的段之外。
让两行由下式给出：
并且
，任一者或这两者都可以是无限的，光线，或有限区段。
平行线
这些线是平行的，当且仅当它们的方向是共线的，即当两个矢量
和
作为线性相关Ú = 一个v对于一些实数一个。对于
和
，这意味着所有的比率
都有值a，或者
对于所有的我。这相当于所有的条件
。在2D中，与
和
，这是PERP产物 [希尔，1994]条件是
，其中
，所述PERP操作者，是垂直于ü。这种情况表明，欧几里德平面中的两个矢量在垂直于同一方向矢量时是平行的
。如果为真，则两条相关的线或者重合，或者根本不相交。
如果一条线上的点P 0也位于另一条线Q（t）上，则可以通过测试轻松地检查一致性。也就是说，存在数字t 0使得：P 0 = Q（t 0）= Q 0 + t 0 v。如果w =（w i）= P 0 - Q 0，那么这相当于w = t 0 v对于某些t 0这与我
所有的一样。在2D中，这是另一个产品条件：。如果这个条件成立的话，那么这个条件是无限的。如果一条线（而不是另一条线）是一个有限的线段，那么它是一致的交点。但是，如果两条线都是有限的线段，那么它们可能（或可能不）重叠。在这种情况下，求解t 0和t 1使得P 0 = Q（t 0）和P 1 = Q（t 1）。如果段间隔[ t 0，t
1 ]和[0,1]是不相交的，没有交集。否则，相交的时间间隔（使用最大和最小操作）得到
。然后交点段是
。这在任何维度上都有效。
非平行线
当两条线或线不平行时，它们可能会交叉在一个独特的点上。在二维欧几里得空间中，无限的线条总是相交的。在更高维度中，他们通常会彼此思念而不相交。但是如果它们相交，那么它们在2D平面上的线性投影也将相交。所以，可以简单地限制到两个坐标，u和v不平行，计算这两个坐标在P（s I）和Q（t I）的二维交点I，然后测试P（s I）= Q（t I）为所有的坐标。要计算2D交点，请考虑图中的两条直线和相关向量：
为了确定小号我，我们有矢量平等的
地方
。在交叉点，矢量
垂直于
，这相当于perp产品条件
。求解这个等式，我们得到：
请注意，分母
只有当前面讨论的线是平行的。类似地，求解Q（t I），我们得到：
的分母是相同的了签，因为
，如果我们想知道，这两个应该只计算一次š 我和牛逼我。然而，知道任何一个都足以得到交点I = P（s I）= Q（t I）。
此外，如果两条线中的一条是有限的线段（或射线），例如P 0 P 1，则仅当
（或者
对于射线）该交点才在该线段中。如果两条线都是线段，那么两个解决方案参数s I和t I必须处于相交的区间[0,1]。虽然这听起来很简单，但由于许多特殊情况需要检查（请参阅我们的实现），两段的交集代码有点微妙。
平面交叉口
如算法4中所述表示
平面，参见
平面。
线平面交叉口
在3D中，线L或者平行于平面P 或者与单个点相交。设L由参数方程给出
，而平面P 由其上的点V 0和法向量给出
。我们首先 通过测试来检查L是否平行于P
，这意味着线方向矢量u垂直于平面法线n。如果这是真的，则L和P是平行的，或者不相交，否则L完全位于平面P中。不相交或重合可以通过测试中的任何一个特定的点是否被确定大号，说P 0，被包含在P ，即是否满足隐线方程：
。
如果线和平面不平行，那么L和P 相交于一个唯一的点P（s I），这个点使用类似于2D中两条线相交的方法计算。考虑下图：
在交点处，矢量
垂直于n， 其中
。这相当于点积条件：
。解决我们得到：
如果线L是从P 0到P 1的有限段，那么只需要检查
以验证段和平面之间存在交点。对于正射线，当与飞机有一个交点时
。
2架飞机的交集
在3D中，两个平面P 1和P 2或者平行，或者在一条直线L上相交。让P 我（我 = 1,2）可以通过给定的点V 我和法线矢量Ñ 我，并有一个隐含的公式：ñ 我 · P + d 我 = 0，其中P =（X，ÿ，Ž） 。平面P 1和P 2每当它们的法向矢量n 1平行时和Ñ 2是平行的，并且这等效于条件是：Ñ 1 X Ñ 2 = 0。在软件，人们将测试，如果
在由分割
会导致溢出，并使用此作为鲁棒条件Ñ 1和Ñ 2在实践中是平行的。当
不平行时，由于u垂直于n 1和n 2，所以是相交线L的方向矢量，因此平行于两个平面，如下图所示。如果| u |是小的，所以最好把它缩小以使| u | = 1，使你成为单位方向矢量。
经过计算
（3加6乘），为了完全确定交线，我们还需要找到一个特定的点。也就是说，我们需要找到一个
位于两个平面上的点。我们可以通过找到一个通用的解决方案来做到隐式方程为P 1 和P 2。但是由于点P 0可以位于一维线L上的任何地方，因此在这3个未知数中只有两个方程。所以我们需要另一个约束来解决一个具体的P 0。有很多方法可以做到这一点：
（A）直线方程。可以设置一个坐标为零，比如z 0 = 0，然后解决其他两个。但是，当这只会工作大号相交平面Z ^ 0 = 0。这将是真实的，当Z ^ -协调ü ž的
非零。因此，首先必须选择u的非零坐标，然后将P 0的对应坐标设置为0.此外，应该选择具有最大绝对值的坐标，因为这将给出最稳健的计算。假设
，那么
就躺在L上。解决这两个方程：
和
，得到：
L的参数方程为：
这里的分母等于u的非零的第三个坐标。所以，忽略一个大的非零坐标的测试，并把乘法计数除法，这个解决方案的总运算次数= 5增加13次乘法。
（B）线相交点。如果一个人知道一个平面上的特定线（例如平面上的两个点），并且这条线与另一个平面相交，那么它的交点I将位于两个平面上。因此，在两平面的交线上，L的参数方程为：P（s）= I + s（n 1 x n 2）。为了计算
和交点（给定线），操作总数= 11增加了19倍。
在一个平面上构建一条必须与另一个平面相交的线的一种方法是将一个平面的法向矢量投影到另一个平面上。这给出了必须始终与飞机交叉线垂直的线。因此，在P 1上的n 2的投影定义了在L上寻找点P 0时与P 2相交的线。更具体地说，将两点0 =（0,0,0）和n 2 =（nx 2，ny 2，nz 2）投影到P 1（0），P 1（n 2）。则P 1中的投影线为L 1：Q（t）= P 1（0）+ t（P 1（n 2）-P 1（0）），并与P 2的交点进行计算。在最有效的情况下，当n 1和n 2都是单位法向矢量并且预先存储常量P 1（0）时，总操作= 17增加+22个相乘。
（C）3平面相交点。另一种方法选择具有隐式方程n 3 · P = 0 的第三平面P 3，其中n 3 = n 1 × n 2且d 3 = 0（意味着它通过原点）。这总是起作用的，因为：（1）L垂直于P 3并因此与它相交，（2）矢量n 1，n 2和n 3是线性无关的。因此，平面P 1，P 2和 P 3相交于必须在 L上的唯一点 P 0。使用3个平面相交的公式（参见下一节），其中对于 P 3， d 3 = 0，得到：
L的参数方程为：
该解决方案的操作次数= 11增加了+23次乘法。
底线是最有效的方法是直接解决方案（A），使用只有5加13乘法来计算交点线的方程。
3架飞机的交集
在3D中，三个平面P 1，P 2和P 3可以通过以下方式相交（或不相交）：
几何关系
路口
代数条件
所有3架飞机都是平行的
对全部
他们重合
一架飞机
他们是不相交的
没有
只有两个平面是平行的，
第三个平面每个都是一条线
[注意：两个平行平面可能重合]
2条平行线
[平面重合
=> 1条线]
只有一
对
没有两个平面是平行的，所以两两相交成三行
对全部
相交线是平行的
他们都一致
1行
用另一条线测试一条线的点
他们是不相交的
3条平行线
相同的测试，但失败=>不重合
没有相交线是平行的
独特的一点
如图所示：
首先要测试一个唯一相交点的最常见情况，也就是说
，因为这排除了所有其他情况。当交点是一个独特的点时，由下式给出：
这可以通过证明这个P 0满足所有平面P 1，P 2和P 3的参数方程来验证。
但是，当分母
非常小时，这种计算的鲁棒性会出现问题。在这种情况下，最好为两个平面得到一个稳健的交线，然后计算这条线与第三个平面相交的点。
实现
以下是这些算法的一些示例“C ++”实现。
//版权所有2001 softSurfer，2012 Dan Sunday
//此代码可以自由使用和修改用于任何目的
//只要包含此版权声明即可。
// SoftSurfer对此代码不作任何保证，也不
承担由于使用而导致的任何真实或想象的损害。
//此代码的用户必须验证其应用程序的正确性。
//假设已经为这些对象提供了类：
// Point和Vector with
// coordinates {float x，y，z;}
//运算符用于：
// ==测试相等性
//！=测试不等式
/ /点=点矢量
//矢量=点 -
矢量=标量*矢量（标量积）
//矢量=矢量*矢量（三维交叉乘积）
// 线和光线和段的定义点{点P0， P1;}
//（一行是无限的，光线和分段从P0开始）
//（一个Ray延伸到P1之外，但是一个Segment在P1结束）
// 用一个点和一个普通的平面 {Point V0; Vector n;}
// ============================================ =======================
#define SMALL_NUM 0.00000001 //避免分割溢出的任何事情
//点积（3D）允许在参数中进行向量运算
#define点（u，v）（（u）.x *（v）.x +（u）.y *（v）.y +（u）.z *（v）.z）
#define perp（u，v）（（u）.x *（v）.y - （u）.y *（v） x）// perp产品（2D）
// intersect2D_2Segments（） ：找到2个的有限区段的2D相交
//输入：两个有限区段S1和S2
//输出：* I 0 =相交点（当其存在时）
// * I1 =相交段的端点[I0， I1]（当它存在时）
//返回：0 =不相交（不相交）
// 1 =相交于唯一点I0
// 2 =从I0到I1的段重叠
int
intersect2D_2Segment（段S1，段S2，Point * I0 ，Point * I1）
{
Vector u = S1.P1-S1.P0;
向量v = S2.P1-S2.P0;
矢量w = S1.P0-S2.P0;
float D = perp（u，v）;
//测试它们是否平行（包括一个点）
if（fabs（D）<SMALL_NUM）{// S1和S2是并行的
if（perp（u，w）！= 0 || perp（v，w） ！= 0）{
return 0; //他们不是共线的
}
//他们是共线的或退化的
//检查他们是退化点
float du = dot（u，u）;
float dv = dot（v，v）;
如果（du == 0 && dv == 0）{//这两个段都是点
if（S1.P0！= S2.P0）//它们是不同点
返回0;
* I0 = S1.P0; //他们是相同的点
返回1;
}
如果（du == 0）{// S1是单点
if（inSegment（S1.P0，S2）== 0）//但是不在S2中
返回0;
* I0 = S1.P0;
返回1;
}
if（dv == 0）{// S2单点
if（inSegment（S2.P0，S1）== 0）//但不在S1中
返回0;
* I0 = S2.P0;
返回1;
}
//他们是共线段 - 重叠（或不）
float t0，t1; // S2中的S1的端点
向量w2 = S1.P1 - S2.P0;
if（vx！= 0）{
t0 = wx / vx;
t1 = w2.x / vx;
}
else {
t0 = wy / vy;
t1 = w2.y / vy;
}
if（t0> t1）{//必须使t0小于t1
float t = t0; T0 = T1; T1 = T; //交换如果不是
}
如果（T0> 1个|| T1 <0）{
返回0; //不重叠
}
t0 = t0 <0？0：t0; // clip to min 0
t1 = t1> 1？1：t1; //
如果（t0 == t1）{//相交是一个点
* I0 = S2.P0 + t0 * v;
返回1;
}
//它们在有效子段中重叠
* I0 = S2.P0 + t0 * v;
* I1 = S2.P0 + t1 * v;
返回2;
} / /
段是歪斜的，并可能相交于一个点
//获取S1的相交参数
float sI = perp（v，w）/ D;
如果（sI <0 || sI> 1）//不与S1相交
返回0;
//获得S2的相交参数
float tI = perp（u，w）/ D;
如果（tI <0 || tI> 1）//不与S2相交
返回0;
* I0 = S1.P0 + sI * u; //计算S1相交点
返回1;
}
// =============================================== ====================
// inSegment（）：确定一个点是否在一个段内
//输入：一个点P和一个共线段S
//返回：1 = P在S内
// 0 = P不在S内
int
inSegment（Point P，S段）
{
if（S.P0.x！= S.P1.x）{//
如果（S.P0.x <= Px && Px <= S.P1.x）
返回1 ;
如果（S.P0.x> = Px && Px> = S.P1.x）
返回1;
}
else {// S是垂直的，所以
如果（S.P0.y <= Py && Py <= S.P1.y）
返回1，则测试y坐标。
如果（S.P0.y> = Py && Py> = S.P1.y）
返回1;
return 0;
}
//===================================================================
// intersect3D_SegmentPlane（）：找到一个段和一个平面的三维交点
//输入：S =一个段，Pn =一个平面= {点V0; 向量n;}
//输出：* I0 =相交点（当它存在时）
//返回：0 =不相交（不相交）
// 1 =唯一点中的交点* I0
// 2 =段位于plane
int
intersect3D_SegmentPlane（Segment S，Plane Pn，Point * I）
{
Vector u = S.P1-S.P0;
矢量w = S.P0-Pn.V0;
float D = dot（Pn.n，u）;
float N = -dot（Pn.n，w）;
if（fabs（D）<SMALL_NUM）{//段与平面平行
如果（N == 0）//段位于平面
返回2;
否则
返回0; //没有交集
}
//它们不平行
//计算相交PARAM
浮SI = N / d;
如果（sI <0 || sI> 1）
返回0; //没有交点
* I = S.P0 + sI * u; //计算段相交点
返回1;
}
// =============================================== ====================
// intersect3D_2Planes（）：找到两个平面的三维交点
//输入：两个平面Pn1和Pn2
//输出：* L =交叉线（当它存在时）
//返回：0 =不交叉（不交叉）
// 1 =两个平面重合
// 2 =唯一线中的交点* L
int
intersect3D_2Planes（平面Pn1，平面Pn2，线* L）
{
向量u = Pn1.n * Pn2.n; //跨产品
float ax =（ux> = 0？ux：-ux）;
float ay =（uy> = 0？uy：-uy）;
float az =（uz> = 0？uz：-uz）;
//测试两个平面是否平行
if（（ax + ay + az）<SMALL_NUM）{// Pn1和Pn2接近平行
//测试是否不相交或重合
Vector v = Pn2.V0 - Pn1.V0;
如果（点（Pn1.n，V）== 0）// Pn2.V0在Pn1中
返回1; // Pn1和Pn2重合，
否则
返回0; // Pn1和Pn2不相交
}
// Pn1和Pn2相交
//首先确定交叉积的最大绝对坐标
int maxc; //最大坐标
if（ax> ay）{
if（ax> az）
maxc = 1;
else maxc = 3;
}
else {
if（ay> az）
maxc = 2;
else maxc = 3;
}
//接下来，在相交线上得到一个点
//将最大坐标为零，并求解另外两个
Point iP; //相交点
float d1，d2; // 2个平面方程中的常数
d1 = -dot（Pn1.n，Pn1.V0）; //注意：可以用平面预先存储
d2 = -dot（Pn2.n，Pn2.V0）; //同上
开关（maxc）{//选择最大坐标
情况1：//与x = 0相交
iP.x = 0;
iP.y =（d2 * Pn1.nz-d1 * Pn2.nz）/ ux;
iP.z =（d1 * Pn2.ny - d2 * Pn1.ny）/ ux;
打破;
情况2：//与y = 0相交
iP.x =（d1 * Pn2.nz -d2 * Pn1.nz）/ uy;
iP.y = 0;
iP.z =（d2 * Pn1.nx-d1 * Pn2.nx）/ uy;
打破;
情况3：//与z = 0相交
iP.x =（d2 * Pn1.ny - d1 * Pn2.ny）/ uz;
iP.y =（d1 * Pn2.nx-d2 * Pn1.nx）/ uz;
iP.z = 0;
}
L-> P0 = iP;
L-> P1 = iP + u;
返回2;
}
// =============================================== ====================
参考
James Foley，Andries van Dam，Steven Feiner和John Hughes，“
计算机图形学（第3版）（2013）”中的“裁剪线”
Joseph O'Rourke，
C计算几何中的 “搜索与交集”
（第二版）（1998）
