Day计算几何与三维凸包学习教案

《Day计算几何与三维凸包学习教案》由会员分享，可在线阅读，更多相关《Day计算几何与三维凸包学习教案（104页珍藏版）》请在装配图网上搜索。

1、会计学1Day计算计算(j sun)几何与三维凸包几何与三维凸包第一页，共104页。第1页/共104页第二页，共104页。an|ab| = |a|*|b|*sinn表示以a,b为边的平行四边形的有向面积。n右手定则：用面积判定方向n可以(ky)用于计算多边形面积第2页/共104页第三页，共104页。n对于点集P，包含P的最小凸多边形n给定点集P=(Xi,Yi)，求点集P的凸包。第3页/共104页第四页，共104页。nnO(n)删除和判断nO(n2)n在线算法第4页/共104页第五页，共104页。n第5页/共104页第六页，共104页。n选取一个一定在凸包上的点X，沿着点集逆时针走一圈，当走回X

2、时，得到整个凸包n(1)X怎么选？n(2)如何找最右手边的射线第6页/共104页第七页，共104页。O(n*h)H是凸包上的节点数Output-Sensitive第7页/共104页第八页，共104页。n第8页/共104页第九页，共104页。nO(n)n排序O(nlogn)n总复杂度O(nlogn)n常用技巧：维护水平序节点第9页/共104页第十页，共104页。n合并凸包的关键：找到切线n上下切线可以分别考虑(kol)第10页/共104页第十一页，共104页。n维护U上可见点的最远点，直到一个点都看不见第11页/共104页第十二页，共104页。nA-B这条边被称为凸包的弦(chord)nQuic

3、kHull(a,b)应当返回S的凸包。第12页/共104页第十三页，共104页。n(3)CB右侧点n对(2)(3)分治n(1)的点全部抛弃n(2)和(3)会有交集么？(1(1) )(2)(3)ABC第13页/共104页第十四页，共104页。n初始调用n指定点集的最左/最右点x,yn调用QuickHull(x,y)和QuickHull(y,x)n去递归第14页/共104页第十五页，共104页。O(nlogn)nNot Output-Sensitive第15页/共104页第十六页，共104页。O(nlogm)nStep 2：合并：合并N/M个凸包。个凸包。第16页/共104页第十七页，共104页。

4、第17页/共104页第十八页，共104页。n凸包上有M个点：O(m*n/m*logm)=O(nlogm)nChans Algorithm求凸包的复杂度是O(nlogm)nM是啥?第18页/共104页第十九页，共104页。=O(nhlogh)n只要M=H，算法就能正确出解第19页/共104页第二十页，共104页。nM=2,4,16,256,2(2t).nO(nlog2)+O(nlog4)+O(nlogh)n=O(n)*(1+2+4+.+logh)n=O(n)*O(logh)=O(nlogh)第20页/共104页第二十一页，共104页。第21页/共104页第二十二页，共104页。第22页/共104

5、页第二十三页，共104页。n(kuzh n)情况。第23页/共104页第二十四页，共104页。nn基础：两个平面的交点n(A1x+B1y+C1z+D1=0,A2x+B2y+C2z+D2=0)第24页/共104页第二十五页，共104页。n平面：点法式/标准式nAx+By+Cz+D=0 A(x-x0)+B(y-y0)+C(z-z0)=0n判定点和平面关系nAx0+By0+Cz0+D 0 -点与法向量同侧第25页/共104页第二十六页，共104页。第26页/共104页第二十七页，共104页。的距离nP0是平面上一点，N是法向量n第一个问题：如何判断(pndun)点X在不在平面上n = 0n或者 =

6、第27页/共104页第二十八页，共104页。第28页/共104页第二十九页，共104页。第29页/共104页第三十页，共104页。第30页/共104页第三十一页，共104页。第31页/共104页第三十二页，共104页。n(2)直线平行，或(1)的条件不满足n分别计算四个端点到另一条线段的最短距离n视为平面问题第32页/共104页第三十三页，共104页。第33页/共104页第三十四页，共104页。Product)n确定n的方向n右手定则/右手系n右手四指从X扫到Y，大拇指方向为N第34页/共104页第三十五页，共104页。第35页/共104页第三十六页，共104页。n+z1x2(k i)+z1y

