节点文献
基于凸剖分的点在多边形内的高效判定
【摘要】 提出一种点在多边形内的快速判定算法.与这方面已知的最快算法相比,新方法在预处理时间、空间需求和判定计算等方面,均达到了相同的复杂度,且没有奇异情况,能运算更快,甚至快一倍多.其步骤是:将一个多边形剖分成一些凸多边形,并进行二叉树的组织管理;然后,判断一个点是否在该多边形内时,先根据二叉树找到最可能包含该点的凸多边形,再判断该点是否位于该凸多边形内,就可完成判定计算.
【基金】 国家自然科学基金项目(批准号:60373051);国家“九七三”计划项目(批准号:2002CB312102);国家“八六三”计划项目(批准号:2006AA01Z306);Research Grant of University of Macau基金资助项目
- 【文献出处】 自然科学进展 , 编辑部邮箱 ,2007年07期
- 【分类号】O243
- 【被引频次】3
- 【下载频次】167