CN116303519A - A route query method, device, electronic equipment, and storage medium - Google Patents

Abstract

The application discloses a path query method and device, electronic equipment and a storage medium. The method comprises the following steps: acquiring a grid filling result of a target area, wherein the grid filling result comprises filling grids under a plurality of grid levels; inquiring a pre-constructed path database according to the sequence from high to low of a grid level, and acquiring a target grid path with grid nodes common to the filling grid, wherein the path database comprises a plurality of equipment paths, and each equipment path comprises a plurality of grid paths under a preset grid level; and obtaining a device path passing through the target area according to the target grid path. According to the technical scheme, the complexity of judging and calculating the points in the polygon can be reduced, and the path query is rapidly realized.

Description

A route query method, device, electronic equipment, and storage medium

technical field

The present application relates to the technical field of data processing, and in particular to a path query method, device, electronic equipment, and storage medium.

Background technique

At present, in the research of location-based services, it often involves the determination and calculation of a point within a polygon. The existing methods mainly use the vector product method, ray method and area method. The vector product method is to connect lines from the test point to each vertex of the polygon, and form multiple vectors. If the sum of the angles formed by these multiple vectors is equal to 360°, the test point is in the polygon, otherwise it is in the polygon. outside. The ray method is to send a ray from the test point and count the number of intersections it has with the sides of the polygon. If the number of intersections is even, the test point is outside the polygon; otherwise, it is inside the polygon. The area method is to connect the test point to each vertex of the polygon to form multiple triangles. If the area of all triangles is equal to the area of the polygon, the test point is inside the polygon, otherwise it is outside the polygon.

The above-mentioned calculation methods in the prior art either have high time complexity, space complexity or high algorithm complexity, occupy a relatively high rate of calculation resources, and take a long time.

Contents of the invention

Based on the above-mentioned problems in the prior art, the embodiments of the present application provide a path query method, device, electronic equipment, and storage medium to reduce the complexity of calculation for determining whether a point is within a polygon, and quickly implement path query.

The embodiment of the application adopts the following technical solutions:

In the first aspect, the embodiment of the present application provides a path query method, the method comprising:

Obtaining a grid filling result of the target area, where the grid filling result includes filling grids under multiple grid levels;

Query the pre-built path database according to the order of the grid level from high to low, and obtain the target grid path that has a common grid node with the filled grid. The path database includes multiple equipment paths, and each equipment path includes multiple Grid paths under preset grid levels;

A device path passing through the target area is obtained according to the target grid path.

Optionally, the plurality of preset grid levels include a plurality of levels between the preset highest grid level to the preset lowest grid level, and the plurality of grid levels include the highest grid level that can be filled to the preset Assuming multiple levels between the lowest grid level, before querying the pre-built path database according to the order of the grid level from high to low, the method further includes:

determining whether the highest fillable grid level is higher than the preset highest grid level;

If it is higher, the path database is queried with the preset highest grid level as the first grid level; if not higher, the path database is queried with the highest fillable grid level as the first grid level .

Optionally, the highest fillable grid level of the target area is obtained through the following steps:

Obtain the boundary point position of the target area;

Perform grid filling on the target area according to the position of the boundary point of the target area and the grid filling query method provided by the H3 grid system, and obtain the filling result of the target area at each grid level, the filling result Include the filling success information or filling failure information of the grid level;

The highest fillable grid level is obtained according to the filling result of each grid level.

Optionally, the path database includes a cache database and a persistent database, and the pre-built path database is queried according to the order of the grid level from high to low to obtain a target grid that has a common grid point with the filled grid path, including:

Querying the cache database according to the order of the grid level from high to low;

If the target grid path does not exist in the cache database, query the persistent database in descending order of grid levels.

Optionally, build the route database through the following steps:

Obtain the track data of the device and the H3 geographic index corresponding to each track point;

According to the H3 geographic index corresponding to each track point, the grid path of the device under multiple preset grid levels is obtained.

Optionally, the obtaining grid paths of the device under multiple preset grid levels according to the H3 geographic index corresponding to each track point includes:

Collecting adjacent track points with the same H3 geographic index on the track data;

According to the H3 geographic index of the collected track points, the grid path of the device under multiple preset grid levels is obtained.

