[發明專利]一種電子地圖多邊形三角剖分方法與裝置

在審

• 申請號: 201310164769.2
• 申請日: 2013-05-07
• 公開（公告）號: CN104143214A
• 公開（公告）日: 2014-11-12
• 發明（設計）人: 焦毅
• 申請（專利權）人: 北京四維圖新科技股份有限公司
• 主分類號: G06T17/05
• 分類號: G06T17/05;G06F17/30
• 代理公司: 北京銀龍知識產權代理有限公司 11243
• 代理人: 許靜;黃燦

技術領域

本發明涉及數字制圖技術領域，尤其涉及一種電子地圖多邊形三角剖分方法與裝置。

背景技術

對電子地圖的繪制一般是對導航電子地圖中建筑、道路、河流、海洋、島嶼等多邊形要素進行三角剖分，目前的三角剖分主要歸納為以下幾種方法：

方法一：人工切割。

方法二：Kong切耳剖分，每次從多邊形中切割出一個耳，直到多邊形被切割成三角形為止。

方法一的缺點：

a)效率低，耗費大量人力資源，無法適應快速編譯；

b)剖分結果不穩定；

c)容易產生人為錯誤；

方法二的缺點：

a)三角剖分結果不穩定——同一個多邊形，如果輸入頂點次序發生變化，三角剖分結果不一樣；

b)產生大量狹長三角形，影響電子導航儀繪制速度與效果；

發明內容

為了解決上述技術問題，本發明提供一種電子地圖多邊形三角剖分方法與裝置，提高導航電子地圖數據生產的效率與質量。

為了達到上述目的，本發明采用的技術方案是：一種電子地圖多邊形三角剖分方法，包括以下步驟：

步驟1：將經過預處理后的點集的邊緣的點進行連線，形成沒有相交線的多邊形；

步驟2：查找所述多邊形中小于180度的內角中的最小角；

步驟3：根據所述最小角的頂點以及所述最小角的頂點的相鄰的所述多邊形的頂點構成一三角形；

步驟4：根據所述多邊形的其他頂點是否存在于所述三角形內判斷所述三角形是否為所述多邊形的耳，

如果所述多邊形的其他頂點不存在于所述三角形內，則所述三角形為所述多邊形的耳，進行步驟5，

如果所述多邊形的其他頂點存在于所述三角形內，則所述三角形不是所述多邊形的耳，進行步驟7；

步驟5：將所述耳從所述多邊形中切割并保存；

步驟6：判斷剩余多邊形的邊數是否大于3，如果是則返回步驟2，如果不是則將所述剩余多邊形與所述耳組合生成三角網；

步驟7：在所述多邊形中的其他小于180度的內角中獲得最小角，返回步驟3。

進一步的，所述步驟2具體包括：

步驟21：計算所述多邊形中所有內角的角度；

步驟22：將所述多邊形中小于180度的內角按照角度大小依次排序；

步驟23：根據所述多邊形中小于180度的內角的角度生成二叉排序樹結構，并獲得最小角。

進一步的，所述步驟5具體包括：

步驟51：將所述耳從所述多邊形中切割并保存，獲得剩余多邊形；

步驟52：從所述二叉排序樹結構中刪除所述三角形的三個頂點，構成新的二叉排序樹；

步驟53：計算與所述最小角相鄰的兩個頂點在所述剩余多邊形中形成的新的內角的角度；

步驟54：將與所述最小角相鄰的兩個頂點在所述剩余多邊形中形成的新的內角中、角度小于180度的內角插入所述新的二叉排序樹中。

進一步的，所述步驟7具體包括：

步驟71：按照所述二叉排序樹中的數值的大小在所述二叉排序樹結構中建立用于中序周游索引的指針；

步驟72：按照所述指針的方向查找所述多邊形中的其他小于180度的內角中的最小角。

進一步的，所述步驟4具體包括：

步驟41：根據所述點集中的邊緣的點的（x，y）坐標建立KDTree結構；

步驟42：根據所述三角形頂點的（x，y）坐標建立所述三角形的包圍矩形；

步驟43：根據KDTree結構的范圍查找算法判斷所述多邊形的其他頂點是否存在于所述包圍矩形內，從而判斷所述多邊形的其他頂點是否存在于所述三角形內，

如果所述多邊形的其他頂點不存在于所述包圍矩形內，則所述多邊形的其他頂點不存在于所述三角形內，則所述三角形為所述多邊形的耳，

如果所述多邊形的其他頂點存在于所述包圍矩形內，進一步判斷存在于所述包圍矩形內的頂點是否存在于所述三角形內，如果不是則所述三角形是所述多邊形的耳，如果是則所述三角形不是所述多邊形的耳。

進一步的，所述步驟43中，在所述多邊形的其他頂點存在于所述包圍矩形內時，還包括：

步驟430：將存在于所述包圍矩形內的頂點與所述三角形的三個頂點連線獲得三個子三角形；