在进行图形求交时，常常需要判定两个图形间是否有包含关系。如点是否包含在线段、平面区域、三维形体中，线段是否包含在平面区域、三维形体中，等等。许多包含判定问题可转化为点的包含判定问题，如判断线段是否在平面上可以转化为判断其两端点是否在平面上。因此下面主要讨论关于点的包含判定算法。

判断点与线段的包含关系，也就是判断点与线的最短距离是否位于容差范围内。造型中常用的线段有三种：

（1）直线段，（2）圆锥曲线段（主要是圆弧），（3）参数曲线（主要是Bezier，B样条与NURBS曲线）。点与面的包含判定也类似地分为三种情况。下面分别讨论。

1、点与直线段的包含判定

假设点坐标为P(x, y, z)，直线段端点为P₁(x₁, y₁, z₁)，P₂(x₂,y₂,z₂)，则点P到线段P₁P₂的距离的平方为

d²=(x-x₁)²+(y-y₁)²+(z-z₁)²-[(x₂-x₁)(x-x₁)+(y₂-y₁)(y-y₁)+(z₂-z₁)(z-z₁)]²/[(x₂-x₁)²+(y₂-y₁)²+(z₂-z₁)²]

当d²<a²时，认为点在线段（或其延长线）上，这时还需进一步判断点是否落在直线段的有效区间内。只要对坐标分量进行比较，假设线段两端点的x分量不等（否则所有分量均相等，那么线段两端点重合，线段退化为一点），那么当x-x₁与x-x₂反号时，点P在线段的有效区间内。

2、点与圆锥曲线段的包含判定

以圆弧为例，假设点的坐标为(x, y, z)，圆弧的中心为（x₀, y₀, z₀），半径为r，起始角a₁，终止角a₂。这些角度都是相对于局部坐标系x轴而言。圆弧所在平面为

　　　　ax+by+cz+d=0

先判断点是否在该平面上，若不在，则点不可能被包含。若在，则通过坐标变换，把问题转换到二维的问题。

给定中心为（x₀, y₀），半径为r，起始角a₁，终止角a₂的圆弧，对平面上一点P（x, y），判断P是否在圆弧上，可分二步进行。第一步判断P是否在圆心为（x₀, y₀），半径为r的圆的圆周上，即下式是否成立：

第二步判断P是否在有效的圆弧段内。

3、点与参数曲线的包含判定

设点坐标为P(x, y, z)，参数曲线为Q(t)=(x(t), y(t), z(t))。点也参数曲线的求交计算包括三个步骤：

（1）计算参数t值，使P到Q(t)的距离最小；

（2）判断t是否在有效参数区间内（通常为[0，1]）；

（3）判断Q(t)与P的距离是否小于a 。若（2），（3）步的判断均为“是”，则点在曲线上；否则点不在曲线上。

第一步应计算t，使得|P-Q(t)|最小，

即 R(t)=(P-Q(t))(P-Q(t))=|P-Q(t)|²最小

根据微积分知识，在该处R'(t)=0即

Q'(t)[P-Q(t)]=0

用数值方法解出t值，再代入曲线参数方程可求出曲线上对应点的坐标。第（2）、（3）步的处理比较简单，不再详述。

4、点与平面区域的包含判定

设点坐标为P(x, y, z)，平面方程为ax+by+cz+d=0。则点到平面的距离为

　　　　d=

若d<a ，则认为点在平面上，否则认为点不在平面上。在造型系统中，通常使用平面上的有界区域作为形体的表面。在这种情况下，对落在平面上的点还应进一步判别它是否落在有效区域内。若点落在该区域内，则认为点与该面相交，否则不相交。下面以平面区域多边形为例，介绍有关算法。

判断平面上一个点是否包含在同平面的一个多边形内，有许多种算法，这里仅介绍常用的三种：叉积判断法、夹角之和检验法以及交点计数检验法。

（1）叉积判断法

假设判断点为P₀。多边形顶点按顺序排列为P₁P₂…P_n。如图2.5.2所示。令V_i=P_i-P₀, i=1, 2, …, n, V_n+1=V₁。

那么，P₀在多边形内的充要条件是叉积V_iXV_i+1(i=1, 2, …, n)的符号相同。叉积判断法仅适用于凸多边形。当多边形为凹时，尽管点在多边形内也不能保证上述叉积符号都相同。这时可采用后面介绍的两种方法。

图2.5.2 叉积判断法

（2）夹角之和检验法

假设某平面上有点P₀和多边形P₁P₂P₃P₄P₅，如图2.5.3所示。将点P₀分别与P_i相连，构成向量V_i=P-P₀。假设角 P_iP₀P_i+1=a_i。如果=0，则点P₀在多边形之外，如图2.5.3(a)所示。如果=2π，则点P₀在多边形之内，如图2.5.3(b)所示。a_i可通过下列公式计算：令S_i=V_i? V_i+1, C_i=V_i·V_i+1，则tg(a_i)=S_i/C_i，所以a_i=arctg(S_i/C_i)且

a_i的符号即代表角度的方向。

图2.5.3 夹角之和检验法

在多边形边数不太多（<44）的情况下，可以采用下列近似公式计算a_i。

　　　　当 |S_i|≤|C_i|

　　当 |S_i|>|C_i|

其中d=0.0355573为常数。当_Σαi≥π

时，可判P₀在多边形内。当_Σαi＜π 时，可判P₀在多边形外。证明略。

（3）交点计数检验法

当多边形是凹多边形，甚至还带孔时，可采用交点计数法判断点是否在多边形内。具体做法是，从判断点作一射线至无穷远：

求射线与多边形边的交点个数。若个数为奇数，则点在多边形内，否则，点在多边形外。

如图2.5.4所示，射线a, c分别与多边形交于二点和四点，为偶数，故判断点A，C在多边形外。而射线b, d与多边形交三点和一点，为奇数，所以B，D在多边形内。

当射线穿过多边形顶点时，必须特殊对待。如图2.5.4所示，射线f过顶点，若将交点计数为2，则会错误地判断F在多边形外。但是，若规定射线过顶点时，计数为1，则又会错误地判断点E在多边形内。正确的方法是，若共享顶点的两边在射线的同一侧，则交点计数加2，否则加1。按这种方法，E点计为2，所以在多边形外；F点计数为１，所以在多边形内。读者可以自己另取一些点来验证。

图2.5.4 交点计数法

5、点与二次曲面/参数曲面的包含判定

假设点坐标为P(x₀, y₀, z₀)，二次曲面方程为Q(x, y, z)=0，则当|Q(x₀, y₀, z₀)|<? 时，认为点在该二次曲面上，在造型系统中，通常使用裁剪的二次曲面。在这种情况下，还要判断点是否在有效范围内。裁剪的二次曲面通常用有理Bezier或有理B样条的参数空间上的闭合曲线来定义曲面的有效范围，故要把点所对应的参数空间的参数坐标计算出来，再判断该参数坐标是否在参数空间有效区域上。

6、点与三维形体的包含判定

判断点是否被三维形体所包含，可先用前面的方法判断点是否在三维形体的表面上，然后判断点是否在形体内部，其方法因形体不同而异。下面以凸多面体为例说明。

设凸多面体某个面的平面方程为ax+by+cz+d=0，调整方程系数的符号，使当ax+by+cz+d<0时，点(x,y,z)位于该平面两侧中包含该凸多面体的一侧。于是要检验一个点是否在凸多面体内部，只要检验是否它对凸多面体的每一个面均满足以上的不等式即可。