In the second aspect, the embodiment of the present application also provides a path query device, the device includes:

an area filling unit, configured to obtain a grid filling result of the target area, the grid filling result including filling grids under multiple grid levels;

a path query unit, configured to query a pre-built path database according to the order of the grid level from high to low, and obtain a target grid path that has a common grid node with the filled grid, the path database includes a plurality of device paths, Each device path includes grid paths under multiple preset grid levels;

A route determining unit, configured to obtain a device route passing through the target area according to the target grid route.

Optionally, the plurality of preset grid levels include a plurality of levels between the preset highest grid level and the preset lowest grid level, and the path query unit is used to perform a sequence of grid levels from high to low. Before querying the pre-built route database, determine whether the highest grid level that can be filled is higher than the preset highest grid level; if higher, use the preset highest grid level as the first grid level query If it is not higher than the path database, query the path database with the highest grid level that can be filled as the first grid level.

In a third aspect, the embodiment of the present application further provides an electronic device, including:

processor; and

A memory arranged to store computer-executable instructions which, when executed, cause the processor to perform a path-finding method.

In a fourth aspect, the embodiment of the present application further provides a computer-readable storage medium, the computer-readable storage medium stores one or more programs, and when the one or more programs are executed by an electronic device including multiple application programs , causing the electronic device to execute the path query method.

The above-mentioned at least one technical solution adopted by the embodiment of the present application can achieve the following beneficial effects: the embodiment of the present application pre-builds a path database, and the device paths in the path database include grid paths under a plurality of preset grid levels. When , the filling grids of multiple grid levels corresponding to the target area are obtained first, and then the path database is queried according to the order of the grid levels from high to low, and the target grid path with the same grid node as the filling grid is obtained. The device path through the target area can be obtained through the target grid path. The embodiment of the present application converts the judgment calculation of the point within the polygon into the query of the common grid node, which greatly reduces the complexity of the algorithm, and the device path passing through the target area can be quickly determined through the database query operation, which significantly saves calculation resource.

Description of drawings

The drawings described here are used to provide a further understanding of the application and constitute a part of the application. The schematic embodiments and descriptions of the application are used to explain the application and do not constitute an improper limitation to the application. In the attached picture:

Fig. 1 is a schematic diagram of a kind of earth grid shown in the embodiment of the present application;

FIG. 2 is a flow chart of a path query method shown in the embodiment of the present application;

FIG. 3 is a schematic diagram of a grid path shown in an embodiment of the present application;

FIG. 4 is a schematic diagram of the interactive process of the path query system shown in the embodiment of the present application;

FIG. 5 is a schematic diagram of the target grid path query process shown in the embodiment of the present application;

FIG. 6 is a schematic structural diagram of a route query device shown in an embodiment of the present application;

FIG. 7 is a schematic structural diagram of an electronic device in an embodiment of the present application.

Detailed ways

In order to make the purpose, technical solution and advantages of the present application clearer, the technical solution of the present application will be clearly and completely described below in conjunction with specific embodiments of the present application and corresponding drawings. Apparently, the described embodiments are only some of the embodiments of the present application, rather than all the embodiments. Based on the embodiments in this application, all other embodiments obtained by persons of ordinary skill in the art without making creative efforts belong to the scope of protection of this application.

Before introducing the embodiments of the present application, a brief introduction to the current H3 grid system is given to facilitate the understanding of various embodiments of the present application.

The H3 grid system is a hexagonal hierarchical index grid system, as shown in Figure 1, which approximates the earth as an icosahedron, and each face of the spherical dodecahedron has the same arrangement of hexagon. The H3 grid system has a spatial index granularity of 16 grid levels as shown in Table 1:

grid level Hexagon side length (km) grid level Hexagon side length (km) 0 1107.712591 8 0.461354684 1 418.6760055 9 0.174375668 2 158.2446558 10 0.065907807 3 59.81085794 11 0.024910561 4 22.6063794 12 0.009415526 5 8.544408276 13 0.003559893 6 3.229482772 14 0.001348575 7 1.220629759 15 0.000509713

Table 1

