CN107346313B - Method and device for virtual face mining - Google Patents

Abstract

The present invention relates to a method and device for virtual face mining. The method includes: acquiring point of interest data, check-in point data and road network data, integrating the point of interest data and the check-in point data to obtain a point set; acquiring the check-in point set of each point of interest according to the point set, Filter the check-in points in the check-in point set to obtain the correct check-in point set; obtain the minimum circumscribed polygon of the correct check-in point set; perform boundary optimization on the minimum circumscribed polygon of the correct check-in point set according to the road network data . The above method and device for excavating a virtual surface obtain the minimum circumscribed polygon of the check-in point set, and use the road network to optimize the boundary of the minimum circumscribed polygon.

Description

Method and device for virtual face mining

technical field

The invention relates to the fields of information retrieval and information mining, in particular to a method and device for virtual surface mining.

Background technique

With the rapid development of the mobile Internet and the popularization of positioning technologies such as GPS (Globe Positioning System, global satellite positioning system), the geographic location data generated by social network users is increasing at an alarming rate. The user uses the positioning technology on the smart mobile terminal to send his position track to the check-in application website. Since different users may check-in in different places, a large amount of location-based check-in data is generated. How to mine the virtual area of geographic location according to the check-in data of social network users is an urgent problem to be solved.

SUMMARY OF THE INVENTION

Based on this, it is necessary to provide a virtual surface mining method for mining the virtual surface of the geographic location according to the check-in data, which can realize the mining of the virtual surface area of the geographic location according to the user's check-in data.

In addition, it is also necessary to provide a device for virtual surface mining, which can realize virtual surface area mining of geographic location according to the user's check-in data.

A method of virtual face mining, comprising:

Obtaining point-of-interest data, check-in point data and road network data, and integrating the point-of-interest data and check-in point data to obtain a point set;

Obtain the check-in point set of each interest point according to the point set, and filter the check-in points in the check-in point set to obtain the correct check-in point set;

Obtain the minimum circumscribed polygon of the correct check-in point set;

Boundary optimization is performed on the minimum circumscribed polygon of the correct check-in point set according to the road network data.

A device for virtual face excavation, comprising:

an integration module, used for acquiring point-of-interest data, check-in point data and road network data, and integrating the point-of-interest data and check-in point data to obtain a point set;

a screening module, configured to obtain a check-in point set of each interest point according to the point set, and filter the check-in points in the check-in point set to obtain a correct check-in point set;

a virtual surface acquisition module, used for acquiring the minimum circumscribed polygon of the correct check-in point set;

An optimization module, configured to perform boundary optimization on the minimum circumscribed polygon of the correct check-in point set according to the road network data.

The above-mentioned method and device for virtual surface mining, by acquiring interest point data, check-in point data and road network data, integrating the interest point data and the check-in point data to obtain a point set, and filtering the check-in points corresponding to each interest point in the point set The correct check-in point set is obtained, the minimum circumscribed polygon of the check-in point set is obtained, and the boundary of the minimum circumscribed polygon is optimized by using the road network.

Description of drawings

1 is a schematic diagram of the internal structure of a terminal in one embodiment;

2 is a flowchart of a method for virtual surface mining in one embodiment;

FIG. 3 is an example schematic diagram of a point of interest and a check-in point;

Fig. 4 is the schematic diagram of R-Tree instance;

Figure 5 is an example schematic diagram of KR-Tree on the map;

6 is a schematic diagram of an inverted index established according to the POI-based ID of FIG. 5;

Fig. 7 is the KR-Tree index schematic diagram established according to Fig. 5;

8A is a schematic diagram of a leaf node included in each node in one embodiment;

8B is a schematic diagram of adding a new node X in FIG. 8A;

8C is a schematic diagram of the expanded area obtained by traversing each non-leaf node after adding X;

8D is a schematic diagram of selecting node A with the smallest expansion area in FIG. 8C and adding X to A;

Figure 9 is a schematic diagram of the convex hull algorithm;

10 is a structural block diagram of an apparatus for excavating virtual surfaces in one embodiment;

FIG. 11 is a structural block diagram of an apparatus for excavating virtual surfaces in another embodiment.

Detailed ways

In order to make the objectives, technical solutions and advantages of the present invention clearer, the present invention will be further described in detail below with reference to the accompanying drawings and embodiments. It should be understood that the specific embodiments described herein are only used to explain the present invention, but not to limit the present invention.

It will be understood that the terms "first", "second", etc., as used herein, may be used herein to describe various elements, but these elements are not limited by these terms. These terms are only used to distinguish a first element from another element. For example, the first set may be referred to as the second set, and, similarly, the second set may be referred to as the first set, without departing from the scope of this disclosure. Both the first set and the second set are sets, but they are not the same set.

FIG. 1 is a schematic diagram of an internal structure of a terminal in an embodiment. As shown in FIG. 1 , the terminal includes a processor, a non-volatile storage medium, a memory, a display screen and an input device connected through a system bus. The operating system is stored in the non-volatile storage medium of the terminal. The processor is used to provide computing and control capabilities to support the operation of the entire terminal, and the processor is used to execute a method for virtual surface mining, including: acquiring point-of-interest data, check-in point data and road network data, and analyzing the point-of-interest data Integrate with the check-in point data to obtain a point set; obtain the check-in point set of each point of interest according to the point set, filter the check-in points in the check-in point set to obtain the correct check-in point set; obtain the correct check-in point set The minimum circumscribed polygon of ; according to the road network data, the boundary optimization is performed on the minimal circumscribed polygon of the correct check-in point set. The display screen of the terminal can be a liquid crystal display screen or an electronic ink display screen, etc., and the input device can be a touch layer covered on the display screen, a button, a trackball or a touchpad set on the terminal shell, or an external device. Keyboard, trackpad or mouse, etc. The terminal may be a mobile phone, a tablet computer or a personal digital assistant. Those skilled in the art can understand that the structure shown in FIG. 1 is only a block diagram of a partial structure related to the solution of the present application, and does not constitute a limitation on the terminal to which the solution of the present application is applied. More or fewer components are shown in the figures, either in combination or with different arrangements of components.

FIG. 2 is a flowchart of a method for virtual face mining in one embodiment. As shown in Figure 2, a method for virtual surface mining includes:

Step 202: Acquire point-of-interest data, check-in point data, and road network data, and integrate the point-of-interest data and check-in point data to obtain a point set.

In this embodiment, POI (Points Of Interest, points of interest) data can be obtained from various electronic map data. Check-in point data refers to user check-in point data, which can be obtained from social networking websites or service providers of some travel check-in websites, such as instant messaging software, Weibo, Twitter, Foursquare, etc. that provide check-in point data. Road network data can be obtained from electronic map data or four-dimensional maps.

Integrating POI data and check-in data includes sorting, clearing, and unifying structured processing of POI data.

Step 204: Acquire a check-in point set of each point of interest according to the point set, and filter the check-in points in the check-in point set to obtain a correct check-in point set.

In this embodiment, a point of interest may include one or more check-in points, or may not include check-in points. There is an error in the check-in point corresponding to the point of interest. The number of other check-in points in the search rectangle node centered on the check-in point is the thermal value. If the thermal value is less than the thermal value threshold, the The check-in point is the wrong check-in point.

FIG. 3 is a schematic diagram of an example of a point of interest and a check-in point. As shown in Figure 3, P1, P2, and P3 are three points of interest. Multiple check-in points are gathered around the point of interest P1, 2 check-in points around P2, and no check-in point around P3. P is the check-in point far away from P3. Among them, points of interest are represented by blank circles, and check-in points are represented by black circles.

Step 206: Obtain the minimum circumscribed polygon of the correct check-in point set.

