基本几何01-基本理论.ppt

《基本几何01-基本理论.ppt》由会员分享，可在线阅读，更多相关《基本几何01-基本理论.ppt（50页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第第4章章 基本几何基本几何之一之一基本理论基本理论2002年10月24日12023/4/16上海交通大学计算机系 何援军24.1引言引言r完整地叙述了一种以向量几何为理论、以完整地叙述了一种以向量几何为理论、以“方向方向性性”概念为基础的几何计算理论体系概念为基础的几何计算理论体系q统一描述点、线（向量）、圆（弧）等基本几何统一描述点、线（向量）、圆（弧）等基本几何及曲线和图形等的表示；及曲线和图形等的表示；q对基本几何建立方向的概念，探索基本几何的方对基本几何建立方向的概念，探索基本几何的方向定义以及它对几何计算效率的影响；向定义以及它对几何计算效率的影响；q构建距离、面积、角度、分比、几

2、何连接和封闭构建距离、面积、角度、分比、几何连接和封闭图形的边界走向等几何属性的新涵义、新体系；图形的边界走向等几何属性的新涵义、新体系；q引入引入“交点特征交点特征”的概念；的概念；q在此基础上研究几何计算的稳定性和算法的复杂在此基础上研究几何计算的稳定性和算法的复杂性理论。性理论。.22023/4/16上海交通大学计算机系 何援军34.1引言引言r.详细阐述了它的基本理论、思想方法、几详细阐述了它的基本理论、思想方法、几何结构、几何问题处理以及它们的算法与何结构、几何问题处理以及它们的算法与复杂性分析等。复杂性分析等。32023/4/16上海交通大学计算机系 何援军44.1引言引言r.它在

3、解决几何交、切运算，包容性测试，它在解决几何交、切运算，包容性测试，几何造型，布尔运算等几何计算的奇异情几何造型，布尔运算等几何计算的奇异情况处理中的重大作用：况处理中的重大作用：q如何有效地将二维布尔运算降为一维向量如何有效地将二维布尔运算降为一维向量计算计算q将三维布尔运算下降为二维布尔运算将三维布尔运算下降为二维布尔运算q.将三维线消隐算法最终归结为一维交集算将三维线消隐算法最终归结为一维交集算法法q等等等等42023/4/16上海交通大学计算机系 何援军54.1引言引言r“交点特征交点特征”和和“几何方向几何方向”的优越性发挥得的优越性发挥得淋漓尽致淋漓尽致r使这些在基本几何的新体系上

4、构筑的典型使这些在基本几何的新体系上构筑的典型几何算法变得出奇的简单。几何算法变得出奇的简单。52023/4/16上海交通大学计算机系 何援军64.1引言引言r在开发一个计算机图形系统的时候，都必须与基在开发一个计算机图形系统的时候，都必须与基本几何元素点、直线和圆（圆周和圆弧段）有关。本几何元素点、直线和圆（圆周和圆弧段）有关。r由于实际问题的大部份都出现于平面上，而平面由于实际问题的大部份都出现于平面上，而平面上的曲线又可转化为由直线段和圆弧段构成，故上的曲线又可转化为由直线段和圆弧段构成，故平面图形能涉及的几何元素只包括点、直线和圆平面图形能涉及的几何元素只包括点、直线和圆（圆周和圆弧段

5、）三种。（圆周和圆弧段）三种。r在图形的相互关系处理中，点实际上不独立构成在图形的相互关系处理中，点实际上不独立构成图形的某一部份（只是作为一种标识），因此，图形的某一部份（只是作为一种标识），因此，基本几何只是直线和圆（弧）两种，用这两种基基本几何只是直线和圆（弧）两种，用这两种基本几何元描述所有图形。本几何元描述所有图形。62023/4/16上海交通大学计算机系 何援军74.1引言引言r两者具有良好的几何不变性质，它们的建两者具有良好的几何不变性质，它们的建立和相交处理都比较简单，所构造图形的立和相交处理都比较简单，所构造图形的处理（如图形面积、周界长度，图形形心处理（如图形面积、周界长度

