System and method for automatic placement of labels for interactive graphics applications

• US 7,131,060 B1
• Filed: 09/29/2000
• Issued: 10/31/2006
• Est. Priority Date: 09/29/2000
• Status: Expired due to Term

• Current Assignee: Raytheon Company (Rtx Corporation)
• Original Assignee: Raytheon Company (Rtx Corporation)
• Inventors: Azuma, Ronald
• Primary Examiner(s): Hong, Stephen
• Assistant Examiner(s): STORK, KYLE R
• Application Number:
  US09/677,467
• Time in Patent Office: 2,223 Days
• Field of Search: 345/630, 345/440, 345/419, 345/650, 715/517, 715/809, 715/512, 715/630, 715/440, 715/419, 715/513, 715/523, 715/530, 715/518, 715/519, 715/790, 703/6, 703/15, 707/3
• US Class Current: 715/260
• CPC Class Codes: G06T 11/60 Editing figures and text; Combining figures or text

Abstract

A method and apparatus for positioning labels on a graphical display, which, in an illustrative embodiment, can include labels for aircraft icons in an air traffic control system'"'"'s computer graphics display. The present invention advantageously identifies clusters of overlapping labels and objects, and calculates non-overlapping label positions on a cluster by cluster basis. In another aspect of the present invention, the movement of labels is accomplished in a smooth, incremental fashion so that cognitive distraction to the user of the graphical display terminal is kept to a minimum.

Claims

1. An apparatus for positioning labels among graphical elements on a computer graphics display, comprising:

a display, and

a processor coupled to said display and operable to identify at least a first cluster of overlapping labels on said display, and operable to calculate initial display coordinates in accordance with an initial position of at least one label in said cluster, to calculate new display coordinates in accordance with a new position of said at least one label in said cluster having less overlap, to display said at least one label at said initial display coordinates, and to move said at least one label on said display from said initial display coordinates to said new display coordinates, wherein said processor is operable to sequentially select labels from a plurality of labels on said display, and to test each of said selected labels for overlap with other labels or graphical elements in said display, and said processor is operable to accumulate an overlap score for each of said selected labels, and operable to generate a list of other labels and graphical elements that overlap each of said selected labels, and operable to compare a plurality of said lists and accumulate cluster lists of overlapping labels and graphical elements, and operable to sort a plurality of said cluster lists according to the number of entries in each.

2. An apparatus for positioning labels among graphical elements on a computer graphics display, comprising:

means for identifying at least a first cluster of overlapping labels, wherein said means for identifying includes,

means for sequentially selecting labels from a plurality of labels on the display;

means for testing each of said selected labels for overlap with other labels or graphical elements in the display;

means for accumulating an overlap score for each of said selected labels;

means for generating a list of other labels and graphical elements that overlap each of said selected labels;

means for comparing a plurality of said lists and accumulating cluster lists of overlapping labels and graphical elements; and

means for sorting a plurality of said cluster lists according to the number of entries in each;

means for calculating initial display coordinates for at least one label in said cluster;

means for calculating new display coordinates for said at least one label in said cluster; and

means for moving said label on the display from an initial position in accordance with said initial display coordinates to a new position in accordance with said new display coordinates.

3. The apparatus of claim 2 wherein said overlap score is based on a degree of overlap of labels and graphical elements.

4. The apparatus of claim 2 including means for determining that the labels are overlapping other labels or graphical elements when they are mutually overlapping.

5. The apparatus of claim 2 including means for determining that the labels are overlapping other labels or graphical elements when they are transitively overlapping.

6. The apparatus of claim 2 wherein said means for sorting orders the sort from largest cluster list to smallest cluster list.

7. The apparatus of claim 2 wherein said means for calculating further comprises:

means for comparing the degree of overlap of labels and graphical elements with said new display coordinates and the existing degree of overlap of labels and graphical elements.

8. The apparatus of claim 2 including means for calculating said new display coordinates according to a stochastic method.

9. The apparatus of claim 2 including means for calculating said new display coordinates according to a heuristic method.

10. The apparatus of claim 2 wherein said means for moving further comprises:

means for interpolating a plurality of intermediate display coordinates between said initial display coordinates and said new display coordinates; and

means for sequentially placing the labels at each of said intermediate display coordinates before placing said labels at said new display coordinates, thereby smoothing the movements of said labels on said display.

11. An apparatus for positioning labels among graphical elements on a computer graphics display, comprising:

means for sequentially selecting labels from a plurality of labels on the display;

means for testing each of said selected labels for overlap with other labels and graphical elements in the display;

means for accumulating an overlap score for each of said selected labels;

means for generating a list of other labels and graphical elements that overlap each of said selected labels;

means for comparing a plurality of said lists and accumulating cluster lists of overlapping labels and graphical elements, each cluster list representing a respective cluster of overlapping labels;

means for sorting a plurality of said cluster lists according to the number of entries in each;

means for calculating initial display coordinates for the labels on a cluster by cluster basis;

means for calculating new display coordinates for the labels on a cluster by cluster basis;

means for comparing, on a cluster by cluster basis, the degree of overlap of labels and graphical elements at said new display coordinates and the degree of overlap of the labels and graphical elements at the initial coordinates; and

