Method and apparatus for determining spatial two-tuple, computer device, and storage medium

1 . A method for determining a spatial two-tuple, performed by a computer device, the method comprising:

obtaining a given spatial distance and a plurality of spatial objects, wherein each of the plurality of spatial objects belongs to a first spatial object set or a second spatial object set;

determining a global area based on a first minimum bounding rectangle (MBR) and a first extended minimum bounding rectangle (EMBR) corresponding to the first spatial object set, and a second MBR and a second EMBR corresponding to the second spatial object set;

obtaining a plurality of subspaces by performing a subspace division on the global area;

determining spatial objects included in each of the plurality of subspaces by partitioning the plurality of spatial objects based on a position relationship between each of the plurality of spatial objects and each of the plurality of subspaces; and

determining a spatial two-tuple included in each of the plurality of subspaces that matches the given spatial distance based on a spatial distance between respective spatial objects included in each of the plurality of subspaces,

wherein the obtaining of the plurality of subspaces by performing the subspace division on the global area comprises:

obtaining a first reference spatial object set by sampling a part of spatial objects located in the global area from the first spatial object set, and obtaining a second reference spatial object set by sampling a part of spatial objects located in the global area from the second spatial object set;

obtaining a first space set by performing a quadtree division on the global area based on a number of spatial objects and positions of the spatial objects in the first reference spatial object set located in the global area, and obtaining a second space set by performing the quadtree division on the global area based on a number of spatial objects and positions of the spatial objects in the second reference spatial object set located in the global area; and

determining the plurality of subspaces by fusing the first space set and the second space set.

2 . The method according to claim 1 ,

wherein the determining of the global area comprises determining a common area between the first MBR corresponding to the first spatial object set and the second EMBR corresponding to the second spatial object set as the global area.

3 . The method of claim 1 ,

wherein the obtaining of the first space set by performing the quadtree division on the global area, and the obtaining of the second space set by performing the quadtree division on the global area comprises:

in response to the number of spatial objects in the first reference spatial object set located in the global area being greater than a threshold, generating four first-level subspaces by performing the quadtree division on the global area;

in response to a number of spatial objects in the first reference spatial object set included in each of the four first-level subspaces being less than or equal to the threshold, determining the four first-level subspaces as the first space set corresponding to the first reference spatial object set; and

in response to the number of spatial objects in the second reference spatial object set located in the global area being greater than the threshold, repeatedly performing the quadtree division on the global area until the second space set corresponding to the second reference spatial object set is determined.

4 . The method according to claim 3 , further comprising:

in response to a number of spatial objects in the first reference spatial object set included in any of the four first-level subspaces being greater than the threshold, generating four second-level subspaces by performing the quadtree division on the any of the four first-level subspaces; and

in response to the number of spatial objects in the first reference spatial object set included in each of the four second-level subspaces being less than or equal to the threshold, determining the four second-level subspaces and each of the four first-level subspaces comprising the number of spatial objects in the first reference spatial object set being less than or equal to the threshold, as the first space set corresponding to the first reference spatial object set.

5 . The method according to claim 4 ,

wherein the determining of the plurality of subspaces by fusing the first space set and the second space set comprises, in response to an N-level subspace in the first space set including an (N+1)-level subspace in the second space set, adding the (N+1)-level subspace to the N-level subspace, where N is a positive integer.

6 . The method according to claim 1 ,

wherein the obtaining of the plurality of subspaces by performing the subspace division on the global area comprises obtaining the plurality of subspaces by performing the quadtree division on the global area for a specified number of times.

7 . The method according to claim 1 ,

wherein the determining of the spatial objects included in each of the plurality of subspaces by partitioning the plurality of spatial objects comprises:

determining a position relationship between the first or second MBR corresponding to each of the plurality of spatial objects and each of the plurality of subspaces; and

when a common area exists between the first or second MBR corresponding to any of the plurality of spatial objects and any of the plurality of subspaces, determining that the any of the plurality of subspaces includes the any of the plurality of spatial objects.

8 . The method according to claim 1 , further comprising:

determining a third MBR of a first spatial object and a third EMBR of a second spatial object in any spatial two-tuple of any of the plurality of subspaces, wherein the first spatial object is any spatial object in the first spatial object set, and the second spatial object is any spatial object in the second spatial object set;

determining any vertex coordinate of a common area between the third MBR and the third EMBR; and

in response to the any vertex coordinate being located in the any of the plurality of subspaces, retaining the any spatial two-tuple in the any of the plurality of subspaces.

9 . The method according to claim 8 , further comprising, in response to the any vertex coordinate being not located in the any of the plurality of subspaces, deleting the any spatial two-tuple from spatial two-tuples in the any of the plurality of subspaces.

10 . A computer device, comprising:

a processor, and

a memory stored with a computer program executable by the processor,

wherein the processor is configured to:

obtain a given spatial distance and a plurality of spatial objects, wherein each of the plurality of spatial objects belongs to a first spatial object set or a second spatial object set;

determine a global area based on a first minimum bounding rectangle (MBR) and a first extended minimum bounding rectangle (EMBR) corresponding to the first spatial object set, and a second MBR and a second EMBR corresponding to the second spatial object set;

obtain a plurality of subspaces by performing a subspace division on the global area;

determine spatial objects included in each of the plurality of subspaces by partitioning the plurality of spatial objects based on a position relationship between each of the plurality of spatial objects and each of the plurality of subspaces; and

