ch二维图形变换及裁剪

第5章二维图形变换及裁剪1第5章二维图形变换及裁剪5.1变换的数学基础5.2二维几何变换5.3二维图形裁剪25.1变换的数学基础5.1.1矢量及其运算5.1.2矩阵及其运算5.1.3齐次坐标35.1.1矢量及其运算矢量的定义矢量：n元组。(由n个实数组成的集合)如：二维矢量(x,y)，三维矢量(x,y,z)(ux，uy)xyoxyz(ux,uy,uz)o45.1.1矢量及其运算矢量矢量的加法55.1.1矢量及其运算矢量的数乘矢量的点积(内积)U•V=|U|×|V|×cosθθUV65.1.1矢量及其运算矢量点积(内积)的性质：θUV75.1.1矢量及其运算矢量点积(内积)的性质：交换律结合律分配律85.1.1矢量及其运算矢量的长度单位矢量：长度为1的矢量(i,j,k,e,…)矢量的夹角:θUV95.1.1矢量及其运算矢量的叉积(向量积) 2个互不平行的矢量，其叉积形成一个与2个矢量都垂直的新的矢量，它的方向符合右手判别法，大小为：|U×V|=|U|*|V|*Sinθ

如果U平行于V，则

U×V=(0,0,0)UU

xVθV105.1.1矢量及其运算矢量叉积的性质：

结合律分配律UU

xVθV115.1.1矢量及其运算矢量叉积的性质：在直角坐标系下： UU

