Search

CN-116244338-B - Geometric object screening method, device, equipment and storage medium

CN116244338BCN 116244338 BCN116244338 BCN 116244338BCN-116244338-B

Abstract

The application provides a geometric object screening method, a geometric object screening device, geometric object screening equipment and a storage medium, and relates to the technical field of data processing. The method comprises the steps of determining a target geometric object, wherein the target geometric object comprises a first geometric object representing a query range and a second geometric object to be detected whether the query range is met or not, determining an approximate object corresponding to the target geometric object, wherein the approximate object comprises a first approximate object corresponding to the first geometric object and/or a second approximate object corresponding to the second geometric object, the data structure of the approximate object is a multi-way tree, nodes on the multi-way tree correspond to spatial blocks in the spatial range of the approximate object, and screening the second geometric object according to the first approximate object and/or the second approximate object so as to reduce geometric objects which do not meet the query range in the second geometric object. Therefore, the screening of the geometric objects is realized by using the approximate objects, and the accuracy of the screening of the geometric objects is improved.

Inventors

  • WANG WEI
  • WANG HAIYAN
  • WANG JIANHUA

Assignees

  • 北京人大金仓信息技术股份有限公司

Dates

Publication Date
20260505
Application Date
20221230

Claims (19)

  1. 1. A geometric object screening method, comprising: Determining a target geometric object, wherein the target geometric object comprises a first geometric object representing a query range and a second geometric object to be detected whether the query range is met; Determining an approximate object corresponding to the target geometric object, wherein the approximate object comprises a first approximate object corresponding to the first geometric object and/or a second approximate object corresponding to the second geometric object, the data structure of the approximate object is a multi-way tree, and nodes on the multi-way tree correspond to space blocks in the space range of the approximate object; Screening the second geometric objects according to the first approximate objects and/or the second approximate objects to reduce geometric objects which do not meet the query range in the second geometric objects; The target geometric object includes an object identifier of the target geometric object, and the determining the approximate object corresponding to the target geometric object includes: if the approximate object is found in the cache space according to the object identification, reading the approximate object from the cache space according to the object identification; said screening said second geometric object according to said first approximation object and/or said second approximation object, comprising: According to the first approximate object and/or the second approximate object, carrying out position relation condition screening on the first geometric object and the second geometric object, and determining the position relation between the first geometric object and the second geometric object; and screening the second geometric object according to the position relation between the first geometric object and the second geometric object.
  2. 2. A geometric object screening method according to claim 1, further comprising: if the approximate object is not found in the cache space according to the object identification, determining whether the target geometric object belongs to a large geometric object; and if the target geometric object belongs to a large geometric object, generating the approximate object and storing the approximate object into the cache space.
  3. 3. The geometric object screening method according to claim 2, wherein the determining whether the target geometric object belongs to a large geometric object if the approximate object is not found in the cache space according to the object identification comprises: determining an attribute value of a minimum boundary matrix MBR of the target geometric object in a target dimension and an attribute upper limit value of an object class of the target geometric object corresponding to the target dimension; comparing the attribute value with the attribute upper limit value; And if the attribute value is larger than the attribute upper limit value, determining that the target geometric object belongs to a large geometric object, otherwise, determining that the target geometric object does not belong to the large geometric object.
  4. 4. A geometric object screening method according to claim 3, wherein said determining the attribute value of the MBR of the target geometric object in the target dimension and the attribute upper limit value of the object class to which the target geometric object belongs in the target dimension, includes: determining a target column to which the target geometric object belongs in a geometric object column of a data table, wherein the same geometric object column of the data table contains attribute information of geometric objects of the same category; according to the object identification, acquiring an attribute value of the MBR of the target geometric object in the target dimension from the attribute information of the target geometric object; and determining the attribute upper limit value of the object class of the target geometric object corresponding to the target dimension as the attribute upper limit value of the target column corresponding to the target dimension, wherein the attribute upper limit value of the target column corresponding to the target dimension is obtained by statistics according to the attribute values of MBRs of a plurality of geometric objects in the target column in the target dimension.
  5. 5. The geometric object screening method according to claim 4, wherein the statistical process of the attribute upper limit value corresponding to the target dimension by the target column includes: According to the attribute values of MBRs of a plurality of geometric objects in the target column on the target dimension, respectively, counting the quantiles of the geometric objects on the target dimension; and counting the attribute upper limit value corresponding to the target dimension of the target column according to the quantile.
  6. 6. The geometric object screening method according to any one of claims 2 to 5, wherein the generating the approximate object and storing the approximate object to the cache space if the target geometric object belongs to a large geometric object, comprises: If the target geometric object belongs to a large geometric object, determining the spatial range of the approximate object according to the MBR of the target geometric object; Recursively subdividing the space range of the approximate object through a multi-way tree algorithm to generate a multi-way tree corresponding to the approximate object, wherein the multi-way tree is used for representing the approximate object; And storing the multi-way tree into the cache space.
  7. 7. The geometric object screening method according to claim 6, wherein in recursively subdividing the spatial range of the approximate object by a multi-way tree algorithm to generate a multi-way tree corresponding to the approximate object, an nth subdivision of the spatial range of the approximate object includes: Traversing nodes in the multi-way tree, and determining the current node; dividing the space block corresponding to the current node into a plurality of subspace blocks; Determining the position relation between the subspace partitions and the target geometric object; And determining the partition type corresponding to the current node and/or creating a corresponding node for the subspace partition meeting the subdivision condition in the subspace partitions according to the position relation.
  8. 8. The geometric object screening method according to claim 7, wherein determining the partition type corresponding to the current node and/or creating a corresponding node for a subspace partition satisfying a subdivision condition among the plurality of subspace partitions according to the positional relationship comprises: If the subspace partitions are all located in the target geometric object, determining that the partition type corresponding to the current node is an inner partition; And if the position relations of the subspace partitions and the target geometric object all belong to an overlapping relation or a contact relation, determining the partition type corresponding to the current node as a boundary partition.
  9. 9. A geometric object screening method according to claim 8, further comprising: If the position relations between the subspace blocks and the target geometric object are different, and subspace blocks with the position relation of the target geometric object being in an overlapping relation or a contact relation exist in the subspace blocks, corresponding nodes are created for the rest subspace blocks except for the subspace blocks with the position relation of the target geometric object being in a separation relation.
  10. 10. The geometric object screening method according to claim 7, wherein the dividing the spatial partition corresponding to the current node into a plurality of subspace partitions comprises: And dividing the space block into a plurality of subspace blocks on average according to the space quadrant, wherein different subspace blocks are positioned in different space quadrants.
  11. 11. The geometric object screening method according to claim 7, wherein after determining the partition type corresponding to the current node and/or creating a corresponding node for a subspace partition satisfying a subdivision condition among the plurality of subspace partitions according to the positional relationship, further comprises: determining the node number of the multi-way tree; if the number of the nodes is larger than a soft boundary value, determining the position relation between the leaf nodes of the multi-way tree and the target geometric object; And determining the block type corresponding to the leaf node according to the position relation between the leaf node and the target geometric object.
  12. 12. A geometric object screening method according to any one of claims 1 to 5, wherein the screening the second geometric object according to the first approximate object and/or the second approximate object to reduce geometric objects in the second geometric object that do not satisfy the query scope includes: According to the first approximate object and/or the second approximate object, carrying out position relation condition screening on the first geometric object and the second geometric object, and determining the position relation between the first geometric object and the second geometric object; screening the second geometric objects according to the position relation between the first geometric objects and the second geometric objects so as to reduce geometric objects which do not meet the query range in the second geometric objects; The positional relationship condition screening may include at least one of inclusion condition screening, separation condition screening, overlap or contact condition screening, and distance range condition screening.
  13. 13. The geometric object screening method according to claim 12, wherein, in the case where the positional relationship condition screening includes inclusion condition screening, the performing positional relationship condition screening on the first geometric object and the second geometric object according to the first approximation object and/or the second approximation object, determining the positional relationship between the first geometric object and the second geometric object includes: If the MBR of the second geometric object is positioned inside the inner partition of the first approximate object, determining that the position relationship between the first geometric object and the second geometric object is an inclusion relationship; If the MBR of the second geometric object does not overlap with the inner partition of the first approximate object and the MBR of the second geometric object does not overlap with the boundary partition of the first approximate object, determining that the first geometric object is in a disjoint relationship or not in an inclusive relationship with the second geometric object.
  14. 14. The geometric object screening method according to claim 12, wherein in the case where the positional relationship condition screening includes inclusion condition screening, the performing positional relationship condition screening on the first geometric object and the second geometric object according to the first approximation object and/or the second approximation object, determining a positional relationship between the first geometric object and the second geometric object includes: If the MBR of the first geometric object is positioned inside the inner partition of the second approximate object, determining that the first geometric object and the second geometric object are in a contained relation; if the MBR of the first geometric object does not overlap with the inner partition of the second approximate object and the MBR of the first geometric object does not overlap with the boundary partition of the second approximate object, determining that the first geometric object is in a disjoint relationship or not contained relationship with the second geometric object.
  15. 15. The geometric object screening method according to claim 12, wherein, in the case that the positional relationship condition screening includes a separation condition screening, the positional relationship between the first geometric object and the second geometric object is determined by performing positional relationship condition screening on the first geometric object and the second geometric object according to the first approximate object and/or the second approximate object, by at least one of: Determining that the first geometric object is in a disjoint relationship with the second geometric object if the MBR of the first geometric object does not overlap with an inner partition of the second approximate object and the MBR of the first geometric object does not overlap with a boundary partition of the second approximate object; Determining that the first geometric object is in a disjoint relationship with the second geometric object if the MBR of the second geometric object does not overlap with the inner partition of the first approximation object and the MBR of the second geometric object does not overlap with the boundary partition of the first approximation object; and if the inner partition of the first approximate object is not overlapped with the inner partition of the second approximate object and the boundary partition of the second approximate object are not overlapped, determining that the first geometric object and the second geometric object are in a separation relation.
  16. 16. A geometric object screening method according to any one of claims 1 to 5, further comprising, prior to said determining the target geometric object: And screening the second geometric objects from the plurality of geometric objects according to the MBRs of the first geometric objects and the MBRs respectively corresponding to the plurality of geometric objects.
  17. 17. A geometric object screening apparatus, comprising: The parameter determining module is used for determining a target geometric object, wherein the target geometric object comprises a first geometric object representing a query range and a second geometric object to be detected whether the query range is met; The system comprises an approximate object determining module, a target geometric object determining module and a target geometric object determining module, wherein the approximate object determining module is used for determining an approximate object corresponding to the target geometric object, the approximate object comprises a first approximate object corresponding to the first geometric object and/or a second approximate object corresponding to the second geometric object, a data structure of the approximate object is a multi-way tree, nodes on the multi-way tree correspond to space blocks in the space range of the approximate object, and the approximate object of the geometric object is a multi-way tree, and the nodes on the multi-way tree correspond to the space blocks in the space range of the approximate object; The screening module is used for screening the second geometric objects according to the first approximate objects and/or the second approximate objects so as to reduce geometric objects which do not meet the query range in the second geometric objects; The object identification of the target geometric object is contained in the target geometric object, and the approximate object determining module is specifically configured to, if the approximate object is found in a cache space according to the object identification, read the approximate object from the cache space according to the object identification; The screening module is specifically configured to screen the first geometric object and the second geometric object according to the first approximate object and/or the second approximate object, determine a positional relationship between the first geometric object and the second geometric object, and screen the second geometric object according to the positional relationship between the first geometric object and the second geometric object.
  18. 18. An electronic device includes at least one processor and a memory; the memory stores computer-executable instructions; The at least one processor executing computer-executable instructions stored in the memory causes the at least one processor to perform the geometric object screening method of any one of claims 1 to 16.
  19. 19. A computer readable storage medium having stored therein computer executable instructions which, when executed by a processor, implement the geometric object screening method of any one of claims 1 to 16.