In this embodiment, the minimum circumscribed polygon of the correct check-in point set may be the minimum circumscribed rectangle, obtain the latitude and longitude of all check-in points in the correct check-in point set, obtain the maximum and minimum longitude and latitude, obtain the difference between the maximum longitude and the minimum longitude, and obtain the maximum latitude and longitude. The difference from the minimum latitude is used as the length and width of the minimum circumscribed rectangle, respectively.

Step 208: Perform boundary optimization on the minimum circumscribed polygon of the correct check-in point set according to the road network data.

The above-mentioned virtual surface mining method obtains a point set by acquiring interest point data, check-in point data and road network data, integrates the interest point data and the check-in point data to obtain a point set, and filters the check-in points corresponding to each interest point in the point set to obtain the correct value. The minimum circumscribed polygon of the check-in point set is obtained, and the road network is used to optimize the boundary of the minimal circumscribed polygon. The minimal circumscribed polygon is the virtual surface of the point of interest, which realizes the mining of the virtual surface.

In addition, after mining the virtual surface of the point of interest, resource information in the virtual surface of the point of interest can be recommended to the user according to the virtual surface of the point of interest where the user is located.

In one embodiment, the step of integrating the point of interest data and the check-in point data to obtain a point set includes:

(1.1): Organize the POI data;

In this embodiment, the attribute of the point of interest is obtained from the point of interest data. The attributes of the point of interest include an identifier of the point of interest (ID, Identity), name, longitude and latitude, and the like. If there is no check-in point and the number of check-in points is less than or equal to the first threshold, it will be cleared. Prevents indexing during computation, saving time and space. A POI ID is a string used to uniquely represent a POI. The string may include one or more of numbers, letters, and characters.

Organizing POI data includes (1.1.1) and steps (1.1.2):

(1.1.1): Use the first hash set to count check-in points, wherein the key of the first hash set is the identifier of the point of interest, and the key value is the number of check-in points.

The first hash set is used to count the check-in points, the key of the first hash set is the ID of the POI of the string type, and the key value is the number of the check-in points of the integer type. For each check-in point, there is an attribute that is the ID of the POI that it checked in, so all check-in points are scanned, the ID items of the POIs that exist in the first hash set, the count of this item is incremented by 1, and the POIs that do not exist ID, the count is assigned a value of 1, and inserted into the first hash set. The first hash set may be a hash table.

(1.1.2): Scan the POI data, if there is no POI identification key of the current POI or the key value corresponding to the POI identification key of the current POI is less than or equal to the first threshold, clear the current POI, and set the The POI identifiers of the cleared POIs are recorded in the second hash set.

The scanned POI point data, in the created first hash set, if there is no current POI ID key or the count value corresponding to the current POI ID key is less than or equal to the first threshold (such as 2, that is, there are too few check-in points, cannot form a face), clear the current POI. And key the ID of the cleared POI into the second hash set S. As shown in Figure 3, for P2 with too few check-in points in the POI and P3 with no check-in points, and the check-in point p is too far from P3 in the POI, the check-in point p is filtered.

For example, some users may check in at the POI of Tsinghua University within the range of Yuanmingyuan. Such inaccurate check-in points are wrong check-in points and need to be cleared.

(1.2): The attributes of the points of interest and the attributes of the check-in points are unifiedly structured, and the attributes of the unified structuring points of interest and the attributes of the check-in points are recorded in the point set array.

Create a point set array points, and uniformly structure the attributes of POI and check-in points. The uniform structure includes: ID (identity), longitude (longitude), latitude (latitude), type (type), offset _lng , offset _lat , Among them, offset _lng is the longitude of the checked-in POI, and offset _lat is the latitude of the checked-in POI. type is used to distinguish whether the point is a POI or a check-in point. For example, when type is 1, it indicates that the point is POI, and when type is 0, it indicates that the point is a check-in point, but not limited to this.

Step (1.2) includes step (1.2.1), step (1.2.2):

Step (1.2.1): Read the sorted POI data to obtain the attributes of the POIs, and uniformly structure the attributes of the POIs.

Read in the POI data, set the type to 1, and set the offset _lng and offset _lat to the longitude and latitude of the POI.

Step (1.2.2): Read the check-in point data, if the POI of the point of interest corresponding to the check-in point is identified in the second hash set, the check-in point will not be added to the point set array. Check-in points whose distances between the corresponding points of interest satisfy the preset conditions are cleared.

The clear condition is:

|latitude-offset _lat |＞a

|longitude-offset _lng |＞2*a

Among them, since the longitude range is 360 degrees, the latitude range is 180 degrees, and the longitude is twice the latitude, a distance threshold of twice is used. If the absolute value of the difference between the longitude of the check-in point and the longitude of the POI point is greater than 2 times a, and the absolute value of the difference between the latitude of the check-in point and the latitude of the POI point is greater than a, the check-in point will be cleared. a is a distance threshold parameter, which can be 0.02, 0.04, etc., but is not limited to this.

In one embodiment, after the step of integrating the point of interest data and the check-in point data to obtain a point set, the method for mining virtual surfaces further includes: performing a structured process on the road network data to obtain a road identifier of each road , The node information contained in each road and the maximum and minimum latitude and longitude of the nodes in each road are recorded in the road set.

In this embodiment, a road set array Roads is established. Structure the road network data, set a road id (identity) for each road, and the road id is the position value of the road in the road set array Roads, and obtain the node information contained in each road and each road. The latitude and longitude of each node in the road, and get the minimum enclosing rectangle of this road. Information such as road grade and road name can also be obtained. Create a node array to store all the nodes on the road and the latitude and longitude of each node. Obtain the maximum and minimum latitude and longitude according to the longitude and latitude of all nodes on this road, and obtain the minimum circumscribed rectangle of this road according to the maximum and minimum longitude and latitude, that is, obtain the difference between the maximum longitude and the minimum longitude, and the difference between the maximum latitude and the minimum latitude, respectively as the minimum The length and width of the bounding rectangle.

In one embodiment, the method for mining virtual surfaces further includes: establishing an index, establishing an inverted index and a first key information balanced tree index according to the point set, and establishing a second key information balanced tree index according to the way set. By establishing a three-part index to speed up the search of the geographical area, it also makes the search and calculation results more accurate.

Step (2) establishes an index, including:

Step (2.1): establishing an inverted index according to the set of points, including: establishing an inverted index, wherein the key is the identifier of the point of interest, the key value is the set of points, and each item in the set of points is the check-in point corresponding to the point of interest The position value in this set of points.

Use the ID of the POI to create an inverted index. Create an inverted index, where the key is the ID of the POI, and the key is the point set (or point set array). Each item in the point set is the position value of the check-in point corresponding to the POI in points. Scan the points, for the ID of the POI that already exists in the inverted index, add the check-in position value to the point set of the item, and for the ID of the POI that does not exist, create a new item and insert it into the inverted index.

Step (2.2): establish the first key information balanced tree index according to the point set, including steps (2.2.1), (2.2.2):

Establish KR-Tree, that is, the first key information balance tree. The KR-Tree is extended on the basis of the R-Tree. Each node in the KR-Tree includes the range information of the rectangle, the branch of the child nodes and the key text information. The key text information includes the ID of the POI of the check-in point, an inverted index, and the like. The key of the inverted index is the ID of the POI of the check-in point, and the key value is the position value of the check-in point in the point set array points.

Fig. 4 is the schematic diagram of R-Tree instance; Fig. 5 is the example schematic diagram of KR-Tree on the map; Fig. 6 is the inverted index schematic diagram established according to the ID based on POI of Fig. 5; Fig. 7 is the KR-Tree established according to Fig. 5 Tree index diagram.