It can be seen from Table 1 that the granularity at the lowest grid level (that is, the 15th layer) is the finest, and the average side length of each grid is 0.509713 meters, and the granularity at the highest grid level (that is, the 0th layer) is the coarsest. The average side length of each grid is 1107.712591 km. As shown in Figure 1, each parent grid corresponds to 7 sub-grids, and the H3 geographic index occupies a maximum of 63 bits. Its structure is shown in Table 2:

Table 2

It can be seen from Table 2 that for grids with higher grid levels (such as layer 0, layer 1, layer 2, etc.), many bits behind are unnecessary, and path query directly based on the H3 geographic index will It takes up more resources and affects query efficiency.

The technical solutions provided by various embodiments of the present application will be described in detail below in conjunction with the accompanying drawings.

This application provides a method for determining and calculating a point within a polygon, which can be used in many scenarios. For example, in a geographic information system, the area is limited by polygons for roads, buildings, parks, etc. in an area. When locating certain targets, such as whether a certain car passes a certain road, or is located in a certain park, etc., this application can be used for quick query. Or when the rainstorm floods an area, the area covered by rainwater can be expressed by polygons, and then using this application can quickly know which roads are not covered by rainwater and are safe.

The execution subject of the path query method provided by the embodiment of the present application may be a computing device, server, or cloud platform; the execution subject of the embodiment of the present application may also be software or hardware. Please refer to FIG. 2 . FIG. 2 introduces a path query method provided in the embodiment of the present application by taking the execution subject as a server as an example. As shown in Figure 2, a route query method provided in the embodiment of the present application may include the following steps S210 to S230:

Step S210, acquiring a grid filling result of the target area, the grid filling result including filling grids under multiple grid levels.

In order to improve the route query efficiency, this application obtains the filled grids of the target area at multiple grid levels. The target area refers to the geographical area of interest, which can be streets, supermarkets, communities, islands, etc. In practical applications, this application Field technicians can select the corresponding target area according to business needs.

As shown in Figure 1, the number of grids at the high grid level is much lower than that at the low grid level, so that when performing database queries, the grid level can be quickly searched in the order of the grid level from high to low. Inquire.

The multiple grid levels include multiple levels between the highest fillable grid level and the preset lowest grid level, where the highest fillable grid level refers to the largest regular hexagon that can be successfully filled into the target area The grid level of the target area, that is, the grid level corresponding to the largest inscribed regular hexagon in the target area is the highest grid level corresponding to the target area. Assuming that the largest regular hexagon that can be filled in the target area is the Lth (L is a positive integer less than 15) grid level, and the preset minimum grid level is the 15th grid level, then this application obtains the Lth grid level, the L+1 grid level . . . , the filling grid of the 15th grid level, the filling grid of each grid level may include one or more hexagonal grids.

Step S220, query the pre-built path database according to the order of the grid level from high to low, and obtain the target grid path that has a common grid node with the filled grid. The path database includes multiple device paths, and each device The paths include grid paths under multiple preset grid levels.

This application builds a route database for devices with planned routes in advance, and the device routes in the route database can be understood as planned routes of devices or distribution routes of devices. The device types in this application are related to business scenarios, including but not limited to vehicles, ships, drones, robots, etc.

Wherein, the path database includes multiple device paths, and each device path is represented by a grid path. As shown in FIG. 3 , in order to improve the route query efficiency, when constructing the grid path, the grid paths under multiple grid levels from the preset highest grid level to the preset lowest grid level are also constructed. The preset highest grid level and the preset lowest grid level can be reasonably set according to the application scenario and application requirements, for example, the preset highest grid level is level 10 or 11, and the preset lowest grid level is level 14 or Level 15.

In this way, when querying the database, the grid path at the same grid level in the database can be queried from the highest grid level that can be filled. If there is no common grid node between the grid path at the same grid level and the filled grid, then Query whether there is a common grid node between the grid path and the filling grid under the next grid level according to the query order, until the target grid path is obtained.

Step S230, obtaining a device path passing through the target area according to the target grid path.

From the path query method shown in Figure 2, it can be seen that this embodiment pre-builds a path database, and the device paths in the path database include grid paths under multiple preset grid levels. When starting the path query, first obtain the corresponding The filled grids of multiple grid levels, and then query the path database according to the order of the grid levels from high to low, and obtain the target grid path with the same grid node as the filled grid, so that it can be obtained through the target grid path The device path through the target zone. This embodiment converts the judgment calculation of the point within the polygon into the query of the common grid node, which greatly reduces the complexity of the algorithm, and can quickly determine the device path passing through the target area through the database query operation, which significantly saves computing resources. .