Description

Geometric object screening method, device, equipment and storage medium Technical Field The present application relates to the field of data processing technologies, and in particular, to a geometric object screening method, device, equipment, and storage medium. Background The spatial data used by the geographic information system (Geographic Information System, GIS) is multi-dimensional data, typically consisting of multi-dimensional coordinates or a sequence of coordinates consisting of multi-dimensional coordinates. For the multidimensional data, a minimum boundary matrix (Minimum Bounding Rectangle, MBR) of a geometric object (namely, the geometric shape corresponding to the spatial data) can be used as the spatial index of the geometric object (namely, the spatial data) to realize the query of the spatial data based on the spatial index, wherein in the first step, if the available spatial index exists in the geometric object, the spatial index is utilized to carry out efficient preliminary screening on the geometric object, for example, the geometric object which does not overlap with the query range is rapidly removed to reduce the query range, and in the second step, the accurate geometric calculation is carried out on the result of the preliminary screening in the first step, so that the geometric object which really meets the query condition is accurately selected. However, the accuracy of the geometric object screening in the first step is lower, so that more geometric objects are reserved to the second step for accurate calculation, and further, the calculation resource waste and the query efficiency are reduced. Disclosure of Invention The application provides a geometric object screening method, a device, equipment and a storage medium, which are used for solving the problems of low computational resource waste and low query efficiency of geometric object query caused by low geometric object screening precision. In a first aspect, the present application provides a geometric object screening method, including: Determining a target geometric object, wherein the target geometric object comprises a first geometric object representing a query range and a second geometric object to be detected whether the query range is met; Determining an approximate object corresponding to the target geometric object, wherein the approximate object comprises a first approximate object corresponding to the first geometric object and/or a second approximate object corresponding to the second geometric object, the data structure of the approximate object is a multi-way tree, and nodes on the multi-way tree correspond to space blocks in the space range of the approximate object; And screening the second geometric objects according to the first approximate objects and/or the second approximate objects to reduce geometric objects which do not meet the query range in the second geometric objects. In one possible implementation manner, the target geometric object includes an object identifier of the target geometric object, and the determining the approximate object corresponding to the target geometric object includes reading the approximate object from the cache space according to the object identifier if the approximate object is found in the cache space according to the object identifier. In a possible implementation manner, the method further comprises the steps of determining whether the target geometric object belongs to a large geometric object or not if the approximate object is not found in the cache space according to the object identification, and generating the approximate object and storing the approximate object in the cache space if the target geometric object belongs to the large geometric object. In one possible implementation manner, if the approximate object is not found in the cache space according to the object identification, determining whether the target geometric object belongs to a large geometric object includes determining an attribute value of a minimum boundary matrix MBR of the target geometric object in a target dimension and an attribute upper limit value corresponding to an object class of the target geometric object in the target dimension, comparing the attribute value with the attribute upper limit value, and if the attribute value is greater than the attribute upper limit value, determining that the target geometric object belongs to the large geometric object, otherwise, determining that the target geometric object does not belong to the large geometric object. In a possible implementation manner, the determining the attribute value of the MBR of the target geometric object in the target dimension and the attribute upper limit value of the object class of the target geometric object in the target dimension include determining, in a geometric object column of a data table, the target column of the target geometric object, wherein the same geometric object column of the data table co