As shown in Figure 4, R-Tree is a spatial index data structure. Its characteristics are: R-Tree is an n-ary tree, and n is a fan of R-Tree; each node corresponds to a rectangle; the leaf nodes contain For objects less than or equal to n, the corresponding rectangle is the enclosing rectangle of all objects; the rectangle of non-leaf nodes is the enclosing rectangle of all child node rectangles. Non-leaf nodes A and B, non-leaf node A includes leaf nodes C, D, E, F, and non-leaf node B includes leaf nodes G, H, I, J.

As shown in Figure 5, the non-leaf node R0 on the map includes two non-leaf nodes R1 and R2, the non-leaf node R1 includes non-leaf nodes R3, R4 and R5, and the non-leaf node R2 includes non-leaf nodes Points R6, R7 and R8. The non-leaf node R3 includes leaf nodes P1 and P2. The non-leaf node R4 includes leaf nodes P11 and P12. The non-leaf node R5 includes leaf nodes P3 and P4. The non-leaf node R6 includes leaf nodes P5 and P7. The non-leaf node R7 includes leaf nodes P9 and P10. The non-leaf node R8 includes leaf nodes P6 and P8.

As shown in Figure 6, the ID of the POI is 438490, and the corresponding check-in points are P1, P2, and P3 in the POI point collection; the POI ID is 857839, and the corresponding check-in points are P11, P12 in the POI point collection; The ID of POI is 402384, and the corresponding check-in points are P4, P5, and P6 in the POI point collection; the ID of POI is 789347, and the corresponding check-in points are P7, P8, P9, and P10 in the POI point collection.

As shown in Figure 7, non-leaf node R0 includes two non-leaf nodes R1 and R2, non-leaf node R1 includes non-leaf nodes R3, R4 and R5, non-leaf node R2 includes non-leaf nodes R6, R7 and R8. The non-leaf node R3 includes leaf nodes P1 and P2. The non-leaf node R4 includes leaf nodes P11 and P12. The non-leaf node R5 includes leaf nodes P3 and P4. The non-leaf node R6 includes leaf nodes P5 and P7. The non-leaf node R7 includes leaf nodes P9 and P10. The non-leaf node R8 includes leaf nodes P6 and P8. Each leaf node corresponds to a POI ID. For example, the ID of POI is 438490, and the corresponding check-in points are P1, P2, and P3 in the POI points; the ID of POI is 857839, and the corresponding check-in points are P11 and P12 in the POI points; , the corresponding check-in points are P4, P5, P6 in the POI point concentration; the ID of the POI is 789347, and the corresponding check-in points in the POI point concentration are P7, P8, P9, P10.

Using the KR-Tree tree, the space is framed by a rectangle starting from the leaf node. The higher the node is, the larger the framed space is, so as to divide the space. According to the data structure of the R tree, when a high-dimensional space query needs to be performed, it is only necessary to traverse the pointers contained in a few leaf nodes to check whether the data pointed to by these pointers meets the requirements, which is highly efficient.

Step (2.2.1): Change the check-in point data into rectangular data with key information.

Create a rectangular array rects with key information. For each check-in point, set the maximum and minimum longitude of the rectangle as the longitude of the check-in point, and the maximum and minimum latitude of the rectangle as the latitude of the check-in point, and with structural attributes, the structure The attribute contains the ID of the POI of the check-in point and an inverted index. The key of the inverted index is the ID of the POI of the check-in point, and the key value is the position value of the check-in point in the point set array points. Add this new rectangle with side length 0 to the rects.

Step (2.2.2): Insert the rectangular data into the first key information balance tree.

Specifically, each rectangle of rects is inserted into the KR-Tree.

Further, step (2.2.2) includes steps (2.2.2.1), (2.2.2.2), (2.2.2.3) and (2.2.2.4).

Step (2.2.2.1): Select leaf node L to place new entry E;

In this embodiment, a leaf node L is selected by the ChooseLeaf method to place a new rectangular record E. Step (2.2.2.1) includes steps (2.2.2.1.1), (2.2.2.1.2), (2.2.2.1.3), (2.2.2.1.4). The new entry E is the new rectangle record.

Step (2.2.2.1.1): Set N as the root node.

Step (2.2.2.1.2): If N is a leaf node, return N directly.

Step (2.2.2.1.3): If N is not a leaf node, traverse the nodes in N, find the node with the smallest expansion when adding E, and define the node as F. If there are multiple such nodes, the node with the smallest area is selected.

In this embodiment, each node has maximum and minimum longitude and latitude, and E also has maximum and minimum longitude and latitude. Among these eight longitude and latitude, the maximum longitude and latitude and the minimum longitude and latitude can be quickly obtained, and the new maximum and minimum longitude and latitude can be calculated. The area of the rectangle is then compared with the area calculated by the old maximum and minimum longitude and latitude, and the node with the smallest area expansion can be obtained. If there are multiple nodes with the same expansion area, select the new node with the smallest area.

As shown in FIG. 8A , the non-leaf node A includes D, E, and F, the non-leaf node B includes G, H, and I, and the non-leaf node C includes J, K, L, and M. As shown in FIG. 8B, a new rectangular record X is to be added. As shown in Figure 8C, set N as the root node A, if A is the root node, traverse the nodes in A to find the maximum and minimum latitude and longitude of X, and the maximum latitude and longitude and minimum latitude and longitude of node A when adding X. Select the maximum longitude and latitude and the minimum longitude and latitude of X and A together, calculate the area of the new maximum and minimum longitude and latitude, and compare it with the area calculated by the maximum and minimum longitude and latitude of A to obtain the expanded area size S1 (dotted box in the figure). In the same way, calculate the expanded area size S2 after X is added to the B node, and calculate the expanded area size S3 after X is added to the C node. Among S1, S2 and S3, S1 is the smallest, then select the node A with the smallest area expansion, and add X to A, as shown in Figure 8D.

Step (2.2.2.1.4): Set N to F and repeat the operation from step (2.2.2.1.2).

Step (2.2.2.2): If the space of L is larger than the preset space, add E to L; if the space of L is not larger than the preset space, split the L to obtain two leaf nodes L and LL. Each leaf node contains the entry in the original leaf node L and the new entry E.

Obtain two leaf nodes L and LL through the SplitNode method.

Step (2.2.2.3): Perform the AdjustTree operation on the two leaf nodes L and LL respectively.

The AdjustTree operation is passed up to the root node for changes in the leaf nodes to change the various matrices. Splitting of nodes may occur in the process of transferring transformations.

Further, step (2.2.2.3) includes steps (2.2.2.3.1), (2.2.2.3.2), (2.2.2.3.3), (2.2.2.3.4) and (2.2.2.3.5) .

Step (2.2.2.3.1): Set M to L.

Step (2.2.2.3.2): If M is the root node, stop the operation.

Step (2.2.2.3.3): Let P be the parent node of M, EN be the entry pointing to M in the parent node P, and adjust EN to ensure that all rectangles in M are enclosed.

Step (2.2.2.3.4): If M has a split node MM, create an entry EMM pointing to MM, if P has space to store EMM, add EMM to P, if not, then Split operation on P to get P and PP.

Step (2.2.2.3.5): If M is equal to L and a split occurs, set MM to PP.

Step (2.2.2.4): If the node splits and the split propagates upwards, causing the root node to split, a new root node is created, and the two child nodes of the new root node are split as the original root node. the last two nodes.

In one embodiment, establishing the second key information balanced tree index according to the road set includes: establishing a rectangle with key information according to the maximum and minimum latitude and longitude of each road in the road set and the position value corresponding to the road, This rectangle with key information is inserted into the second key information balanced tree.

Use the maximum and minimum latitude and longitude of each road and the corresponding position value of the road in Roads to create a rectangle with key information, add it to the rectangle set, and use the KR-Tree method for establishing check-in points. To build the KR-Tree of the road network, insert each rectangle in the set of rectangles into the second key information balance tree. The difference from the KR-Tree method of establishing check-in points is that the leaf nodes are the minimum circumscribed rectangles of each road in the road network, not the check-in points with side length 0.

