Voronoi图细分算法研究

《Voronoi图细分算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、浙江工业大学学位论文原创性声明本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行研究工作所取得的研究成果。除文中已经加以标注引用的内容外，本论文不包含其他个人或集体已经发表或撰写过的研究成果，也不含为获得浙江工业大学或其它教育机构的学位证书而使用过的材料。对本文的研究作出重要贡献的个人和集体，均已在文中以明确方式标明。本人承担本声明的法律责任。作者签名：袈孑岙k日期：洲乡年岁月枷日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权浙江工业

2、大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。本学位论文属于1、保密口，在年解密后适用本授权书．2、不保密口．(请在以上相应方框内打“√”)作者签名：导师签名：友孑祉泰翟聪日期：硼．；年岁月≯日．，日期：zot3年夕月30日浙江工业大学硕士学位论文Voronoi图细分算法研究摘要IIIIMl

3、llll／

4、

5、l舢Y241188Voronoi图在计算几何中是一个重要的概念，它在地质、机器人轨迹控制、气象学等方面都得到广泛的应用，因此构建Voronoi图就显得十分重要。已有的Voronoi图算法大致上

6、可以分为矢量法和栅格法两类，矢量法的优势是生成的图形精度较高，但在高维空间上就要将面或更复杂的图形分解为点和线后处理，会破坏生成元的完整性，而且矢量法的存储结构比较复杂；栅格法对于生成元与空间没有限制，但是生成的图形精度低，算法过程耗时长。本文在绪论部分介绍]'Voronoi图的研究背景和研究现状，在第二章中主要总结归纳了Voronoi图的相关理论。借助于四叉树数据结构和区间运算技术，本文重点在第三章提出了一种新的计算平面点集Voronoi图的细分算法，并推算出了此算法的时间复杂度。且与增量算法和栅格扩张法进行了对比分析，显示了这个新算法的有效性。本文第四章首先提

7、出了一种新的计算平面多边形内部Voronoi图的一般细分算法，然后对此算法作了进一步的改进，对比得出改进后的算法能极大地提高计算精度和速度。近年来随着计算机计算能力大幅提升，在几何造型和图形学中，代数曲线曲面的应用也越来越多。本文的第浙江工业大学硕士学位论文五章提出了一种新的以代数曲线为边界的二维形体的Voronoi图的细分算法，并用实例验证了这个算法是可行的。第六章主要是总结本篇论文的工作并提出今后研究的方向。关键词：Voronoi图，代数曲线，多边形，区间算术，细分算法浙江工业大学硕士学位论文SUBDIVISIONALGORITHMFORVORONOIDIAG

8、RAMABSTRACTVoronoidiagramisanimportantcomputationalgeometryconcept．Itisappliedwidelyingeology,robottrajectorycontrol，meteorologyandotherfields．SoitisveryimportanttoconstructVoronoidiagram．Voronoidiagramgenerationmethodsconsistofvectorandgridalgorithms．Vectoralgorithmsusuallyhavehighac

9、curacy,butinmultidimensionalspacecase，thesurfacesormorecomplexgeometricobjectswillbedecomposedintopointsandlines，SOtheintegrityofthegrowthelementswillbedestroyed，andthedatastoragestructureisverycomplex．Gridalgorithmshavenolimitongrowthelementsandspacetype．HoweveLthequalityofVoronoidia

10、gramsgeneratedarelowandneedmoretime．Inchapterl，theresearchbackgroundisgiven．Then，inchaper2，sometheoriesofVoronoidiagramareintroduced．Basedonquadtreedatastructureandintervalarithmetictechnique，anewsubdivisionalgorithmforVoronoidiagramofaplanarpointsetisproposedinchapter3．A浙江工业大学硕士学位论文c

11、ompar