一种基于可见边的平面细分遍历算法

• 作 者: 潘荣江 孟祥旭
• 机 构: 山东大学计算机科学与技术学院
• 出 处: 计算机工程与应用
• 发表日期: 2002年16期
• 关键词: 平面细分遍历算法 数据结构 地理信息系统 入口检测算法 Traversal algorithm Planar subdivision Visibility of
• 基金项目: 国家自然科学基金资助(编号:69973028),,高等学校优秀青年教师教学科研奖励计划项目资助,,山东省科技攻关计划项目资助

文章描述了一种基于可见边的平面细分遍历算法。该算法不需要增加标志位，也不需要堆栈和队列，只使用O（1）的辅助内存空间，并且充分利用了边的可见性，对于面集为F，每个面f上有|f|条边的平面细分，该算法最多进行∑↓f∈F4.|f|.ln|f|/2次边的比较，理论分析和实际运行结果表明，该算法与同类遍历算法相比速度要快得多。