多边形生成合并及布尔运算算法研究

发布时间：2021-03-25 23:39

　　近些年来,随着GIS、计算机辅助设计、三维物体表面重建、医学或卫星图像数据处理等领域的发展,多边形的相关运算越来越重要。多边形的相关运算可大致分为生成、合并及布尔运算,是计算几何中的几个重要的问题。本文对多边形相关的算法进行了深入细致的研究。大致分为四个部分:多边形合并算法、线段集生成简单多边形算法、多边形的三角剖分以及多边形布尔运算算法。主要目的分为两个,一个是简化算法过程,降低时间复杂度,另一个是缩短连接线长度,在实际应用方面可降低成本。1.给出的多边形合并算法是将两个不相交多边形连接成一条回路。该算法通过删除多边形两侧距离较短的点,并将剩余顶点构成一个新的多边形,然后对新多边形进行Delaunay三角剖分,以Delaunay边作为对角线构成四边形,找到四边形的边长增值最小的连接点与的对应点,删除相应边,得到具有最小长度的回路,降低了算法的时间复杂度。2.给出了线段集生成简单多边形算法,首先逐层计算线段集的凸壳,为了缩短连接线段长度和将这些凸壳根据Delaunay三角剖分选取最近点或次最近点改变成简单多边形,然后计算多边形之间的交点并删除,最后将这些简单多边形合并成一个简单多边形。... 

【文章来源】：哈尔滨理工大学黑龙江省

【文章页数】：53 页

【学位级别】：硕士

【部分图文】：

a1V(p)，2V(p)的图示

第 2 章 基础知识近些年来，多边形的合并、线段集生成简单多边形、多边形的三角剖分以及布尔运算在实际中得到越来越多的应用，接下来介绍本文的相关知识点。2.1 多边形三角剖分2.1.1 Voronoi 图的基本概念[31]设1p ,2p 是平面上的两点，L是1 2p p 的垂直平分线，L将平面划分成rL 、RL ，位于rL 内的点具有特性： 1 2, ,l ld p p d p p，其中 , l id p p 表示lp 与ip之间的欧几里得距离，i=1,2。这说明，位于rL 内的点比平面中的其他点更加接近点1p ，也就是说，rL 内的点是比平面上其他点更接近1p 的点的轨迹，记为1V ( p )，如图 2-1a 所示。如果用1 2H ( p , p )表示半平面rL ，而2 1( , )RL H p p，则有1 1 2 2 2 1V ( p ) H ( p , p ), V ( p ) H ( p , p)。

哈尔滨理工大学理学硕士学位论文多边形域，称为关联于ip 的 Voronoi 多边形（-1b 表示关联于1p 的 Voronoi 多边形，是一个四于S 中的每个点都可以做一个 Voronoi 多边形onoi 多边形构成的图，记为 Vor ( S )，如图 2-2 中 Voronoi 顶点，边称为 Voronoi 边。


本文编号：3100528