期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

基于凸剖分的点在多边形内的高效判定 被引量：1

下载PDF
导出
摘要 提出一种点在多边形内的快速判定算法.与这方面已知的最快算法相比,新方法在预处理时间、空间需求和判定计算等方面,均达到了相同的复杂度,且没有奇异情况,能运算更快,甚至快一倍多.其步骤是:将一个多边形剖分成一些凸多边形,并进行二叉树的组织管理;然后,判断一个点是否在该多边形内时,先根据二叉树找到最可能包含该点的凸多边形,再判断该点是否位于该凸多边形内,就可完成判定计算.
作者 李静 王文成 吴恩华
机构地区 中国科学院软件研究所计算机科学国家重点实验室
出处 《自然科学进展》 北大核心 2007年第7期995-1000,共6页
基金 国家自然科学基金项目(批准号:60373051) 国家"九七三"计划项目(批准号:2002CB312102) 国家"八六三"计划项目(批准号:2006AA01Z306) Research Grant of University of Macau基金资助项目
关键词 点 多边形 包容性检测 加速
分类号 TP301.6 [自动化与计算机技术—计算机系统结构]
  • 相关文献

参考文献13

  • 1de Berg M,van Kreveld M, Overmars M, et al. Computational Geometry: Algorithms and Applications. 2nd ed. Berlin: Springer Verlag, 2000
  • 2http://www, ecse. rpi. edu/Homepages/wrf/Research/Short-Notes/ pnpoly, html[2006-11-29]
  • 3http: //www. ecse. rpi. edu/Homepages/wrf/geom/pnpoly, html [2006-11-29]
  • 4Preparata FP, Shamos MI. Chapter 2 Geometric Searching. Computational Geometry: An Introduction. 2nd ed. New York: Springer Verlag. 1985, 36-94
  • 5Hormann K, Agathos A. The point in polygon problem for arbitrary polygons. Computational Geometry: Theory and Applications, 2001, 20:131-144
  • 6Feito FR, Torres JC, Urena A. Orientation, simplicity, and inclusion test for planar polygons. Computers & Graphics, 1995, 19(4) : 595-600
  • 7Feito FR, Torres JC. Inclusion test for general polyhedra. Computers & Graphics, 1997, 21(1): 23-30
  • 8Taylor G. Point in polygon test. Survey Review, 1994, 32: 479-484
  • 9Zalik B. , Gordon J. Clapworthy, A universal trapezoidation algorithm for planar polygons. Computers & Graphies, 1999, 23(3) : 253-263
  • 10Zalik B, Kolingerova I. A cell-based point-in-polygon algorithm suitable for large sets of points. Computers & Geosciences, 2001, 27(10): 1135-1145

同被引文献9

引证文献1

二级引证文献6

自然科学进展
2007年 第7期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部