6、，图形形心等的求取）都较为简易。等的求取）都较为简易。r由于产生这两种几何元的插补原理简单，由于产生这两种几何元的插补原理简单，插补机成本较低，目前的自动绘图机和数插补机成本较低，目前的自动绘图机和数控切割机都采用直线和圆弧插补形式。控切割机都采用直线和圆弧插补形式。r因此，对这两种几何元的研究是平面图形因此，对这两种几何元的研究是平面图形处理的基础性工作。处理的基础性工作。72023/4/16上海交通大学计算机系 何援军84.1引言引言r直直线线和和圆圆（弧弧）的的定定义义和和它它们们之之间间的的相相互互关关系系虽虽然然并并不不复复杂杂，但但是是作作为为描描述述所所有有图图形形的的基基础础，

7、使使用用广广泛泛，因因此此其其定定义义的的严严密密性，以及处理的效率就显得至关重要。性，以及处理的效率就显得至关重要。r需需要要深深入入地地研研究究这这两两种种几几何何元元的的有有关关问问题题，建建立立一一套套完完整整的的、正正确确的的和和有有效效的的基基本本几几何何直线、圆（弧）定义和求解系统。直线、圆（弧）定义和求解系统。82023/4/16上海交通大学计算机系 何援军94.2 基本几何的描述基本几何的描述92023/4/16上海交通大学计算机系 何援军104.2.1 直线的描述直线的描述1）直线的二点式方程）直线的二点式方程q设设直直线线通通过过点点P1(x1,y1)和和P2(x2,y2

8、)，则则直直线线方程可表示为：方程可表示为：q上上述述描描述述形形式式用用作作计计算算机机内内表表示示并并不不可可取取，因为需要特别注意：因为需要特别注意：q x2-x1=0 或或 y2-y1=0两种状态两种状态q以防止计算时溢出。以防止计算时溢出。102023/4/16上海交通大学计算机系 何援军114.2.1 直线的描述直线的描述2）直线的参数方程）直线的参数方程r如果把如果把 1）式左式的值记为式左式的值记为t，就有：就有：这是一种较好的直线描述方式，优点是：这是一种较好的直线描述方式，优点是：l直观，直线通过的两点明显地表现在方程之中；直观，直线通过的两点明显地表现在方程之中；l能够描

9、述任何形式的直线；能够描述任何形式的直线；l参数参数t有明显的几何意义：有明显的几何意义：当：当：t0,1，表示表示P1P2间的线段；间的线段；t（-,）表示通过表示通过P1P2的无穷直线。的无穷直线。112023/4/16上海交通大学计算机系 何援军124.2.1 直线的描述直线的描述3）直线的标准方程）直线的标准方程q设若将式设若将式1）式左式两端同乘以式左式两端同乘以(x2-x1)且移项，且移项，则有则有(y2-y1)(x-x1)-(x2-x1)(y-y1)=0q令令A=y2-y1B=-(x2-x1)C=-(Ax1+By1)q就得到直线的标准方程：就得到直线的标准方程：Ax+By+c=0

10、122023/4/16上海交通大学计算机系 何援军134.2.1 直线的描述直线的描述r直直线线的的标标准准方方程程的的优优点点在在于于它它能能够够表表达达二二维维平面上的任何直线。平面上的任何直线。r向量向量a=(A,B)表示直线的法向。表示直线的法向。q平平面面上上任任何何点点P(xp,yp)到到直直线线的的距距离离可可表表示示为：为：q当当 D0时，表示时，表示P在直线的正侧；在直线的正侧；D0时，表示时，表示P在直线的负侧；在直线的负侧；D0时，表示时，表示P点在直线上。点在直线上。132023/4/16上海交通大学计算机系 何援军144.2.1 直线的描述直线的描述r标标准准直直线线

