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

摘要：

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

关键词：BSP树、平衡二叉树、任意简单多边形、二分查找、快排序

所属期刊栏目：38

分类号：TP391(计算技术、计算机技术)

资助基金：国家自然科学基金资助项目41002119;国家“863”计划基金资助项目2006AA06Z114;国家科技支撑计划基金资助项目2006BAB01A01;中央级公益性科研院所基本科研业务费专项基金

在线出版日期：2012-05-22（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：30-34