As mentioned above, the grid filling result of the target device includes filling grids at multiple levels from the highest grid level that can be filled to the preset lowest grid level, and the device paths in the path database include The grid paths under multiple levels from the grid level to the preset lowest grid level. In some embodiments of the present application, before querying the pre-built path database according to the order of the grid level from high to low, the method Also includes:

determining whether the highest fillable grid level is higher than the preset highest grid level;

If higher, querying the route database with the preset highest grid level as the first grid level;

If not, query the path database with the highest fillable grid level as the first grid level.

In this embodiment, before querying the path database, the relationship between the highest fillable grid level corresponding to the target area and the preset highest grid level corresponding to the device path should be judged first, and the first grid for database query should be determined according to the relationship between the two Hierarchy to avoid invalid queries and improve query efficiency.

In some implementable solutions of this embodiment, the highest fillable grid level of the target area may be obtained through the following steps:

Obtain the boundary point position of the target area;

Carry out grid filling on the target area according to the position of the boundary point of the target area and the grid filling query method of the H3 grid system, and obtain the filling result of the target area at each grid level, and the filling result includes Filling success information or filling failure information of the grid level;

The highest fillable grid level is obtained according to the filling result of each grid level.

Assuming that the target area is a quadrilateral, input the coordinates of the four vertices of the quadrilateral into the grid filling query method h3.polyfillAddress() of the H3 grid system. Through this method, the filling result of each grid level can be queried. If the hexagonal grid at the grid level can be filled into the target area, then this method gives the filling success information and the index value of each filled grid. If the hexagonal grid of a certain grid level cannot be filled into the target area, the method will give a filling failure message. This quickly determines the highest mesh level at which the target area can be successfully filled.

The embodiment of the present application shows an implementation method of obtaining the highest grid level of the grid that can be filled. In other embodiments, it can also be based on the largest inscribed regular hexagon of the target area and the regular hexagon of each grid level. The side length relationship of the polygon is obtained to obtain the highest grid level that can be filled.

In some embodiments of the present application, as shown in FIG. 4 , the path database includes a cache database and a persistent database. The cache database is, for example, a Redis database, and the persistent database is, for example, a Mysql database.

Correspondingly, in the above step S120, query the pre-built path database according to the order of the grid level from high to low, and obtain the target grid path that has a common grid node with the filled grid, including:

Querying the cache database according to the order of the grid level from high to low;

If the target grid path does not exist in the cache database, query the persistent database in descending order of grid levels.

In this embodiment, the cache database is queried first, and then the persistent database is queried when there is no target grid path in the cache database, which can reduce the frequency of read operations with the persistent database and improve path query efficiency to a certain extent.

In practical applications, the cache database should also be updated regularly, for example, an expiration time is set for the device path in the cache database, and when the expiration time is reached, the expired device path is deleted from the cache database. When the target grid path is obtained from the persistent database, the device path of the target grid path may be saved in the cache database.

In order to comprehensively understand the route query method of the embodiment of the present application, the vehicle allocation is taken as an example for illustration below in conjunction with FIG. 4 and FIG. 5 .

It is assumed that the vehicle management platform manages all registered service vehicles, such as patrol cars, sweepers, garbage collection vehicles and other vehicles. Each service vehicle has a pre-assigned driving route. When allocating service vehicles on the vehicle management platform, it is necessary to query the driving route of the service vehicle, and allocate vehicles reasonably based on the query results.

As shown in Figure 4, each service vehicle can be assigned a driving route through the client. In the vehicle registration stage, the server obtains the driving route of each service vehicle through the client, and can construct each service vehicle according to the trajectory data of the driving route. The grid path under the 10th to 14th grid level, and the grid path of each service vehicle is written into the Mysql database for storage.

Suppose the target area is the street A to be cleaned. In this way, when the street A to be cleaned needs to be cleaned, the filled grid of the street A to be cleaned should be obtained, and the Redis database can be queried according to the filled grid. If the target grid path is not found, then Query the Mysql database, and assign the service vehicles of the queried target grid path to the street A to be cleaned for cleaning.