11、方方程程在在计计算算机机图图形形处处理理中中常常作作为为直直线的描述，它以向量线的描述，它以向量L（A,B,C）的形式存放。的形式存放。r显显然然，若若改改变变系系数数（A,B,C）的的符符号号也也可可得得到到同同一一条条直直线线的的方方程程，但但是是直直线线的的正正、负负侧侧，即直线的方向改变了。即直线的方向改变了。r为为了了今今后后图图形形处处理理的的方方便便，本本教教程程将将只只采采用用下列直线方向：下列直线方向：q点点P1到到P2的直线方向的右侧为正侧的直线方向的右侧为正侧 左侧为负侧左侧为负侧 （同（同y轴方向）轴方向）142023/4/16上海交通大学计算机系 何援军154.2.1

12、 直线的描述直线的描述4）直线的法线式方程）直线的法线式方程q若对直线的标准方程式同除以因子若对直线的标准方程式同除以因子就成为：就成为：记为记为ax+by+c=0 其中，其中，152023/4/16上海交通大学计算机系 何援军164.2.1 直线的描述直线的描述r直直线线的的法法线线式式方方程程中中a和和b有有明明显显的的几几何何意意义：义：qa=sin，b=-cosq是是直直线线正正向向（保保证证直直线线右右侧侧为为正正，左左侧为负的方向）与侧为负的方向）与x轴正向的夹角，且轴正向的夹角，且qa2b21162023/4/16上海交通大学计算机系 何援军174.2.1 直线的描述直线的描述r

13、直直线线的的法法线线式式方方程程除除了了具具有有标标准准方方程程的的优优点点外，还具有外，还具有3个特点：个特点：q计计算算点点到到直直线线的的距距离离时时，只只要要把把点点直直接接代代入入直线的方程计算出函数值即可。直线的方程计算出函数值即可。q由由于于直直线线方方程程的的系系数数给给出出了了法法向向的的正正弦弦和和余余弦弦，在在考考虑虑与与直直线线角角度度有有关关的的曲曲线线元元相相关关计计算中特别方便。算中特别方便。q由由于于其其法法向向量量系系数数具具有有单单位位模模长长，它它在在以以直直线为新轴的坐标变换中特别方便。线为新轴的坐标变换中特别方便。172023/4/16上海交通大学计算

14、机系 何援军184.2.1 直线的描述直线的描述r描描述述直直线线的的形形式式尚尚有有截截距距式式、点点斜斜式式等等多多种种，但但是是在在计计算算机机图图形形处处理理的的理理论论和和实实践践中中值值得得推荐的是上面四种。特别是：推荐的是上面四种。特别是：r直线的参数方程直线的参数方程r直线的法线式方程直线的法线式方程 ax+by+c=0182023/4/16上海交通大学计算机系 何援军194.2.2 圆的描述圆的描述r圆圆的的定定义义通通常常只只有有两两种种形形式式，圆圆的的一一般般定定义义和圆的参数方程定义。和圆的参数方程定义。r以下表示以点以下表示以点(xc,yc)为圆心，为圆心，R为半径

15、的圆。为半径的圆。1）圆的一般定义）圆的一般定义 (x-xc)2+(y-yc)2=R22）圆的参数定义）圆的参数定义x=xc+Rcosy=yc+Rsin192023/4/16上海交通大学计算机系 何援军204.2.3 圆弧的描述圆弧的描述r对对直直线线段段，通通常常只只需需确确定定一一个个起起点点和和一一个个终终点就能全部决定。点就能全部决定。r对对于于圆圆弧弧段段则则复复杂杂些些，这这种种选选择择将将变变得得比比较较复杂。复杂。202023/4/16上海交通大学计算机系 何援军214.2.3 圆弧的描述圆弧的描述1)指定圆心位置、半径、起点幅角和终点幅角指定圆心位置、半径、起点幅角和终点幅角