In one embodiment, for a certain POI, the check-in point set of the POI can be quickly obtained through the inverted index and the first key information balance tree index, and the minimum circumscribed rectangle of the check-in point set is calculated. Assuming that the check-in points are evenly distributed in the minimum circumscribed rectangle, the side length of the minimum circumscribed rectangle occupied by each check-in point can be calculated, and then for each check-in point, the thermal value within the search rectangle is calculated. The value filters out the wrong check-in points to get the correct check-in point set.

The step of acquiring the check-in point set of each interest point according to the point set includes: acquiring the check-in point set of each interest point according to the inverted index.

Specifically, the inverted index of the check-in point established by the ID of the POI is used to obtain all the check-in point sets. Each item in the check-in point set is the position value of the check-in point in the established point set array points.

The steps of filtering the check-in points in the check-in point set to obtain the correct check-in point set include:

Step (3.1) obtains the minimum circumscribed rectangle of the check-in point set.

Step (3.1) includes step (3.1.1) and step (3.1.2).

Step (3.1.1): Acquire the latitude and longitude of each check-in point according to the set of check-in points, and obtain the maximum and minimum latitude and longitude.

Use the point set array points to obtain the latitude and longitude of each check-in point. Traverse the check-in point set to obtain the maximum and minimum latitude and longitude, that is, the geographic location (min_lat, max_lat, min_lng, max_lng) of the minimum circumscribed rectangle of the check-in point set.

Step (3.1.2): Calculate the length and width of the minimum circumscribed rectangle of the check-in point set.

The length of the minimum circumscribed rectangle of the check-in point set is obtained according to the maximum longitude minus the minimum longitude, and the width of the minimum circumscribed rectangle of the check-in point set is obtained according to the maximum latitude minus the minimum latitude.

L ₁ =max_lng-min_lng

L ₂ =max_lat-min_lat

Among them, max_lat is the maximum latitude, min_lat is the minimum latitude, max_lng is the maximum longitude, and min_lng is the minimum longitude.

Step (3.2) obtains the side length of the minimum circumscribed rectangle occupied by the check-in point.

Assuming that the check-in points are uniformly distributed in the minimum circumscribed rectangle, for each check-in point, the side length min_dis of the minimum circumscribed rectangle occupied by it is calculated.

Among them, α is the coefficient of enlarging the rectangular area, which can be 3, etc., and n is the number of check-in points. When min_dis is greater than the maximum side length of the minimum circumscribed rectangle divided by the coefficient α,

Step (3.3): Traverse the set of check-in points, and calculate the thermal value of each check-in point.

Step (3.3) includes steps (3.3.1) and (3.3.2).

Step (3.3.1): For each check-in point, establish a search rectangle node for searching on the first key information balance tree centered on the check-in point.

Specifically, a search rectangle node search_rect centered on the check-in point and capable of searching on the first key information balance tree is established for each check-in point.

Calculate the maximum and minimum latitude and longitude of the search rectangle node centered on the current check-in point P0.

lng ₁ =P ₀ .lng-min_dis

lng ₂ =P ₀ .lng+min_dis

Among them, lat ₁ is the minimum latitude of the search rectangle node, lat ₂ is the maximum latitude of the search rectangle node, lng ₁ is the minimum longitude of the search rectangle node, and lng ₂ is the maximum longitude of the search rectangle node. The key information of the search rectangle is the ID of the POI on the check-in point.

Step (3.3.2): search on the first key information balance tree index and calculate the number of other check-in points on the POI sign corresponding to the check-in point within the range of the search rectangle node. The number is used as the thermal value of the check-in point.

Step (3.3.2) includes step (3.3.2.1) and step (3.3.2.2).

Step (3.3.2.1): T is the root node of an R tree. If T is a non-leaf node, and the rectangle corresponding to T coincides with search_rect, check all entries stored in T, and for all these entries, search for the root node of the subtree pointed to by each entry (ie, the T node child nodes).

Step (3.3.2.2): If T is a leaf node, and the rectangle corresponding to T is coincident with search_rect, then directly check all record entries pointed to by search_rect. Returns the check-in point whose POI ID is the current POI ID.

Step (3.4): Filter the wrong check-in points according to the thermal value of each check-in point to obtain the correct check-in point set.

Step (3.4) includes step (3.4.1) and step (3.4.2).

Step (3.4.1): If the number of check-in points in the check-in point set is greater than the first number, the threshold of the thermal value is the first value; if the number of check-in points in the check-in point set is not greater than the first number, the threshold of the thermal value is a second value, and the first threshold is greater than the second threshold.

In this embodiment, the first number can be set as required, such as 500. For the number of check-in points in the check-in point set greater than 500, the threshold θ of the thermal value is the maximum value of the thermal value of the check-in point multiplied by the first coefficient to obtain the first value. If the number of check-in points in the check-in point set is less than 500, the threshold of the thermal value is the maximum value of the thermal value of the check-in point multiplied by the second coefficient to obtain the second value. Obtain the thermal value of all check-in points in the check-in point set, and compare the thermal value of each check-in point to obtain the maximum thermal value of the check-in point. The first coefficient and the second coefficient may be determined as required. For example, the first coefficient is 0.5, and the second coefficient is 0.1.

The size of the virtual surface is dynamically divided according to the number of check-ins of different POIs.

Step (3.4.2): Traverse the set of check-in points, clear the check-in points whose thermal value of each check-in point is less than the threshold of the thermal value, and obtain a correct set of check-in points.

Further, the set of check-in points is traversed, and the check-in points whose thermal value of each check-in point is less than the threshold of the thermal value and less than the first threshold are eliminated. The first threshold can be determined as required, for example, the first threshold is 10.

In one embodiment, the step of obtaining the minimum circumscribed polygon of the correct check-in point set includes (4.1) to (4.6):

Step (4.1): Define the convex hull, which is the smallest convex set containing the check-in point set.

凸包记为CH(Q)，定义为

凸包CH(Q)是包含Q的最小凸集。Specifically, the check-in point set

The convex hull is denoted CH(Q) and is defined as

The convex hull CH(Q) is the smallest convex set containing Q.

Step (4.2): Select the point with the smallest x-axis coordinate or the point with the smallest y-axis coordinate in the check-in point set, and record it as the base point P ₀ .

Specifically, select the point with the smallest x-axis coordinate in the check-in point set (ie, the check-in point), if there are more than one, select the point with the smallest y-axis coordinate, that is, find the bottom leftmost point in the check-in point set Q, denoted as base point P ₀ .

Step (4.3): Sort the points in the check-in point set according to the lexicographical order of the rotation angle of the base point P ₀ and the distance from P ₀ .

Step (4.3) includes step (4.3.1), step (4.3.2) and step (4.3.3).

Step (4.3.1): Perform a coordinate transformation on the check-in point, and take the base point P ₀ as the origin of the coordinates, then the rotation angle θ _i and the distance γ _i of the check-in point P _i (x _i , y _i ) about the base point P ₀ are respectively: :

Step (4.3.2): Use the monotonically decreasing characteristic of cos(θ) between [0, π] to configure the monotonically decreasing function f(i).

Step (4.3.3): Convert the lexicographical ordering of rotation angle and distance into ordering in descending order of f(i) and ascending order of γ _i , which simplifies the calculation process.

Step (4.4): Push the sorted check-in points into the stack in order.

Specifically, initialize P ₀ , P ₁ , and P ₂ , and push them into Stack in sequence.

Step (4.5): Starting from the fourth check-in point after sorting, if the check-in point is on the left side of the vector formed by the last two adjacent points pushed into the stack, the point is pushed into the stack, otherwise the last check-in point pushed into the stack is out. stack.

