Declustering Point-of-Interest Icons

• US 20090110302A1
• Filed: 10/31/2007
• Published: 04/30/2009
• Est. Priority Date: 10/31/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Snow, Bradford J.
• Granted Patent: US 8,339,399 B2
• Time in Patent Office: Days
• US Class Current: 382/225
• CPC Class Codes: G06T 11/206 Drawing of charts or graphs
• CPC Class Codes: G06T 17/05 Geographic models

Abstract

Super-clusters of point-of-interest locations are created based on how close the point-of-interest locations are to one another. Additionally, one or more mini-clusters are created in each of the super-clusters based on how close the point-of-interest locations within each super-cluster are to one another. For each of one or more mini-clusters, some point-of-interest icons corresponding to the point-of-interest locations are placed based at least in part on a mean out positioning vector that is based at least in part on a center of the mini-cluster and a center of the super-cluster that includes the mini-cluster. Additionally, some point-of-interest icons are attempted to be placed as a group, while others are attempted to be placed individually.

Claims

1. One or more computer storage media having stored thereon multiple instructions that, when executed by one or more processors, cause the one or more processors to:

create super-clusters of point-of-interest locations based on how close the point-of-interest locations are to one another;

create one or more mini-clusters included in each of the super-clusters based on how close the point-of-interest locations within each super-cluster are to one another; and

for each of one or more mini-clusters, place point-of-interest icons corresponding to the point-of-interest locations based at least in part on a mean out positioning vector that is based at least in part on a center of the mini-cluster and a center of the super-cluster that includes the mini-cluster.

2. One or more computer storage media as recited in claim 1, wherein the instructions further cause the one or more processors to:

place multiple point-of-interest icons in a first mini-cluster on a circle having a center at the center of the first mini-cluster; and

rotate the circle to attempt to identify locations for the point-of-interest icons that have no collisions.

3. One or more computer storage media as recited in claim 2, wherein the instructions further cause the one or more processors to:

reduce the circle to an arc less than 360 degrees;

increase a distance between the center of the mini-cluster and the arc; and

rotate the arc to attempt to identify locations for the point-of-interest icons that have no collisions.

4. One or more computer storage media as recited in claim 1, wherein each of the point-of-interest icons is attempted to be placed without collision, and wherein collision occurs for a point-of-interest icon when the point-of-interest icon is attempted to be displayed in any pixels in which any other leader line, point-of-interest icon, or point-of-interest location is displayed.

5. One or more computer storage media as recited in claim 1, wherein the instructions further cause the one or more processors to place a point-of-interest icon included in one of the one or more mini-clusters along the mean out positioning vector for the one of the one or more mini-clusters.

6. One or more computer storage media as recited in claim 5, wherein the instructions further cause the one or more processors to rotate the mean out positioning vector about the center of the super-cluster that includes the mini-cluster, attempting to place the point-of-interest icon along the mean out positioning vector as the mean out positioning vector is rotated.

7. One or more computer storage media as recited in claim 1, wherein the instructions further cause the one or more processors to select super-clusters to have the point-of-interest icons corresponding to the point-of-interest locations included in the mini-clusters within the super-clusters placed in an order where super-clusters including more point-of-interest locations are selected prior to super-clusters including fewer point-of-interest locations.

8. One or more computer storage media as recited in claim 1, wherein the instructions further cause the one or more processors to select mini-clusters to have the point-of-interest icons corresponding to the point-of-interest locations included in the mini-clusters placed in an order where mini-clusters having centers closer to the center of the super-cluster that includes the mini-clusters are selected prior to mini-clusters having centers further from the center of the super-cluster.

9. One or more computer storage media as recited in claim 1, wherein for any of the point-of-interest icons that are not successfully placed based on mean out positioning vectors, attempting to place the point-of-interest icon in a series of stages, the series of stages including:

a first stage that allows no collisions;

a second stage that allows collisions only between a leader line of the point-of-interest icon and leader lines of other point-of-interest icons;

a third stage that allows collisions only between the leader line of the point-of-interest icon and leader lines of other point-of-interest icons or other point-of-interest locations; and

a fourth stage that allows collisions between the leader line of the point-of-interest icon and anything else.

10. A method comprising:

creating super-clusters of point-of-interest locations;

creating, within each super-cluster, one or more mini-clusters of point-of-interest locations;

for each mini-cluster having a single point-of-interest location, placing a point-of-interest icon corresponding to the single point-of-interest location for display; and

