Generating simplified map shapes
In some implementations, a method performed by data processing apparatuses includes receiving map data that identifies a layout of physical objects within a physical area, identifying contiguous groups of the physical objects as composite objects, selecting bounding algorithms to use for generating graphical shapes for the composite objects, generating graphical shapes by applying the selected bounding algorithms to the composite objects, and testing the graphical shapes against one or more criteria. For candidate graphical shapes that fail a test, a new bounding algorithm can be selected and the generating and the testing can be repeated using the new bounding algorithm. A simplified graphical map can be output that represents the physical objects within the physical area using the graphical shapes.
1. A method for generating simplified graphical maps, the method comprising:
receiving, at a graphics processing computer system, map data that identifies a layout of physical objects within a physical area;
identifying, by the graphics processing computer system, contiguous groups of the physical objects as composite objects;
selecting, by the graphics processing computer system, bounding algorithms to use for generating graphical shapes for the composite objects, wherein the bounding algorithms are selected individually for each of the composite objects from among a plurality of bounding algorithms based on characteristics of each of the composite objects;
generating, by the graphics processing computer system, graphical shapes by applying the selected bounding algorithms to the composite objects;
for each of the graphical shapes, testing, by the graphics processing computer system, the graphical shape against one or more criteria to determine whether the graphical shape is within a threshold fit with respect to an object which the shape represents, wherein at least one of the one or more criteria tested against the graphical shape comprises the area of the graphical shape being within a threshold of the area of the composite object;
in response to determining that a particular graphical shape of the graphical shapes has failed the testing against the one or more criteria, (i) selecting a new bounding algorithm, (ii) regenerating the graphical shape for the composite object using the new bounding algorithm, and (iii) performing another test on the regenerated graphical shape; and
outputting, by the graphics processing computer system, a simplified graphical map that represents the physical objects within the physical area, using the generated graphical shapes that have passed a previously performed test.
2. The method of claim 1 , wherein identifying the composite objects comprises:
selecting a physical object from among the physical objects;
determining, using a spatial index, whether another physical object is within a threshold distance of the selected physical object;
in response to the other physical object being within the threshold distance, adding the other physical object to a composite object that includes the selected physical object; and
selecting the other physical object and repeating the determining and the adding until no other physical objects are determined to be within the threshold distance of any shapes of the composite object.
3. The method of claim 1 , wherein identifying the composite object further comprises determining the threshold distance for the selected physical object, by identifying a classification of the selected physical object, and identifying a corresponding threshold distance for objects of the classification.
4. The method of claim 1 , wherein selecting the bounding algorithms comprises:
determining whether the composite object is diagonally oriented within the physical area; and
selecting a convex hull bounding algorithm when the composite object is diagonally oriented, or otherwise selecting a bounding box algorithm.
5. The method of claim 4 , wherein when the convex hull algorithm is selected and the graphical shape generated for the composite object fails the testing against the one or more criteria, the new bounding algorithm that is selected comprises a buffering bounding algorithm, wherein the buffering bounding algorithm comprises (i) performing a buffer operation on the composite object to generate a buffered composite object, (ii) performing a union operation on the buffered composite object to generate a union composite object, and (iii) performing an unbuffer operation on the union composite object to generate at least one graphical shape for the composite object.
6. The method of claim 5 , wherein when the buffering bounding algorithm results in the generation of more than one shape, the graphical shape that was generated by applying the convex hull bounding algorithm is selected to represent the composite object.
7. The method of claim 4 , wherein when the bounding box algorithm is selected and the graphical shape generated for the composite object fails the testing against the one or more criteria, the new bounding algorithm that is selected comprises an orthogonal convex hull bounding algorithm.
8. The method of claim 7 , wherein when the orthogonal hull convex hull bounding algorithm is selected and the graphical shape generated for the composite object fails the testing against the one or more criteria, the new bounding algorithm that is selected comprises a buffering bounding algorithm, wherein the buffering bounding algorithm comprises (i) performing a buffer operation on the composite object to generate a buffered composite object, (ii) performing a union operation on the buffered composite object to generate a union composite object, and (iii) performing an unbuffer operation on the union composite object to generate at least one graphical shape for the composite object.
9. The method of claim 8 , wherein when the buffering bounding algorithm results in the generation of more than one shape, the graphical shape that was generated by applying the orthogonal convex hull bounding algorithm is selected to represent the composite object.
10. The method of claim 1 , wherein the area of the composite object is determined by aggregating the areas of the physical objects included in the composite object.
11. The method of claim 1 , wherein at least two different bounding algorithms are selected for generating graphical shapes for the simplified graphical map.
12. The method of claim 1 , wherein the physical area comprises a retail store and the physical objects comprise aisles within the retail store.
13. The method of claim 1 , wherein the outputting includes storing the simplified graphical map in one or more digital files.
14. The method of claim 1 , wherein the outputting includes presenting one or more graphical indicators on the simplified graphical map, the one or more graphical indicators representing one or more of a section location, an item location, or a user location within the simplified graphical map.
15. A computer system comprising:
a data processing apparatus including one or more processors, memory, and storage devices storing instructions that, when executed, cause the one or more processors to perform operations comprising:
receiving, at a graphics processing computer system, map data that identifies a layout of physical objects within a physical area;
identifying, by the graphics processing computer system, contiguous groups of the physical objects as composite objects;
selecting, by the graphics processing computer system, bounding algorithms to use for generating graphical shapes for the composite objects, wherein the bounding algorithms are selected individually for each of the composite objects from among a plurality of bounding algorithms based on characteristics of each of the composite objects;
generating, by the graphics processing computer system, graphical shapes by applying the selected bounding algorithms to the composite objects;
for each of the graphical shapes, testing, by the graphics processing computer system, the graphical shape against one or more criteria to determine whether the graphical shape is within a threshold fit with respect to an object which the shape represents, wherein at least one of the one or more criteria tested against the graphical shape comprises the area of the graphical shape being within a threshold of the area of the composite object;
in response to determining that a particular graphical shape of the graphical shapes has failed the testing against the one or more criteria, (i) selecting a new bounding algorithm, (ii) regenerating the graphical shape for the composite object using the new bounding algorithm, and (iii) performing another test on the regenerated graphical shape; and
outputting, by the graphics processing computer system, a simplified graphical map that represents the physical objects within the physical area, using the generated graphical shapes that have passed a previously performed test.
16. The computer system of claim 15 , wherein identifying the composite objects comprises:
selecting a physical object from among the physical objects;
determining, using a spatial index, whether another physical object is within a threshold distance of the selected physical object;
in response to the other physical object being within the threshold distance, adding the other physical object to a composite object that includes the selected physical object; and
selecting the other physical object and repeating the determining and the adding until no other physical objects are determined to be within the threshold distance of any shapes of the composite object.
17. The computer system of claim 15 , wherein the outputting includes presenting one or more graphical indicators on the simplified graphical map, the one or more graphical indicators representing one or more of a section location, an item location, or a user location within the simplified graphical map.
18. A non-transitory computer-readable storage medium coupled to one or more processors and having instructions stored thereon which, when executed by the one or more processors, cause the one or more processors to perform operations comprising:
receiving, at a graphics processing computer system, map data that identifies a layout of physical objects within a physical area;
identifying, by the graphics processing computer system, contiguous groups of the physical objects as composite objects;
selecting, by the graphics processing computer system, bounding algorithms to use for generating graphical shapes for the composite objects, wherein the bounding algorithms are selected individually for each of the composite objects from among a plurality of bounding algorithms based on characteristics of each of the composite objects;
generating, by the graphics processing computer system, graphical shapes by applying the selected bounding algorithms to the composite objects;
for each of the graphical shapes, testing, by the graphics processing computer system, the graphical shape against one or more criteria to determine whether the graphical shape is within a threshold fit with respect to an object which the shape represents, wherein at least one of the one or more criteria tested against the graphical shape comprises the area of the graphical shape being within a threshold of the area of the composite object;
in response to determining that a particular graphical shape of the graphical shapes has failed the testing against the one or more criteria, (i) selecting a new bounding algorithm, (ii) regenerating the graphical shape for the composite object using the new bounding algorithm, and (iii) performing another test on the regenerated graphical shape; and
outputting, by the graphics processing computer system, a simplified graphical map that represents the physical objects within the physical area, using the generated graphical shapes that have passed a previously performed test.
19. The non-transitory computer-readable storage medium of claim 18 , wherein identifying the composite objects comprises:
selecting a physical object from among the physical objects;
determining, using a spatial index, whether another physical object is within a threshold distance of the selected physical object;
in response to the other physical object being within the threshold distance, adding the other physical object to a composite object that includes the selected physical object; and
selecting the other physical object and repeating the determining and the adding until no other physical objects are determined to be within the threshold distance of any shapes of the composite object.
20. The non-transitory computer-readable storage medium of claim 18 , wherein the outputting includes presenting one or more graphical indicators on the simplified graphical map, the one or more graphical indicators representing one or more of a section location, an item location, or a user location within the simplified graphical map.