xVθV125.1变换的数学基础5.1.1矢量及其运算5.1.2矩阵及其运算5.1.3齐次坐标135.1.2矩阵及其运算矩阵的定义： 由m×n个数按m行n列排列的一个整体，简称m×n矩阵。 其中，aij称为矩阵A的第i行第j列元素14矩阵运算加法 设A，B为两个具有相同行和列数的矩阵，数乘 kA=[k*aij]|i=1...m,j=1,..n5.1.2矩阵及其运算15乘法设A为m×消n矩阵躲，B为n×存p矩阵单位童矩阵在一绞矩阵呆中，概主对厅角线随各元在素aii=1，其辫余元丸素皆疏为0的矩犯阵称楚为单碗位矩就阵。n阶单哪位矩央阵通尘常记勤作In。Am来×n=穿Am蒸×n·In5.棒1.确2矩阵皮及其鸽运算16逆矩奋阵若矩音阵A存在A·洗A-1=A-1·A弹=I，则称A-1为A的逆动矩阵执。矩阵谦的转舅置把矩短阵A=品(aij)m×拉n的行访和列狂互换漆而得宏到的n×朽m矩阵轧称为A的转伏置矩绝阵，完记作AT。(AT)T=涛A(A迈+B意)T=陵AT+迈BT(aA暑)T=aAT(A买·B货)T=借BT·AT当A为n阶矩逆阵，描且A=窃AT，则A是对刻称矩葱阵。5.纸1.怠2矩阵狱及其旗运算17矩阵扇运算崖的基该本性素质加法类的交心换律璃与结储合律A+红B=恼B+恨A;A+礼(B阳+C搅)=驳(A购+B呈)+性C数乘犬的分煎配律着及结菌合律a(方A+盈B)航=aA康+a臭B;a(动A洞·忙B)萄=殿(aA)甲·B近=A五·旁(aB)(a隙+b惊)A芦=aA+bAa(绞bA)必=炕(ab掉)A5.示1.绒2矩阵悉及其践运算18矩阵贼乘法精的结派合律狗及分垦配律A(槐B冠·C阳)或=赚(A秒·极B)罩C(A愤+B律)瓦·肤C石=醉A尺·忘C+广B谈·粥CC怕·(责A+锁B)失=繁C好·A俩+桑C愈·艇B矩阵笼的乘登法不很满足半交换罗律！5.哨1.奖2矩阵熟及其筝运算195.巾1变换尾的数安学基刚础5.市1.姐1矢量痰及其洞运算5.抽1.陕2矩阵械及其控运算5.削1.脂3齐次余坐标205.稳1.扯3齐次嗽坐标所谓葡齐次得坐标店表示茶法就灯是由n+1维向忧量表搬示一茄个n维向立量。哄如n维向储量(P1,P2,炎…视,Pn)表示技为（hP1,hP2,hPn，h），押其中h是任启一不枯为0的比闭例系士数，疮称为哑坐啦标或没比例掘因子。h可以邻取不削同的醉值，戚所以夸同一歇点的沉齐次锈坐标叨不是朝唯一社的。蚀如普碌通坐沙标系钢下的刚点（2,患3）变层换为之齐次父坐标级可以皱是(1突,1撕.5吴,0冒.5抓)、(4碑,6诵,2悉)、(6泄,9废,3澡)等等倍。普通粥坐标偏与齐跨次坐朴标的羡关系耐为“逢一对凡多”由普游通坐浮标h→齐次毯坐标由齐短次坐奥标÷h→普通鸦坐标当h=狸1时，盏称为规格兰化的表齐次横坐标。在计制算机骄图形滋学中偶，通次常使讲用规桨格化水的齐驻次坐射标。21例：(x扮,y兄)点对许应的否齐次梯坐标歪为:(x冤,y赚)点对采应的脖齐次木坐标蛙为三掠维空否间的乎一条显直线袭：5.编1.敞3齐次刚坐标22齐次教坐标闹的作侧用1.将各挣种变欠换用制阶数校统一暗的矩置阵来魔表示绘。使服变换捆矩阵槐具有杜统一顷的表呀示形扫式，惭便于斩变换抖的合已成(组合猾变换)及软植、硬句件实均现。2.便于风表示n维无掠穷远枣点。例如也：(xh,yh,闲h)，令h等于0时，序表示盯二维速平面搅中的密无穷尝远点欲。5.役1.尘3齐次烦坐标23第5章及二维催图形镰变换都及裁估剪5.宗1变换跨的数鞋学基冤础5.杠2二维掠几何廊变换5.锦3二维拐图形敲裁剪245.财2二维收几何睡变换1.平移央变换2.缩放每变换3.旋转吧变换4.变形抄变换5.反射(对称)变换6.组合虚变换25总结扒以上敞这些率变换什后的质图形庭结果旬，可沫以得滋到这课样的触结论腰：图形雹变化掀了，叠但原胞图形要的构咳成规梁则（隶拓扑歪关系雁）没蛾有改川变；图形鱼发生附的变暖化，猴是其侵顶点雁位置笑（几景何信若息）俩的改匀变决肉定的呜。这种梢通过婆维持尼图形含的拓仿扑关游系不嫁变，钢而仅久改变庄图形租的几杜何位烧置来指实现妖图形姨改变辨的方得法，字我们勾称之睁为图形翁的几厕何变哄换。几种帐常见各的几估何变释换：录旋转陈、错急切、饱缩放…。5.标2二维美几何创变换－概露述26几何闭变换聚：在二宽维图汤形处蓬理过里程中耽，常遥常需喇要对扁平面朴图形监的形叛状、垄尺寸枯、方比向和揪位置象进行区修改禁，来家达到榨改变芳图形旬的目另的。几何卸变换兰：是享一种线性坑变换。对原旋来图花形中胆一点抓的坐暂标通升过变筛换生态成一尼个新拒的点嫌坐标制；对捕原来刘图形酒中的姐一条斜直线腔的变缩慧换是驰通过秤直线之上的谅两点赞作变党换生贷成新粪的端陪点坐委标，杯然后渐连接朽这两伏个新积的端液点，尾便得寺到变的换后羽的直闭线；闪类似填的，带可以撇进行记各种释图形能的几帅何变净换。几何返变换寒的表想示采伤用矩景阵形宰式，窗称为映变换胡矩阵槐；点社的坐峡标表语示采掉用齐瓣次坐德标形注式。故几锻何变慕换操驻作的亲过程犯是将桥变换军矩阵M作用轰于齐逢次坐蠢标点P生成爽新的泼坐标廉点P´陷,即P´赏=M·P。5.糠2二维茄几何市变换－概回述27P(薪x,奶y)1.平移循变换点的她平移指变换柱是指嗓该点可在X轴和Y轴方掉向上群分别坡移动闪一段炕距离魂。设图喜形上瓣点P(旅x,甜y)，在X轴和Y轴方续向分支别移咽动Tx和Ty，结果损生成临新的纷点P´(x´,y´),如图埋所示绳，则每有yxP´涨(x强´,拿y´闷)TxTy其中TX,TY称为遮点在X轴和Y轴上渗的位木移。用齐狮次坐幕标和张矩阵柄形式跟可表竖示为圾：yxxyP(x,y)P(x,y)YtxtyX28令二烛维平忌移变嗽换矩峡阵为负：如果Tx或Ty大于宅零，席则点泊向右府或向怠上移握动；如果Tx或Ty小于陶零，汽则点轮向左即或向脱下移朋动。1.平移傲变换P(x,y)P(x,y)YtxtyX292.缩放盒变换点的乐缩放质是指将该窑点沿X轴和Y轴方汉向按测比例杆缩小歉或放著大。设图塘形上倍的点P(员x,绪y)，在X轴和Y轴方勉向分素别作Sx和Sy的缩寸放，溪结果消生成掉新的爸点坐干标P´著(x团´,续y´渡)，如图嫌所示盘，则丝式：其中Sx，Sy称为讲点在X轴和Y轴上势的缩互放比族例。用齐负次坐最标和贝矩阵武形式院可表拌示为晋：yx以坐感标原册点为野放缩需参照鹿点，弓不仅劣改变流了物生体的持大小叶和形四状，至也改希变了辨它离拔原点民的距断离。P(x,y)P(x,y)30当|Sx|=斜|Sy|时，餐变换充前的刻图形渔与变榆换后腔的图地形相锻似。当|Sx|=胶|Sy|>库1时，宰图形叶将放牧大，任并远付离坐狗标原施点；当|Sx|=监|Sy|<丙1时，陷图形蜻将缩辛小，旗并靠构近坐扫标原生点；当|Sx|≠|Sy|时，跳图形绍将发顶生畸姨变。令二乏维缩冶放变串换矩祸阵为纵：2.缩放妖变换31点的航旋转害变换卫是将鲁点绕坐标壁原点旋转榴一角匆度的疲坐标尘变换至。用齐由次坐俱标和昆矩阵足形式虾可表桥示为二维谅旋转糖矩阵R2()3.旋转宫变换设有锻图形搅上点P(更x,充y)，将其唇绕原液点旋潮转角度(逆时档针旋禽转为束正)，结怪果生貌成的优新的其点坐枪标P´敲(x呜´,逮y´获)。顺时距针时撒的变鸽换矩跟阵？θαyP´(x´,y´)ρP(x,y)x324.变形摔变换变形烫变换晨是用既来产馅生一按个目无标图待形的布失真忍，也风称错怜切变交换。还现考饥虑y-变形岗和x-变形衡两种勾：y-变形帆是将点P(痰x,杨y)变换收到点P´手(x得´,旷y´)，使x´景=x键y´战=x·债sh污y+阅y(s惯hy批≠0扶)其中sh待y为变形稠系数。sh工y>被0，sh烘y<慰0，xy错切虏参数sh恶y=tg，表传示y方向甩的错姓切程欲度。334.变形殃变换x-变形凯变换是指舟将点P(到x,稀y)变换矮到点P´陕(x暂´,宰y´)，应尤有x´盈=x+灿y·息sh育x(s垄hx扣≠0把)y´讽=y其中sh意x为变渗形系贸数，sh尝x的符俩号超决定悉了图逼形向恩右或谢向左交变形烧。shx>0，shx<0，错切朱变换您引起界图形湾角度素关系姐的改蛛变，饺甚至祸导致脱图形拖发生音变形辽。xy错切地参数sh侧x=tg，表岩示X方向土的错袜切程机度。345.对称先变换(反射李变换)当b=带d=沫0,谱a=盘-1细,e傍=1时，(x淡’搞y’摔1防)=焦(-则x世y准1)：与y轴对释称的开反射放变换差。当b=丛d=涂0,盒a=园1,早e=吐-1时，(x吓’系y’拥1嚼)=摘(禽x风-y任1米)：与x轴对编称的滚反射赶变换瓦。当b=侍d=违0,界a=赔e=豆-1时，(x切’办y’誉1得)=稼(-舱x蚕-y屑1药)：与原术点对肝称的惹反射纺变换陈。当b=示d=停1,尤a=巾e=回0时，(x限’回y’胃1剧)=峡(y议x毒1钳)：与y=誓x对称松的反眯射变勇换。当b=类d=椅-1惰,a勤=e兵=0时，(x替’峰y’寒1氏)=倦(-膝y内-x敏1钓)：与y=裂-x对称跪的反角射变斧换。xyxy356.组合掠变换如何候实现剧复杂菊变换任？实际钳上，竟一般行的图收形变瞒换更看多的墙是组壁合变朗换，厚即由控一系劲列基站本的叠几何仁变换伶组合敬而成甩。则组皇合变挎换矩密阵也爷可由限一系乘列基伤本几取何变行换矩蹦阵的伶乘积赵来表惭示。矩阵娇的乘仅法满纱足结甘合律企，但别不满挎足交穗换律阀。下面羡将举挂例说缺明组能合变卸换的汇方法瓜。366.组合巩变换－例1例:对一督线段笔先放萝大2倍(即Sx=Sy=2巩)，再平貌移Tx=1乡丰0，Ty=0。解:设点(x君,y雷)为线期段上箱的任剑意一史点，客点(x闯´,衰y´兼)为点(x月,y耳)放大府后的颤坐标没，则粪：[x昨´,声y´镇,1宿]T=S2(2验,2津)[荡x,芹y,恶1]T设点(x竖´´专,y载´´肆)为点(x仙´,汪y´遇)经平妹移后馒的坐怨标，蜓则：[x约´´炸,y萝´´依,1朗]T=轻T2(1碌0,挽0)题[差x´情,y描´,列1]T，即：[x舍´´圣,y折´´尤,1雕]T=任T2(1洁0,赔0)扶S2(2语,2炭)淹[x疮,y饺,1讲]Tyx(x,y)yx(x´,y´)yx(x´´,y´´)Tx376.组合度变换－例1（续蜡）令：M即为菌组合术变换旨矩阵树。旁设线撒段的沟两端兄点坐蕉标为(x1,y1)和(x2,y2)，经M变换构后，系得到袭新的吨坐标(x1´,方y1´)和(x2´,己y2´)，连接犹这两借个新缺的坐誉标点技便生堂成了著变换播后的例线段舟。yx(x,y)yx(x´,y´)yx(x´´,y´´)Tx386.组合江变换－例2例：掩对一琴图形云，绕恶平面口上的货一点(Cx,Cy)作旋饿转变额换，纽奉旋转捏角度为θ，计算螺其变刃换矩保阵。解：迷旋转蛛变换螺是绕某坐标搂原点软旋转葡的，颈此处衔不能匀直接艳使用度旋转连变换雄矩阵缺，应互先将胆点(Cx,Cy)平移晚至原思点，渣然后以作旋陵转变扩换，歇最后片再把年该点贩移回壶原处肿。设话点(x味,y参)为图态形中恳的点薪，点(x妥´,挪y´货)为点(x线,y飞)经变锁换后叮的坐叠标，写则:[x香´,徐y´风,1穿]T=抹T2(Cx,Cy)爷R2(θ陷)T2(-渗Cx,-炭Cy)裙[x暮,y倾,1比]T组合郑变换秩矩阵就为：(Cx,Cy)yx396.组合袄变换－例3图形涉关于劲任意阻的反餐射轴y=a+bx的反喝射(对称)变换网。406.组合抱变换－例3（续塔）解：1.将坐冈标原索点平够移到(0玻,a)处2.将反掌射轴血（已田平移京后的示直线蝇）按版顺时矛针方烛向旋权转θ角，已使之订与x轴重垃合3.图形贞关于x轴的荐反射番变换4.将反零射轴浙逆时标针旋糠转θ角5.恢复肿反射鼻轴的富原始边位置组合防变换精矩阵康为：416.组合卷变换－例4通用腾固定取点缩玩放平移睁物体延使固符定点台与坐障标原岂点重蚕合；对于竭坐标真原点窜缩放亏；用步坡骤1的反裁向平州移将记物体溪移回绿原始朝位置派。426.组合悄变换－例5通用饺定向扇缩放比例验变换全中的朱比例额因子Sx，Sy只能裙在x轴方值向或y轴方劣向起染作用机。实厉际图货形变斑换中苗，不撑仅是置在x，y方向亦变换互，往侵往要眨求在错任意挎方向姻进行霉比例军变换肢。通哲过旋毙转变金换和指比例砖变换态的组天合，迁可以忠实现炼任意默方向拢的比镜例变弄换。绕=4什50方向纹缩放YXs1s2436.组合书变换－小锄结矩阵葱运算满足近结合苹律，捧但不术满足育交换阻律。居所以中，一咱般情期况下饭，不编同顺鸡序的模变换古将得鞠到不佳同的指结果乏。先平移再旋转P2(x,y)P(x,y)YθP1(x,y)X刚体趴变换崖。直线榴段或辰多边协形的票变换可通藏过每洽个顶疑点的怕变换咱，再败在新辜位置垫重画璃图形冒得到客。曲线冶的变跑换：变换寺矩阵削乘以还曲线旁的参开数方技程。先旋转再平移P1(x,y)P(x,y)YP2(x,y)Xθ445.嘱2.帜1二维傍几何轨变换－小勾结放缩、旋转、错切、对称平移整体音比例变换用规僵范化治齐次栗坐标零表示牲的二绸维基予本几谦何变看换矩街阵是时一个3×圣3的方露阵：455.锯2.绘1二维巨几何餐变换－小烘结上面橡讨论锈的五耕种基贫本变花换(平移写、比欣例、筒旋转衰、反侍射(对称)和错创切)给出助的都森是点变非换的公吃式，泉对于胶复杂围对象(如线恨框模乓型)，图轨形的蚁变换朝实际怨上都取可以骂通过住点变愧换来育完成渗。例如耕直线扭段的坟变换膨可以鸡通过捆对两惭个顶辅点坐片标进膜行变胶换，杏连接聋新顶敢点得透到变刻换后芦的新者直线尊；多边美形的浑变换读可以特通过留对每省个顶矛点进珍行变举换，挪连接夺新顶桥点得遇到变笛换后弦的新戴多边制形来娇实现荒。曲线艇的变朵换可缝通过忽变换睁控制析多边坝形的哭控制唤点并某重新猫画线慌来完帖成。465.顶2.芽1二维饶几何路变换－小溜结符合暗下面软形式险的坐浮标变牢换称敌为二占维仿射逼变换（Af蛾fi爱ne不T债ra似ns幸fo植rm足at钓io亡n）。变换并后的醒坐标x’和y’都是永变换浅前的菜坐标x和y的线医性函尺数。贺参数aij是由案变换券类型胡确定猪的常眉数。仿射茧变换欲具有西平行将线变伯换成勾平行享线，抖有限间点映虎射到觉有限津点的而一般珠特性残。平捉移、浪比例半、旋俭转、旗反射(对称)和错厅切五鹿种变窜换都煎是二览维仿茂射变阀换的崖特例氏。任何受一组碎二维渴仿射左变换纤总可溜表示愿为这酒五种肃变换岁的组万合。佣因此笛，平把移、良比例凑、旋盗转、立反射(对称)的仿越射变夫换保蚂持变颂换前眯后两胶直线督间的上角度祝、平壁行关返系和势长度兄之比巷不改疫变。47第5章们二维本图形牙变换恩及裁壮剪5.右1变换原的数健学基结础5.驶2二维盈几何妙变换5.星3二维漆图形称裁剪485.问3二维柴图形头裁剪5.渠3.随1图形壳学中汇常用电的坐蚕标系5.煤3.扩2直线承段的虽裁剪5.狮3.层3多边床形的捉裁剪5.梅3.间4字符趁的裁材剪49裁剪坏：确定瓶图形匹中哪间些部恼分落睛在裁赔剪窗纯口之晚内，陶哪些企落在仓裁剪朱窗口拥之外,以便万只显亦示落若在裁含剪窗吉口内/外的找那部待分图欺形。革这个惊选择没过程泡称为裁剪。图形碍裁剪努算法鬼，直券接影罪响图哀形系曾统的窃效率欣。5.迹1二维正图形达的裁池剪裁剪窗口50Di百sp孙la归y责Wi拢nd敏owWi张nd淹ow裹3Wi到nd屡ow克2Wi折nd悉ow病1外裁飘剪在圾多窗晶口场捐合较棋常用插。例遗如：Di惧sp准la级y仗Wi朋nd盏ow：内定裁剪袜，针牢对Wi带nd歪ow哈1－3外裁放剪；Wi吉nd鞭ow虑2：内储裁剪土，针各对Wi须nd勾ow由1、3外裁补剪；Wi驰nd要ow钟1、3：各缩慧自内栏裁剪技。内裁降剪、境外裁某剪51第5章欠二维留光栅筝图形锁的处五理5.赵1二维爬图形鹊的裁砍剪5.韵1.舟1直线器段的源裁剪5.宗1.涝2多边说形的衬裁剪5.侦1.窑3字符锅的裁骄剪5.削2走样奏与反滔走样525.霞1.舟1直线驰段的员裁剪1.直接攻求交所算法2.租C惧oh待en丝式-Su胁th召er捉La究nd算法(编码碧法)3.中点滩分割弦算法4.Ni姑ch灿ol递l-冈Le矮e-工Ni摔ch周ol烘l算法5.愿C蚕yr晚us塑-B漆ec雷k算法(参数侦法)6.絮L杀ia索ng－Ba翅rs于ke舟y算法7.凹多迎边形其窗口蜜的裁婚剪535.搁1.肥1直线耕段的麦裁剪任何远图形踏都可丽能包嘴含点远、直诸线、惑曲线钉、字李符和玻多边效形等仇图元进，洪但它迈们都骗可以寇分解欣成点核的集膨合。能否银将直甚线段大裁剪尽问题懂简化脑为点筛的裁同剪问携题？假设刊窗口仇的左诊下角之坐标么为(xL,yB),右上命角坐末标为(xR,yT)，对域于给施定点P(吵x,壤y)更,则P点在蛮窗口叮内的点条件盟是要鲜满足墓下列辣不等证式：xL<=肤x细<辜=xRan赴dyB<=裂y治<煤=yT否则，P点就职在窗抓口外族。(xL,yB)(xR,yT)PPP问题容：对宇于任俯意多歌边形吉窗口子，如逗何判森别？点与兰多边槽形的抹内外搜关系做判别启。545.卵1.童1直线叶段的夫裁剪直线酬段裁氧剪是母复杂看图形喷裁剪呼的基独础。直线擦段常鲁见；可构富成多炼边形含；复杂倘的曲费线可刚以通楚过直荣线段士来逼有近。曲线愿裁剪机可否蚀化为吴直线在段的险裁剪娱？555.挣1.衰1直线福段的井裁剪直线涌段与脆窗口筛的关获系通鹊常有进以下沾三种姥情况匠：整个估线段崇全在确窗口馆内；整个翠线段竭全在招窗口狱外；线段帆部分富在窗态口外话，部貌分在规窗口老内。当窗派口为凸多猫边形时，茫任何尸一条候直线约段紧只会至多有一鹅段在燃窗口猜内：当一被条直疑线段酸的两怖个端滚点全往在窗秒口内别时，皇该直边线段呀整个缩慧在窗汽口内声；当一住条直雾线段呼的两押个端猪点，克一个左在窗奖口内识，一蛾个在算窗口声外时治，该侦直线啄段部董分在浓窗口蚁内，受部分顺在窗界口外户；当一加条直舅线段麦的两言个端盈点全愿在窗今口外俯时，咳该直咏线段蜡可能晃整个客在窗记口外赶，也戏可能赏部分腥在窗步口内竟，部披分在而窗口屋外。565.饼1.哥1直线楚段的仍裁剪直线恨段裁瞎剪：晴实质专上就债是快密速判迷断出管线段激与裁次剪窗粱口的合关系方；(1意)线段罪完全楚可见繁；(2贺)显然铃不可当见；(3简)其它帝。然后蛾对于巴可见总部分利，求谦出端辞点，德绘制铺线段库。为提按高效孔率：快速威判断时情形(1愈)、(2庭)；对于愈情形(3马)，应蛮设法忽快速胳求出藏线段蜜和裁重剪窗吼口的变交点束。571.直接顺求交乘算法如何胞判断篮线段热是否漆显然锤不可桶见？直线毁与窗旱口边妇如何切求交柴？Y求交点I0、I1，

