2.5.2求交线算法

2.5.2求交线算法

^{求交线显然是指求面与面的交线，下面讨论几种常见的情况。}

X{\hA-D0

^{1、平面与平面的交线}

^{在CAD中一般使用平面上有界区域。先考虑最简单的情形。两个平面区域分别由P(u, w), Q(s, t), u, w, s, t? [0, 1]定义。如果它们不共面而且不分离，则必交于一直线段。这条直线必落在P(u, w)-Q(s, t)=0所定义的无限直线上。注意这是个含有四个未知数，三个方程式的方程组，只要分别与八条边界线方程：u=0, u=1, w=0, w=1, s=0, s=1, t=0, t=1联立，即可求出线段的两个端点的参数。在上述方程组中，只要找到两组解，就可以不再对剩余其它方程组求解。找到的两组解就是所求的交线段端点参数。}

^{当两个一般的多边形（即既可能是凸的，也可能是凹的，甚至可能带有内孔）相交时，可能有多段交线。我们可以把两个多边形分别记为A和B，用如下的算法求出它们的交线：}电脑爱好者网&|1d\d,Ud

^{（1）把A的所有边与B求交，求出所有有效交点；}

^{（2）把B的所有边与A求交，求出所有有效交点；}电脑爱好者网R%B'RR0c,n2w[

^{（3）把所有交点先按y，再按x的大小进行排序；}

^{（4）把每对交点的中点与A和B进行包含性检测，若该中点即在A中又在B中，则该对交点定义了一条交线段。}电脑爱好者网,sD(M(x4@%T`}` m

^{2、平面与二次曲面的交线}电脑爱好者网'~2urN] [#O

^{求平面与二次曲面的交线有两种方法：代数法和几何法。}电脑爱好者网 j#}&f|;?4va

^{用代数法考虑平面与二次曲面求交问题时，可以把二次曲面表示为代数形式，}电脑爱好者网 D-@C(N$f2C j

^{Ax2+By2+Cz2+2Dxy+2Eyz+2Fxz+2Gx+2Hy+2Iz+J=0}电脑爱好者网[D Wjed/v3g

^{可以通过平移与旋转坐标变换把平面变为XOY平面，对二次曲面进行同样的坐标变换。由于在新坐标系下平面的方程为z=0，所以新坐标系下二次曲面方程中，把含z项都去掉即为平面与二次曲面的交线方程（在新坐标系下）。对该交线方程进行一次逆坐标变换即可获得在原坐标系下的交线方程。在具体实现时，交线可以用二元二次方程系数表示（代数表示），辅之以局部坐标系到用户坐标系的变换矩阵。这种方法的缺点是，每当需要使用这些交线时，都要进行坐标变换。例如，判断一个空间点是否在交线上，必须先对它进行坐标变换，变到z=0平面上，再进行检测。需要绘制该交线时，也要先在局部坐标系下求出点坐标，再变换到用户坐标系下的坐标。所以交线采用另一种方法（几何表示）更合理。几何方法存储曲线的类型（椭圆、抛物线或双曲线），以及定义参数（中心点、对称轴、半径等大小尺寸）的数值信息，使用局部坐标系到用户坐标系的变换，把局部坐标系下的定义参数变换到用户坐标系直接使用。这第二种方法使用较少的变换，但需要用计算来判断曲线的种类，及计算曲线的定义参数。由于浮点运算的不精确性，容易发生判错类型以及定义参数误差过大的问题。}

^{当平面与二次曲面的交线需要精确表示时，往往采用几何法求交。二次曲面采用几何表示，平面与二次曲面求交时，根据它们的相对位置与角度（根据定义参数），直接判断交线类型，其准确性大大优于用代数法计算分类的方法。几何法不需要对面进行变换，所以只要通过很少的计算就可以得到交线的精确描述。由于存储的信息是具有几何意义的，所以判断相等性、相对性等问题时，可以确定有几何意义的容差。下面以平面一球求交为例，说明几何法求交算法。}电脑爱好者网8FL,L8?NS,C

^{平面用一个记录p表示，p的两子域p.b, p.w分别代表平面上一点与平面法向量。球面用记录s表示。它的两个子域s.c, s.r分别代表球面中心和半径。则可写出平面与球面相交的算法如下：}电脑爱好者网(D1K0hO!UKnydL`

plane_sphere_intersect(p, s)电脑爱好者网S0g6a#[6kv

plane p;电脑爱好者网i)y ur^9h[1S

sphere s;

[ {`suxx%HI0

{电脑爱好者网2I{1A[rE:t!z

d=球面中心到平面的有向距离；

TA:^hA~mn0

if(abs(d)=s.r)电脑爱好者网d&Yye"?em

{ 二个面相交于一（切）点s.c-d * p.w;}

/Y+Q)j:L i0

else if (abs(d)>s.r)电脑爱好者网 I:Kyi f-{

{ 两个面无交；}电脑爱好者网{xug2z%_z7W&g*`

else电脑爱好者网%r6D;Q5JJ"yv

{ 所求交线是圆。其圆半，半径，圆所在平面法向量为电脑爱好者网ytC+sQ j@Ws

c=s.c-d * p. w;电脑爱好者网uBKEp,N%K][ {

r=sqr t(s.r²-d²);

p,wao
JfF0

w=p.w;

`gkcUIy P&mi0

}电脑爱好者网-l8]!f_N\.D

}

o6D%}6jW'kt6@0

^{一个平面与一个圆柱面可以无交、交于一条直线（切线）、二条直线、一个椭圆或一个圆，可以用两个面的定义参数求出它们的相对位置关系和相对角度关系，进而判断其交属于何种情况，并求出交线的定义参数。平面与圆锥的交线也可类似求出。}电脑爱好者网.R~!a3`Z4s-\6iJ

3. ^{平面与参数曲面的交线} 电脑爱好者网
   {{&x.E QD9? Z0A#WB

^{最简单的方法是把参数曲面的表示（x(s,t), y(s,t), z(s,t)）代入平面方程}

^ax+by+cz+d=0

^{得到用参数曲面的参数s、t表示的交线方程}电脑爱好者网 UhIsm&oeHb
D~

^{ax(s,t)+by(s,t)+cz(s,t)+d=0}电脑爱好者网u#Vp"Os.o3[/g.{

^{另一种方法是用平移和旋转变换对平面进行坐标变换，使平面成为新坐标系下的xoy平面。再用相同的变换应用于参数曲面方程得到参数曲面在新坐标系下的方程}电脑爱好者网E
Z1x9PC&__uc"S7A

^{（x*, y*, z*）=（x*(s,t), y*(s,t), z*(s,t)）}

^{由此得交线在新坐标系下的方程为z*(s, t)=0}电脑爱好者网 pEazOX&qJHnJ

`w-m[K7E0