的左侧(t是栈Stack指针，P^t表示栈中第t个元素)，则P_i入栈，且i＝i+1，否则P_t出栈。Specifically, P _i goes from P ₃ to P _n-1 , if P _i is strictly a vector in the stack

The left side of (t is the stack pointer, P ^t represents the t-th element in the stack), then P _i is pushed into the stack, and i=i+1, otherwise P _t is popped out of the stack.

The two adjacent points refer to the last two check-in points in the stack.

Judgment on the left, for any three points P ₀ (x ₀ , y ₀ ), P ₁ (x ₁ , y ₁ ), and P ₂ (x ₂ , y ₂ ) on the plane, let

的左侧；If A(T)> ₀ , then P2 is strictly in

the left side;

上；If A(T)=0, then P ₂ is

superior;

的右侧。If A(T)< ₀ , then P2 is strictly in

on the right.

Step (4.6): Return all elements in the stack to get the convex hull.

Specifically, all elements in the stack are returned to obtain the convex hull CH(Q).

的左侧，因此入栈。P₈在

的右侧，P₆出栈，同样在

的右侧，P₉出栈。以此类推，最后得出凸包集合{P₀,P₄，P₅,P₇,P₈,P₃,P₁}。For example, Figure 8 is a schematic diagram of the convex hull algorithm. As shown in Figure 8, the convex hull contains P ₀ , P ₁ , P ₂ , P ₃ , P ₄ , P ₅ , P ₆ , P ₇ , P ₈ , P ₉ check-in points, and the check-in points in the calculation of the convex hull are In the process of minimum circumscribed polygon, select the most left and bottom point as the base point P ₀ , the remaining points are sorted according to the angle and distance, and the sorting results are P ₄ , P ₅ , P ₇ , P ₉ , P ₆ , P ₈ , P ₂ , P ₃ , P ₁ . Push P ₀ , P ₄ , and P ₅ into Stack, and P ₇ is in the vector

the left side of , so it is pushed onto the stack. P ₈ in

On the right side of , P ₆ is popped, also in

On the right side of , P ₉ pops the stack. And so on, finally get the convex hull set {P ₀ , P ₄ , P ₅ , P ₇ , P ₈ , P ₃ , P ₁ }.

In one embodiment, the step of performing boundary optimization on the minimum circumscribed polygon of the correct check-in point set according to the road network data includes: performing boundary optimization on the minimum circumscribed polygon of the correct check-in point set according to the road set.

The steps of performing boundary optimization on the minimum circumscribed polygon of the correct check-in point set according to the road set include:

Step (5.1): Calculate the geographic location of the minimum circumscribed rectangle of the convex hull, and the key information of the minimum circumscribed rectangle is the point of interest identifier;

Step (5.2): Obtain the number of check-in points in the convex hull.

Specifically, in the same way as the search operations on the first key information balance tree in steps (3.3.2.1) and (3.3.2.2), search for all POIs whose ID is the convex hull PIO within this minimum circumscribed rectangle. ID check-in point collection, and calculate the number of check-in points.

T is the root node of an R-tree. If T is a non-leaf node, and the rectangle corresponding to T coincides with search_rect, check all entries stored in T, and for all these entries, search for the root node of the subtree pointed to by each entry (ie, the T node child nodes).

If T is a leaf node, and the rectangle corresponding to T overlaps with search_rect, check all records pointed to by search_rect directly. Returns the check-in point whose POI ID is the current POI ID.

Step (5.3): Use the second key information balance tree index to search out the road result set of all the roads within the minimum circumscribed rectangle of the convex hull.

The specific search method is the same as step (3.3.2.1) and step (3.3.2.2). In the obtained road result set, if the number of roads exceeds the predetermined number, it means that the convex hull is not suitable for road network optimization. The predetermined number can be set as required, such as 500 and so on.

Step (5.4): Obtain the latitude and longitude of the center point of the convex hull.

Specifically, average the longitudes and latitudes on all the boundary points of the convex hull, that is, divide the sum of the longitudes on the boundary points of the convex hull by the number of boundary points to obtain the average longitude, and divide the latitude sum on the boundary points of the convex hull by the sum of the latitudes. The average latitude is obtained by the number of boundary points, and the average longitude and average latitude are used as the latitude and longitude of the center point.

Among them, lat _center is the latitude of the center point, lng _center is the longitude of the center point, n is the number of boundary points on the convex hull, lat _i is the latitude of the ith boundary point on the convex hull, and lng _i is the ith boundary point on the convex hull The longitude of a boundary point.

Step (5.5): For each point on the convex hull, determine whether the line connecting the center of the convex hull and each point on the boundary of the convex hull intersects the road in the road result set; if it does, the coordinates of the point are Set to the coordinates of the intersection of the two lines, get a new convex hull, and calculate the number of check-in points in the new convex hull; if the number of check-in points in the new convex hull is the same as the number of check-in points in the original convex hull If the scale is greater than the preset scale, the intersection of the two lines will be the boundary point of the convex hull.

Specifically, each point Pi on the convex _hull is a check-in point on the convex hull. Determine whether the connecting line between the convex hull center P _center and each point P _i on the convex hull boundary intersects with the road Road _j (j=1,2,...,n) in the road set in step (5.3). If it intersects, set the coordinates of the point as the coordinates of the intersection, get a new convex hull, and calculate the number of check-in points in the new convex hull.

If the ratio of the number of check-in points in the new convex hull to the number of check-in points in the original convex hull is greater than the preset ratio, it is retained, so that the intersection of the two lines is the boundary point of the convex hull. The preset ratio can be set as required, such as 0.6.

Figure 1010 is a structural block diagram of an apparatus for excavating virtual surfaces in one embodiment. As shown in FIG. 1010 , an apparatus for excavating virtual surfaces includes an integration module 1002 , a screening module 1004 , a virtual surface acquisition module 1006 and an optimization module 1008 . in:

The integration module 1002 is used for acquiring point of interest data, check-in point data and road network data, and integrating the interest point data and check-in point data to obtain a point set;

The screening module 1004 is configured to obtain the check-in point set of each interest point according to the point set, and filter the check-in points in the check-in point set to obtain the correct check-in point set;

The virtual surface obtaining module 1006 is used to obtain the minimum circumscribed polygon of the correct check-in point set;

The optimization module 1008 is configured to perform boundary optimization on the minimum circumscribed polygon of the correct check-in point set according to the road network data.

The above-mentioned virtual surface mining device obtains the point set by acquiring the point of interest data, the check-in point data and the road network data, integrates the point of interest data and the check-in point data to obtain a point set, and filters the check-in points corresponding to each point of interest in the point set to obtain the correct value. The minimum circumscribed polygon of the check-in point set is obtained, and the road network is used to optimize the boundary of the minimal circumscribed polygon. The minimal circumscribed polygon is the virtual surface of the point of interest, which realizes the mining of the virtual surface.

FIG. 11 is a structural block diagram of an apparatus for excavating virtual surfaces in another embodiment. As shown in FIG. 11 , an apparatus for virtual surface mining includes an index building module 1010 in addition to an integration module 1002 , a screening module 1004 , a virtual surface acquisition module 1006 and an optimization module 1008 . in:

The integration module 1002 is further configured to perform structured processing on the road network data to obtain the road identification of each road, the node information contained in each road, and the maximum and minimum latitude and longitude of the nodes in each road, and record them in the road set middle;

The index establishment module 1010 is configured to establish an inverted index and a first key information balanced tree index according to the point set, and establish a second key information balanced tree index according to the road set;

The screening module 1004 is further configured to obtain the check-in point set of each point of interest according to the inverted index;

The optimization module 1008 is further configured to perform boundary optimization on the minimum circumscribed polygon of the correct check-in point set according to the road set.

In one embodiment, the index establishment module 1010 is further configured to establish an inverted index according to the point set, including:

Establish an inverted index, wherein the key is the point of interest identifier, the key value is a collection array, and each item in the collection array is the position value of the check-in point corresponding to the interest point in the point collection;

The first key information balanced tree index is established according to the point set, including:

Change the check-in point data to rectangular data with key information;

inserting the rectangular data into the first key information balance tree;

and establishing a second key information balanced tree index according to the road set, including:

According to the maximum and minimum latitude and longitude of each road in the road set and the corresponding position value of the road, a rectangle with key information is established, and the rectangle with key information is inserted into the second key information balance tree.

In one embodiment, the integration module 1002 organizes the POI data; performs unified structuring of the attributes of the POIs and the attributes of the check-in points, and records the attributes of the unified structured POIs and the attributes of the check-in points in the point set in the array.

The integration module 1002 is further configured to use the first hash set to count check-in points, wherein the key of the first hash set is the point of interest identifier, and the key value is the number of check-in points;

Scan the POI data, if there is no POI identification key of the current POI or the key value corresponding to the POI identification key of the current POI is less than or equal to the first threshold, then clear the current POI, and use the cleared POI's interest The point identification is recorded in the second hash set;

Read the sorted POI data to obtain the attributes of the POI, and uniformly structure the attributes of the POI;

Read the check-in point data, if the point-of-interest identifier of the point of interest corresponding to the check-in point is in the second hash set, the check-in point will not be added to the point set array. Clear the check-in points that meet the preset conditions.

The rectangular data is inserted into the first key information balance tree, including:

Select leaf node L to place new entry E;

If the space of L is larger than the preset space, add E to L, if the space of L is not larger than the preset space, then split the L to obtain two leaf nodes L and LL, and the two leaf nodes contain The entry in the original leaf node L and the new entry E;

Perform the AdjustTree operation on the two leaf nodes L and LL respectively. If the node splits and the split propagates upwards and the root node splits, a new root node is created, and the two child nodes of the new root node are created. The points are the two nodes after the original root node is split.

The step of selecting a leaf node L to place a new entry E includes:

Set N as the root node;

Repeat the following steps:

If N is a leaf node, return N directly;

If N is not a leaf node, traverse the nodes in N, find the node with the smallest expansion when adding E, and define the node as F;

Let N be F.

The steps of respectively performing the AdjustTree operation on the two leaf nodes L and LL include:

Set M to L;

Repeat the following steps:

If M is the root node, stop the operation;

Let P be the parent node of M, EN be the entry pointing to M in the parent node P, and adjust EN to ensure that all rectangles in M are enclosed;

If M has a split node MM, create an entry EMM pointing to MM, if P has space to store EMM, add EMM to P, if not, split P to get P and PP ;

If M is equal to L and a split occurs, set MM to PP.

The screening module 1004 is further configured to filter the check-in points in the check-in point set to obtain the correct check-in point set, including:

Get the minimum circumscribed rectangle of the check-in point set;

Get the side length of the minimum circumscribed rectangle occupied by the check-in point;

Traverse the set of check-in points and calculate the thermal value of each check-in point;

According to the calorific value of each check-in point, the wrong check-in points are filtered, and the correct check-in point set is obtained.

In one embodiment, the obtaining the minimum circumscribed rectangle of the check-in point set includes:

Obtain the latitude and longitude of each check-in point according to the set of check-in points, and obtain the maximum and minimum latitude and longitude;

The length of the minimum circumscribed rectangle of the check-in point set is obtained according to the maximum longitude minus the minimum longitude, and the width of the minimum circumscribed rectangle of the check-in point set is obtained according to the maximum latitude minus the minimum latitude.

In one embodiment, the check-in point set is traversed to calculate the thermal value of each check-in point, including:

For each check-in point, establish a search rectangle node for searching on the first key information balance tree centered on the check-in point;

Search on the first key information balance tree index and calculate the number of other check-in points on the POI identifier corresponding to the check-in point within the range of the search rectangle node, and the number is used as the thermal power of the check-in point value.

In one embodiment, the wrong check-in points are filtered according to the thermal value of each check-in point to obtain a correct check-in point set, including:

If the number of check-in points in the check-in point set is greater than the first number, the threshold of the thermal value is the first value; if the number of check-in points in the check-in point set is not greater than the first number, the threshold of the thermal value is the second value, and the first value The threshold is greater than the second threshold;

Traverse the set of check-in points, clear the check-in points whose thermal value of each check-in point is less than the threshold of thermal value, and obtain the correct set of check-in points.

In one embodiment, the virtual surface obtaining module 1006 obtains the minimum circumscribed polygon of the correct check-in point set, including:

Define the convex hull, which is the smallest convex set containing the check-in point set;

Select the point with the smallest x-axis coordinate or the point with the smallest y-axis coordinate in the check-in point set, and record it as the base point P ₀ ;

Sort the check-in points in the check-in point set according to the lexicographical order of the corner of the base point P ₀ and the distance from P ₀ ;

Push the sorted check-in points into the stack in order;

Starting from the fourth check-in point after sorting, if the point is on the left side of the vector formed by the last two adjacent points pushed into the stack, the point is pushed into the stack, otherwise the last push-in check-in point is pushed out of the stack;

Return all elements in the stack to get the convex hull.

The optimization module 1008 is further configured to perform boundary optimization on the minimum circumscribed polygon of the correct check-in point set according to the road set, including:

Calculate the geographic location of the smallest circumscribed rectangle of the convex hull, and the key information of the smallest circumscribed rectangle is the point of interest identifier;

Get the number of check-in points in the convex hull;

Use the second key information balanced tree index to search out the road result set of all roads in the minimum circumscribed rectangle of the convex hull;

Get the latitude and longitude of the center point of the convex hull;

For each point on the convex hull, determine whether the line connecting the center of the convex hull and each point on the boundary of the convex hull intersects the road in the road result set;

If it intersects, set the coordinates of the point as the coordinates of the intersection of the two lines, get a new convex hull, and calculate the number of check-in points in the new convex hull;

If the ratio of the number of check-in points in the new convex hull to the number of check-in points in the original convex hull is greater than the preset ratio, the intersection of the two lines is set as the boundary point of the convex hull.

Those of ordinary skill in the art can understand that all or part of the processes in the methods of the above embodiments can be implemented by instructing relevant hardware through a computer program, and the program can be stored in a non-volatile computer-readable storage medium , when the program is executed, it may include the flow of the above-mentioned method embodiments. The storage medium may be a magnetic disk, an optical disk, a read-only memory (Read-Only Memory, ROM), or the like.

The above-mentioned embodiments only represent several embodiments of the present invention, and the descriptions thereof are specific and detailed, but should not be construed as limiting the scope of the patent of the present invention. It should be noted that, for those skilled in the art, without departing from the concept of the present invention, several modifications and improvements can be made, which all belong to the protection scope of the present invention. Therefore, the protection scope of the patent of the present invention should be subject to the appended claims.

Claims (30)

