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

A technology of closed graphics and ray method, which is applied in the direction of structured data retrieval, geographic information database, etc., can solve the problems of complexity without order-of-magnitude optimization, without avoiding one-by-one judgment, etc.

Inactive Publication Date: 2019-04-05
高静
View PDF3 Cites 6 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

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

Method used

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
View more

Image

Smart Image Click on the blue labels to locate them in the text.
Viewing Examples
Smart Image
  • Method for judging the position relation between points and closed graphs through a differential ray method
  • Method for judging the position relation between points and closed graphs through a differential ray method
  • Method for judging the position relation between points and closed graphs through a differential ray method

Examples

Experimental program
Comparison scheme
Effect test

Embodiment Construction

[0020] Any closed figures in the two-dimensional X-Y Cartesian coordinate system, such as rectangles, triangles, rhombuses, parallelograms, circles, ellipses, and other irregular closed figures, are composed of curved line segments (a straight line segment is a part of a curved line segment) a special form). The curve segment can be simulated by the differential method by connecting specific points on the curve (hereinafter referred to as the on-line points) one by one. The characteristics of these points are: equidistant △x on the X-axis. According to the idea of ​​the limit of differential calculus, as long as △x is small enough, lim (△x—>0), the connection line of a specific point will infinitely approach the original curve. A polygon formed by connecting lines with specific points will be closer to the original shape. The present invention will be described below by taking a typical closed figure on the two-dimensional coordinate system: an ellipse as an example. as atta...

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to view more

PUM

No PUM Login to view more

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 ...

Claims

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to view more

Application Information

Patent Timeline
no application Login to view more
Patent Type & Authority Applications(China)
IPC IPC(8): G06F16/29
Inventor 高静
Owner 高静
Who we serve
  • R&D Engineer
  • R&D Manager
  • IP Professional
Why Eureka
  • Industry Leading Data Capabilities
  • Powerful AI technology
  • Patent DNA Extraction
Social media
Try Eureka
PatSnap group products

Browse by: Latest US Patents, China's latest patents, Technical Efficacy Thesaurus, Application Domain, Technology Topic.

© 2024 PatSnap. All rights reserved.Legal|Privacy policy|Modern Slavery Act Transparency Statement|Sitemap