摘要
人们利用移动设备享用的很多位置服务涉及点与凸多边形位置判定问题.移动设备资源受限的客观条件使得设计轻量级算法解决该问题成为当务之急.寻找一种轻量级的判定算法是必要的,减少与点进行操作的边的条数成为一种可行思路.因此,基于减治思想提出了一种轻量级点与凸多边形位置关系判定算法.算法包括三个模块:区域划分、点的区域判断和点与凸多边形的位置关系判断.算法通过将点与凸多边形的位置关系判断转化为点与凸多边形的部分区域位置关系判断,减少了时间开销.通过将凸多边形的顶点编序并划分为多个子区域作为算法的预处理部分,算法的时间开销可以达到O(log√n).本算法可以适用在移动设备资源受限的场景下快速进行点与凸多边形的位置关系判断.
基金项目
国家自然科学基金(61702168)
国家自然科学基金(62072134)
广西可信软件重点实验室研究项目(Kx202014)
维普
万方数据