基于循环链表的凸包增量算法研究与实现  

Research and Implementation of the Convex Hull of Incremental Algorithm Based on Circulation Linked List

作　　者：徐东[1] 刘海见[1] 杨健[1] 

机构地区：[1]海军大连舰艇学院基础部,大连116018

出　　处：《现代计算机（中旬刊）》2014年第4期36-39,共4页Modern Computer

基　　金：海军大连舰艇学院科研发展基金资助项目

摘　　要：采用循环链表构建凸包,使凸包的各顶点在增量过程中,始终处于动态变化的稳定循环链中,无差错地生成结果凸包。相比顺序表而言,每次只需修改指针,无须在内存中频繁移动顶点数据,节省大量的系统时间及内存资源,从根本上解决首尾相接的凸包动态生成问题,极好地满足程序的鲁棒性原则,代码执行效率高。Uses circular linked list to construct the convex hull, makes the convex hull of each vertex always in the dynamic stability of circular chain in the process of increment, error-free convex hull to generate the results. Compared to order table, every time only need to modify a pointer, without frequent mobile vertex data in the memory, the system can save much time and memory resources, fundamentally solves the problem of the convex hull of the head-tail dynamically generated, perfectly meets the program＆#39;s principle of robustness, and high code execution efficiency.

关 键 词：循环链表 凸包增量 切点 迭代 

分 类 号：TP274[自动化与计算机技术—检测技术与自动化装置]