7、2(k j)+z1z2(k k)n=(y1z2-y2z1)i+(z1x2-z2x1)j+(x1y2-x2y1)kn每一项看起来都像一个二维叉积。n回忆(huy)：三阶行列式按第1行展开第36页/共104页第三十七页，共104页。以得到相同的结果。第37页/共104页第三十八页，共104页。以a,b,c为三边的平行六面体体积第38页/共104页第三十九页，共104页。na(bc)记作a,b,c第39页/共104页第四十页，共104页。棱锥体积？nV(三棱锥)=1/6V(六面体)n三维空间中的三棱锥也被称为单纯形第40页/共104页第四十一页，共104页。n构造变换矩阵，进行矩阵乘法n声明向量为(

8、x,y,z,1)n第四维的作用第41页/共104页第四十二页，共104页。第42页/共104页第四十三页，共104页。(xunzhun)度n在三维平面上，一个向量先绕x旋转(xunzhun)度，再按y旋转(xunzhun)度，最后按z旋转(xunzhun)度第43页/共104页第四十四页，共104页。第44页/共104页第四十五页，共104页。n将指定向量旋转到z轴第45页/共104页第四十六页，共104页。n现在可以处理沿原点旋转的情况(qngkung)了n先将法向量旋转到z轴，沿xOy平面旋转角度，再把法向量转回去第46页/共104页第四十七页，共104页。n第二个矩阵是假设法向量为单位向

9、量得到的n解决(jiju)原问题第47页/共104页第四十八页，共104页。量n将点(x,y,z)带入，可以(ky)得到第二式第48页/共104页第四十九页，共104页。n关键：存储凸多边形的面(facet)n拆一条边为两条半边n见右面(yumin)的环绕标志n所有平面法线向外第49页/共104页第五十页，共104页。第50页/共104页第五十一页，共104页。第51页/共104页第五十二页，共104页。第52页/共104页第五十三页，共104页。n递归：沿ac和cb方向搜索n去递归n拓展性：能不能拓展到高维度上第53页/共104页第五十四页，共104页。n(tuy ng)求凸包，凸包的任一条

10、边均可n时间复杂度O(nh)第54页/共104页第五十五页，共104页。 if(k = i | SignedVolume(Pi,Pj,Pk,Pl) EPS) k = l; if(k = j) return; Ih = i; Jh = j; Kh = k; h+;wrap(k,j); wrap(i,k);第55页/共104页第五十六页，共104页。n判定(pndng)面(a,b,c)对点P可见n 0nN=(b-a)(c-a)n 0 - p-a,b-a,c-a 0第56页/共104页第五十七页，共104页。nn地平线的两端(lin dun)，一定是一个可见面一个不可见面第57页/共104页第五十八

11、页，共104页。n初始化：得到一个非退化(tuhu)的三棱锥n初始化失败的情况第58页/共104页第五十九页，共104页。n时间复杂度：O(n2)n查询可见面和地平线n可以(ky)用一个DFS统一解决n拓展性：可以(ky)拓展到高维情况第59页/共104页第六十页，共104页。第60页/共104页第六十一页，共104页。第61页/共104页第六十二页，共104页。n直接从冲突图里面读取n设置点为已处理，删除平面n直接对二分图进行操作n加入新面n枚举每个点，判断可见性第62页/共104页第六十三页，共104页。n初始(ch sh)化：建立单纯形，O(4n)建立初始(ch sh)冲突图n时间复杂度

12、O(n2)。第63页/共104页第六十四页，共104页。n假设e原先连接两个面f1,f2（恰好有一个面将被剔除）n证明：点Pt若能看见f，必定能看见f1或f2n在加入facet时只需要(xyo)考虑能见到f1/f2的点第64页/共104页第六十五页，共104页。nn整个过程中创建的facet个数是O(n)的n算法的复杂度是O(nlogn)，证明较为繁复先略过(l u)n参见Computational Geometry: Algorithms and Applications, Chapter 11第65页/共104页第六十六页，共104页。第66页/共104页第六十七页，共104页。n处理所有

13、位于面a-b-c右侧的点集凸包n判定点集和法线同侧:p-a,p-b,p-c 0第67页/共104页第六十八页，共104页。n红色箭头为各平面法线n这个算法(sun f)是有效的么？第68页/共104页第六十九页，共104页。nn为什么2d下没有这个问题？n递归的各个集合有交集n处理方式(fngsh)：随意分配到一个集合内T第69页/共104页第七十页，共104页。n找到离平面(P0,P1,P2)最远的点Kn删除在三棱锥K-P0-P1-P2内的点和面n将S中剩下的点分到三个外集中nQuickhull(K,P0,P1,S1)nQuickhull(K,P1,P2,S2)nQuickhull(K,P2

14、,P0,S3)第70页/共104页第七十一页，共104页。n相当于二维下的点和三维下的边nSimplified Beneath-Beyond Theoremn若H是空间Rd上的一个凸包，P是H外一点，一个facet F是H+P的凸包当且仅当：n(1) FH，P在F下方n(2) F H，且F由P和一个ridge组成，这个ridge关联的一个facet在p下方，其他在p上方第71页/共104页第七十二页，共104页。n创建facetn分配顶点n删除可见面n复杂度：O(nlogn)(d=4)第72页/共104页第七十三页，共104页。nnChans Algorithm能否扩张到三维？第73页/共10

