计算平面点集凸包的实时插入算法

Real-time Insert Algorithm for Computing Convex Hull of Finite Planar Sets

讨论平面点集的凸包实时插入算法。算法基于Graham扫描算法,对3个点检测顺序的转向。本文证明,当S的N个点以流的形式进入系统,计算S的凸包所需的检测次数小于3N。

In this paper, based on Graham scan algorithm, a real-time algorithm for computing convex hull of a finite planar set is proposed to check the sequential turn of 3 points. If N points of S are to be computed as stream, the number of tests for compu- ting convex hull of S is lower than 3N,