Determining distances between real-world entities modeled as geometric shapes

1. A system comprising:

a processor; and

a non-transitory storage medium storing instructions executable on the processor to:

receive a request for determining a requested distance between shapes representing geographical real-world entities, and receive input data comprising a respective set of points for each of the shapes, the requested distance being one of a minimum distance and a maximum distance between the shapes;

subdivide a coordinate space, the subdividing comprising:

forming a plurality of non-empty quadrants, the non-empty quadrants associated with the shapes,

in response to the plurality of non-empty quadrants not satisfying Polygonal Map quadtree rules, further subdividing the plurality of non-empty quadrants into a further plurality of non-empty quadrants,

forming a plurality of sets of the further plurality of non-empty quadrants, and

disregarding at least one set of the plurality of sets based on distance information associated with the at least one set of the plurality of sets;

identify a non-empty quadrant set comprising non-empty quadrants based on the subdividing, the identified non-empty quadrant set satisfying a predetermined condition of the Polygonal Map quadtree rules, wherein identifying the non-empty quadrant set comprises excluding, from the non-empty quadrant set, empty quadrants produced by the subdividing;

determine a distance between portions of the shapes in the non-empty quadrants of the identified non-empty quadrant set; and

output the determined distance between the portions of the shapes in the non-empty quadrants of the identified non-empty quadrant set as the requested distance responsive to the request.

2. The system of claim 1 , wherein the instructions are executable on the processor to:

associate keys with respective sets of the plurality of sets of the further plurality of non-empty quadrants; and

identify the non-empty quadrant set from the plurality of sets of the further plurality of non-empty quadrants based on respective minimum bounding rectangle (MBR) distances, the respective MBR distances being distances between respective MBRs enclosing the shapes.

3. The system of claim 2 , wherein the instructions are executable on the processor to:

for a particular portion of the shapes included in the identified non-empty quadrant set:

determine distances of the particular portion to other portions of the shapes included in other non-empty quadrants of the identified non-empty quadrant set;

record as a global variable, an optimal distance value of the distances; and

output the optimal distance value as the requested distance responsive to the request.

4. The system of claim 1 , wherein the shapes comprise a first shape and multiple other shapes, and the instructions are executable on the processor to:

determine distances between a non-empty quadrant of the first shape and non-empty quadrants of the multiple other shapes; and

select one of the distances as the requested distance.

5. The system of claim 1 , wherein the instructions are executable on the processor to:

determine if a given non-empty quadrant set comprising non-empty quadrants satisfies the predetermined condition; and

in response to the given non-empty quadrant set not satisfying the predetermined condition, subdivide the non-empty quadrants of the given non-empty quadrant set into smaller quadrants.

6. The system of claim 1 , wherein the shapes are one or more of areal shapes and non-areal shapes.

7. The system of claim 1 , wherein the shapes comprise a first shape and a second shape that is different from the first shape.

8. The system of claim 1 , wherein the instructions are executable on the processor to determine that the identified non-empty quadrant set satisfies the predetermined condition of the Polygonal Map quadtree rules responsive to determining that each non-empty quadrant in the non-empty quadrant set includes only one vertex of a respective shape of the shapes.

9. The system of claim 1 , wherein the empty quadrants excluded from the non-empty quadrant set do not include any part of the shapes.

10. A method performed by a computing device, comprising:

receiving input data of polygons respectively representing real-world entities, the input data comprising a respective set of vertices for each polygon of the polygons;

receiving a request to compute a minimum distance between the polygons;

positioning the polygons in a coordinate space based on the respective sets of vertices;

forming a plurality of quadrant sets from quadrants derived from subdividing the coordinate space associated with the polygons;

identifying a quadrant set from the plurality of quadrant sets, the identifying comprising determining that the quadrant set satisfies a predetermined condition of Polygonal Map quadtree rules based on determining that each non-empty quadrant in the quadrant set includes only one vertex of a respective polygon of the polygons, and wherein the identifying of the quadrant set comprises excluding, from the quadrant set, empty quadrants produced by the subdividing;

determining a distance between most proximal edges of the polygons in the non-empty quadrants of the quadrant set; and

outputting the distance of the most proximal edges as the minimum distance between the polygons.

11. The method of claim 10 , wherein the polygons comprise a first polygon and other polygons, the method further comprising:

determining distances between a non-empty quadrant of the first polygon and non-empty quadrants of the other polygons.

12. The method of claim 10 , comprising:

forming, by the computing device, the plurality of quadrant sets from quadrants satisfying the predetermined condition.

13. The method of claim 12 , further comprising:

identifying, by the computing device, a first quadrant set of the plurality of quadrant sets, wherein the quadrants in the first quadrant set have a minimum distance based on distances between respective minimum bounding rectangles (MBRs) enclosing the polygons;

for a particular edge of the polygons included in the first quadrant set:

determining, by the computing device, distances of the particular edge from other edges included in other quadrants of the first quadrant set; and

recording, by the computing device, a lowest value of the distances as a global variable.

14. The method of claim 10 , wherein the empty quadrants excluded from the quadrant set do not include any part of the polygons.

15. A non-transitory computer readable medium comprising instructions that upon execution cause a system to:

receive a request for determining a requested distance between geographic entities, the requested distance being one of a maximum distance and a minimum distance between the geographic entities;

access input data of shapes respectively modeling the geographic entities, the input data comprising a respective set of points defining each shape of the shapes in a coordinate space;

subdivide the coordinate space, the subdividing comprising:

forming a plurality of non-empty quadrants, the non-empty quadrants associated with the shapes,

in response to the plurality of non-empty quadrants not satisfying Polygonal Map quadtree rules, further subdividing the plurality of non-empty quadrants into a further plurality of non-empty quadrants,

forming a plurality of sets of the further plurality of non-empty quadrants, and

disregarding at least one set of the plurality of sets based on distance information associated with the at least one set of the plurality of sets;

identify a quadrant set including non-empty quadrants based on the subdividing, the identified quadrant set satisfying a predetermined condition of the Polygonal Map quadtree rules, wherein the identifying of the quadrant set comprises excluding, from the quadrant set, empty quadrants produced by the subdividing;

determine a distance between portions of the shapes included in the non-empty quadrants of the identified quadrant set; and

output, as the requested distance, the distance between the portions of the shapes in the non-empty quadrants of the identified quadrant set.

16. The non-transitory computer readable medium of claim 15 , wherein the empty quadrants excluded from the quadrant set do not include any part of the shapes.