基于线性方程的三维地理围栏算法研究
四川师范大学, 计算机科学学院, 四川成都 610101
| 摘 要： | 三维空间地理围栏是基于位置服务（LBS, Location Based Services）的一种新应用，它可以给围栏关联者提供实时的、基于立体位置变化的相关服务，其核心是判断目标点与围栏区域的位置关系，可抽象为几何数学中点与空间图形位置关系判别，即点包含问题。目前，主流的射线法在边界判断存在奇异性问题，虽有诸多改进算法被提出，但多数算法受限于二维形式，对于复杂的空间立体环境，无法满足高精度位置判别需求。因此本文从求解线性方程组的思想出发，将点与多面体围栏位置关系的判断转化为点与平面位置关系的判断，提出一种基于线性方程的三维地理围栏新算法，可以快速、准确完成目标点与围栏位置关系判断。首先，结合凸剖分思想和BSP树技术对复杂多面体围栏进行预处理并形成二叉树；其次，递归查询目标点位于二叉树的位置，并获取子凸多面体围栏数据；最后，使用线性方程算法对目标点与子凸多面体进行点包含判断。实验结果表明，与改进后的射线法相比，线性方程新算法在凸多面体围栏位置判别上效率提升40%-48.49%，在简单非凸多面体围栏上提升12.5%-20%。 |
| 关 键 词： | 地理围栏; 点包含算法; 线性方程; 凸剖分; BSP树 |
| DOI： | 10.57237/j.cst.2023.02.004 |
View:
Downloads:
收稿日期: 2023-02-23
接受日期: 2023-04-10
在线出版日期: 2023-04-25
Research on 3D Geographic Fence Algorithm Based on Linear Equation
School of Computer Science, Sichuan Normal University, Chengdu 610101, China
| Abstract: | Three-dimensional spatial geo-fencing is a new application based on location-based services (LBS, Location Based Services), which can provide real-time, three-dimensional location change-based related services to fence associates, and its core is to judge the location relationship between target points and fence area, which can be abstracted as point and space figure location relationship discrimination in geometry and mathematics, i.e., point inclusion problem. At present, the mainstream ray method has singularity problem in boundary judgment, and although many improved algorithms have been proposed, most of them are limited to two-dimensional form, which cannot meet the demand of high-precision position discrimination for complex spatial three-dimensional environment. Therefore, this paper starts from the idea of solving a system of linear equations, transforms the judgment of the position relationship between points and polyhedral fences into the judgment of the position relationship between points and planes, and proposes a new algorithm of 3D geo-fencing based on linear equations, which can quickly and accurately complete the judgment of the position relationship between target points and fences. Firstly, the complex polyhedral fence is pre-processed and formed into a binary tree by combining the idea of convex dissection and BSP tree technology; secondly, the target point is recursively queried to be located in the binary tree and the sub-convex polyhedral fence data is obtained; finally, the linear equation algorithm is used to judge the point inclusion between the target point and the sub-convex polyhedron. Experimental results show that the new linear equation algorithm is 40%-48.49% more efficient in convex polyhedral fence position discrimination and 12.5%-20% more efficient in simple nonconvex polyhedral fences compared with the improved ray method. |
| Keywords: | Geographic Fence; Point Inclusion Algorithm; Linear Equation; Convex Subdivision; BSP Tree |
参考文献
| [1] | 郭磊, 王晓烨, 田晓龙, 霍德啸. 浅谈物联网时代LBS发展应用新模式 [J]. 智能城市, 2020, 6 (07): 19-20. DOI: 10.19301/j.cnki.zncs.2020.07.007. |
| [2] | 金保可. 室内位置信息服务平台的研究与实现 [D]. 北京邮电大学, 2016. |
| [3] | 玉山江•艾孜木, 王鑫, 徐畅玥, 曹新辰, 刁雅静. 基于文献计量的地理围栏研究脉络与热点分析 [J]. 现代信息科技, 2021, 5 (24): 108-112+116. DOI: 10.19850/j.cnki.2096-4706.2021.24.028. |
| [4] | 王静, 刘飞. 基于地理围栏的景点信息推送设计与实现 [J]. 科技视界, 2022 (21): 16-18. DOI: 10.19694/j.cnki.issn2095-2457.2022.21.05. |
| [5] | 成凯. 基于移动终端传感器的室内地理围栏的研究 [D]. 华中师范大学, 2017. |
| [6] | 张华伟, 史久琛, 李啸宇, 董苏. 基于Android的儿童运动分析及监控系统设计 [J]. 现代计算机 (专业版), 2017 (34): 57-61. |
| [7] | 黄俊. 基于Android系统的远程监控与控制系统的设计与实现 [D]. 宁波大学, 2014. |
| [8] | 谢东岑, 梁晓龙, 张佳强, 付其喜, 张凯. 无人机地理围栏越界探测算法改进与分析 [J]. 航空工程进展, 2020, 11 (02): 207-213. DOI: 10.16615/j.cnki.1674-8190.2020.02.008. |
| [9] | 侯岳奇, 陶浩, 龚俊斌, 梁晓龙, 张诺. 多约束条件下无人艇和无人机集群协同航迹规划 [J]. 中国舰船研究, 2021, 16 (01): 74-82. DOI: 10.19693/j.issn.1673-3185.02091. |
| [10] | 石刚杰, 魏冠楠, 葛修川. 一种航空三维地理信息采集器[P]. 山东省: CN217424372U, 2022-09-13. |
| [11] | Vaclav Skala. Point-in-convex polygon and point-in-convex polyhedron algorithms with O (1) complexity using space subdivision [J]. AIP Conference Proceedings, 2016, 1738 (1). |
| [12] | Wang Wei, Gong Shuiqing, Li Pei Lin, Chui Mingwei. Research on Convex Polyhedron Collision Detection Algorithm Based on Improved Particle Swarm Optimization [P]. mems-12, 2012. |
| [13] | 魏延生, 张树清, 李华朋, 丁小辉, 刘照. 基于点圆理论的2D/3D点包含高效判定 [J]. 中国科学院大学学报, 2018, 35 (03): 353-361. |
| [14] | 翟艳, 徐卫亚, 张强. 点与多边形或多面体的拓扑关系判断 [J]. 计算机工程与设计, 2015, 36 (04): 972-976. DOI: 10.16208/j.issn1000-7024.2015.04.026. |
| [15] | 章磊, 何芬, 李鸿赟. 一种基于奇异射线法检测点在多边形内的方法 [J]. 计算机应用研究, 2020, 37 (S2): 133-135. |
| [16] | 章磊, 何芬, 李鸿赟. 一种基于空间位置进行警情高发统计的方法[J]. 科技与创新, 2021 (01): 60-61+63. DOI: 10.15913/j.cnki.kjycx.2021.01.020. |
| [17] | 张洪, 武威, 关晓飞, 张迎宾, 郑路, 武艳强, 陈光齐. 基于局部凸分解的一般多面体接触搜索方法 [J]. 岩石力学与工程学报, 2018, 37 (12): 2709-2720. |
