作者：刘永和；刘玉芳；宋金星

作者单位：河南理工大学资源环境学院

摘要：侧向判别问题是几何学、CAD制图学和地理学分析中经常用到的空间关系问题,它是求解其他复杂空间关系的一个基础.凸包问题是计算几何中的基本问题,是解决其他问题的基础.卷包裹法和格雷厄姆法是凸包求解的经典算法,但其算法步骤较为复杂.笔者利用侧向判别算法改进了用于生成平面点集凸包的卷包裹法和格雷厄姆法,这两种新算法分别具有运算速度较快、易于理解和编程等优点,具有较强的实践意义.

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

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

DOI：10.16186/j.cnki.1673-9787.2006.02.011

分类号：TP301.6