I0I1既为可见部分ExitYP1在窗口内？NP=P0P0=P1P1=PExitN求交点I，P0I既为可见部分NP0P1显然不可见？YP0P1不可见ExitNP0P1与窗口有交？NYP0在窗口内？P1在窗口内？YP0P1完全可见Exit581.直接予求交倍算法直线培段与敲窗口赵边如冤何求树交？沈－两呼线段灵求交参数陕式、渠非参小数式设直软线过P1(x1,y1)，P2(x2,y2)，m为斜除率，诊则：直线枕与窗喘口各恢边的晕交点颜为：L，xL，y=晋m(鸽xL-x1)+轧y1，m≠兵∞R，xR，y=傍m(葡xR-x1)+狡y1，m≠棚∞用斜踩率解寸释Y,yT，x=邮x1+(麻1/眉m)未(yT-y1)，m≠绵0B，yB，x=宣x1+(俭1/速m)延(yB-y1)，m≠扶0总会除求出语一个驳交点等，即驰使交动点位椒于窗地口外游。591.直接宏求交兼算法解方想程组→求出飞交点赢参数tl、te∈[机0,米1]îíì-+=-+=)()(:),(),(010010111000lltl∈[0,1]yytyyxxtxxyxPyxP的参数方程为îíì=-+=)(minminmaxmineyyxxtxx矩形窗口下边界的参数方程为:te∈[0,1]îíì=-+-+=-+)()()(),(),(min010minmaxmin010111000lelyyytyxxtxxxtxyxPyxP和矩形窗口下边的交点满足方程组tl∈[0,1]te

∈[0,1]602.铺C浅oh当en挎-Su扩th雨er只La咐nd算法这是躲一个内最早任最流与行的奸线段展裁剪涝算法拜。自19弯68年以盏来被昼公认嫩为是伏一个治好的渐算法荒也称仓编码如算法圈。该算取法通靠过初始将测试来减洁少要盘计算迟的交味点数恼目从山而加衣快线友段裁哑剪算汇法的膜速度。基本堤思想王：对于愚每条霸线段P1P2分为令三种亡情况蛇处理:（1）若P1P2完全应在窗驱口内奥，则袄显示恋该线陵段P1P2。（2）若P1P2明显像在窗债口外宝，则丸丢弃乔该线飞段。（3）若线袭段不船满足（1）或音（2）的条粱件，熄则在怀交点冤处把并线段闪分为仇两段努。其泡中一兆段完绳全在遣窗口岂外，品可弃嘉之。螺然后仆对另西一段票重复烤上述解处理农。递归穗的裁绘剪过崭程612.播C博oh昏en越-Su都th混er抵La架nd算法为快近速判所断，尸采用栽如下梨编码汤方法执：由窗茧口四宏条边杏所在垮直线隐把二淡维平效面分肌成9个区粥域，竞每个稳区域跃赋予病一个桨四位肆编码厌：CtCbCrCl（上跨下右多左）肢；直线做的端茶点都谨按其阔所处蹄区域素赋予循相应妻的区碑域码俘，用私来标垃识出朱端点梁相对溜于裁盯剪窗挥口边带界的雅位置惨。各位男编码痕含义片，端昼点坐醋标(x,枯y)：上：if地y六>yT,拒Ct=1邪,铺el赖se帖,箩0;下：if只y颈<yB,Cb=1应,会el穗se桨,颂0；右：if右x移>xR,虾Cr=1孔,怠el拾se直,蹄0;左：if锣x伏<xL,Cl=1带,傲el桐se瓣,军0;100100010101100000000100101000100110622.名C虑oh开en亦-Su杀th年er沈La廉nd算法任何鞭位赋萄值为1，代碗表端洗点落理在相付应的疫位置捎上，套否则柄该位读为0。例如帮：端根点B：区济域码残为00丈00；端点A：区诊域码它为10齿01；100100010101100000000100101000100110ABCD632.锦C捆oh钩en验-Su连th剖er电La租nd算法漆原理编码妇将窗壶口及愚其邻巡寿域分辰为5个区观域：⑴内域俯：区剥域(0银00汗0)。⑵上菠域：体区域(100督1,100省0,101背0)。⑶下是域：治区域(0101透,临0100计,榨0110胀)。⑷右孩域：睛区域(1艰010,苍0欠010,刮0构110)。⑸左轧域：误区域(1雕001,台00撤01,拴01艺01)。对线蚁段的辜两个骨端点顾的区型号进端行“位与”运飘算，盒可知咽这两歌个端烧点是谦否同等在窗绳口的捷同一漠侧(上、吵下、绒左、罢右)；如果韵两端叶点的编码酒均为00险00，表睛示直密线在浴窗口锻内。如果浸两端寒点的编码鞠相与不为00政00，表隔示直闯线在格窗口捞外。如果更两端煎点的勺编码阔不全厉为00至00，但创相与渠为00逆00，则期该直仍线可能部分钻可见剑，需筑计算认直线脚段与彻窗口退的交蜻点，蛾确定驱哪一常部分藏可见恼。100100010101100000000100101000100110642.粉C酷oh剥en锤-Su胁th棋er搭La仔nd算法材原理若co帅de梯1=变0，且co发de夕2=握0，则P1P2完全执在窗糠口内骂，“带取”递；若co稳de朴1&滨co谦de域2≠冰0，则P1P2明显捆在窗罩口外悬，“伤弃”惕；否则见，在还交点秆处把圣线段介分为妨两段象。其吼中一宝段完漫全在货窗口拿外，替可弃主之。枣然后膀对另饭一段洗重复喘上述占处理僵。100110001010000100000010010101000110P1P2P3P4652.匪C状oh则en槐-Su撞th为er感La睡nd算法阁原理如何童判定屋应该摧与窗微口的才哪条堆边求幕交呢替？编码领中对余应位浮为1的边窜。100100010101100000000100101000100110按左坡右上畅下的炊顺序傍求窗驶口与案直线鼓段的言端点662.柜C樱oh迹en把-Su需th希er酿La牙nd算法铺原理按照茂左、爽右、匠下、胜上的早顺序洒计算宪线段P1嘱(x傲1,情y1但)P机2(杆x2痒,y堤2)与窗茶口边搜界的涂交点姨：if鄙(L腾EF天T&流co回de!=乐0)用等林比例犯关系晒解释{夺x=格XL尊;耕y=气y1喘+(躁y2廊-y贴1)鹿*(婆XL耍-x贴1)旧/(勾x2绒-x赚1)认;}el劣seif谷(R吗IG茫HT附&c魄od动e!=筒0){浙x=侍XR浅;谦y=谎y1箭+(免y2洁-y奴1)吨*(驱XR乳-x皇1)逢/(采x2更-x来1)秤;}el陷seif嫂(B汇OT瓦TO孕M&膨co营de!=呈0){孤y=贴YB浊;丸x=牲x1美+(穷x2圈-x造1)伙*(伪YB毅-y尘1)蛮/(尚y2迫-y宇1)欠;}el罢seif熟(T蒙OP&怜co输de继!期=0识){融y=衔YT佣;影x=叉x1跃+(滤x2胳-x独1)徒*(则YT绍-y蜻1)扬/(抬y2威-y戴1)盏;}672.团C淡oh马en感-Su打th樱er款La驱nd算法捆描述Co泛he顺n-刷Su兵th鼻er特la固nd算法伐的关叙键在语于总暂是先诸确定载窗口两外的登一个责端点病，这停样位尤于此肾端点首至与块窗口开边的捐交点峡之间斥的线柿段必屑为不杆可见妻，故盗可将泊其抛艰弃。浓然后悲利用控此法越处理节剩余折的部膨分。BO撇OLdo挨ne川,d吐ra坚w;/*此do忧ne暮:完成奔；dr炕aw苦:可见级；*/Un股si成gn啦ed沟c彼ha顿r派co露de传1,赚co懒de肢2；/*端点1，端滤点2的编今码*/Wh返il音e摸(!轰do惹ne卸){if碎(判断co贱de歉1,舌co鼻de置2,若为垫第一弦种情鞭况){兔do利ne攀=福T宰RU遥E;填d晕ra奋w婚=尽TR屿UE灵;想}el叹se熊i役f饿(为第勾二种叙情况){以do耽ne贵=煌T匹RU响E;矛d学ra渠w罢=流FA狸LS倒E;京}el先se胃i愧f定(检查co虹de畜1,若在间窗口咳内){交换阵端点即及端箱点的傻编码疤；以菜左，烛右，列下，亏上的至次序炊对端狱点1进行汁判断锁及求顶交；虑将交情点的兄值赋眼给端秘点1丹}}/*维En疮d倒of锈w框hi谎le尤*/682.例C做oh弊en童-Su壁th栽er毯La迁nd算法茶小结最坏拜情形范，线堡段求这交四随次。阻（左及、右扛、下拔、上境）P1（01袋01）P2（10肤10）P1’(0100)P2’（1000）P2’’（0000）P1’’(0000)692.胜C捷oh席en虾-Su骂th席er文La写nd算法牺小结本算女法的畏优点你在于魄简单赢，易咱于实姓现。用编拾码方丽法来市快速理判断浩线段尽和裁出剪窗穷口的百关系粥。他也盛可以铁简单贪的描畏述为你将直堡线段萍在窗傻口外蜓的部搅分删千去(按左货、右内、下织、上连的顺局序依秧次进况行)，剩信余部隙分就沃是可握见部遮分。在这员个算菜法中锐求交丛点是纲很重域要的呆，他钟决定纹了算练法的速度。尤其令适用黄于大冈窗口但场合拜及小喷窗口迎场合惧。大部唱分线恋段完作全可郊见或辫完全佣不可氏见。本算完法对默于其赛他形睁状的虏窗口润是否茧同样苗有效晃就值用得讨哗论了葡。这伙也说尸明了具在图久形算芬法中肾，没拉有几计个是峰对大竖多数溜情况赚有效感的。703.中点闷分割乒算法基本占思想达：从P0点出福发找屿出离P0最近走的可歉见点恢，从P1点出蛛发找水出离P1最近默的可速见点右。这盏两个辩可见挂点的懂连线抓就是志原线海段的肤可见神部分紧。可看逝作Co腐he民n-联Su战th抢er披la切nd算法池一个轧硬件拔实现葬的特失例。P0P1AB713.中点日分割仙算法与Co唯he粥n-锄Su政th蛛er乐la爬nd算法谣一样罢，首认先对敞线段衬端点碑进行踩编码吧，并赚把线略段与陷窗口肃的关幸系分为为三振种情汪况：(1谣)线段陈完全门可见昼；(2士)显然脏不可坏见；(3美)其它对前奶两种挥情况诸，进何行一啦样的处颂理；对于掠第三拨种情添况，用中点毫分割的方介法求限出线段与跃窗口杯的交浙点。仓（A、B分别蓄为距P0、P1最近末的可雪见点洞，Pm为P0P1中点）P0P1PmAB723.中点国分割史算法ExitYP0可见？P=P0P0P1显然不可见？YNP0P1不可见ND(Pm,P1)<ε？ExitPm=(P0+P1)/2YP=Pm求距渠离P0最近肝可见臭点PNP0Pm显然不可见？P0=PmY可见点一定落在PmP1上P1=PmN可见点一定落在P0Pm上P0P1PmAB733.中点港分割爽算法中点神分割芬法：船从P0出发纳找距催离P0最近黑可见拾点：先求嫂出P0P1的中骗点Pm注,若P0Pm不是肌显然闲不可疫见的就，并记且P0Pm在窗外口中购有可践见部嘴分，缎则距P0最近匆的可沟见点删一定逼落在P0Pm上，工所以窑用P0Pm代替P0P1；否则不取PmP1代替P0P1。再对急新的P0P1求中迹点Pm。重虚复上丢述过戴程，见直到PmP1长度结小于臂给定企的控羞制常昌数为痰止，箩此时Pm收敛访于交钳点。从P1出发描找距乖离P1最近班可见恳点的川方法我类似幼。743.中点畅分割福算法－小锦结与Co溜he脊n-Su方th界er堤la溜ng算法运在思岔想上红没有抗任何叠区别寄。采用均编码售的方范法快乐速判解断直罚线段毅与裁听剪窗情口的毕关系剪。区别当在于辫两者籍求与臂裁剪诵窗口督交点场的方弓法不岔同。中点钥分割毕算法貌：二低分查填找Co途he革n-Su扑th样er禁la跨ng算法黄：直杨接计柔算更利免于硬肚件实苏现，炭可看远作C-谎S算法欢的一舟个特深例。75从P0出发努找最翻近可稻见点玩的方盗法:先求阅出P0P1的中诞点Pm若P0Pm不是贫显然款不可崖见的他，并孕且P0Pm在窗布口有可见而部分朗，则怕距P0最近扮的可躬见点黑一定主落在P0Pm上，鸽所以泽用P0Pm代替P0P1；否则掘取PmP1代替P0P1再对蹦新的P0P1求中滚点Pm。重匪复上棍述过图程，臣直到蚁长度役小于给倘定的场控制印常数形为止拼，此疏时Pm收敛挥于交苗点。从p1出发细找最抢近可低见点层采用欲上面做类似弃方法形。中点秒分割洪法ε可取减为1个象挤素765.沫C惜yr守us怎-B末ec帐k算法前述矮算法尸均假魄设裁书剪窗阿口为兆一规教则的近矩形倦窗口检。若裁责剪窗妈口为茅非规寄则矩蛙形的物任意锦凸多由边形吼时，仅以上堡算法疑不再姓完全液适用帽。775.责C腹yr验us至-B揪ec丘k算法考虑练直线忙段的厌参数叠方程傻：XLXRYBYTP1P2ABCD直线上任一点的参数t为：则直线与规则矩形窗口边的交点参数：若，舍弃。785.遗C小yr丧us冬-B圆ec泄k算法裁剪志线段P1P2：tL=1影/6；tR=5的/6tB=-穷1/递5；tT=7你/5部分t∈任[0困,1精]。xy-111-10P3(-5/2,-1)P4(3/2,2)P1(-3/2,-3/4)P2(3/2,1/2)裁剪府线段P3P4：tL=3聋/8；tR=7怕/8tB=0；tT=2棚/3所有福的t∈君[0笔,1扶]。部分果可见凶线段缎：可否愁简单柏利用说交点附的t值进届行判技断？79xy-111-125.揭C贫yr申us纱-B赛ec永k算法裁剪鹿线段P1P2：tL=-竹1/决2；tR=3翼/2tB=3翻/2；tT=-号1/赢2不是尘所有踢的t∈[0捧,1阔]。0P3(3/2,-1/2)P4(2,1/2)裁剪仔线段P3P4：tL=-蛮5；tR=-溪4tB=-扇1/念2；tT=3财/2不是思所有男的t屠∈[珍0,天1]。完全方可见司及完披全不告可见蜻线段娇：P1(-1/2,1/2)P2(1/2,-1/2)可见逆，不锦能简叶单的讯利用座交点衡的t值来随进行滚裁剪薄。必室须找危到一烘个可谱靠的唯方法隙，用恐来判呆定线宿段上送的一芹点是困位于团窗口沃之内壶、之稿外或向边界含上。805.嫌C两yr刺us卡-B狭ec孔k算法系－原粒理下限虽：●上限鉴：●D=双P2–P1P1P2P1P2815.民C戏yr贼us惩-B耗ec搬k算法Cy域ru亭s-筐Be除ck算法盘的基火本思菜想是恶采用看法矢酿量的立概念纵来判星定线运段上骗的一百点是喉在窗概口之涨内，压之外咸，还被是在违窗口直的边严界上争。对任蜡意凸颈多边既形，寇其边糊界上伟任一挡点a处的镰内法骑矢量ni满足饶：ni•(b–a浇)≥泼0其中挡：b为多零边形丹边界到上另咬外一裕点。ni为过a点边掩界的标内法参矢量寇；no为外参法矢盈量。θn0nib’V1•V2=|率V1|×|V2|×co月sθθV1V2bb”a82f如果f是凸昨区域亚边界沙上的健一点队，n是凸禽区域盯边界间在f点的胜内法坡向量御，则河对于享线段P1P2上的让一点P(俯t)，满足闹下式踪蝶：若n•[P杠(t)–当f]＜0，则表亡示P(昏t)马–f指向氧区域猪的外圆部(相对米当前于边)；若n•[P酿(t)–训f]宴=0，则表绸示P(熟t)干–f与包既含f的边值界重盏合且葬与内旺法矢恭量n垂直叮；若n•[P酷(t)–栽f]＞0，则表罗示P(次t)蜂–f指向廊区域鸣的内邪部(相对价当前适边)。由此赵可知，P(高t)满足n•[P签(t)–饱f]解=0的t值的误点即拨为直伤线与扒边界垦的交嫂点。n•[P写(t)–停f]＜0n•[P(t)–f]=0n•[P(t)–f]＞05.椒C座yr订us阅-B狠ec甚k算法膜－原松理n83Cy钥ru鞠s-兼Be玻ck算法袋中对掘于线桃段的庙可见洪性是镜这样旨判断变的：设：物内法拉矢量ni与连伪接线银段上泼一点P(顽t)至边垦界上梨一点fi的矢闭量的降点积鸟为：ni•[P(匆t)联-fi]，(i刘=1舱,2阴,3怕..斥.)与式箱子P(访t)内=P1+(渡P2–P1)t，(0宾≤t边≤1芒)合并得障：ni•答[P1+(干P2–P1)t衫-fi]，(i焦=1温,2薪,3嘱..阔..够.)则线造段上旨一点沾在边济界上谎的条技件为华：ni•[胡P1+(显P2–P1)t育-fi]=欲0重(i脚=1倍,2惯,3册..丙)n•[P予(t)–酱f]＜0n•[P偶(t)–她f]打=0n•[P暗(t)–星f]＞0fi5.尖C标yr馅us雄-B总ec丛k算法赵－原悠理n84线段浪上点晌在边石界上容的条泥件为准：ni•[纸P1+(桐P2–P1)t冒-fi]=顽0海(i肿=1钟,2烈,3熟..蹦)令：D=勤P2–P1；wi=P1–fi，可每得交虫点：如果D球•ni=0，则要么D垂直于ni，要么P2=P1，线拿段退顾化为抓一点她：如果wi•ni＜0，表衡示点汤位于妨区域礼和窗坡口之嗓外；如果wi•ni＝0，表泄示点服位于卫区域喇和窗丈口边童界上谣；如果wi•ni＞0，表御示点驻位于切区域密和窗公口之惩内。5.傍C吗yr拳us榨-B泡ec逐k算法和－原袍理n•[P钩(t)–辅f]＜0n•[P柿(t)–带f]暗=0n•[P亲(t)–透f]＞0fi式5.1.1－1n85否则馋，可索根据瘦“式5.闸1.新1－1”求出丸线段肚和裁就剪窗芬口的绩交点芳。对加于交途点的t值选影择：首先调，要皱符合0≤减t≤尼1；其次静，对坝于凸桥窗口色来说胜，每孤一个傻线段泽与其狭至多对有两誉个交谷点（喘既有斥两个例相应的t值）状。所引以我送们可诞以把窗计算胀出的t值分桐成两赵组：磁一组波为下身限组园，是冠分布虫在线等段起涨点一蝇侧的肥；一祖组为乐上限安组，罗是分莲布在仁线段腿终点智一侧舅的。这样介，只塞要找竖出下妙限组斩中的展最大扁值及衫上限丑组中壤的最幸小值俭，就竖可确刮定可胞见线竖段部歪分了倦。有了冠这些爽，整携个算部法就尖可以顷建立疾了。分组扬的依耀据？5.勒C真yr旱us凤-B叔ec灶k算法冰－原押理865.厕C莲yr槐us亿-B验ec盾k算法竭－原吉理下限意：●上限责：●D=笨P2–P1P1P2下限巧组以D闪•ni＞0为特教征，厅表示巡寿在该糕处沿P1P2方向任前进锅将接斤近或进入挖多边重形内雪侧。上限恰组以D烂•ni<0为特州征，涨表示接在该执处沿P1P2方向话前进裤将越和来越康远地吐离开炼多边捷形区水域。P1P287置下祝限最蛮小值tL=0；上锹限最总大值tU=1wh欧il影e对于坚每一牲个窗垄口边i自do搭b皱eg性inifD•ni=0朴t紫he忆nIfwi•ni<0固t促he框ngo适to12el另se画从P(银tL)至P(桥tU)的线帮段el锁se抛D•ni≠0计算t值if筹D旋·ni>0劲t仓he雕n姻/*寻找污下限啄组的tL值*/If材t班≥岗0登th焦entL=ma封x(逗t,身tL)el偿se值/啄*寻找色上限械组的tU值*/if冷t贪≤基1眼th万entU=mi延n(启t,舍tU)网e炉ndiftL≤tUth念en画从P(以tL)至P(鞋tU)的线低段en傻d清of仪a戏lg玻or辅it豆hm5.想C酸yr们us康-B感ec绵k算法剑－算园法描杠述88该算浇法比Co链he疲n-捎Su沃th自er欣la元nd等算晨法适午用的德范围婚更广济一些债，它停可以傅对任积何凸寄多边颗形适旧用，填但对治于凹甩多边爱形就亦失效脚了。么为了胳解决茶这个狱问题狸，又乓引入路对凹勤多边涝形进巧行判名断和渣分割帅的算稿法：齐叉积这法，怨旋转壮法。当凸猴多边雀形是骆矩形武窗口狡且矩苹形的趋边与铅坐标拐轴平揭行时日，该嚼算法呼退化睁为Li挑an迈g-醉Ba田rs牵ky算法炒。5.衰C币yr误us痛-B严ec及k算法妻－小识结89XLXRYBYT6.Li起an贞g-妙Ba安rs即ky算法写入笔图形快学教它科书鞋的中警国人伏的算极法。设要摇裁剪召的线混段是P1P2。P1P2和窗寄口边枯界交羽于A,榜B,灵C,忍D四点钥，见著图。算法紫的基浅本思铺想是景从A,毯B和P1三点掌中找余出最眯靠近P2的点腾，图端中要剩找的何点是P1。从C,幻玉D和P2中找贱出最纠靠近P1的点桥。图焰中要叹找的由点是C点。仔那么P1C就是P1P2线段费上的逢可见红部分耽。P1P2ABCD本质施上，赔可看民作是村一种艰特殊荣形式强的Cy里ru管s-分Be败ck算法严。906.Li母an絮g-再Ba冰rs练ky算法线段歪的参贪数表缎示：x=醉x1+t△决xy=岸y1+t△探y0≤垦t怀≤1罪,搜△x庸=美x2-x1,露△y为=y2-y1窗口紧边界她的四饶条边神分为山两类局：始边和终边。91求出P1P2与两条闲始边的交肃点参碎数t1、t2，令tL=m朋ax叠(t1,t2,0偏)，则tL即为三者望中离p2最近哑的点敌的参饺数；求出p1p2与两条摊终边的交荡点参稍数t3、t4，令tU=m僵in摔(t3,t4,1播)，则tU即为三或者中鹅离p1最近毅的点扛的参讨数；若tU≥tL,则可愈见线恩段区暗间为[tL,tU]；否选则，p1p2完全脂不可鹿见，稼如：p1’p2’，tL=t2’,tU=t3’,tU≤tL6.Li宴an欧g-村Ba运rs震ky算法t1t2t3t4P1P2t1’t4’P1’P2’t3’t2’926.Li尤an专g-餐Ba糊rs声ky算法裁剪汤区域碰的内好部可淋表示熊为：xL≤x沫≤xR，yB≤y引≤yT直线匠段的床参数阴表示科为：x=刻x1+t恒