Page 330 - 《软件学报》2025年第9期

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
2025,36(9):4241−4249 [doi: 10.13328/j.cnki.jos.007307] [CSTR: 32375.14.jos.007307] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563

*
基于网格行创建条带结构的点在多边形内判断方法

李佳玮 1,2,3 , 王盛春 1,2,4 , 王文成 1,2,3

(基础软件与系统重点实验室 (中国科学院 软件研究所), 北京 100190)
1
2
(计算机科学国家重点实验室 (中国科学院 软件研究所), 北京 100190)
3
(中国科学院大学, 北京 100049)
4
(中船智海创新研究院, 北京 100036)
通信作者: 王文成, E-mail: whn@ios.ac.cn
摘 要: 对于点在多边形内的检测处理, 近期提出的一种网格法具有很高的计算效率. 该方法对于每个网格单元内
的多边形片段进行条带结构的组织, 使得每个条带中的边均与该条带的左右边界相交. 如此, 该方法加强了局部化
计算, 并能方便使用 GPU 进行并行计算, 使得检测效率优于以往的各种方法. 但该方法基于网格单元创建条带结
构, 会产生冗余的条带, 并且创建时的空间需求较大而不便在 GPU 上创建条带结构. 对此, 提出基于网格行创建条
带结构, 由此可消除冗余的条带, 减少创建计算的空间需求, 因而能在 GPU 上进行条带结构的创建, 提高工作效率.
实验表明, 相比原有方法, 新方法大幅加快了条带结构的创建, 甚至可加速 40 余倍, 并且有更快的检测速度, 能更
高效地处理动态多边形.
关键词: 点在多边形中判断; 网格法; 条带
中图法分类号: TP393

中文引用格式: 李佳玮, 王盛春, 王文成. 基于网格行创建条带结构的点在多边形内判断方法. 软件学报, 2025, 36(9): 4241–4249.
http://www.jos.org.cn/1000-9825/7307.htm
英文引用格式: Li JW, Wang SC, Wang WC. Row-based Stripe Construction in Grids for Point-in-polygon Tests. Ruan Jian Xue
Bao/Journal of Software, 2025, 36(9): 4241–4249 (in Chinese). http://www.jos.org.cn/1000-9825/7307.htm

Row-based Stripe Construction in Grids for Point-in-polygon Tests
LI Jia-Wei 1,2,3 , WANG Sheng-Chun 1,2,4 , WANG Wen-Cheng 1,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.

* 基金项目: 国家自然科学基金 (62072446)
收稿时间: 2024-04-17; 修改时间: 2024-08-19; 采用时间: 2024-10-09; jos 在线出版时间: 2025-02-19
CNKI 网络首发时间: 2025-02-19