Interactive representation of clusters of geographical entities

• US 9,697,751 B2
• Filed: 03/09/2010
• Issued: 07/04/2017
• Est. Priority Date: 03/09/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Ramos, Gonzalo A.
• Primary Examiner(s): Al Kawsar, Abdullah
• Assistant Examiner(s): Chung, Mong-Shune
• Application Number:
  US12/720,548
• Publication Number:
  US 20110225541A1
• Time in Patent Office: 2,674 Days
• Field of Search: 715798, 715800, 715801, 715790
• CPC Class Codes: G01C 21/3682 output of POI information on a road map G01C21/3614, G01C21/3685 take precedence
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/957 Browsing optimisation, e.g. caching or content distillation
• CPC Class Codes: G06F 2203/04806 Zoom, i.e. interaction techniques or interactors for controlling the zooming operation
• CPC Class Codes: G06F 3/0481 based on specific properties of the displayed interaction object or a metaphor-based environment, e.g. interaction with desktop elements like windows or icons, or assisted by a cursor's changing behaviour or appearance
• CPC Class Codes: G06F 3/04817 using icons graphical or visual programming using iconic symbols G06F8/34
• CPC Class Codes: G06F 3/0482 Interaction with lists of selectable items, e.g. menus
• CPC Class Codes: G09B 29/007 using computer methods
• CPC Class Codes: G09B 29/10 Map spot or coordinate position indicators; Map reading aids optical projection apparatus per se G03B
• CPC Class Codes: H04N 21/4314 for fitting data in a restricted space on the screen, e.g. EPG data in a rectangular grid

Abstract

Various embodiments enable, in a mapping context, various visual entities to be clustered into groups that do not occlude one another. In at least some embodiments, individual clusters are represented on a map by a puddle defined by a computed contour line. Users can interact with the puddle to acquire more information about the puddle'"'"'s content. In at least some embodiments, user interaction can include zooming operations, clicking operations, hovering operations and the like.

Claims

1. A computer-implemented method comprising:

determining a screen size occupied by individual visual entities when the individual visual entities are presented on a map, the individual visual entities having different locations on the map;

based at least on the screen size occupied by the individual visual entities, determining a first distance represented by the individual visual entities when the map is shown at a first scale and a second distance represented by the individual visual entities when the map is shown at a second scale;

based at least on the first distance represented by the individual visual entities when the map is shown at the first scale, defining a first cluster of first visual entities that includes overlapping first visual entities that overlap on the map when the map is shown at the first scale;

causing the map to be displayed at the first scale with a first puddle, the first puddle having a first irregular shape that encompasses the first visual entities of the first cluster;

receiving a user action requesting a zoom-in operation to be performed on the map from the first scale to the second scale;

based at least on the second distance represented by the individual visual entities when the map is shown at the second scale, defining a second cluster of second visual entities and a third cluster of third visual entities, the second cluster including overlapping second visual entities that overlap when the map is shown at the second scale and the third cluster including overlapping third visual entities that overlap when the map is shown at the second scale; and

causing the map to be displayed at the second scale with a second puddle that encompasses the second cluster of second visual entities and a third puddle that encompasses the third cluster of third visual entities, the second puddle and the third puddle replacing the first puddle.

2. The method of claim 1, the screen size representing a diameter in pixels occupied by the individual visual entities.

3. The method of claim 1, wherein the second cluster does not include any visual entities that are also included in the third cluster.

4. The method of claim 1, wherein the first puddle includes at least some areas on the map that do not have a corresponding visual entity located thereon.

5. The method of claim 1, further comprising:

computing the first puddle, the second puddle, and the third puddle utilizing a bounding structure having vertices, the computing comprising iteratively moving the vertices closer to a border defined by a magnitude in 2D space associated with respective visual entities of the respective cluster, wherein the magnitude in 2D space for each vertex peaks at the vertex'"'"'s location and decays away from the vertex'"'"'s location.

6. The method of claim 1, further comprising rendering a single representative visual entity on the first puddle.

