基于侧向判别和侧向偏序排列的凸包生成算法  

Algorithms for calculating converx hull based on side-distinguishing method

作　　者：刘永和[1] 刘玉芳[1] 宋金星[1] 

机构地区：[1]河南理工大学资源环境学院,河南焦作454003

出　　处：《河南理工大学学报（自然科学版）》2006年第2期130-133,共4页Journal of Henan Polytechnic University（Natural Science）

基　　金：河南省自然科学基金资助项目(0124140155)

摘　　要：侧向判别问题是几何学、CAD制图学和地理学分析中经常用到的空间关系问题,它是求解其他复杂空间关系的一个基础.凸包问题是计算几何中的基本问题,是解决其他问题的基础.卷包裹法和格雷厄姆法是凸包求解的经典算法,但其算法步骤较为复杂.笔者利用侧向判别算法改进了用于生成平面点集凸包的卷包裹法和格雷厄姆法,这两种新算法分别具有运算速度较快、易于理解和编程等优点,具有较强的实践意义.Side distinguishing is a spatial relation question used often in geometry, CAD ／ CAC, geographical analysis and is a basis for solving other complex spatial relation question. The converx hull is a fundamental problem in calculate geometry and solving other questions. Gift wrapping method and Graham method are traditional arithmethic of converx hull calculating, and arithmetic steps is very complex. The author improved two traditional algorithms for calculating converx hull in the paper. The new algorithm has the advantage of faster running and easier programming.

关 键 词：侧向判别 凸包 卷包裹法 格雷厄姆算法 

分 类 号：O189.11[理学—数学]