| 引用本文: | 李佳玮,王盛春,王文成.基于网格行创建条带结构的点在多边形内判断方法.软件学报,2025,36(9):4241-4249 |
| |
|
| |
|
|
| 本文已被：浏览 650次 下载 1216次 |
码上扫一扫！ |
|
|
| 基于网格行创建条带结构的点在多边形内判断方法 |
|
李佳玮1,2,3, 王盛春1,2,4, 王文成1,2,3
|
|
1.基础软件与系统重点实验室(中国科学院 软件研究所), 北京 100190;2.计算机科学国家重点实验室 (中国科学院 软件研究所), 北京 100190;3.中国科学院大学, 北京 100049;4.中船智海创新研究院, 北京 100036
|
|
| 摘要: |
| 对于点在多边形内的检测处理, 近期提出的一种网格法具有很高的计算效率. 该方法对于每个网格单元内的多边形片段进行条带结构的组织, 使得每个条带中的边均与该条带的左右边界相交. 如此, 该方法加强了局部化计算, 并能方便使用GPU进行并行计算, 使得检测效率优于以往的各种方法. 但该方法基于网格单元创建条带结构, 会产生冗余的条带, 并且创建时的空间需求较大而不便在GPU上创建条带结构. 对此, 提出基于网格行创建条带结构, 由此可消除冗余的条带, 减少创建计算的空间需求, 因而能在GPU上进行条带结构的创建, 提高工作效率. 实验表明, 相比原有方法, 新方法大幅加快了条带结构的创建, 甚至可加速40余倍, 并且有更快的检测速度, 能更高效地处理动态多边形. |
| 关键词: 点在多边形中判断 网格法 条带 |
| DOI：10.13328/j.cnki.jos.007307 |
| 分类号: |
| 基金项目:国家自然科学基金(62072446) |
|
| Row-based Stripe Construction in Grids for Point-in-polygon Tests |
|
LI Jia-Wei1,2,3, WANG Sheng-Chun1,2,4, WANG Wen-Cheng1,2,3
|
|
1.Key Laboratory of System Software (Institute of Software, Chinese Academy of Sciences), Beijing 100190, China;2.State Key Laboratory of Computer Science (Institute of Software, Chinese Academy of Sciences), Beijing 100190, China;3.University of Chinese Academy of Sciences, Beijing 100049, China;4.CSSC Intelligent Innovation Research Institute, Beijing 100036, China
|
| Abstract: |
| In terms of point-in-polygon tests, a grid method proposed recently exhibits high computational efficiency. This method organizes the polygon fragments within each grid cell into stripe structures, ensuring that edges in each stripe intersect with both the left and right boundaries of the stripe. In this way, localization computation is enhanced, and GPUs are used for convenient parallel computation, resulting in a detection efficiency superior to that of various previous methods. However, stripe structures constructed based on grid cells generate redundant stripes. Besides, the method has a high space requirement for stripe construction, making it inconvenient to construct stripe structures on GPUs. In response to this, this study proposes to construct stripe structures via grid rows. Thus, redundant strips can be eliminated, and the space requirement for the creation of computation is reduced, due to which stripe structures can be constructed on GPUs, and work efficiency is improved. Experimental results show that, compared with the original method, the new method significantly accelerates the construction of stripe structures, even by over 40 times. Moreover, it has a faster detection speed and can handle dynamic polygons more efficiently. |
| Key words: point-in-polygon test grid method stripe |
|
|
|
|