Assuming that the highest grid level corresponding to the street A to be cleaned is the 12th grid level, the filling grids of each grid level under the 12th to 14th grid levels are constructed, and the filling grids of each grid level can be Contains one or more hexagonal grids. When multiple hexagonal grids are included, multiple hexagonal grids can be combined according to certain rules, such as according to H3 geographic index rules, or according to hexagonal grids Combination of the distribution state, for example, in a clockwise direction. Of course, it can also be combined in a tree structure. The embodiment of the present application does not limit the combination manner of multiple filling grids.

As shown in Figure 5, first query the grid path of the 12th grid level in the path database according to the filling grid of the 12th grid level of the street A to be cleaned. grid node, the sweeper corresponding to the grid path is the target sweeper. Otherwise, query the grid path of the 13th grid level in the path database according to the filling grid of the 13th grid level of the street A to be cleaned, if there is no grid path with a common grid node with the filling grid, Then continue to query the grid path of the 14th grid level in the route database according to the filling grid of the 14th grid level of the street A to be cleaned, if there is still no grid with the same grid node as the filling grid at this time path, there is currently no unassigned sweeper.

In some embodiments of the present application, the route database may be constructed through the following steps:

Obtain the track data of the device and the H3 geographic index corresponding to each track point;

According to the H3 geographic index corresponding to each track point, the grid path of the device under multiple preset grid levels is obtained.

As shown in Figure 4, the server obtains the trajectory data of the device through the client. The device is such as a vehicle, ship, drone, robot, etc. The trajectory data can be obtained through the positioning system of the device, and the corresponding H3 geographic location can be obtained according to the latitude and longitude information of the trajectory point. Index, the H3 geographic index has a data structure in the form of Table 2. Through the H3 geographic index, the grid level corresponding to the track point and the corresponding base grid can be obtained, so that the device can be obtained according to the H3 geographic index corresponding to each track point. Grid paths at multiple preset grid levels.

In some possible implementations of this embodiment, according to the H3 geographic index corresponding to each track point, the grid path of the device under multiple preset grid levels is obtained, including:

Collecting adjacent track points with the same H3 geographic index on the track data;

According to the H3 geographic index of the collected track points, the grid path of the device under multiple preset grid levels is obtained.

For example, as shown in Figure 3, assuming that the grid level corresponding to all trajectory points is the 15th grid level, the adjacent trajectory points with the same index value of the base grid on the trajectory data are collected, so that after the aggregation Each trajectory point of corresponds to a base grid, and the grid path of the 15th grid level can be obtained according to the collected trajectory point sequence. Then obtain the parent grid corresponding to each grid node in the grid path of the 15th grid level, gather the adjacent parent grids with the same index value, and obtain the grid of the 14th grid level according to the aggregation result The path, and the grid path of a higher grid level can be obtained according to this.

The embodiment of the present application also provides a path query device 600. As shown in FIG. 6, a schematic structural diagram of a path query device in the embodiment of the present application is provided. The query unit 620 and the path determination unit 630, wherein:

An area filling unit 610, configured to obtain a grid filling result of the target area, the grid filling result including filling grids under multiple grid levels;

The path query unit 620 is configured to query the pre-built path database according to the order of the grid level from high to low, and obtain a target grid path that has a common grid node with the filled grid, and the path database includes multiple device paths , each device path includes grid paths under multiple preset grid levels;

A path determination unit 630, configured to obtain a device path passing through the target area according to the target grid path.

In one embodiment of the present application, the plurality of preset grid levels include a plurality of levels between the preset highest grid level and the preset lowest grid level, and the plurality of grid levels include fillable For multiple levels between the highest grid level and the preset lowest grid level, the path query unit 620 is used to determine the highest grid level that can be filled before querying the pre-built path database according to the grid level from high to low. Whether the grid level is higher than the preset highest grid level; if higher, then use the preset highest grid level as the first grid level to query the path database; if not higher, use the fillable The highest grid level is the first grid level to query the route database.

In one embodiment of the present application, the area filling unit 610 is configured to obtain the highest fillable grid level of the target area through the following steps:

Obtain the position of the boundary point of the target area; perform grid filling on the target area according to the position of the boundary point of the target area and the grid filling query method provided by the H3 grid system, and obtain the grid level of the target area at each grid level The filling result of the grid level includes the filling success information or filling failure information of the grid level; the highest grid level that can be filled is obtained according to the filling result of each grid level.

In one embodiment of the present application, the path database includes a cache database and a persistent database, and the path query unit 620 is configured to query the cache database in descending order of the grid level; if there is no If the target grid path exists, the persistent database is queried in order of grid levels from high to low.

In an embodiment of the present application, the path query device 600 further includes an initialization unit;

The initialization unit is used to build the path database through the following steps:

Obtain the track data of the device and the H3 geographic index corresponding to each track point; obtain the grid path of the device under multiple preset grid levels according to the H3 geographic index corresponding to each track point.

In one embodiment of the present application, the initialization unit is also used to collect adjacent track points with the same H3 geographic index on the track data; The grid path under the default grid hierarchy.

It can be understood that the above-mentioned route query device can implement each step of the route query method provided in the foregoing embodiments, and relevant explanations about the route query method are applicable to the route query device, and will not be repeated here.

Fig. 7 is a schematic structural diagram of an electronic device according to an embodiment of the present application. Please refer to FIG. 7 , at the hardware level, the electronic device includes a processor, and optionally also includes an internal bus, a network interface, and a memory. Wherein, the memory may include a memory, such as a high-speed random-access memory (Random-Access Memory, RAM), and may also include a non-volatile memory (non-volatile memory), such as at least one disk memory. Of course, the electronic device may also include hardware required by other services.

The processor, the network interface and the memory can be connected to each other through an internal bus, which can be an ISA (Industry Standard Architecture, industry standard architecture) bus, a PCI (Peripheral Component Interconnect, peripheral component interconnection standard) bus or an EISA (Extended Industry StandardArchitecture, extended industry standard architecture) bus, etc. The bus can be divided into address bus, data bus, control bus and so on. For ease of representation, only one double-headed arrow is used in FIG. 7 , but it does not mean that there is only one bus or one type of bus.

Memory for storing programs. Specifically, the program may include program code, and the program code includes computer operation instructions. Storage, which can include internal memory and nonvolatile storage, provides instructions and data to the processor.

The processor reads the corresponding computer program from the non-volatile memory into the memory and then runs it, forming a trajectory fusion device on a logical level. The processor executes the program stored in the memory, and is specifically used to perform the following operations:

Obtaining a grid filling result of the target area, where the grid filling result includes filling grids under multiple grid levels;

Query the pre-built path database according to the order of the grid level from high to low, and obtain the target grid path that has a common grid node with the filled grid. The path database includes multiple equipment paths, and each equipment path includes multiple Grid paths under preset grid levels;

A device path passing through the target area is obtained according to the target grid path.

The above-mentioned method performed by the path query device disclosed in the embodiment shown in FIG. 1 of the present application may be applied to a processor or implemented by the processor. A processor may be an integrated circuit chip with signal processing capabilities. In the implementation process, each step of the above method can be completed by an integrated logic circuit of hardware in a processor or an instruction in the form of software. Above-mentioned processor can be general-purpose processor, comprises central processing unit (Central Processing Unit, CPU), network processor (Network Processor, NP) etc.; It can also be digital signal processor (Digital Signal Processor, DSP), ASIC (Application Specific Integrated Circuit, ASIC), field programmable gate array (Field-Programmable Gate Array, FPGA) or other programmable logic devices, discrete gate or transistor logic devices, discrete hardware components. Various methods, steps, and logic block diagrams disclosed in the embodiments of the present application may be implemented or executed. A general-purpose processor may be a microprocessor, or the processor may be any conventional processor, or the like. The steps of the method disclosed in connection with the embodiments of the present application may be directly implemented by a hardware decoding processor, or implemented by a combination of hardware and software modules in the decoding processor. The software module can be located in a mature storage medium in the field such as random access memory, flash memory, read-only memory, programmable read-only memory or electrically erasable programmable memory, register. The storage medium is located in the memory, and the processor reads the information in the memory, and completes the steps of the above path query method in combination with its hardware.

The electronic device can also execute the method performed by the route query device in FIG. 1, and realize the functions of the route query device in the embodiment shown in FIG. 1, which will not be repeated in this embodiment of the present application.