for each mini-cluster having multiple point-of-interest locations, attempting to place point-of-interest icons corresponding to the multiple point-of-interest locations as a group, and placing the point-of-interest icons corresponding to the multiple point-of-interest locations individually only if the attempting to place the point-of-interest icons as a group is unsuccessful.

11. A method as recited in claim 10, wherein placing the point-of-interest icon corresponding to the single point-of-interest location for a first mini-cluster comprises placing the point-of-interest icon along a mean out positioning vector based at least in part on the single point-of-interest location and a center of the super-cluster that includes the first mini-cluster.

12. A method as recited in claim 10, wherein placing the point-of-interest icons corresponding to the multiple point-of-interest locations individually comprises attempting to place the point-of-interest icons in a series of stages, the series of stages including:

a first stage that allows no collisions;

a second stage that allows collisions only between a leader line of the point-of-interest icon and leader lines of other point-of-interest icons;

a third stage that allows collisions only between the leader line of the point-of-interest icon and leader lines of other point-of-interest icons or other point-of-interest locations; and

a fourth stage that allows collisions between the leader line of the point-of-interest icon and anything else.

13. A method as recited in claim 12, wherein a collision occurs for a point-of-interest icon when the point-of-interest icon is attempted to be located in a same location as any other leader line, point-of-interest icon, or point-of-interest location.

14. A method as recited in claim 10, wherein placing the point-of-interest icons corresponding to the multiple point-of-interest locations individually comprises attempting to place each of the point-of-interest icons using mean out positioning.

15. A method as recited in claim 14, wherein placing the point-of-interest icons corresponding to the multiple point-of-interest locations individually further comprises for any point-of-interest icon that is not placed:

attempting to place the point-of-interest icon at an initial distance and angle from the corresponding point-of-interest location; and

if the point-of-interest icon cannot be successfully placed at the initial distance and angle, then attempting to place the point-of-interest icon at locations resulting from spinning the point-of-interest icon around the location at the initial distance.

16. A method as recited in claim 15, wherein placing the point-of-interest icons corresponding to the multiple point-of-interest locations individually further comprises for any point-of-interest icon that is not placed after attempting to place the point-of-interest icon at locations resulting from spinning the point-of-interest icon around the location at the initial distance:

increasing the distance from the point-of-interest location;

attempting to place the point-of-interest icon at the increased distance and the angle from the corresponding point-of-interest location; and

if the point-of-interest icon cannot be successfully place at the increased distance and the angle, then attempting to place the point-of-interest icon at locations resulting from spinning the point-of-interest icon around the location at the increased distance.

17. A method as recited in claim 10, wherein attempting to place the point-of-interest icons as a group comprises:

placing multiple point-of-interest icons in the mini-cluster on a circle having a center at the center of the mini-cluster; and

rotating the circle to attempt to identify locations for the point-of-interest icons that have no collisions.

18. A computing device comprising:

a processor; and

a computer readable media having stored thereon instructions that cause the one or more processors to;

create super-clusters of point-of-interest locations;

create, within each super-cluster, one or more mini-clusters of point-of-interest locations;

for each mini-cluster having a single point-of-interest location, place a point-of-interest icon corresponding to the single point-of-interest location for display based at least in part on a mean out positioning vector that is based at least in part on a center of the mini-cluster and a center of the super-cluster that includes the mini-cluster; and

for each mini-cluster having multiple point-of-interest locations, attempt to place point-of-interest icons corresponding to the multiple point-of-interest locations as a group, and place the point-of-interest icons corresponding to the multiple point-of-interest locations individually only if the attempt to place the point-of-interest icons as a group is unsuccessful.

19. A computing device as recited in claim 18, wherein each of the point-of-interest icons is attempted to be placed without collision, and wherein collision occurs for a point-of-interest icon when the point-of-interest icon is attempted to be placed in a same location as any other leader line, point-of-interest icon, or point-of-interest location.

20. A computing device as recited in claim 18, wherein to place the point-of-interest icons corresponding to the multiple point-of-interest locations individually comprises attempting to place the point-of-interest icons in a series of stages, the series of stages including:

a first stage that allows no collisions;

a second stage that allows collisions only between a leader line of the point-of-interest icon and leader lines of other point-of-interest icons;

a third stage that allows collisions only between the leader line of the point-of-interest icon and leader lines of other point-of-interest icons or other point-of-interest locations; and

a fourth stage that allows collisions between the leader line of the point-of-interest icon and anything else.