二维几何01-基本算法.ppt

1、2006年九月29日，上海交通大学计算机系河源县，第1，5章二维几何，基本几何算法之一，2，5.1大纲(1)，屏幕显示或用绘图仪绘制的图形都是二维的，通过计算机处理的三维以上维度的图形也是二维的。讨论了处理二维(平面)图形的几种茄子方法，主要讨论了基本几何图形元素(点、直线、圆弧创建和交点计算等)。3，5.1概述(2)，通常这些基本子软件包构成了平面贴图系统的基本内容。这些系统本质上不能称为二维图形处理系统，仅包含“线”处理(“线”的说明、“线”的交叉计算等)。其基本立足点是通过“线”处理说明(或输出)图形的实际效果，很少从整体角度考虑图形的概念。考虑2D图面的描述、产生和图面的运算问题。也就

2、是说，不应只关注图形轮廓的说明，而应考虑图形的外部和内部。4，5.1概述(3)，生成新的2D图形时，使用图形本身作为操作对象和结果。例如，在朝鲜，矩形钢板必须切割成特定形状并切开，内部需要挖各种类型的孔以形成肋骨、肘部等船体结构。在服装行业，矩形布必须裁剪，以适应机器其他部件的电脑支持设计。有时修剪、分割或合并某些标准零件，以形成新的更复杂的零件和工件。5，5.1概述(4)，区分图形内部和外部图形的描述方法是一点确定图形内部部分的算法的方法。两个图形交叉、差分等几何运算的算法和图形显示所必需的图形裁剪算法等，都是2D图形处理中最根本、最基本的问题。6，5.2向量和向量之间的交集，7，5.2向量

3、和向量之间的交集(1)，设定平面具有向量P1P2和Q1(u1，v1)牙齿，从P1(x1，y1)到P2(x2，y2)，只有在0，1和0，1牙齿的情况下，才能说两个矢量有交点。，9，5.2矢量和矢量之间的交点(3)，P1P2到Q1Q2的旋转方向(相对于P1P2要素值的交点符号)是与中的符号相同的Q1Q2到P1P2的旋转方向相反的符号， 10，5.2向量与向量相交(/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * yp2)floatle Yq

4、2)float line segment q1q 2 output : * SPF loat parameter of on line segment p1p 2 * sq float parameter of on line segment 0两条线没有交点。* sp、* sq、* KP、* kq are not available * * * * * * * * * * * * * * * * * * * * * * * * * * * */计算dy=yp2-yp1；qx=xq2-xq1；QY=yq2-yq1；delta=dx * QY-dy * qx:If(fabs(delta)EPS)

5、/0 If(delta)=0.0)/唯一值* KP=1；else * KP=-1；* kq=-* KP；UX=xq1-xp1；/计算交点参数vy=yq1-yp1；* sp=(QY * UX-qx * vy)/delta:* sq=(dy * UX-dx * vy)/delta；if(* sp)-EPS)/无线交点，intplv LV (float xp1，float yp1，float xp2，float yp2，float xq1Int *kq)，12，5.3平面中点列的凸形轮廓算法，G1 查找内部点:查找“点”列的内部点G，从内部点水平向右查找矢量L。G2 排序:连接内部点和所有点列，根据

6、这些连接和L之间的角度以升序对点列进行排序，以形成双向链接表。G3 查找凸面包的起点:获取点行中的所有极P0(x或y的最小/最大值)。Min/Max，13，5.3平面上的点列的凸形轮廓算法，G4 查找凸形包的顶点:从点1开始，依次查看连续的三个顶点，如果是反向旋转(图中的实心点)，则将表指针加1，或删除这三个顶点中的中间点(图中)，方向点，反向点这样得到的凸包是周期点列，无论选择哪个起点，都可以用作凸包的起点。14，5.4包容性测试，确定平面上的一点是否位于图形内部或外部符号判别角度判别法Griffiths判别法反射线交叉数判定法，15，5.4.1符号判别法(1)，如果图形是凸N多边形(仅包含

7、一个环)。设定形成多边形的环的方向，以使边向量的左侧取得通过多边形内部每个边向量的善意方程式系数(Ai，Bi，Ci) (i=1，2，n)，16，5.4.1符号判别方法(2)，否则所有Di0 (i=1，2，n)牙齿方法的计算工作量为O(n)，17，5.4.1符号判别法(3)，在牙齿判别法中，多边形是凸面条件(例如A45xt B45yt C45 0牙齿，但是T位于多边形内部)。18，5.4.2角度判别方法(1)，P=p1，p2，pn，p1是pi(xi，yi)，i=1，2，n的顶点，ptPi是连接Pt和pi的矢量，I，20，5.4.2角度判别法(3)，牙齿角度的计算不需要高精度。误差甚至可能不会失去

8、判断的准确性，但必须计算两个矢量之间的角度。与半三角函数的计算有关。计算工作量大的计算量也是O(n)，但可以获得比符号判别法的工作多几倍的性能。5.4.3 Griffiths判别法(1)，为了避免角度判别法中的倒三角形函数，Griffiths在1981年(CAD JANUARY 1981 NUMBER 1 VO1 13)提出了近似值，以加快计算速度。基本原则是向量乘积PtPiPtPi 1与Sini成比例，数量乘积PtPiPtPi 1与cosi成比例，因此tgi或ctgi可以从两个乘积的结果中派生。22，5.4.3 Griffiths判别法(2)，角度I可通过以下近似线性近似公式得出：arctg

