《基本几何01-基本理论.ppt》由会员分享，可在线阅读，更多相关《基本几何01-基本理论.ppt（50页珍藏版）》请在三一办公上搜索。
1、2002年10月24日,1,第4章 基本几何,之一基本理论,2,4.1引言,完整地叙述了一种以向量几何为理论、以“方向性”概念为基础的几何计算理论体系统一描述点、线（向量）、圆（弧）等基本几何及曲线和图形等的表示；对基本几何建立方向的概念，探索基本几何的方向定义以及它对几何计算效率的影响；构建距离、面积、角度、分比、几何连接和封闭图形的边界走向等几何属性的新涵义、新体系；引入“交点特征”的概念；在此基础上研究几何计算的稳定性和算法的复杂性理论。.,3,4.1引言,.详细阐述了它的基本理论、思想方法、几何结构、几何问题处理以及它们的算法与复杂性分析等。,4,4.1引言,.它在解决几何交、切运算，
2、包容性测试，几何造型，布尔运算等几何计算的奇异情况处理中的重大作用：如何有效地将二维布尔运算降为一维向量计算将三维布尔运算下降为二维布尔运算.将三维线消隐算法最终归结为一维交集算法等等,5,4.1引言,“交点特征”和“几何方向”的优越性发挥得淋漓尽致使这些在基本几何的新体系上构筑的典型几何算法变得出奇的简单。,6,4.1引言,在开发一个计算机图形系统的时候，都必须与基本几何元素点、直线和圆（圆周和圆弧段）有关。由于实际问题的大部份都出现于平面上，而平面上的曲线又可转化为由直线段和圆弧段构成，故平面图形能涉及的几何元素只包括点、直线和圆（圆周和圆弧段）三种。在图形的相互关系处理中，点实际上不独立
3、构成图形的某一部份（只是作为一种标识），因此，基本几何只是直线和圆（弧）两种，用这两种基本几何元描述所有图形。,7,4.1引言,两者具有良好的几何不变性质，它们的建立和相交处理都比较简单，所构造图形的处理（如图形面积、周界长度，图形形心等的求取）都较为简易。由于产生这两种几何元的插补原理简单，插补机成本较低，目前的自动绘图机和数控切割机都采用直线和圆弧插补形式。因此，对这两种几何元的研究是平面图形处理的基础性工作。,8,4.1引言,直线和圆（弧）的定义和它们之间的相互关系虽然并不复杂，但是作为描述所有图形的基础，使用广泛，因此其定义的严密性，以及处理的效率就显得至关重要。需要深入地研究这两种几
4、何元的有关问题，建立一套完整的、正确的和有效的基本几何直线、圆（弧）定义和求解系统。,9,4.2 基本几何的描述,10,4.2.1 直线的描述,1）直线的二点式方程设直线通过点P1(x1,y1)和P2(x2,y2)，则直线方程可表示为：上述描述形式用作计算机内表示并不可取，因为需要特别注意：x2-x1=0 或 y2-y1=0两种状态以防止计算时溢出。,11,4.2.1 直线的描述,2）直线的参数方程如果把 1）式左式的值记为t，就有：这是一种较好的直线描述方式，优点是：直观，直线通过的两点明显地表现在方程之中；能够描述任何形式的直线；参数t有明显的几何意义：当：t0,1，表示P1P2间的线段；
5、t（-,）表示通过P1P2的无穷直线。,12,4.2.1 直线的描述,3）直线的标准方程设若将式1）式左式两端同乘以(x2-x1)且移项，则有(y2-y1)(x-x1)-(x2-x1)(y-y1)=0令A=y2-y1B=-(x2-x1)C=-(Ax1+By1)就得到直线的标准方程：Ax+By+c=0,13,4.2.1 直线的描述,直线的标准方程的优点在于它能够表达二维平面上的任何直线。向量a=(A,B)表示直线的法向。平面上任何点P(xp,yp)到直线的距离可表示为：当D0时，表示P在直线的正侧；D0时，表示P在直线的负侧；D0时，表示P点在直线上。,14,4.2.1 直线的描述,标准直线方程
6、在计算机图形处理中常作为直线的描述，它以向量L（A,B,C）的形式存放。显然，若改变系数（A,B,C）的符号也可得到同一条直线的方程，但是直线的正、负侧，即直线的方向改变了。为了今后图形处理的方便，本教程将只采用下列直线方向：点P1到P2的直线方向的右侧为正侧 左侧为负侧（同y轴方向）,15,4.2.1 直线的描述,4）直线的法线式方程若对直线的标准方程式同除以因子就成为：记为ax+by+c=0 其中，,16,4.2.1 直线的描述,直线的法线式方程中a和b有明显的几何意义：a=sin，b=-cos是直线正向（保证直线右侧为正，左侧为负的方向）与x轴正向的夹角，且a2b21,17,4.2.1
7、直线的描述,直线的法线式方程除了具有标准方程的优点外，还具有3个特点：计算点到直线的距离时，只要把点直接代入直线的方程计算出函数值即可。由于直线方程的系数给出了法向的正弦和余弦，在考虑与直线角度有关的曲线元相关计算中特别方便。由于其法向量系数具有单位模长，它在以直线为新轴的坐标变换中特别方便。,18,4.2.1 直线的描述,描述直线的形式尚有截距式、点斜式等多种，但是在计算机图形处理的理论和实践中值得推荐的是上面四种。特别是：直线的参数方程直线的法线式方程 ax+by+c=0,19,4.2.2 圆的描述,圆的定义通常只有两种形式，圆的一般定义和圆的参数方程定义。以下表示以点(xc,yc)为圆心
8、，R为半径的圆。1）圆的一般定义(x-xc)2+(y-yc)2=R22）圆的参数定义x=xc+Rcosy=yc+Rsin,20,4.2.3 圆弧的描述,对直线段，通常只需确定一个起点和一个终点就能全部决定。对于圆弧段则复杂些，这种选择将变得比较复杂。,21,4.2.3 圆弧的描述,1)指定圆心位置、半径、起点幅角和终点幅角2)指定圆心位置指定圆心位置、半径及其方向、起点和终点,会出现数据的不相容!,22,4.2.3 圆弧的描述,3)指定起点和终点以及凸出因子凸出因子b=tg(/4)，其中为圆弧段张角圆弧方向隐含于凸出因子b内。当b1，为优弧b=1，为半圆b1，为劣弧,23,4.2.3 圆弧的描
9、述,4)指定起点和终点、半径及其方向、优弧还是劣弧,描述了小于（不等于！）360o的任何圆弧较少的存储量直观、几何意义明显无二义性,24,4.2.3 圆弧的描述,5)指定起点和终点，弓形高h和圆弧方向圆弧方向隐含于弓形高h内，h也称作圆弧的幅度。|h|R，表优弧；|h|R，表劣弧；|h|=R，表半圆；h=0，表直线。,描述了小于（不等于！）360o的任何圆弧统一了直线段和圆弧段的描述方法有较少的存储量不太直观进行图形运算的过程中需要反复求半径。,25,4.3 基本几何的统一描述,当选用何种方式来作为计算机内的描述手段时，除应考虑直线段和圆弧段的本身因素外，还要考虑它们用于组合曲线或图形描述时参
10、数的有效程度。两个相接的几何段其中间点是公共的，就不希望重复存放。考察4）、5）两种方式，取其所长、避其所短。,26,4.3 基本几何的统一描述,取“指定起点和终点、半径及其方向和劣弧”取“弓形高h0”时表示两点之间的直线连接关系扩展“两点间分离因素（不显示连接）”统一两点之间的连接关系如下：所受的限制是：圆弧段只能选择为一种，或为劣弧或为优弧（包括半圆）。但这种限制对使用不会产生太大的影响。当然它不能描述整圆。,27,4.4 用基本几何描述图形,圆弧曲线：若曲线由基本几何段（直线段或圆弧段）构造，且当基本几何段为圆弧段时，则为劣弧段（可至半圆），这样的曲线叫做圆弧曲线。,28,4.4 用基本
11、几何描述图形,当构成圆弧曲线的相邻几何段相切时，圆弧曲线就描述一条光滑曲线。但由定义可知，圆弧曲线不要求相邻的几何段保持相切关系，因此，它能够描述由基本几何（直线段和圆弧段）构造的任何平面图形。计算机描述一般安排一个较大的二维数组以适应不同类型图形的描述。因此，所记录的图形可能并不充满整个XYR数组，可以用XYR（1,1）（C语言为XYR00）指出该记录的实际长度。typedef struct float x,y,r;XYR;加上文字可描述一般工程图。,29,4.5 基本几何的方向,对基本几何元素（直线、圆/弧和边界走向、连接方向等）引入定向概念对其属性（距离、角度、面积、分比、交点特征等）引
12、入正负概念这些概念的引入将大幅度简化几何计算,30,4.5 基本几何的方向,在直角坐标系下，平面曲线的表达式f(x,y)=0可将平面分成三个点集：G0=(x,y)|f(x.y)=0G+=(x,y)|f(x.y)0G-=(x,y)|f(x.y)0若图形是由封闭的几何段构成的，上述表达式可用来确定平面的点是在图形的外部还是内部。推广到三维后，也可据以判定空间点是在物体的内部还是外部。这对图形的几何运算十分有用。,31,4.5 基本几何的方向,1）点 由它的一对坐标（x,y）定义2）圆(x-xc)2+(y-yc)2=R2 R0，逆时针走向；R0，顺时针走向圆上的切线方向和圆的方向一致,32,4.5
13、基本几何的方向,3）直线（直线段/向量）由其规范化的标准式方程：ax+by+c=0 定义，其中a2+b2=1 直线的方向选取这样一个方向：当人沿着这个方向行走时，他的左手方向为负区域(内部)，右手方向为正区域(外部)由P1到P2和由P2到P1所建立的直线其方向（因而其系数）是不同的点Px,y到直线的距离：D=ax+by+c，D=0，点在直线上D0，点在直线右侧,33,4.5 基本几何的方向,4）圆弧段起点P1，终点P2有向半径R满足这样的圆弧段有两个取劣弧段（可至半圆）,34,4.5 基本几何的方向,5）角度直线L1与直线L2的夹角为由直线L1的正向绕两直线的交点，按最近旋转与直线L2的正向重
14、合的旋转角度。逆时针旋转时，为正；顺时针旋转时,为负。圆周上两点，所对应的圆心角是取劣弧段所对应的圆心角。,35,4.5 基本几何的方向,6）距离沿直线的距离的方向和直线的走向相同，顺着走向时，距离为正，逆着走向时，距离为负。圆上的弧长以逆时针方向为正，顺时针方向为负。,36,4.5 基本几何的方向,几何元素平移的距离按几何元素的方向决定，移向正区域距离取正，移向负区域距离取负。,37,4.5 基本几何的方向,7）面积由逆时针走向的封闭曲线构成的图形的面积为正，反之为负。,38,4.5 基本几何的方向,8）分比设P为平面上二点P1、P2的分比点，则分比值当P为内分点时，0，外分点时 0。,39
15、,4.5 基本几何的方向,9）几何元素连接时的方向几何元素连接时，其走向保持几何元素的连续走向，即由一个几何元素顺着另一个几何元素的方向前进。例如当求取两相离圆的公切线时，所求的公切线就满足皮带轮转动规律。,40,4.5 基本几何的方向,10）封闭边界的走向当人沿着封闭图形的边界行走时，他的左手指向图形的内部，右手指向图形的外部。（图形的外边界为逆时针走向，内边界为顺时针走向。）,?,内部?,当边界为凸时，才有：外边界为逆时针走向内边界为顺时针走向。,41,4.5 基本几何的方向,11）交点的特征值交点由2个参数表述，分别对应于相交的两向量L1和L2：几何参数（t1：对应于向量L1，t2：对应
16、于向量L2）特征参数（It1：对应于向量L1，It1：对应于向量L2）特征值It1的定值：如果向量L1至向量L2的最近旋转是逆时针，则It1特征值为+1，否则为-1。由于向量积是不可逆的，因此，2个特征值的符号相反，其代数和为0。,42,4.5 基本几何的方向,交点特征的几何意义：设有一向量P1P2和一封闭图形边界相交对向量P1P2而言若交点S的特征值为-1，则向量P1P2由交点S进入该图形内部，称此交点为入点(S1)；若交点S的特征值为+1，则向量P1P2从交点S离开图形，称此交点为出点(S2)。这个结论在以后的几何计算（例如图形布尔运算）及三维隐藏线消除中十分有用。,2002年10月24日
17、,上海交通大学计算机系 何援军,43,4.6几何元素定向的优点,44,4.6.1 定义图形的外部和内部,对直线、圆弧以及图形边界等定义方向将能够较好地解决一系列图形处理中的问题。能够定义出图形的外部和内部，便于图形的进一步处理。图形外部和内部的概念在二维图形的交、并、差运算中极为有用。图形面积正、负的定义使得在计算带有内孔图形的面积时只要计算其各个边界所围面积的代数和就行了。,45,4.6.2 避免一些奇异状态,在直线和圆弧等基本几何元素的相交计算中，不仅可以减少子程序的参数个数，而且可以避免一些奇异状态例题：求一条直线和圆的交点,从右至左，当X逼近于相等时产生一个跳跃现象。,如果两个解按照直
18、线的方向排列，而规定选择是前进方向的第一个，或第二个或两者，则形参个数可减少一个，且不会出现奇异状态，选择也比较直观，便于使用,程序中选取X大的解，当X相等时选取Y大的解。,46,4.6.3 简化计算,例一：已知半径分别为R1和R2的两定圆和一半径R，求作一圆同时切于两定圆。分析：如果不计R，R1，R2的方向，那未解决这个问题先要知道所求圆与R1和R2是外切还是内切。如果是外切，则以半径之和；如果是内切，则以半径之差，分别作两定圆的两同心圆，其交点即为所求圆的圆心。,47,4.6.3 简化计算,如果指定了三圆的方向（由半径符号定），则不必判断是外切还是内切，只要分别以（R1+R）和（R2+R）
19、为半径作已知两圆的同心圆，就可自动求取两圆的外切或内切圆，而不必关心三圆之间是外切还是内切。,48,4.6.3 简化计算,例二：已知两圆相切，求公切点。分析：由于半径带有符号，公切点可直接由内外分点的统一公式确定，不必判别两圆是外切还是内切,49,4.6.4便于进一步的图形处理,由于几何元素定义了方向，图形的边界就能区分出图形外部和内部的概念，这在图形的几何运算、剖面线绘制和隐藏线的消除算法等提供了良好的基础；为二维图学和三维图学的统一描述和处理也提供了方便。,50,总结,1)直线描述：以向量L(a,b,c)的形式存放。2)圆弧描述：指定起点和终点、半径及其方向(优弧还是劣弧)3)方向性概念：交点的特征值,
