点集图形重建的算法研究

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

1、硕士学位论文点集图形重建的算法研究THEALGORITHMSTUDYOFPOLYGONALSHAPERECONSTRUCTION孟迪哈尔滨工业大学2016年6月国内图书分类号：TP391学校代码：10213国际图书分类号：004.9密级：公开理学硕士学位论文点集图形重建的算法研究硕士研究生：孟迪导师：张池平教授申请学位：理学硕士学科：计算数学所在单位：理学院答辩日期：2016年6月授予学位单位：哈尔滨工业大学ClassifiedIndex:TP391U.D.C:004.9DissertationfortheMasterDegreeinEngineeri

2、ngTHEALGORITHMSTUDYOFPOLYGONALSHAPERECONSTRUCTIONCandidate：MengDiSupervisor：Prof.ZhangChiPingAcademicDegreeAppliedfor：MasterofScienceSpeciality：ComputationalMathematicsAffiliation：DepartmentofMathematicsDateofDefence：June,2016Degree-Conferring-Institution：HarbinInstituteofTechno

3、logy哈尔滨工业大学理学硕士学位论文摘要点集图形在许多课题中都有涉及，例如，特殊空间的点、数字照片中的像素、银河中的星球和空间数据等。并且，点集图形集重建是图形重建领域的一个非常重要的内容。假设平面中有一系列离散的点，这些点仅凭我们的视觉系统是无法感知其所要表达的具体形状的。本文研究的主要内容就是如何由这些离散的点重建出一个我们能够识别的具体图形。为了重建出一个具体的图形，要从这个图形的凸包开始，一步步将这个图形的凸包进行凹化，这样就能够使更多的点回到边界上，从而能够更加接近点集所要表达的真实的图形。当一个点集是一列不含边界的离散点的时候，需要建立这

4、个点集的一个凸包边界。本文利用的是Delaunay三角剖分的方法。显然，一个点集的凸包边界，就是这个点集经过Delaunay三角剖分之后形成的三角网的一个子集。所以，只要确定介值并删去多余的边即可得到这个点集的凸包。除此之外，本文还设计了一个有适当半径的圆，通过这个圆与点集中的两点形成的弦来确定这个点集的凸包。当输入的点集带有边界时，就需要对这个点集的边界进行检测。本文主要用到的算法是合并算法，分离算法和独立算法。当一个点集的凸包被构建完成后，就要对这个点集的凸包进行凹化处理。在进行凹化处理的时候，需要删去已知的边并利用这条边的两端点和点集内一点建立两

5、条新的边。这就需要在每一步都选取适当的边和适当的点。在选择时，本文将已有的就近选择标准、最长边选择标准、等角选择标准结合起来，得到一个新的选择标准。最后文章给出这个算法的停止条件，如果满足条件，则算法停止，如果不满足，算法将循环进行。关键词：平面点集；图形重建；凸包；凹化-I-哈尔滨工业大学理学硕士学位论文AbstractProcessingadotpatternorpointsetintheplaneisausefulandimportantprobleminpatternrecognition.Dotpatternsencounteredinvar

6、iousproblemsincludepointsinfeaturespace,pixelinadigitalimage,physicalobjectslikestarsinthegalaxyorspatialdata.Supposethereisaseriesofdiscretepointsintheplane,whichwecannotperceivethespecificshapeitwanttoexpressonlydependsonourvisualsystem.Themainproblemthatwewanttostudyishowtore

7、constructfromthesediscretepointsoutaspecificgraphicsthatwecanidentify.Toreconstructaspecificpattern,weneedconcavethisgraphicfromtheconvexhullstepbystep,sothatwecanmakemorepointsbacktotheborder,whichcanbesetclosertothepointtoaskgraphicrepresentationofthereal.Thus,thefirsttaskisto

8、establishtheconvexhulloftheset.Supposeasetofdis