Appropriately sized target expansion

• US 7,679,617 B2
• Filed: 02/15/2007
• Issued: 03/16/2010
• Est. Priority Date: 02/15/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Baudisch, Patrick, Kolmykov-Zotov, Alexander
• Primary Examiner(s): Nguyen; Kimbinh T
• Application Number:
  US11/675,171
• Publication Number:
  US 20080198160A1
• Time in Patent Office: 1,125 Days
• Field of Search: 345/423, 345/473, 382/103, 382/117, 715/764, 715/814
• US Class Current: 345/423
• CPC Class Codes: G06F 3/04817 using icons graphical or visual programming using iconic symbols G06F8/34

Abstract

The present starburst target expansion technique connects targets to peripheral screen space to produce reasonably sized tiles for all targets including those that are located inside of a cluster. The resulting layout is characterized by lines escaping from the cluster center. By providing targets located inside a cluster with access to empty screen space, the present starburst target expansion technique is able to assign screen space to targets that remain small if expanded using the traditional Voronoi approach. If used on a device with limited input accuracy, such as a pen-based tablet or a touch screen-based kiosk system, target expansion via the starburst target expansion technique can lead to substantial performance improvements.

Claims

1. A computer-implemented process for expanding targets on a display, comprising:

using a computing device for;

analyzing a display containing multiple targets to identify available space for expanding the multiple targets; and

expanding one or more targets into the available space, comprising;

organizing the multiple targets into cliques of donors of screen space and recipients of screen space;

organizing the multiple targets into nested rings;

routing claim lines from each of the multiple targets towards the periphery of the display using the nested rings; and

growing the claim lines into tiles that utilize the available space.

2. The computer-implemented process of claim 1 wherein analyzing the display comprises:

performing a Voronoi tessellation on the targets to obtain a tile for each target;

designating the targets corresponding to the small tiles as targets in need of expansion.

3. The computer-implemented process of claim 1 wherein organizing targets into cliques of donors and participants comprises:

creating cliques of targets based on adjacency, wherein each target in the clique is a recipient of screen space;

adding all donors immediately adjacent to the cliques to the clique;

if a donor is adjacent to multiple cliques adding the donor to the smallest average tile size; and

adding additional donors if they are particularly large or they are located in an area in which a clique lacks good donors.

4. The computer-implemented process of claim 1 wherein organizing targets into nested rings comprises:

computing a convex hull over all targets of a clique to create an outer ring;

computing a convex hull over the targets inside the outer ring to create an inner ring;

continuing to compute a convex hull inside the previous inner ring to create a new inner ring until no further convex hulls can be created.

5. The computer-implemented process of claim 4 wherein routing claim lines comprises:

starting at the inner most ring, connecting all targets to the closest section of the immediately enclosing ring by drawing a portion of the claim line;

for each ring outside the inner most ring, routing all the targets on or inside that ring to the closest section of the next out ring, by drawing a portion of a claim line; and

once all targets are connected to the outmost ring, drawing claim lines radially into peripheral display space.

6. The computer-implemented process of claim 5 wherein the portions of the claim lines are drawn from a target to the mid-section of the closest ring section.

7. The computer-implemented process of claim 1 wherein growing the claim lines into tiles that use available space comprises:

for each pixel on the screen assigning it to the closest claim line.

8. The computer-implemented process of claim 4 wherein routing the claim lines comprises:

locating available screen space by casting rays from the outer ring into the periphery of the display, intersecting said rays with clique and display boundaries and measuring the length of each ray, and using the rays to define boundaries of sectors of the display;

excluding any sectors that are too shallow from further processing;

placing claim line end points into sectors not excluded to partition the screen space radially; and

routing claim lines from the claim line end points to a target.

9. The computer-implemented process of claim 8 wherein the endpoints are layered in a staggered fashion.

10. A computer-readable medium having computer-executable instructions for performing the process recited in claim 1.

11. A process for expanding targets in a cluster on a display into available screen space comprising:

using a computing device for;

identifying targets that require additional expansion;

organizing targets into cliques of space donors and space recipients;

creating a skeleton to be used for growing targets into available display space using the cliques of space donors and space recipients; and

growing the targets into tiles that utilize available space using the skeleton.

12. The computer-implemented process of claim 11 wherein identifying targets that need expansion, comprises:

performing a Voronoi tessellation on the targets to obtain a tile for each target;

identifying small tiles by identifying those tiles with tile sizes far below the average tile size; and

designating the targets corresponding to the small tiles as targets in need of expansion.

13. The computer-implemented process of claim 11 wherein the action of expanding each target into the available space comprises for each pixel on the screen assigning it to the closest portion of the skeleton.

14. A system for expanding targets in target clusters on a computer display, comprising:

a target expansion module for identifying targets that require additional expansion;

a clique organization module for organizing targets into cliques of space donors and space recipients;

a nested ring organization module for organizing the targets of each clique into nested rings using the cliques of space donors and space recipients;

a skeleton routing module for creating a skeleton by routing lines to be used for expanding targets into available display space; and

a skeleton growing module for growing the targets into expanded tiles that utilize available space using the skeleton.

15. The system of claim 14 wherein the target expansion module comprises:

a sub-module for performing a Voronoi tessellation on the targets to obtain a tile for each target;

a sub-module for identifying small tiles by identifying those tiles with tile sizes far below the average tile size; and

a sub-module for designating the targets corresponding to the small tiles as targets in need of expansion.

16. The system of claim 14 wherein the skeleton growing module grows targets into expanded tiles by assigning all pixels of the display to a portion of the skeleton each pixel is closest to.

17. The system of claim 14 wherein the targets are of arbitrary shapes defined by a set of points.

18. The system of claim 14 wherein the shapes of the tiles are adjusted by considering the probability of a user selecting a given target.

19. The system of claim 14 wherein the shapes of the tiles are adjusted by varying the pixels associated with a given skeleton portion based on the available space around the given portion of the skeleton.