Research And Engineering Application Of Geo-fence Algorithm Based On Linear Equation

Many important pieces of information that people acquire and use in the Internet of Everything era,whether in daily life or scientific research,are related to their geographic location.Geographical location will become one of the most commonly used information elements in today’s convenient life and the future intelligent world.Location-Based Service（LBS）refers to a service which is carried out by acquiring the geographical location of devices.Geo-fence is a new LBS application.It can actively detect the entry or departure of fence-associated users,and provide real-time,location-based related services for fence-associated users.It is widely used in security monitoring,environmental protection,smart home,and other fields.The most fundamental and critical point in the application of geo-fencing technology is how to judge the Location Relationship between the fence-associated users and the geo-fences,and the judgment can be abstractly described as a common problem in computational geometry--Point-in-Polygon problem.The algorithm used to study the Point-in-Polygon problem is known as a Point-in-Polygon algorithm,which serves as the foundation for related algorithms in a variety of research fields.Although a large number of Point-in-Polygon algorithms have been proposed,the focus of such algorithms remains on how to provide faster and more robust judgments.The ray method,for example,is the basic algorithm of point inclusion algorithms.And because of its simple principle and applicability to a variety of polygons,it is frequently used as a benchmark algorithm for comparison with other Point-in-Polygon algorithms.However,in some critical cases,the ray method will misjudge.Based on the idea of solving linear equations,this paper transforms the problem of judging the position relation between points and polygons into that between points and lines,and proposes a geo-fence algorithm based on linear equation.The algorithm is divided into two steps:（i）Pre-processing.Combining the convex decomposition technology and the idea of BSP tree,the geo-fence of simple non-convex polygon is preprocessed to eliminate the concave points of the original polygon and divide it into multiple sub-convex polygons to form a BSP tree.All the leaf nodes of the BSP tree are sub-convex polygons,while the non-leaf nodes are segmentation lines.（ii）Point inclusion judgment.Traverses the BSP tree preprocessed in the first step,quickly locates the sub-convex polygon that the point to be determined may be in,and uses linear equation algorithm to make point inclusion judgment based on the sub-convex polygon.Based on the above research,this paper adopts Spring Boot,My SQL,Amap API and other technologies to build a comprehensive position service platform based on the Bei Dou + 5G.The linear equation algorithm is used in the geo-fence monitoring module to achieve "instant" notification of terminals（devices）entry or departure the polygon fence.The practical test results show that the linear equation algorithm’s principle is simple,can effectively deal with high-precision geographic coordinate data,and the algorithm has good robustness,which is of reference value to the research of point inclusion algorithm and other related application scenarios.