MATLAB Delaunay算法提取离散点边界的方法
最近在项目进行中遇到要提取离散点边界的问题，像我这样的对于matlab不是特别熟练的朋友一开始肯定摸不着头脑，到底选用哪种算法可以有效地提取到所有已知点的轮廓线呢。本人经过大量的文献搜索及代码实验找到了几个效果比较好的轮廓提取代码，在这里做个总结，并且希望能够对遇到同样问题的朋友有所启发。
关于离散点边界提取的三种方法：
1.Convhull离散点集获得边界
2.AlphaShape算法检测边缘点
3.Delaunay三角剖分算法
前两种方法在之前的博客中已经做了总结这里就不展开了，现在主要介绍第三种算法。
该算法的总体思路如下：
1、利用delaunay函数，对所有数据点进行 Delaunay三角剖分处理，delaunay函数的返回值是一个N*3的矩阵，其中N为剖分出的三角形个数，3为每个三角形的三个端点的序号。
2、根据triangles矩阵，提取出所有 delaunay三角剖分时所连接的边，依次扫描 triangles矩阵的每一行，将 delaunay三角剖分时所连接的边添加到一个新的矩阵中，最后构成一个M*2的矩阵，其中M是一共所连接的边的条数。
3、显然，最小凸多边形上的边应该仅在以上矩阵中出现一次，因此，将以上矩阵中那些出现次数超过一次的边全部去掉，最后保留的便是最小凸多边形的边。
4、根据最小凸多边形的边，很容易得到构成最小凸多边形的结点的顺序，从而解决问题。
输入参数 points是一个2*P矩阵，P为数据点的个数，第一行是这些数据点对应的x坐标，第二行是对应的y坐标；输出参数 polygon 是一个2*Q矩阵，Q为凸多边形的顶点个数（首尾相连），第一行是这些顶点对应的x坐标，第二行是对应的y坐标。代码实现如下：
functionpolygon=minimal_convex_polygon(points) %进行delaunay三角剖分，将所有连接了的边保存在矩阵lines中 triangles=sort(delaunay(points(1,:),points(2,:)),2); lines=zeros(size(triangles,1)*3,2); fori=1:size(triangles,1) lines(3*i-2,:)=[triangles(i,1),triangles(i,2)]; lines(3*i-1,:)=[triangles(i,1),triangles(i,3)]; lines(3*i,:)=[triangles(i,2),triangles(i,3)]; end %去掉lines中出现次数超过一次的边 [~,IA]=unique(lines,'rows'); lines=setdiff(lines(IA,:),lines(setdiff(1:size(lines,1),IA),:),'rows'); %跟踪lines中的数据点，将凸多边形的顶点编号保存在seqs中 seqs=zeros(size(lines,1)+1,1); seqs(1:2)=lines(1,:); lines(1,:)=[]; fori=3:size(seqs) pos=find(lines==seqs(i-1)); row=rem(pos-1,size(lines,1))+1; col=ceil(pos/size(lines,1)); seqs(i)=lines(row,3-col); lines(row,:)=[]; end %根据seqs，得到凸多边形顶点坐标 polygon=points(:,seqs); end
定义了实现函数，下面进行调用：
plot(Pp(1,:),Pp(2,:),'*r','LineWidth',4);%Pp第一行为x坐标，第二行为y坐标 polygon=minimal_convex_polygon(Pp); holdon; plot(polygon(1,:),polygon(2,:),'LineWidth',2);
效果图片我还不会添加进来，有兴趣的朋友可以试一试。
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。