16、2)指指定定圆圆心心位位置置指指定定圆圆心心位位置置、半半径径及及其其方方向向、起点和终点起点和终点会会出出现现数数据据的不相容的不相容!212023/4/16上海交通大学计算机系 何援军224.2.3 圆弧的描述圆弧的描述3)指定起点和终点以及凸出因子指定起点和终点以及凸出因子q凸出因子凸出因子b=tg(/4)，其中其中为圆弧段张角为圆弧段张角q圆弧方向隐含于凸出因子圆弧方向隐含于凸出因子b内。内。q当当b1，为优弧为优弧b=1，为半圆为半圆bR，表优弧；，表优弧；l|h|0qG-=(x,y)|f(x.y)0，逆时针走向；逆时针走向；l R0，顺时针走向顺时针走向l圆上的切线方向和圆的方向一

17、致圆上的切线方向和圆的方向一致312023/4/16上海交通大学计算机系 何援军324.5 基本几何的方向基本几何的方向3）直线（直线段）直线（直线段/向量）向量）q由其规范化的标准式方程：由其规范化的标准式方程：ax+by+c=0 定义，其中定义，其中a2+b2=1 q直直线线的的方方向向选选取取这这样样一一个个方方向向：当当人人沿沿着着这这个个方方向向行行走走时时，他他的的左左手手方方向向为为负负区区域域(内内部部)，右右手手方方向向为正区域为正区域(外部外部)q由由P1到到P2和和由由P2到到P1所所建建立立的的直直线线其其方方向向（因因而而其其系系数）是不同的数）是不同的q点点Px,y

18、到直线的距离：到直线的距离：D=ax+by+c，D=0，点在直线上点在直线上D0，点在直线右侧点在直线右侧322023/4/16上海交通大学计算机系 何援军334.5 基本几何的方向基本几何的方向4）圆弧段）圆弧段l起点起点P1，终点终点P2l有向半径有向半径Rl满足这样的圆弧段有两个满足这样的圆弧段有两个l取劣弧段（可至半圆）取劣弧段（可至半圆）332023/4/16上海交通大学计算机系 何援军344.5 基本几何的方向基本几何的方向5）角度）角度r直直线线L1与与直直线线L2的的夹夹角角为为由由直直线线L1的的正正向向绕绕两两直直线线的的交交点点，按按最最近近旋旋转转与与直直线线L2的的正

19、正向向重重合合的的旋旋转转角角度度。逆逆时时针针旋旋转转时时，为为正正；顺顺时时针针旋旋转转时时,为为负。负。r圆周上两点，所对应的圆心角是取劣弧段所对应的圆周上两点，所对应的圆心角是取劣弧段所对应的圆心角。圆心角。342023/4/16上海交通大学计算机系 何援军354.5 基本几何的方向基本几何的方向6）距离）距离r沿沿直直线线的的距距离离的的方方向向和和直直线线的的走走向向相相同同，顺顺着着走走向向时，距离为正，逆着走向时，距离为负。时，距离为正，逆着走向时，距离为负。r圆上的弧长以逆时针方向为正，顺时针方向为负。圆上的弧长以逆时针方向为正，顺时针方向为负。352023/4/16上海交通

20、大学计算机系 何援军364.5 基本几何的方向基本几何的方向r几何元素平移的距离按几何元素的方向决定，几何元素平移的距离按几何元素的方向决定，移向正区域距离取正，移向负区域距离取负。移向正区域距离取正，移向负区域距离取负。362023/4/16上海交通大学计算机系 何援军374.5 基本几何的方向基本几何的方向7）面积）面积r由逆时针走向的封闭曲线构成的图形的面积由逆时针走向的封闭曲线构成的图形的面积为正，反之为负。为正，反之为负。372023/4/16上海交通大学计算机系 何援军384.5 基本几何的方向基本几何的方向8）分比）分比r设设P为平面上二点为平面上二点P1、P2的分比点，则分比值

