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

在審

• 申請(qǐng)?zhí)枺?/td>: 201310164769.2
• 申請(qǐng)日: 2013-05-07
• 公開(kāi)（公告）號(hào): CN104143214A
• 公開(kāi)（公告）日: 2014-11-12
• 發(fā)明（設(shè)計(jì)）人: 焦毅
• 申請(qǐng)（專(zhuān)利權(quán)）人: 北京四維圖新科技股份有限公司
• 主分類(lèi)號(hào): G06T17/05
• 分類(lèi)號(hào): G06T17/05;G06F17/30
• 代理公司: 北京銀龍知識(shí)產(chǎn)權(quán)代理有限公司 11243
• 代理人: 許靜;黃燦

1.一種電子地圖多邊形三角剖分方法，其特征在于，包括以下步驟：

步驟1：將經(jīng)過(guò)預(yù)處理后的點(diǎn)集的邊緣的點(diǎn)進(jìn)行連線(xiàn)，形成沒(méi)有相交線(xiàn)的多邊形；

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

步驟3：根據(jù)所述最小角的頂點(diǎn)以及所述最小角的頂點(diǎn)的相鄰的所述多邊形的頂點(diǎn)構(gòu)成一三角形；

步驟4：根據(jù)所述多邊形的其他頂點(diǎn)是否存在于所述三角形內(nèi)判斷所述三角形是否為所述多邊形的耳，

如果所述多邊形的其他頂點(diǎn)不存在于所述三角形內(nèi)，則所述三角形為所述多邊形的耳，進(jìn)行步驟5，

如果所述多邊形的其他頂點(diǎn)存在于所述三角形內(nèi)，則所述三角形不是所述多邊形的耳，進(jìn)行步驟7；

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

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

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

2.根據(jù)權(quán)利要求1所述的一種電子地圖多邊形三角剖分方法，其特征在于，所述步驟2具體包括：

步驟21：計(jì)算所述多邊形中所有內(nèi)角的角度；

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

步驟23：根據(jù)所述多邊形中小于180度的內(nèi)角的角度生成二叉排序樹(shù)結(jié)構(gòu)，并獲得最小角。

3.根據(jù)權(quán)利要求2所述的一種電子地圖多邊形三角剖分方法，其特征在于，所述步驟5具體包括：

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

步驟52：從所述二叉排序樹(shù)結(jié)構(gòu)中刪除所述三角形的三個(gè)頂點(diǎn)，構(gòu)成新的二叉排序樹(shù)；

步驟53：計(jì)算與所述最小角相鄰的兩個(gè)頂點(diǎn)在所述剩余多邊形中形成的新的內(nèi)角的角度；

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

4.根據(jù)權(quán)利要求2所述的一種電子地圖多邊形三角剖分方法，其特征在于，所述步驟7具體包括：

步驟71：按照所述二叉排序樹(shù)中的數(shù)值的大小在所述二叉排序樹(shù)結(jié)構(gòu)中建立用于中序周游索引的指針；

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

5.根據(jù)權(quán)利要求1所述的一種電子地圖多邊形三角剖分方法，其特征在于，所述步驟4具體包括：

步驟41：根據(jù)所述點(diǎn)集中的邊緣的點(diǎn)的（x，y）坐標(biāo)建立KDTree結(jié)構(gòu)；

步驟42：根據(jù)所述三角形頂點(diǎn)的（x，y）坐標(biāo)建立所述三角形的包圍矩形；

步驟43：根據(jù)KDTree結(jié)構(gòu)的范圍查找算法判斷所述多邊形的其他頂點(diǎn)是否存在于所述包圍矩形內(nèi)，從而判斷所述多邊形的其他頂點(diǎn)是否存在于所述三角形內(nèi)，

如果所述多邊形的其他頂點(diǎn)不存在于所述包圍矩形內(nèi)，則所述多邊形的其他頂點(diǎn)不存在于所述三角形內(nèi)，則所述三角形為所述多邊形的耳，

如果所述多邊形的其他頂點(diǎn)存在于所述包圍矩形內(nèi)，進(jìn)一步判斷存在于所述包圍矩形內(nèi)的頂點(diǎn)是否存在于所述三角形內(nèi)，如果不是則所述三角形是所述多邊形的耳，如果是則所述三角形不是所述多邊形的耳。

6.根據(jù)權(quán)利要求5所述的一種電子地圖多邊形三角剖分方法，其特征在于，所述步驟43中，在所述多邊形的其他頂點(diǎn)存在于所述包圍矩形內(nèi)時(shí)，還包括：

步驟430：將存在于所述包圍矩形內(nèi)的頂點(diǎn)與所述三角形的三個(gè)頂點(diǎn)連線(xiàn)獲得三個(gè)子三角形；

判斷所述三個(gè)子三角形的面積的和是否大于所述三角形的面積，如果是則存在與所述包圍矩形內(nèi)的頂點(diǎn)不在所述三角形內(nèi)，所述三角形為多邊形的耳，如果不是則存在與所述包圍矩形內(nèi)的頂點(diǎn)在所述三角形內(nèi)，所述三角形不是多邊形的耳。

7.根據(jù)權(quán)利要求5所述的一種電子地圖多邊形三角剖分方法，其特征在于，所述步驟42中，所述包圍矩形由所述三角形頂點(diǎn)中的最小x坐標(biāo)、最小y坐標(biāo)、最大x坐標(biāo)、最大y坐標(biāo)形成。