7. The method of claim 1, further comprising:

iteratively merging the individual visual entities into either the second cluster or the third cluster.

8. The method of claim 7, wherein the individual visual entities comprise push pins.

9. The method of claim 1, further comprising:

receiving another user action; and

responsive to receiving the another user action, providing additional information associated with the first puddle.

10. The method of claim 9, wherein the another user action comprises a click on or a hover over the first puddle.

11. The method of claim 9, wherein the additional information is presented in a preview or a miniature browser window.

12. The method of claim 1, wherein the first puddle is displayed without at least some visual entities of the first cluster, the second puddle is displayed without at least some visual entities of the second cluster, and the third puddle is displayed without at least some visual entities of the third cluster.

13. A system comprising:

one or more processors; and

one or more computer readable media having stored thereon computer readable instructions that, when executed by the one or more processors, cause the one or more processors to;

cause a first puddle to be displayed on a map shown at a first scale, the first puddle representing a first cluster of visual entities on the map;

receive a user action requesting a zoom-in operation on the map to a second scale;

determine that individual visual entities represented by the first cluster would overlap on the map when shown at the second scale;

cause the map to show a visual transition of the first puddle being replaced by a second puddle and a third puddle, the second puddle representing a second cluster of visual entities that includes the individual visual entities from the first cluster that would overlap on the map when shown at the second scale, the third puddle representing a third cluster of visual entities including at least some other visual entities included in the first cluster, the visual transition being performed by;

rendering a collection of vertices associated with the first cluster of visual entities in the first puddle;

removing the first puddle to leave the collection of vertices;

performing the zoom-in operation;

rendering the second puddle and the third puddle to include associated vertices of the collection of vertices; and

remove the associated vertices from the second puddle and the third puddle.

14. The system of claim 13, wherein the visual transition shows corresponding visual indications of respective directions from which the second puddle and the third puddle originate.

15. The system of claim 14, wherein the user action comprises a click on an instrumentality shown on the map.

16. The system of claim 14, wherein the visual transition comprises fading tails on individual visual entities moving toward the second puddle and the third puddle.

17. A system comprising:

one or more processors; and

one or more computer readable media having stored thereon computer readable instructions that, when executed by the one or more processors, cause the one or more processors to;

determine a screen size occupied by individual visual entities when the individual visual entities are presented on a map, the individual visual entities having different locations on the map;

based at least on the screen size occupied by the individual visual entities, determine a first distance represented by the individual visual entities when the map is shown at a first scale and a second distance represented by the individual visual entities when the map is shown at a second scale;

based at least on the first distance represented by the individual visual entities when the map is shown at the first scale, define a first cluster of first visual entities that includes overlapping first visual entities that overlap on the map when the map is shown at the first scale;

cause the map to be displayed at the first scale with a first puddle, the first puddle having a first irregular shape that encompasses the first visual entities of the first cluster;

receive a user action requesting a zoom-in operation to be performed on the map from the first scale to the second scale;

based at least on the second distance represented by the individual visual entities when the map is shown at the second scale, define a second cluster of second visual entities and a third cluster of third visual entities, the second cluster including overlapping second visual entities that overlap when the map is shown at the second scale and the third cluster including overlapping third visual entities that overlap when the map is shown at the second scale; and

cause the map to be displayed at the second scale with a second puddle that encompasses the second cluster of second visual entities and a third puddle that encompasses the third cluster of third visual entities, the second puddle and the third puddle replacing the first puddle.

18. The system of claim 17, wherein the first puddle, the second puddle, and the third puddle each have different irregular shapes defined by corresponding locations of respective visual entities therein.

19. The system of claim 17, embodied as a client computing device comprising a portable computer, a handheld computer, or a cell phone.

20. The system of claim 17, embodied as a server, wherein the computer readable instructions, when executed by the one or more processors, cause the one or more processors to:

send results to a client computing device, the results representing the map at the second scale with the second puddle and the third puddle.