基于减治的点与凸多边形位置关系判定算法

Judgment Algorithm for the Position Relationship between Point and Convex Polygon Based on Reduction and Rule

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

Many location-based services used by people involve the problem of determining the positional relation between points and convex polygons. The limited resources of mobile devices make lightweight algorithms designed to resolve the above issue to be an urgent problem. Therefore, finding a lightweight decision algorithm is necessary, and reducing the number of edges that operate on points has become a feasible idea. Therefore, a lightweight algorithm of position relationship determination between a point and a convex polygon is proposed based on reduction and governance. The algorithm includes: region division, region judgment of a point, and position relationship judgment between a point and a convex polygon. The algorithm converts the position relationship judgment between a point and a convex polygon into the position relationship judgment between the point and a part of the convex polygon, which reduces the time cost. By sorting vertexes of the part of the convex polygon beforehand, the time cost of our algorithm can achieve O(log√n). This algorithm can be applied to determine quickly the position relationship between points and convex polygons in scenarios where mobile device resources are limited.