15、4页第七十四页，共104页。n给定一个凸点集，在O(logn)时间内，找到点P使得面ABP和面ABC二面角最大第74页/共104页第七十五页，共104页。第75页/共104页第七十六页，共104页。n以上是一次找删除点集的操作n可以证明(zhngmng)这么做保证K最大为O(logn)级别第76页/共104页第七十七页，共104页。n每次退回Pi-1查询，只查询Pi-1中当前结果的邻居n可以(ky)证明查询的复杂度也是O(logn)第77页/共104页第七十八页，共104页。第78页/共104页第七十九页，共104页。n分别考虑上下凸壳第79页/共104页第八十页，共104页。n(2)边P1P

16、2在三维凸包的下凸壳上，当且仅当某个时间t时，P1P2是二维凸壳的一条边n求t=-inf+inf之间凸壳的动画第80页/共104页第八十一页，共104页。nnSolve(mid+1,r)n合并两段点集的动画第81页/共104页第八十二页，共104页。nRV右侧(yu c)时，A需要增删对应的点n以上两个事件对应的时刻由分治过程得到。第82页/共104页第八十三页，共104页。nu-vu-v之间删除un(2)不满足(mnz)：新的切线是u+v，在u和v之间插入u+n(3)不满足(mnz)：新的切线是uv+，在u和v+之间删除vn(4)不满足(mnz)：新的切线是uv-，在u和v之间插入v-第83

17、页/共104页第八十四页，共104页。nImplementation第84页/共104页第八十五页，共104页。nTurn(a,b,c)n假设此时last和next里存储(cn ch)的是两个t=-inf时的凸包第85页/共104页第八十六页，共104页。n合并(hbng)凸壳的事件第86页/共104页第八十七页，共104页。n(shch)第87页/共104页第八十八页，共104页。nI,j,k都在某个平面z=sx+ty+b上，且其他点在平面上方(shn fn)n另一侧凸包可以类似处理第88页/共104页第八十九页，共104页。n存储分治中所有时刻的凸包点集，考虑时刻b的情况第89页/共104

18、页第九十页，共104页。第90页/共104页第九十一页，共104页。n优，但实现非常困难，需要辅助的定位结构nChans D-C 思路精巧，实现灵活，但效率较低第91页/共104页第九十二页，共104页。求其重心(zhngxn)坐标。n几何定义：顶点和对面重心(zhngxn)的连线交点为重心(zhngxn)。nG=(A+B+C+D)/4n可以推广到N维单纯形上nP3：给定平面内的凸包，求凸包的重心(zhngxn)坐标。nP4：给定空间内的凸包，求凸包的重心(zhngxn)坐标。第92页/共104页第九十三页，共104页。nSolution to P4n假设无四点共面，凸包每个面都是三角形第93

19、页/共104页第九十四页，共104页。n对每个面进行三角(snjio)剖分再带入上式n假设K个面，每个面有Si个节点nG=(Pi,1+Pi,j+Pi,j+1)*Pi,1,Pi,j,Pi,j+1)/24Vn顺便得到了多面体的体积。第94页/共104页第九十五页，共104页。n定放置于计算机顶部的前提下，芯片离计算机顶部的最远和最近距离。n称压纸器为稳定的，当且仅当压纸器的重心向任何(rnh)方向移动0.2单位时，压纸器都处于平衡状态。第95页/共104页第九十六页，共104页。nFig10nFig11：两种放置(fngzh)方法第96页/共104页第九十七页，共104页。n四点共面n底面扩大为四边形n稳定性测试：重心离底面四边的距离不小于0.2第97页/共104页第九十八页，共104页。第98页/共104页第九十九页，共104页。第99页/共104页第一百页，共104页。第100页/共104页第一百零一页，共104页。第101页/共104页第一百零二页，共104页。nn两个相邻的截面中间是一个四棱台第102页/共104页第一百零三页，共104页。n在计算近似面积时，也可以利用这种法则第103页/共104页第一百零四页，共104页。