Efficient label insertion and collision handling

Abstract

Techniques are described for efficient label insertion and collision handling. A bounding geometry for a label to be graphically displayed on a display screen as part of an electronic map is determined, wherein the bounding geometry comprises a circle. The bounding geometry is inserted into a grid index, wherein the grid index represents a viewport of the electronic map. Disjoint regions of the grid index intersected by the bounding geometry are identified, wherein each disjoint region represents a different portion of the viewport. For each intersected disjoint region, it is identified whether there is at least one collision between the bounding geometry and one or more existing bounding geometries in the disjoint region; and responsive to identifying whether there is at least one collision in the intersected disjoint region, a target opacity of the label is set.

What is claimed is: 
     
       1. A computer-implemented method comprising:
 determining a bounding geometry for a label as part of an electronic map; 
 inserting the determined bounding geometry into a grid index, wherein the grid index represents a viewport of the electronic map; 
 identifying disjoint regions of the grid index intersected by the determined bounding geometry, wherein different disjoint regions represent different portions of the viewport; 
 for one or more intersected disjoint regions:
 identifying a position of the determined bounding geometry within the intersected disjoint region; 
 identifying positions of one or more existing bounding geometries in the disjoint region; and 
 determining whether the identified position of the determined bounding geometry and the identified positions of at least one of the one or more existing bounding geometries overlap; and 
 
 responsive to identifying that the determined bounding geometry overlaps at least one of the one or more existing bounding geometries, setting a target opacity of the label. 
 
     
     
       2. The method of  claim 1 , wherein the determined bounding geometry overlaps at least one of the one or more existing bounding geometries, further comprising:
 removing the determined bounding geometry from the grid index; and 
 marking the label as collided. 
 
     
     
       3. The method of  claim 1 , wherein the determined bounding geometry does not overlap any existing bounding geometries, further comprising:
 marking the determined bounding geometry as used. 
 
     
     
       4. The method of  claim 1 , wherein a size of each disjoint region is based at least in part on a size of the determined bounding geometry. 
     
     
       5. The method of  claim 4 , wherein the size of each disjoint region is within a threshold amount of double the size of the determined bounding geometry. 
     
     
       6. The method of  claim 1 , wherein the label comprises a text string comprising a plurality of letters, wherein the determined bounding geometry comprises a set of circles such that there is a circle for each letter of the plurality of letters. 
     
     
       7. The method of  claim 1 , wherein the label comprises a text string comprising a plurality of letters, wherein the determined bounding geometry comprises a set of circles such that a beginning and an end of the text string are bounded, there is not more than a first threshold distance between adjacent circles, and there is not more than a threshold amount of overlap between circles. 
     
     
       8. The method of  claim 1 , wherein determining the determined bounding geometry for the label comprises:
 determining the label is a line label; 
 identifying a line geometry associated with the label; 
 identifying a size of the label; and 
 fitting one or more circles to the label based at least in part on the size and the line geometry. 
 
     
     
       9. The method of  claim 8 , wherein the size of the label is based at least in part on a style. 
     
     
       10. The method of  claim 1 , wherein identifying whether the determined bounding geometry overlaps at least one of the one or more existing bounding geometries comprises:
 for each existing bounding geometry in the disjoint region:
 comparing coordinate space overlapped by the determined bounding geometry and coordinate space overlapped by the existing bounding geometry. 
 
 
     
     
       11. The method of  claim 1 , wherein determining whether the positions of the determined bounding geometry and the one or more existing bounding geometries overlap comprises:
 identifying pixels used by the one or more existing bounding geometries; 
 identifying pixels used by the determined bounding geometry; and 
 determining whether at least one pixel is used by both the bounding geometry and the existing bounding geometry. 
 
     
     
       12. The method of  claim 1 , wherein determining whether the positions of the determined bounding geometry and the one or more existing bounding geometries overlap comprises:
 identifying global coordinate bounds of the one or more existing bounding geometries; 
 identifying global coordinate bounds of the determined bounding geometry; and 
 determining whether at the global coordinate bounds of the one or more existing bounding geometries and the global coordinate bounds of the determined bounding geometry include shared coordinate space. 
 
     
     
       13. A non-transitory computer-readable storage medium storing executable instructions that, when executed by a processor, cause the processor to perform steps comprising:
 determining a bounding geometry for a label as part of an electronic map; 
 inserting the determined bounding geometry into a grid index, wherein the grid index represents a viewport of the electronic map; 
 identifying disjoint regions of the grid index intersected by the determined bounding geometry, wherein different disjoint regions represent different portions of the viewport; 
 for one or more intersected disjoint regions:
 identifying a position of the determined bounding geometry within the intersected disjoint region; 
 identifying positions of one or more existing bounding geometries in the disjoint region; and 
 determining whether the identified position of the determined bounding geometry and the identified positions of at least one of the one or more existing bounding geometries overlap; and 
 
 responsive to determining that the determined bounding geometry overlaps at least one of the one or more existing bounding geometries, setting a target opacity of the label. 
 
     
     
       14. The non-transitory computer-readable storage medium of  claim 13 , wherein the determined bounding geometry overlaps at least one of the one or more existing bounding geometries, the steps further comprising:
 removing the determined bounding geometry from the grid index; and 
 marking the label as collided. 
 
     
     
       15. The non-transitory computer-readable storage medium of  claim 13 , wherein the determined bounding geometry overlaps at least one of the one or more existing bounding geometries, further comprising:
 marking the determined bounding geometry as used. 
 
     
     
       16. The non-transitory computer-readable storage medium of  claim 13 , wherein the label comprises a text string comprising a plurality of letters, wherein the determined bounding geometry comprises a set of circles such that a beginning and an end of the text string are bounded, there is not more than a first threshold distance between adjacent circles, and there is not more than a threshold amount of overlap between circles. 
     
     
       17. The non-transitory computer-readable storage medium of  claim 13 , wherein determining the determined bounding geometry for the label comprises:
 determining the label is a line label; 
 identifying a line geometry associated with the label; 
 identifying a size of the label; and 
 fitting one or more circles to the label based at least in part on the size and the line geometry. 
 
     
     
       18. The non-transitory computer-readable storage medium of  claim 13 , wherein determining whether the determined bounding geometry overlaps at least one of the one or more existing bounding geometries:
 for each existing bounding geometry in the disjoint region:
 comparing coordinate space overlapped by the determined bounding geometry and coordinate space overlapped by the existing bounding geometry. 
 
 
     
     
       19. The non-transitory computer-readable storage medium of  claim 13 , wherein determining whether the determined bounding geometry overlaps at least one of the one or more existing bounding geometries comprises:
 identifying pixels used by the one or more existing bounding geometries; 
 identifying pixels used by the determined bounding geometry; and 
 determining whether at least one pixel is used by both the bounding geometry and the existing bounding geometry. 
 
     
     
       20. The non-transitory computer-readable storage medium of  claim 13 , wherein determining whether the determined bounding geometry overlaps at least one of the one or more existing bounding geometries comprises:
 identifying global coordinate bounds of the one or more existing bounding geometries; 
 identifying global coordinate bounds of the determined bounding geometry; and 
 determining whether at the global coordinate bounds of the one or more existing bounding geometries and the global coordinate bounds of the determined bounding geometry include shared coordinate space.