摘要
Graham 扫描在计算几何中是一种基本的后追踪技术.Graham 扫描三角形化简单多边形算法三角形化一个,1个顶点的简单多边形 P 的时间为 D(kn),k-1是多边形 P 的凹顶点数.在最坏的情况下,此算法为 O(n^2).其数据结构简单,运行速度快、极易应用.改进后的算法进一步简化了检测“耳朵”的步骤,使之更严谨、简明,并用 C 语言编程实现了改进后的算法.
The Graham scan is a fundamental backtracking technology in computational geometry.The Graham scan triangularization sirnple polygon algrithm triangulates an n-bertex polygon P in O(kn)-time,where k-1 is the number of concave vertices in P.In the worst case the running time of the algorithm is O(n^2).It is easy to implement because its running is fast and the data structur is very simple.The reformed algorithm simplifies the steps of checking the“ears”,so it is more concise and rigid,which programmed with C language bascd on re- formed algorithm.
出处
《大连铁道学院学报》
1991年第4期50-54,共5页
Journal of Dalian Railway Institute
关键词
多边形
Graham扫描
对角线
计算机
polygons
algorithm/computational geometry
Grahann scan
triangularization
diagonal
backtracking
