一种电子地图多边形三角剖分方法与装置

摘要

本发明涉及电子地图多边形三角剖分方法与装置，其中，电子地图多边形三角剖分方法包括：步骤1：经过预处理后的点集的边缘的点进行连线，形成没有相交线的多边形；步骤2：查找多边形中小于180度的内角中的最小角；步骤3：根据最小角的顶点以及最小角的顶点的相邻的多边形的顶点构成三角形；步骤4：根据多边形的其他顶点是否存在于三角形内判断三角形是否为多边形的耳，如果三角形为多边形的耳，进行步骤5，如果三角形不是多边形的耳，进行步骤7；步骤5：将耳从多边形中切割并保存；步骤6：判断剩余多边形的边数是否大于3，如果是则返回步骤2，如果不是则生成三角网；步骤7：在多边形中的其他内角中获得最小角，返回步骤3。

主权项

一种电子地图多边形三角剖分方法，其特征在于，包括以下步骤：步骤1：将经过预处理后的点集的边缘的点进行连线，形成没有相交线的多边形；步骤2：查找所述多边形中小于180度的内角中的最小角；步骤3：根据所述最小角的顶点以及所述最小角的顶点的相邻的所述多边形的顶点构成一三角形；步骤4：根据所述多边形的其他顶点是否存在于所述三角形内判断所述三角形是否为所述多边形的耳，如果所述多边形的其他顶点不存在于所述三角形内，则所述三角形为所述多边形的耳，进行步骤5，如果所述多边形的其他顶点存在于所述三角形内，则所述三角形不是所述多边形的耳，进行步骤7；步骤5：将所述耳从所述多边形中切割并保存；步骤6：判断剩余多边形的边数是否大于3，如果是则返回步骤2，如果不是则将所述剩余多边形与所述耳组合生成三角网；步骤7：在所述多边形中的其他小于180度的内角中获得最小角，返回步骤3。