21、的分比点，则分比值r当当P为内分点时，为内分点时，0，外分点时外分点时 0。382023/4/16上海交通大学计算机系 何援军394.5 基本几何的方向基本几何的方向9）几何元素连接时的方向）几何元素连接时的方向r几何元素连接时，其走向保持几何元素的连续走向，几何元素连接时，其走向保持几何元素的连续走向，即由一个几何元素顺着另一个几何元素的方向前进。即由一个几何元素顺着另一个几何元素的方向前进。r例如当求取两相离圆的公切线时，所求的公切线就例如当求取两相离圆的公切线时，所求的公切线就满足皮带轮转动规律。满足皮带轮转动规律。392023/4/16上海交通大学计算机系 何援军404.5 基本几何的

22、方向基本几何的方向10）封闭边界的走向）封闭边界的走向r当人沿着封闭图形的边界行走时，他的左手指向图形的当人沿着封闭图形的边界行走时，他的左手指向图形的内部，右手指向图形的外部。内部，右手指向图形的外部。（图形的外边界为逆时针走向，内边界为顺时针走向。）（图形的外边界为逆时针走向，内边界为顺时针走向。）（图形的外边界为逆时针走向，内边界为顺时针走向。）（图形的外边界为逆时针走向，内边界为顺时针走向。）?内部内部?当边界为凸时，才有：当边界为凸时，才有：q外边界为逆时针走向外边界为逆时针走向q内边界为顺时针走向。内边界为顺时针走向。402023/4/16上海交通大学计算机系 何援军414.5 基

23、本几何的方向基本几何的方向11）交点的特征值）交点的特征值r交点由交点由2个参数表述，分别对应于相交的两向量个参数表述，分别对应于相交的两向量L1和和L2：q几何参数（几何参数（t1：对应于向量对应于向量L1，t2：对应于向量对应于向量L2）q特征参数（特征参数（It1：对应于向量对应于向量L1，It1：对应于向量对应于向量L2）r特特征征值值It1的的定定值值：如如果果向向量量L1至至向向量量L2的的最最近近旋旋转转是是逆逆时针，则时针，则It1特征值为特征值为+1，否则为，否则为-1。r由由于于向向量量积积是是不不可可逆逆的的，因因此此，2个个特特征征值值的的符符号号相相反反，其代数和为其

24、代数和为0。412023/4/16上海交通大学计算机系 何援军424.5 基本几何的方向基本几何的方向交点特征的几何意义：交点特征的几何意义：r设设有有一一向向量量P1P2和和一一封封闭闭图图形形边边界相交界相交r对向量对向量P1P2而言而言q若若交交点点S的的特特征征值值为为-1，则则向向量量P1P2由由交交点点S进进入入该该图图形形内内部，称此交点为部，称此交点为入点入点(S1)；q若若交交点点S的的特特征征值值为为+1，则则向向量量P1P2从从交交点点S离离开开图图形形，称称此交点为此交点为出点出点(S2)。r这这个个结结论论在在以以后后的的几几何何计计算算（例例如如图图形形布布尔尔运运

25、算算）及及三三维维隐隐藏藏线线消除中十分有用。消除中十分有用。424.6几何元素定向的优点几何元素定向的优点2002年10月24日43上海交通大学计算机系 何援军2023/4/16上海交通大学计算机系 何援军444.6.1 定义图形的外部和内部定义图形的外部和内部r对对直直线线、圆圆弧弧以以及及图图形形边边界界等等定定义义方方向向将将能够较好地解决一系列图形处理中的问题。能够较好地解决一系列图形处理中的问题。q能能够够定定义义出出图图形形的的外外部部和和内内部部，便便于于图图形形的的进一步处理。进一步处理。q图图形形外外部部和和内内部部的的概概念念在在二二维维图图形形的的交交、并并、差运算中极

