期刊文献+

基于凸片段分解和格网的点在多边形中的可见边检测 被引量:1

Visibility Queries of Points in Polygons by Decomposed Convex Segments and Grids
下载PDF
导出
摘要 检测点在多边形中的可见边是计算几何中的一种基本计算,文中对此提出一种加速算法.首先对多边形进行凸片段分解,以利用点在凸多边形中可见边的快速计算;然后利用格网结构实现由近及远的计算,避免处理被遮挡的凸片段.该算法可基于格网结构方便地进行并行处理,并可统一处理含空洞和不含空洞的多边形,其预处理时间复杂度为O(n),空间复杂度也是很低的O(n),而检测的时间复杂度在O(logn)~O(n)之间自适应变化,其中n为多边形的边数. It is a basic operation in computational geometry to detect the visible edges of a point in a polygon. With regard to this, this paper presents a new algorithm for acceleration. Firstly, it decomposes the polygon into convex segments, to take the advantage that it is fast to compute the visible edges of a point in a convex polygon. Then, it uses a grid to treat convex segments from near to far, to avoid treating those occluded ones. Also by the grid, the new algorithm can be easily implemented in parallel. The new algorithm treats the polygons with or without holes uniformly. It has a lower time complexity O(n) on preprocessing to construct a data structure in O(n) storage, while finds visible edges of a point in O(log n)~O(n) time adaptively, where n is the number of polygon edges.
出处 《计算机辅助设计与图形学学报》 EI CSCD 北大核心 2013年第8期1114-1120,共7页 Journal of Computer-Aided Design & Computer Graphics
基金 国家自然科学基金(60833007 60928006) 中国科学院知识创新工程领域前沿项目
关键词 多边形 可见边 凸片段 格网 并行计算 polygon visible edges convex line segments grid~ parallel computation
  • 相关文献

参考文献8

  • 1Bose P,Lubiw A,Munro J I.Efficient visibility queries insimple polygons [J].Computational Geometry,2002,23(3):313-335.
  • 2Aronov B,Guibas L J,Teichmann M,et al.Visibilityqueries and maintenance in simple polygons [J].Discrete andComputational Geometry,2002,27(4):461-483.
  • 3Pocchiola M,Vegter G.The visibility complex [C] //Proceedings of the 9th Annual Symposium on ComputationalGeometry.New York:ACM Press,1993 :328-337.
  • 4Zarei A,Ghodsi M.Query point visibility computation inpolygons with holes [J].Computational Geometry,2008,39(2):78-90.
  • 5Lu L,Yang C L,Wang J Y.Point visibility computing inpolygons with holes [J].Journal of InformationComputational Science,2011,8(16):4165-4173.
  • 6Zalik B,Kolingerova I.A cell-based point-in-polygonalgorithm suitable for large sets of points [J].Computers &?Geosciences,2001,27(10):1135-1145.
  • 7孙春娟,王文成,李静,吴恩华.基于凸片段分解的多边形窗口线裁剪算法[J].计算机辅助设计与图形学学报,2006,18(12):1799-1805. 被引量:6
  • 8Skala V.OClg N)line clipping algorithm in E2 [J].Computers Graphics,1994,18(4):517-524.

二级参考文献7

  • 1Rogers David F.Procedural elements for computer graphics[M].2nd ed.Beijing:China Machine Press,2002
  • 2Skala V.Line clipping in E^2 with O(1) processing complexity[J].Computers & Graphics,1996,20(4):523-530
  • 3Skala V.O(lgN) line clipping algorithm in E^2[J].Computers & Graphics,1994,18(4):517-524
  • 4Huang Y Q,Liu Y K.An algorithm for the clipping against a polygon based on shearing transformation[J].Computer Graphics Forum,2002,21(4):683-688
  • 5Taloy G.Point in polygon test[J].Survey Review-Commonwealth Association of Surveying and Land Economy,1994,32(254):479-484
  • 6刘勇奎,颜叶,石教英.一个有效的多边形窗口的线裁剪算法[J].计算机学报,1999,22(11):1209-1214. 被引量:38
  • 7陆国栋,邢世海,彭群生.基于顶点编码的多边形窗口线裁剪高效算法[J].计算机学报,2002,25(9):987-993. 被引量:16

共引文献5

同被引文献13

引证文献1

二级引证文献4

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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