determine a spatial two-tuple included in each of the plurality of subspaces that matches the given spatial distance based on a spatial distance between respective spatial objects included in each of the plurality of subspaces,

wherein, in obtaining the plurality of subspaces by performing the subspace division on the global area, the processor is configured to:

obtain a first reference spatial object set by sampling a part of spatial objects located in the global area from the first spatial object set, and obtain a second reference spatial object set by sampling a part of spatial objects located in the global area from the second spatial object set;

obtain a first space set by performing a quadtree division on the global area based on a number of spatial objects and positions of the spatial objects in the first reference spatial object set located in the global area, and obtain a second space set by performing the quadtree division on the global area based on a number of spatial objects and positions of the spatial objects in the second reference spatial object set located in the global area; and

determine the plurality of subspaces by fusing the first space set and the second space set.

11 . The computer device of claim 10 ,

wherein in determining the global area, the processor is configured to:

determine a common area between the first MBR corresponding to the first spatial object set and the second EMBR corresponding to the second spatial object set as the global area.

12 . The computer device of claim 10 ,

wherein, in obtaining the first space set and the second space set, the processor is further configured to:

in response to the number of spatial objects in the first reference spatial object set located in the global area being greater than a threshold, generate four first-level subspaces by performing the quadtree division on the global area;

in response to a number of spatial objects in the first reference spatial object set included in each of the four first-level subspaces being less than or equal to the threshold, determine the four first-level subspaces as the first space set corresponding to the first reference spatial object set; and

in response to the number of spatial objects in the second reference spatial object set located in the global area being greater than the threshold, repeatedly perform the quadtree division on the global area until the second space set corresponding to the second reference spatial object set is determined.

13 . The computer device of claim 12 ,

wherein the processor is further configured to:

in response to a number of spatial objects in the first reference spatial object set included in any of the four first-level subspaces being greater than the threshold, generate four second-level subspaces by performing the quadtree division on the any of the four first-level subspaces; and

in response to the number of spatial objects in the first reference spatial object set included in each of the four second-level subspaces being less than or equal to the threshold, determine the four second-level subspaces and each of the four first-level subspaces comprising the number of spatial objects in the first reference spatial object set being less than or equal to the threshold, as the first space set corresponding to the first reference spatial object set.

14 . The computer device of claim 13 ,

wherein in determining the plurality of subspaces by fusing the first space set and the second space set, the processor is configured to:

in response to an N-level subspace in the first space set including an (N+1)-level subspace in the second space set, add the (N+1)-level subspace to the N-level subspace, where N is a positive integer.

15 . The computer device of claim 10 ,

wherein, in obtaining the plurality of subspaces by performing the subspace division on the global area, the processor is configured to:

obtain the plurality of subspaces by performing the quadtree division on the global area for a specified number of times.

16 . The computer device of claim 10 ,

wherein, in determining the spatial objects included in each of the plurality of subspaces, the processor is configured to:

determine a position relationship between the first or second MBR corresponding to each of the plurality of spatial objects and each of the plurality of subspaces; and

when a common area exists between the first or second MBR corresponding to any of the plurality of spatial objects and any of the plurality of subspaces, determine that the any of the plurality of subspaces includes the any of the plurality of spatial objects.

17 . The computer device of claim 10 ,

wherein the processor is further configured to:

determine a third MBR of a first spatial object and a third EMBR of a second spatial object in any spatial two-tuple of any of the plurality of subspaces, wherein the first spatial object is any spatial object in the first spatial object set, and the second spatial object is any spatial object in the second spatial object set;

determine any vertex coordinate of a common area between the third MBR and the third EMBR; and

in response to the any vertex coordinate being located in the any of the plurality of subspaces, retain the any spatial two-tuple in the any of the plurality of subspaces, and in response to the any vertex coordinate being not located in the any of the plurality of subspaces, delete the any spatial two-tuple from spatial two-tuples in the any of the plurality of subspaces.

18 . A non-transitory computer-readable storage medium having a computer program stored thereon, wherein when the computer program is executed by a processor of a computer, a method for determining a spatial two-tuple is implemented, the method comprising:

obtaining a given spatial distance and a plurality of spatial objects, wherein each of the plurality of spatial objects belongs to a first spatial object set or a second spatial object set;

determining a global area based on a first minimum bounding rectangle (MBR) and a first extended minimum bounding rectangle (EMBR) corresponding to the first spatial object set, and a second MBR and a second EMBR corresponding to the second spatial object set;

obtaining a plurality of subspaces by performing a subspace division on the global area;

determining spatial objects included in each of the plurality of subspaces by partitioning the plurality of spatial objects based on a position relationship between each of the plurality of spatial objects and each of the plurality of subspaces; and

determining a spatial two-tuple included in each of the plurality of subspaces that matches the given spatial distance based on a spatial distance between respective spatial objects included in each of the plurality of subspaces,

wherein the obtaining of the plurality of subspaces by performing the subspace division on the global area comprises:

obtaining a first reference spatial object set by sampling a part of spatial objects located in the global area from the first spatial object set, and obtaining a second reference spatial object set by sampling a part of spatial objects located in the global area from the second spatial object set;

obtaining a first space set by performing a quadtree division on the global area based on a number of spatial objects and positions of the spatial objects in the first reference spatial object set located in the global area, and obtaining a second space set by performing the quadtree division on the global area based on a number of spatial objects and positions of the spatial objects in the second reference spatial object set located in the global area; and

determining the plurality of subspaces by fusing the first space set and the second space set.