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

计算机与现代化 ›› 2013, Vol. 1 ›› Issue (1): 12-14.doi:

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

刘萍

甘肃民族师范学院，甘肃合作747000

收稿日期:2012-09-14 修回日期:1900-01-01 出版日期:2013-02-06 发布日期:2013-02-06

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

LIU Ping

Gansu Normal University for Nationalities, Hezuo 747000, China

Received:2012-09-14 Revised:1900-01-01 Online:2013-02-06 Published:2013-02-06

摘要/Abstract

摘要：

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



关键词: 关键词：凸包, 实时插入算法, Graham扫描算法

Abstract:

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 computing convex hull of S is lower than 3N.

Key words: 

刘萍. 计算平面点集凸包的实时插入算法 [J]. 计算机与现代化, 2013, 1(1): 12-14.

LIU Ping. Realtime Insert Algorithm for Computing Convex Hull of Finite Planar Sets[J]. Computer and Modernization, 2013, 1(1): 12-14.