The embodiment of the present application also provides a computer-readable storage medium, the computer-readable storage medium stores one or more programs, and the one or more programs include instructions, and when the instructions are executed by an electronic device including a plurality of application programs , the electronic device can be made to execute the method performed by the path query device in the embodiment shown in Figure 1, and specifically perform the following operations:

Obtaining a grid filling result of the target area, where the grid filling result includes filling grids under multiple grid levels;

Query the pre-built path database according to the order of the grid level from high to low, and obtain the target grid path that has a common grid node with the filled grid. The path database includes multiple equipment paths, and each equipment path includes multiple Grid paths under preset grid levels;

A device path passing through the target area is obtained according to the target grid path.

Those skilled in the art should understand that the embodiments of the present invention may be provided as methods, systems, or computer program products. Accordingly, the present invention can take the form of an entirely hardware embodiment, an entirely software embodiment, or an embodiment combining software and hardware aspects. Furthermore, the present invention may take the form of a computer program product embodied on one or more computer-usable storage media (including but not limited to disk storage, CD-ROM, optical storage, etc.) having computer-usable program code embodied therein.

The present invention is described with reference to flowchart illustrations and/or block diagrams of methods, apparatus (systems), and computer program products according to embodiments of the invention. It should be understood that each procedure and/or block in the flowchart and/or block diagram, and a combination of procedures and/or blocks in the flowchart and/or block diagram can be realized by computer program instructions. These computer program instructions may be provided to a general purpose computer, special purpose computer, embedded processor, or processor of other programmable data processing equipment to produce a machine such that the instructions executed by the processor of the computer or other programmable data processing equipment produce a An apparatus for realizing the functions specified in one or more procedures of the flowchart and/or one or more blocks of the block diagram.

These computer program instructions may also be stored in a computer-readable memory capable of directing a computer or other programmable data processing apparatus to operate in a specific manner, such that the instructions stored in the computer-readable memory produce an article of manufacture comprising instruction means, the instructions The device realizes the function specified in one or more procedures of the flowchart and/or one or more blocks of the block diagram.

These computer program instructions can also be loaded onto a computer or other programmable data processing device, causing a series of operational steps to be performed on the computer or other programmable device to produce a computer-implemented process, thereby The instructions provide steps for implementing the functions specified in the flow chart or blocks of the flowchart and/or the block or blocks of the block diagrams.

In a typical configuration, a computing device includes one or more processors (CPUs), input/output interfaces, network interfaces, and memory.

Memory may include non-permanent storage in computer readable media, in the form of random access memory (RAM) and/or nonvolatile memory such as read only memory (ROM) or flash RAM. Memory is an example of computer readable media.

Computer-readable media, including both permanent and non-permanent, removable and non-removable media, can be implemented by any method or technology for storage of information. Information may be computer readable instructions, data structures, modules of a program, or other data. Examples of computer storage media include, but are not limited to, phase change memory (PRAM), static random access memory (SRAM), dynamic random access memory (DRAM), other types of random access memory (RAM), read only memory (ROM), Electrically Erasable Programmable Read-Only Memory (EEPROM), Flash memory or other memory technology, Compact Disc Read-Only Memory (CD-ROM), Digital Versatile Disc (DVD) or other optical storage, Magnetic tape cartridge, tape magnetic disk storage or other magnetic storage device or any other non-transmission medium that can be used to store information that can be accessed by a computing device. As defined herein, computer-readable media excludes transitory computer-readable media, such as modulated data signals and carrier waves.

It should also be noted that the term "comprises", "comprises" or any other variation thereof is intended to cover a non-exclusive inclusion such that a process, method, article, or apparatus comprising a set of elements includes not only those elements, but also includes Other elements not expressly listed, or elements inherent in the process, method, commodity, or apparatus are also included. Without further limitations, an element defined by the phrase "comprising a ..." does not exclude the presence of additional identical elements in the process, method, article or apparatus comprising said element.

Those skilled in the art should understand that the embodiments of the present application may be provided as methods, systems or computer program products. Accordingly, the present application can take the form of an entirely hardware embodiment, an entirely software embodiment or an embodiment combining software and hardware aspects. Furthermore, the present application may take the form of a computer program product embodied on one or more computer-usable storage media (including but not limited to disk storage, CD-ROM, optical storage, etc.) having computer-usable program code embodied therein.

