基于凸剖分的点在多边形内的高效判定  

作　　者：李静[1] 王文成[1] 吴恩华[1] 

机构地区：[1]中国科学院软件研究所计算机科学国家重点实验室

出　　处：《自然科学进展》2007年第7期995-1000,共6页

基　　金：国家自然科学基金项目(批准号:60373051);国家"九七三"计划项目(批准号:2002CB312102);国家"八六三"计划项目(批准号:2006AA01Z306);Research Grant of University of Macau基金资助项目

摘　　要：提出一种点在多边形内的快速判定算法.与这方面已知的最快算法相比,新方法在预处理时间、空间需求和判定计算等方面,均达到了相同的复杂度,且没有奇异情况,能运算更快,甚至快一倍多.其步骤是:将一个多边形剖分成一些凸多边形,并进行二叉树的组织管理;然后,判断一个点是否在该多边形内时,先根据二叉树找到最可能包含该点的凸多边形,再判断该点是否位于该凸多边形内,就可完成判定计算.

关 键 词：点 多边形 包容性检测 加速 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]