26、为有用。差运算中极为有用。q图图形形面面积积正正、负负的的定定义义使使得得在在计计算算带带有有内内孔孔图图形形的的面面积积时时只只要要计计算算其其各各个个边边界界所所围围面面积积的代数和就行了。的代数和就行了。442023/4/16上海交通大学计算机系 何援军454.6.2 避免一些奇异状态避免一些奇异状态r在在直直线线和和圆圆弧弧等等基基本本几几何何元元素素的的相相交交计计算算中中，不不仅仅可可以以减少子程序的参数个数，而且可以避免一些奇异状态减少子程序的参数个数，而且可以避免一些奇异状态r例题：求一条直线和圆的交点例题：求一条直线和圆的交点从从右右至至左左，当当X逼逼近近于于相相等等时时产

27、产生生一一个跳跃现象。个跳跃现象。如如果果两两个个解解按按照照直直线线的的方方向向排排列列，而而规规定定选选择择是是前前进进方方向向的的第第一一个个，或或第第二二个个或或两两者者，则则形形参参个个数数可可减减少少一一个个，且且不不会会出出现现奇异状态，选择也比较直观，便于使用奇异状态，选择也比较直观，便于使用 程程序序中中选选取取X大大的的解解，当当X相相等等时时选选取取Y大的解。大的解。452023/4/16上海交通大学计算机系 何援军464.6.3 简化计算简化计算r例例一一：已已知知半半径径分分别别为为R1和和R2的的两两定定圆圆和和一一半半径径R，求作一圆同时切于两定圆。求作一圆同时切

28、于两定圆。r分分析析：如如果果不不计计R，R1，R2的的方方向向，那那未未解解决决这这个个问问题题先先要要知知道道所所求求圆圆与与R1和和R2是是外外切切还还是是内内切切。如如果果是是外外切切，则则以以半半径径之之和和；如如果果是是内内切切，则则以以半半径径之之差差，分别作两定圆的两同心圆，其交点即为所求圆的圆心分别作两定圆的两同心圆，其交点即为所求圆的圆心。462023/4/16上海交通大学计算机系 何援军474.6.3 简化计算简化计算r如如果果指指定定了了三三圆圆的的方方向向（由由半半径径符符号号定定），则则不不必必判判断断是是外外切切还还是是内内切切，只只要要分分别别以以（R1+R）和

29、和（R2+R）为为半半径径作作已已知知两两圆圆的的同同心心圆圆，就就可可自自动动求求取取两两圆圆的的外外切切或或内内切切圆圆，而不必关心三圆之间是外切还是内切。而不必关心三圆之间是外切还是内切。472023/4/16上海交通大学计算机系 何援军484.6.3 简化计算简化计算r例二：已知两圆相切，求公切点。例二：已知两圆相切，求公切点。r分析：由于半径带有符号，公切点可直接分析：由于半径带有符号，公切点可直接由内外分点的统一公式由内外分点的统一公式r确定，不必判别两圆是外切还是内切确定，不必判别两圆是外切还是内切482023/4/16上海交通大学计算机系 何援军494.6.4便于进一步的图形处

30、理便于进一步的图形处理r由于几何元素定义了方向，图形的边界就由于几何元素定义了方向，图形的边界就能区分出图形外部和内部的概念，这在图能区分出图形外部和内部的概念，这在图形的几何运算、剖面线绘制和隐藏线的消形的几何运算、剖面线绘制和隐藏线的消除算法等提供了良好的基础；除算法等提供了良好的基础；r为二维图学和三维图学的统一描述和处理为二维图学和三维图学的统一描述和处理也提供了方便。也提供了方便。492023/4/16上海交通大学计算机系 何援军50总结总结1)直线描述：直线描述：以向量以向量L(a,b,c)的形式存放。的形式存放。2)圆弧描述：圆弧描述：指定起点和终点、半径及其方向指定起点和终点、半径及其方向(优弧还是劣弧优弧还是劣弧)3)方向性概念：方向性概念：交点的特征值交点的特征值50