MATLAB中Delaunay算法如何提取離散點邊界

小編給大家分享一下MATLAB中Delaunay算法如何提取離散點邊界，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！

關于離散點邊界提取的三種方法：

1.Convhull 離散點集獲得邊界

2.Alpha Shape算法檢測邊緣點

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 坐標。代碼實現如下：

function polygon = minimal_convex_polygon(points)
 % 進行 delaunay 三角剖分，將所有連接了的邊保存在矩陣 lines 中
 triangles = sort(delaunay(points(1, :), points(2, :)), 2);
 lines = zeros(size(triangles, 1) * 3, 2);
 for i = 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, :) = [];
 for i = 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);
hold on;
plot(polygon(1, :), polygon(2, :), 'LineWidth', 2);

以上是“MATLAB中Delaunay算法如何提取離散點邊界”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！