The above descriptions are only examples of the present application, and are not intended to limit the present application. For those skilled in the art, various modifications and changes may occur in this application. Any modification, equivalent replacement, improvement, etc. made within the spirit and principle of the present application shall be included within the scope of the claims of the present application.

Claims (10)

1. A method of path query, the method comprising:

acquiring a grid filling result of a target area, wherein the grid filling result comprises filling grids under a plurality of grid levels;

inquiring a pre-constructed path database according to the sequence from high to low of a grid level, and acquiring a target grid path with grid nodes common to the filling grid, wherein the path database comprises a plurality of equipment paths, and each equipment path comprises a plurality of grid paths under a preset grid level;

and obtaining a device path passing through the target area according to the target grid path.

2. The path query method of claim 1, wherein the plurality of preset mesh levels includes a plurality of levels between a preset highest mesh level and a preset lowest mesh level, the plurality of mesh levels including a plurality of levels between a fillable highest mesh level and a preset lowest mesh level, the method further comprising, prior to querying a pre-built path database in a mesh level order from high to low:

determining whether the fillable highest grid level is higher than the preset highest grid level;

if the path database is higher than the preset highest grid level, querying the path database by taking the preset highest grid level as a first grid level;

and if the path database is not higher than the first grid level, querying the path database by taking the fillable highest grid level as the first grid level.

3. The path query method of claim 2, wherein the fillable highest grid level of the target area is obtained by:

acquiring the boundary point position of a target area;

grid filling is carried out on the target area according to the boundary point positions of the target area and a grid filling query method provided by an H3 grid system, so that filling results of the target area in each grid level are obtained, and the filling results comprise filling success information or filling failure information of the grid level;

and acquiring the fillable highest grid level according to the filling result of each grid level.

4. The path query method as claimed in claim 1, wherein the path database comprises a cache database and a persistence database, the querying the path database constructed in advance in order of a grid level from high to low, obtaining a target grid path having a common grid point with the filling grid, comprising:

querying the cache database from high to low according to a grid level;

and if the target grid path does not exist in the cache database, querying the persistence database according to a grid level from high to low.

5. The path query method as claimed in claim 1, wherein the path database is constructed by:

acquiring track data of equipment and H3 geographic indexes corresponding to each track point;

and acquiring grid paths of the equipment under a plurality of preset grid levels according to the H3 geographic index corresponding to each track point.

6. The path query method as claimed in claim 5, wherein said obtaining the mesh path of the device under a plurality of preset mesh levels according to the H3 geographic index corresponding to each track point comprises:

collecting adjacent track points with the same H3 geographic index on the track data;

and acquiring grid paths of the equipment under a plurality of preset grid levels according to the H3 geographic indexes of the collected track points.

7. A path query device, the device comprising:

the regional filling unit is used for acquiring a grid filling result of the target region, wherein the grid filling result comprises filling grids under a plurality of grid levels;

the path query unit is used for sequentially querying a pre-constructed path database from high to low according to a grid level, and acquiring a target grid path with grid nodes common to the filling grid, wherein the path database comprises a plurality of equipment paths, and each equipment path comprises a plurality of grid paths under a preset grid level;

and the path determining unit is used for obtaining the equipment path passing through the target area according to the target grid path.

8. The path query device according to claim 7, wherein said plurality of preset mesh levels includes a plurality of levels between a preset highest mesh level and a preset lowest mesh level, a path query unit for determining whether said fillable highest mesh level is higher than said preset highest mesh level before querying a pre-built path database in order of mesh levels from high to low; if the path database is higher than the preset highest grid level, querying the path database by taking the preset highest grid level as a first grid level; and if the path database is not higher than the first grid level, querying the path database by taking the fillable highest grid level as the first grid level.

9. An electronic device, comprising:

a processor; and

a memory arranged to store computer executable instructions which, when executed, cause the processor to perform the path query method of any of claims 1 to 6.

10. A computer readable storage medium storing one or more programs, which when executed by an electronic device comprising a plurality of application programs, cause the electronic device to perform the path query method of any of claims 1-6.

Images