一种改进的点在多边形内外判断算法

• 作者: 李楠 肖克炎
• 来源期刊: 计算机工程
• 学科: 工学
• 关键词: BSP树 平衡二叉树 任意简单多边形 二分查找 快排序
• 年，卷（期）: 2012,（5）
• 所属期刊栏目: 专栏
• 页码范围: 30-34
• 分类号: TP391
• 字数: 3090字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-3428.2012.05.007

摘要

为解决多边形内外算法中BSP树退化为链表的问题,提出一种改进的点在多边形内外的判断算法.在 构建水平扫描线的BSP树之前,对水平扫描线按照Y值进行排序,将排好序的水平扫描线按照二分法的顺序插入到BSP树中,其查找时间复 杂度为O(lbn).实验结果表明,该算法在不增加BSP构建时间复杂度的前提下,能够保证BSP树的查找效果总是最优的,且简单易行, 具有较好的通用性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	肖克炎	中国地质科学院矿产资源研究所	173	2593	29.0	42.0
2	李楠	中国地质科学院矿产资源研究所	42	402	12.0	18.0