Method for judging the position relation between points and closed graphs through a differential ray method

Abstract

The invention provides a method for rapidly judging the relation between points and polygons. A traditional ray method is greatly improved. A differential idea is utilized to convert a graph into a polygon formed by point connection, a data structure capable of being quickly retrieved is newly built to store information of the points, and rays of a traditional ray method are converted into rays ofa traditional ray method. Line segment relation judgment and conversion into to-be-checked point The values between the data structures are searched and compared to obtain the intersection times of the rays and the graphs. according to the parity of the value, obtaining the position relation between the point to be checked and the polygon through a general rule of a ray method. The time complexity of the method is O (1), the method has no correlation with the number N of edges, and the performance of the method is greatly improved compared with that of a traditional method in calculation occasions with complex graphs and high precision requirements.

Description

technical field [0001] The invention relates to a method for quickly identifying the positional relationship between a point on a map and an arbitrary closed figure in a geographic information system (GIS) application. Background technique [0002] Determine whether the point is inside or outside the polygonal area. The acquisition of this positional relationship is an important technology in the fields of navigation, high-precision positioning, and automatic driving. It is widely used in transportation and scientific research; for example, the rental of shared bicycles and shared cars In business activities, it is necessary to determine whether a bicycle or car has entered a no-parking area. Once it is judged that the user has entered the no-parking area and the user is about to park, the operating company needs to remind the user to leave by means of prompting an alarm or failing to end the business. [0003] Generally, the determination of the relationship between points ...

AI Technical Summary

Problems solved by technology

[0007] For a polygon with N sides, the above-mentioned traditional ray method needs to calculate each side and ray to determine whether they intersect. The N sides must be compared one by one, and the time complexity is O(N); Inspur Communication Information System Co., Ltd. application The "201510255047.7" patent and the "CN201810029493.X" patent applied by Alibaba Group Holding Co., Ltd. have improved the above-mentioned ray method, but they have not avoided the judgment of points or line segments one by one, and the complexity has not been optimized by orders of magnitude. Shanghai Zhuo The "201610242654.4" patent applied by Yi Technology Co., Ltd. has improved the ray method to a large extent, and the time complexity has been reduced to O(㏒N), which is an excellent solution

Images