摘要
多边形区域三角化的基本思想是:首先将简单多边形分解为多个单调多边形,然后对每个单调多边形进行三角化。快速多边形区域三角化算法先由多边形顶点的位置特征分为不同的类型,并沿指定方向对顶点进行排序,然后顺序取出各顶点,根据顶点类型,确定准单调多边形的产生、增长或结束,最后对所产生的多个单调多边形进行三角化。该算法充分利用多边形的顶点、边的拓扑关系,计算量少、实现简单,适用于带有洞、岛的任意简单多边形,速度较快。
The basic idea of triangulation for simple triangle was described as follows ： the polygon was subdivided into monotonous polygons and then triangulated. The algorithm classified all the vertexes by its location characteristics, and sorted them along the appointed axis, and then selected the vertexes orderly to decide the creation, expansion or formation of a monotonous polygon by its type, at last triangulated the formative monotonous polygon. In the algorithm, the topology of the vertexes and edges made full use of so as to reduce calculation task, simplify implementation and made it suitable for any simple triangle with holes and islands , speediness and nearly linear time complexity.
出处
《计算机应用研究》
CSCD
北大核心
2008年第10期3030-3033,共4页
Application Research of Computers
基金
国家自然科学基金资助项目(50774092)
关键词
多边形
单调多边形
拓扑关系
线性时间复杂度
三角化
polygon
monotonous polygon
topological relationship
linear time complexity
triangulation
