二维点集凹包算法介绍

最近遇到一个求二维点集凹包的问题,凹包的叫法不知道是否准确,问题可以描述为:(原文下载在文章末尾) 在二维平面上有一系列的点,求能包围所有点集的二维多边形。(好像搜“离散点边界”或“点云边界提取”比凹包更准确)
这个很容易想起二维凸包问题,目前已经有很多算法实现点集的凸包,凸包:https://en.wikipedia.org/wiki/Convex_hull ,这里不再赘述。 主要介绍二维点集凹包的一些算法,这里只做大致介绍,不做详细叙述。 通过网上查找资料,网址http://www.tuicool.com/articles/iUvMjm 介绍了计算凹包的3中方法,且在github上有源码下载链接,感兴趣的可以下载测试。

基于Delaunay三角化,如左图,先将所有的点进行Delaunay三角化,然后删掉太长的边得到点集的凹包。 滚边法(Edge Pivoting),先找到一个凸点作为起始点,一般取y最小的点,顺时针查询距离其几何距离在R内的所有点,即求所谓的 R邻域 ,对R邻域的点集进行排序,再在领域中一个点作为连接点,再以此点作为起始点求R邻域。但是这个算法作者实现的并不是很稳定,总是出现一条单边,而不是多边形,但是还是要感谢作者无私奉献源码。

滚球法(Ball Pivoting),这个是比较稳定用得也比较多的方法,引用作者的话:对于任何点集,我们把这些点想象为钉在平面上的钉子。假如拿一个半径大于一定值的球去从边界接近这个钉群,我们可以用这个球在这些钉子群的边界滚一圈,每次滚动,球都能接触到两个钉子而被卡住。可知如果球的半径越小,越精细。 下面介绍目前求凹包的几种其它算法。

还是上一个网址提到的alpha shape ,参考文献:Edelsbrunner H, Kirkpatrick D, Seidel R. On the shape of a set of points in the plane[J]. IEEE Transactions on information theory, 1983, 29(4): 551-559. 感觉就是滚边法,球的半径参数α越大,边界多边形越接近凸包,α越小,越接近凹包。

搜索盒的边界搜索算法,参考文献:陈涛, 李光耀. 平面离散点集的边界搜索算法[J]. 计算机仿真, 2004, 21(3): 21-23.(这也是我想到的实现方法,结果已经有人早就实现了,看来做项目之前真的是需要多多调研) 算法将一系列的点集根据搜索盒(矩形)分类,找到边界搜索盒,再讲边界点链接起来。 行列法,参考文献:袁满, 袁志华. 一种基于行列法离散点边界搜索算法倡[J]. 计算机应用研究, 2010, 27(11). 先给定一系列离散点集,按行进行搜索,求每行的最大最小值,链接成多边形,再按列搜索,求每列的最大最小值,行列搜索结果相结合,进行边界修正,得到边界多边形,最后进行光顺处理。

原文下载:http://pan.baidu.com/s/1slNMxIH 密码:la94

Ailsa

Read more posts by this author.

Subscribe to CG-HHU

Get the latest posts delivered right to your inbox.

or subscribe via RSS with Feedly!