摘要
凸壳问题是计算机图形学、图像处理、模式识别等众多领域中的一个基本问题。正切线算法需对新加入的实时点进行实时编号,本文实现了对新加入点的自动编号,且增加一个实时点最多只需对2个单调段进行计算,提高了运算效率,在最坏情况下时间复杂度为。
Convex hull problem is one of the fundamental problems in computer graphics,image processing,CAD/CAM,and pattern recognition.In tangent algorithm,a real time point which is newly added in needs to be numbered.In this paper,the automatic number-ing for each newly added point has been realized and only two monotonous segments need to be computed when a real time point is added in.So the algorithm improves the efficiency and the time complexity is .
出处
《微计算机信息》
北大核心
2007年第3期252-254,共3页
Control & Automation
基金
广西自然科学基金(0447035)
关键词
凸壳
单调段
极值点
切点
convex hull,monotonous segments,extreme point,tangent point