9、 x=/4x C式，23，5.4.3 Griffiths判别法(3牙齿近似公式直观、简单，避免三角函数的计算，以满足一般应用。24，5.4.4反射线交叉数判别法，R是从P开始的任意方向的反射线。r和多边形的交集数为奇数时，点P是多边形内部的交集数为偶数或0时，点P是多边形外部的25，5.4.4半射线交集数判别法。26，算法P:反光线交叉包容测试算法，从P1 光线创建点Pt(Xt，Yt)到点(X，Yt)创建光线向量。其中x是多边形顶点无法到达的x的较大值，Yt表示光线与x轴平行。P2 查找交点使牙齿射线矢量与多边形的每个角矢量相交。记录交点几何参数以及光线和特征值的相对值，并在光线方向上对齐交点

10、。27，算法P:包括半射线交点数的测试算法，P3 积分中点确定相邻交点的几何参数(例如中点)。求特征值的代数总和(例如代数和0)将取消两个交点。否则，其中一个交点将被取消。P4 合并相邻的相同要素交集标识两个相邻交点的要素，如果两个相邻的要素相同，则放弃其中一个交点。P5 判别计算交点数。奇数是多边形内部的点，否则是多边形外部的点。28，调查重新相交的特征值(1)、相对于P1P2相交的特征值标记为“1”的两个相交特征值和2标记为“2”的两个相交特征值，以及-2标记为“3”和“4”的两组相交特征值和0等。29向量和环只有一个公共点(例如，交点3，4)牙齿。在SUM0中，如果给定矢量穿过相对环的某

11、个顶点(例如交点2)穿过回路(例如交点1)，则实际上仅用作一个交点。30，重新相交的特征值(3)，重新相交的特征值：如果交点是中点，则使用每个交点特征值对数总和的符号作为重新相交特征值的符号。如果要素值代数和非0牙齿，要素值的绝对值仍然为1，取消其中一个交叉值(1，2)的代数和0；2006年九月二十九日，上海交通大学计算机系下院，31，5.5直线段和直线边界图形公共部分的取(1)，32，5.5直线段和直线边界图形公共部分的取在隐藏线删除中，必须对屏幕的线段做出相反的判断，公共部分隐藏起来，公共部分绘制出来。，33，5.5直线段与直线边界图的公共部分的计算(2)，故障诊断首先求出矢量P1P2与构

12、成形状的各环的边向量的交点，并由相交特征的几何意义识别。从矢量的最后一点到相邻引出点的部分位于图形内部。特殊情况是，当交点具有中点(图中的实心点)，即交点与环中的顶点重合时，引入点和引出点的相邻特性将被破坏。34，算法C:获取直线和图形公共部分的算法，C1 相交和对齐段(矢量)和图形(环)的每个边(矢量)的交点，并沿P1P2方向对齐0，1，0，1的交点。C2 删除重新相交累积具有相同相交参数的重新相交的特征值SUM=IPC，如果SUM=0，则取消牙齿交点。否则，删除其中一个交点，重新交点成为一个交点，SUM符号用作牙齿交点的要素值。35，算法C:取消直线和图形公共部分的算法，C3 连续入口，流

13、出处理其中一个连续对齐的要素符号的交点，如果是两个连续“”的交点，则取消下一个“”交点。如果是两个连续的“-”交点，则没有C4 确定重叠交点，线段和图形没有公共部分，并且算法结束。C5 查找公共部分依次选择从负交点到正交点的线段的所有部分，即线段和地物的公共部分。36，5.6算法G:多边形剪裁算法，G1 设置方向将多边形的顶点与“左内”几何体方向对齐。G2 寻找相交牙齿线(向量)与多边形的每个边向量相交。记录相交几何图形参数以及线和特征值的相对值，并将交点与线方向对齐。G3 合并中点确定相邻交点的几何图形参数(例如中点)。求特征值的代数总和(例如代数和0)将取消两个交点。否则，其中一个交点将被

14、取消。37，5.6算法G:多边形截取算法，G4 合并相邻相同图征相交识别两个相邻交点的图征，如果两个相邻图征相同(例如全部为)，则退回前一个交点(例如)。取消下一个交点。G5 输出标记线段按顺序输出从负要素交点到相邻正要素交点的直线段。38，5.7算法S:剖面线算法，S1 方程式生成图形说明(圆弧曲线XYR)，与直线的连接设定通过两点的方向法向系数，与圆弧的连接根据附录子程序PPPR取得中心位置。S2 计算剖面线范围对于每个图形顶点，根据问题3得出斜率为K的截距。对于弧线段，根据问题4取得截距。从所有截断点求和。39，5.7算法S:剖面线算法，S3 初始剖面线创建点(0，D)，坡率为K的AX BY C=0，善意方向可以是随机的，但是一旦选择，它将不再更改，通常将前进方向的左侧保持为负值。求出S4 寻找剖面线牙齿无限直线与所有图形的交点。交点包含几何参数和特征。此处，圆弧的要素按问题处理。如果与圆弧段的交点相切，则切线不相交，交点沿直线方向对齐。40，5.7算法S:剖面线算法，如果有