means for moving the graphical elements on the display from initial positions according to said initial display coordinates to new positions according to said new display coordinates if said new display coordinates result in a reduction of the degree of overlap.

12. The apparatus of claim 11 wherein said overlap score is based on the degree of overlap between labels and graphical elements.

13. The apparatus of claim 11 wherein labels are determined to be overlapping other labels or graphical elements when they are mutually overlapping.

14. The apparatus of claim 11 wherein labels are determined to be overlapping other labels or graphical elements when they are transitively overlapping.

15. The apparatus of claim 11 wherein said means for sorting orders the sort from largest cluster list to smallest cluster list.

16. The apparatus of claim 11 wherein said new display coordinates are calculated stochastically.

17. The apparatus of claim 11 wherein said new display coordinates are calculated heuristically.

18. The apparatus of claim 11 wherein said calculating of new display coordinates is ordered according to said cluster list.

19. The apparatus of claim 11 wherein said means for moving further comprises:

means for interpolating a plurality of intermediate display coordinates between said initial display coordinates and said new display coordinates and

means for sequentially placing the labels at each of said intermediate display coordinates before placing said labels at said new display coordinates, thereby smoothing the movements of said labels on said display.

20. A method of positioning labels among graphical elements on a computer graphics display, comprising the steps of:

identifying at least a first cluster of overlapping labels and graphical elements wherein said identifying comprises;

sequentially selecting labels from a plurality of labels on the display;

testing each of said selected labels for overlap with other labels and graphical elements in the display;

accumulating an overlap score for each of said selected labels;

generating a list of other labels and graphical elements that overlap each of said selected labels;

comparing a plurality of said lists and accumulating cluster lists of overlapping labels and graphical elements; and

sorting a plurality of said cluster lists according to the number of entries in each;

calculating initial display coordinates for at least one label in said cluster;

calculating new display coordinates for said at least one label in said cluster; and

moving said label on the display from said initial display coordinates to said new display coordinates.

21. The method of claim 20 wherein said overlap score is based on the degree of overlap between labels and graphical elements.

22. The method of claim 20 wherein labels are determined to be overlapping other labels or graphical elements when they are mutually overlapping.

23. The method of claim 20 wherein labels are determined to be overlapping other labels or graphical elements when they are transitively overlapping.

24. The method of claim 20 wherein said sorting is ordered from largest cluster list to smallest cluster list.

25. The method of claim 20 wherein said calculating step further comprises the step of:

comparing the degree of overlap of labels and graphical elements with said new display coordinates and an existing degree of overlap of labels and graphical elements with said initial display coordinates, and if the new coordinates result in a reduction of the degree of overlap, proceeding to said moving step.

26. The method of claim 20 wherein said new display coordinates are calculated according to a stochastic method.

27. The method of claim 20 wherein said new display coordinates are calculated according to a heuristic method.

28. The method of claim 20 wherein said moving step further comprises the steps of:

interpolating a plurality of intermediate display coordinates between said initial display coordinates and said new display coordinates, and

sequentially placing the labels at each of said intermediate display coordinates before placing said labels at said new display coordinates, thereby smoothing the movements of said labels on said display.

29. A method of positioning labels among graphical elements on a computer graphics display, comprising the steps of:

sequentially selecting labels from a plurality of labels on the display;

testing each of said selected labels for overlap with other labels and graphical elements in the display;

accumulating an overlap score for each of said selected labels;

generating a list of other labels and graphical elements that overlap each of said selected labels;

comparing a plurality of said lists and accumulating cluster lists of overlapping labels and graphical elements, each cluster list representing a respective cluster of overlapping labels;

sorting a plurality of said cluster lists according to the number of entries in each;

calculating initial display coordinates for the labels on a cluster by cluster basis;

calculating new display coordinates for the labels on a cluster by cluster basis;

comparing, on a cluster by cluster basis, the degree of overlap of labels and graphical elements with said new display coordinates with an existing degree of overlap of the labels and graphical elements with said initial display coordinates, and

if the new coordinates result in a reduction of the degree of overlap, moving the graphical elements on the display from initial positions according to said initial display coordinates to new positions according to said new display coordinates.

30. The method of claim 29 wherein said overlap score is based on the degree of overlap between labels and graphical elements.

31. The method of claim 29 wherein labels are determined to be overlapping other labels or graphical elements when they are mutually overlapping.

32. The method of claim 29 wherein labels are determined to be overlapping other labels or graphical elements when they are transitively overlapping.

33. The method of claim 29 wherein said sorting is ordered from largest cluster list to smallest cluster list.

34. The method of claim 29 wherein said new display coordinates are calculated according to a stochastic method.

35. The method of claim 29 wherein said new display coordinates are calculated according to a heuristic method.

36. The method of claim 29 wherein said calculating of new display coordinates is ordered according to said cluster list.

37. The method of claim 29 wherein said moving step further comprises the steps of:

interpolating a plurality of intermediate display coordinates between the said initial display coordinates and said new display coordinates, and

sequentially placing the labels at each of said intermediate display coordinates before placing said labels at said new display coordinates, thereby smoothing the movements of said labels on said display.

38. The method of claim 29, further comprising the step of repeating the foregoing sequence of steps through a plurality of iterations.