1. A method for virtual face mining, comprising: Obtaining point-of-interest data, check-in point data and road network data, and integrating the point-of-interest data and check-in point data to obtain a point set; Obtain the check-in point set of each interest point according to the point set, and filter the check-in points in the check-in point set to obtain the correct check-in point set; Obtain the minimum circumscribed polygon of the correct check-in point set; According to the road network data, boundary optimization is performed on the minimum circumscribed polygon of the correct check-in point set to obtain the virtual surface of each interest point. 2. The method according to claim 1, wherein the step of integrating the point of interest data and the check-in point data to obtain a point set comprises: collating said point of interest data; The attributes of the points of interest and the attributes of the check-in points are unifiedly structured, and the attributes of the unified structuring points of interest and the attributes of the check-in points are recorded in the point set array. 3. The method according to claim 2, wherein the step of organizing the POI data comprises: Use the first hash set to count check-in points, wherein the key of the first hash set is the identifier of the point of interest, and the key value is the number of check-in points; Scan the POI data, if there is no POI identification key of the current POI or the key value corresponding to the POI identification key of the current POI is less than or equal to the first threshold, clear the current POI, and use the deleted POI to The POI identifier is recorded in the second hash set; The step of uniformly structuring the attributes of the points of interest and the attributes of the check-in points, and recording the attributes of the unified structuring points of interest and the attributes of the check-in points in the point set array includes: Reading the sorted POI data to obtain the attributes of the POIs, and uniformly structuring the attributes of the POIs; Read the check-in point data, if the point-of-interest identifier of the point of interest corresponding to the check-in point is in the second hash set, then the check-in point is not added to the point set array, if the check-in point and the corresponding point of interest are Check-in points whose distances meet the preset conditions are cleared. 4. The method according to claim 1, wherein after the step of integrating the point of interest data and the check-in point data to obtain a point set, the method further comprises: Structuring the road network data to obtain the road identification of each road, the node information contained in each road, and the maximum and minimum latitude and longitude of the nodes in each road, and record them in the road set; Establish an inverted index and a first key information balanced tree index according to the point set, and establish a second key information balanced tree index according to the road set; The step of acquiring the check-in point set of each interest point according to the point set includes: Obtain the check-in point set of each interest point according to the inverted index; The step of performing boundary optimization on the minimum circumscribed polygon of the correct check-in point set according to the road network data includes: Boundary optimization is performed on the minimum circumscribed polygon of the correct check-in point set according to the road set. 5. The method according to claim 4, wherein establishing an inverted index according to the point set comprises: establishing an inverted index, wherein the key is a point of interest identifier, the key value is a point set, and each item in the point set is the position value of the check-in point corresponding to the interest point in the point set; Establishing a first key information balanced tree index according to the point set, including: Change the check-in point data to rectangular data with key information; inserting the rectangular data into the first key information balance tree; Establishing a second key information balanced tree index according to the road set, including: A rectangle with key information is established according to the maximum and minimum latitude and longitude of each road in the road set and the position value corresponding to the road, and the rectangle with key information is inserted into the second key information balance tree. 6. The method according to claim 5, wherein the step of inserting the rectangular data into the first key information balance tree comprises: Select leaf node L to place new entry E; If the space of L is larger than the preset space, add E to L. If the space of L is not larger than the preset space, then split the L to obtain two leaf nodes L and LL. Contains the entry in the original leaf node L and the new entry E; Perform the AdjustTree operation on the two leaf nodes L and LL respectively. If the node splits and the split propagates upwards and causes the root node to split, a new root node is created, and the new root node is The two child nodes are the two nodes after the original root node is split. 7. The method according to claim 6, wherein the step of selecting a leaf node L to place a new entry E comprises: Set N as the root node; Repeat the following steps: If N is a leaf node, return N directly; If N is not a leaf node, traverse the nodes in N, find the node with the smallest expansion when adding E, and define the node as F; Let N be F. 8. method according to claim 7, is characterized in that, the step that described two leaf nodes L and LL are carried out AdjustTree operation respectively comprises: Set M to L; Repeat the following steps: If M is the root node, stop the operation; Let P be the parent node of M, EN be the entry pointing to M in the parent node P, and adjust EN to ensure that all rectangles in M are enclosed; If M has a split node MM, create an entry EMM pointing to MM, if P has space to store EMM, add EMM to P, if not, split P to get P and PP ; If M is equal to L and a split occurs, set MM to PP. 9. The method according to claim 4, wherein the step of filtering the check-in points in the check-in point set to obtain the correct check-in point set comprises: Get the minimum circumscribed rectangle of the check-in point set; Obtain the side length of the minimum circumscribed rectangle occupied by the check-in point; Traverse the set of check-in points, and calculate the thermal value of each check-in point; According to the calorific value of each check-in point, the wrong check-in points are filtered, and the correct check-in point set is obtained. 10. The method according to claim 9, wherein the step of obtaining the minimum circumscribed rectangle of the check-in point set comprises: Obtain the latitude and longitude of each check-in point according to the set of check-in points, and obtain the maximum and minimum latitude and longitude; The length of the minimum circumscribed rectangle of the check-in point set is obtained according to the maximum longitude minus the minimum longitude, and the width of the minimum circumscribed rectangle of the check-in point set is obtained according to the maximum latitude minus the minimum latitude. 11. The method according to claim 9, wherein the step of traversing the set of check-in points and calculating the thermal value of each check-in point comprises: For each check-in point, establish a search rectangle node for searching on the first key information balance tree centered on the check-in point; Search on the first key information balance tree index and calculate the number of other check-in points within the range of the search rectangle node that are registered on the POI identifier corresponding to the check-in point, and the number is used as the number of check-in points. Describe the thermal value of the check-in point. 12. The method according to claim 9, wherein the step of filtering the wrong check-in points according to the thermal value of each check-in point to obtain the correct check-in point set comprises: If the number of check-in points in the check-in point set is greater than the first number, the threshold of the thermal value is the first value; if the number of check-in points in the check-in point set is not greater than the first number, the threshold of the thermal value is the second value, and the first value The threshold is greater than the second threshold; Traverse the set of check-in points, clear the check-in points whose thermal value of each check-in point is less than the threshold of thermal value, and obtain the correct set of check-in points. 13. The method according to claim 4, wherein the step of obtaining the minimum circumscribed polygon of the correct check-in point set comprises: Define a convex hull, the convex hull is the smallest convex set containing the check-in point set; Select the point with the smallest x-axis coordinate or the point with the smallest y-axis coordinate in the check-in point set, and record it as the base point P ₀ ; Sort the check-in points in the check-in point set according to the lexicographical order of the corner of the base point P ₀ and the distance from P ₀ to the points in the check-in point set; Push the sorted check-in points into the stack in order; From the fourth check-in point after sorting, if the point is on the left side of the vector formed by the last two adjacent points pushed into the stack, then the check-in point is pushed into the stack, otherwise the last check-in point pushed into the stack is pushed out of the stack; Return all elements in the stack to get the convex hull. 14. The method according to claim 13, wherein the step of performing boundary optimization on the minimum circumscribed polygon of the correct check-in point set according to the road set comprises: Calculate the geographic location of the minimum circumscribed rectangle of the convex hull, and the key information of the minimum circumscribed rectangle is the point of interest identifier; Obtain the number of check-in points in the convex hull; Use the second key information balanced tree index to search out the road result set of all roads within the minimum circumscribed rectangle of the convex hull; Obtain the latitude and longitude of the center point of the convex hull; For each point on the convex hull, determine whether the line connecting the center of the convex hull and each point on the boundary of the convex hull intersects the road in the road result set; If it intersects, set the coordinates of the point as the coordinates of the intersection of the two lines, obtain a new convex hull, and calculate the number of check-in points in the new convex hull; If the ratio of the number of check-in points in the new convex hull to the number of check-in points in the original convex hull is greater than the preset ratio, the intersection of the two lines is set as the boundary point of the convex hull. 15. A device for virtual surface excavation, comprising: an integration module, used for acquiring point-of-interest data, check-in point data and road network data, and integrating the point-of-interest data and check-in point data to obtain a point set; a screening module, configured to obtain a check-in point set of each interest point according to the point set, and filter the check-in points in the check-in point set to obtain a correct check-in point set; a virtual surface acquisition module, used for acquiring the minimum circumscribed polygon of the correct check-in point set; The optimization module is configured to perform boundary optimization on the minimum circumscribed polygon of the correct check-in point set according to the road network data to obtain the virtual surface of each interest point. 16. The apparatus of claim 15, wherein the apparatus further comprises: The integration module is also used to perform structured processing on the road network data to obtain the road identification of each road, the node information contained in each road, and the maximum and minimum latitude and longitude of the nodes in each road, and record them on the road. in the collection; an index establishment module, configured to establish an inverted index and a first key information balanced tree index according to the point set, and establish a second key information balanced tree index according to the road set; The screening module is further configured to obtain the check-in point set of each interest point according to the inverted index; The optimization module is further configured to perform boundary optimization on the minimum circumscribed polygon of the correct check-in point set according to the road set. 17. The apparatus according to claim 16, wherein the index establishment module is further configured to establish an inverted index according to the point set, comprising: establishing an inverted index, wherein the key is the point of interest identifier, the key value is a set array, and each item in the set array is the position value of the check-in point corresponding to the interest point in the point set; Establishing a first key information balanced tree index according to the point set, including: Change the check-in point data to rectangular data with key information; inserting the rectangular data into the first key information balance tree; and establishing a second key information balanced tree index according to the road set, including: A rectangle with key information is established according to the maximum and minimum latitude and longitude of each road in the road set and the position value corresponding to the road, and the rectangle with key information is inserted into the second key information balance tree. 18. The apparatus according to claim 17, wherein the index establishment module is used for inserting the rectangular data into the first key information balanced tree, comprising: Select leaf node L to place new entry E; If the space of L is larger than the preset space, add E to L. If the space of L is not larger than the preset space, then split the L to obtain two leaf nodes L and LL. Contains the entry in the original leaf node L and the new entry E; Perform the AdjustTree operation on the two leaf nodes L and LL respectively. If the node splits and the split propagates upwards and causes the root node to split, a new root node is created, and the new root node is The two child nodes are the two nodes after the original root node is split. 19. The apparatus according to claim 18, wherein the index establishment module is used to select a leaf node L to place a new entry E, comprising: Used to set N as the root node; Repeat the following steps: If N is a leaf node, return N directly; If N is not a leaf node, traverse the nodes in N, find the node with the smallest expansion when adding E, and define the node as F; Let N be F. 20. device according to claim 19, is characterized in that, described index establishment module is used to respectively carry out AdjustTree operation to described two leaf nodes L and LL, comprising: Let M be L; Repeat the following steps: If M is the root node, stop the operation; Let P be the parent node of M, EN be the entry pointing to M in the parent node P, and adjust EN to ensure that all rectangles in M are enclosed; If M has a split node MM, create an entry EMM pointing to MM, if P has space to store EMM, add EMM to P, if not, split P to get P and PP ; If M is equal to L and a split occurs, set MM to PP. 21. The apparatus according to claim 16, wherein the screening module is configured to filter the check-in points in the check-in point set to obtain a correct check-in point set, comprising: Get the minimum circumscribed rectangle of the check-in point set; Obtain the side length of the minimum circumscribed rectangle occupied by the check-in point; Traverse the set of check-in points, and calculate the thermal value of each check-in point; According to the calorific value of each check-in point, the wrong check-in points are filtered, and the correct check-in point set is obtained. 22. The device according to claim 21, wherein the screening module is configured to obtain the minimum circumscribed rectangle of the check-in point set, comprising: Obtain the latitude and longitude of each check-in point according to the set of check-in points, and obtain the maximum and minimum latitude and longitude; The length of the minimum circumscribed rectangle of the check-in point set is obtained according to the maximum longitude minus the minimum longitude, and the width of the minimum circumscribed rectangle of the check-in point set is obtained according to the maximum latitude minus the minimum latitude. 23. The apparatus according to claim 21, wherein the screening module is configured to traverse the set of check-in points, and calculate the thermal value of each check-in point, comprising: For each check-in point, establish a search rectangle node for searching on the first key information balance tree centered on the check-in point; Search on the first key information balance tree index and calculate the number of other check-in points within the range of the search rectangle node that are registered on the POI identifier corresponding to the check-in point, and the number is used as the number of check-in points. Describe the thermal value of the check-in point. 24. The device according to claim 21, wherein the screening module is used to filter the wrong check-in points according to the thermal value of each check-in point to obtain a correct check-in point set, comprising: If the number of check-in points in the check-in point set is greater than the first number, the threshold of the thermal value is the first value; if the number of check-in points in the check-in point set is not greater than the first number, the threshold of the thermal value is the second value, and the first value The threshold is greater than the second threshold; Traverse the set of check-in points, clear the check-in points whose thermal value of each check-in point is less than the threshold of thermal value, and obtain the correct set of check-in points. 25. The apparatus according to claim 16, wherein the virtual surface obtaining module is configured to obtain the minimum circumscribed polygon of the correct check-in point set, comprising: Define a convex hull, the convex hull is the smallest convex set containing the check-in point set; Select the point with the smallest x-axis coordinate or the point with the smallest y-axis coordinate in the check-in point set, and record it as the base point P ₀ ; Sort the check-in points in the check-in point set according to the lexicographical order of the corner of the base point P ₀ and the distance from P ₀ to the points in the check-in point set; Push the sorted check-in points into the stack in order; From the fourth check-in point after sorting, if the point is on the left side of the vector formed by the last two adjacent points pushed into the stack, then the check-in point is pushed into the stack, otherwise the last check-in point pushed into the stack is pushed out of the stack; Return all elements in the stack to get the convex hull. 26. The apparatus according to claim 25, wherein the optimization module is further configured to perform boundary optimization on the minimum circumscribed polygon of the correct check-in point set according to the road set, comprising: Calculate the geographic location of the minimum circumscribed rectangle of the convex hull, and the key information of the minimum circumscribed rectangle is the point of interest identifier; Obtain the number of check-in points in the convex hull; Use the second key information balanced tree index to search out the road result set of all roads within the minimum circumscribed rectangle of the convex hull; Obtain the latitude and longitude of the center point of the convex hull; For each point on the convex hull, determine whether the line connecting the center of the convex hull and each point on the boundary of the convex hull intersects the road in the road result set; If it intersects, set the coordinates of the point as the coordinates of the intersection of the two lines, obtain a new convex hull, and calculate the number of check-in points in the new convex hull; If the ratio of the number of check-in points in the new convex hull to the number of check-in points in the original convex hull is greater than the preset ratio, the intersection of the two lines is set as the boundary point of the convex hull. 27. The device according to claim 15, wherein the integration module is configured to integrate the point of interest data and the check-in point data to obtain a point set, comprising: collating said point of interest data; The attributes of the points of interest and the attributes of the check-in points are unifiedly structured, and the attributes of the unified structuring points of interest and the attributes of the check-in points are recorded in the point set array. 28. The apparatus according to claim 18, wherein the integration module is configured to organize the POI data, comprising: Use the first hash set to count check-in points, wherein the key of the first hash set is the identifier of the point of interest, and the key value is the number of check-in points; Scan the POI data, if there is no POI identification key of the current POI or the key value corresponding to the POI identification key of the current POI is less than or equal to the first threshold, clear the current POI, and use the deleted POI to The POI identifier is recorded in the second hash set; The step of uniformly structuring the attributes of the points of interest and the attributes of the check-in points, and recording the attributes of the unified structuring points of interest and the attributes of the check-in points in the point set array includes: Reading the sorted POI data to obtain the attributes of the POIs, and uniformly structuring the attributes of the POIs; Read the check-in point data, if the point-of-interest identifier of the point of interest corresponding to the check-in point is in the second hash set, then the check-in point is not added to the point set array, if the check-in point and the corresponding point of interest are Check-in points whose distances meet the preset conditions are cleared. 29. A terminal comprising a memory and a processor, wherein the memory stores a computer program, wherein the processor implements the steps of the method according to any one of claims 1 to 14 when the processor executes the computer program . 30. A non-volatile computer-readable storage medium storing a computer program, wherein the computer program implements the steps of the method according to any one of claims 1 to 14 when the computer program is executed by a processor.

Images