BACKGROUND OF THE INVENTION Moving electronic map displays are generally well-known and include marine and aviation charts as well as terrain and road maps. They are used in many commercial navigation products. Vehicle navigation systems are the most generally well-known use of moving maps. For example, US Patent 5,442,557, entitled NAVIGATION DEVICE, issued to Kaneko on August 15,1995, the complete disclosure of which is incorporated herein by reference, generally discloses a vehicle navigation device that measures a current position of a movable body and generates current position information indicating the current position of the movable body relative to a map. The map, shown in Figure 1A is coupled to an information storage unit having stored map information, including additional information that is useful to navigation. A control unit generates a current position of the movable body, map information relative to the current position of the movable body, and the additional navigation information. An external display shows the information. The map 10 shown in Figure 1A shows the user's vehicle 12 relative to road map information 14 and general information 16 of interest to the user. Figure 1B illustrates another map 20 that again shows general road map information 14 along with additional road identification information 22A, 22B, 22C, 22D. Figure 1B also shows diverging direction signs indicated by respective arrows 24A, 24B, 24C, including respective destinations 26A, 26B, 26C and a highway intersection 28 in an area in the vicinity of Kawagoe, Saitama Prefecture, Japan. The above data is useful in determining > which road should be selected.

In another example, US Patent 4,646,089, entitled TRAVEL GuiDANcE SYSTEM FOR VEHICLES, issued to Takanabe, et al. on February 24,1987, the complete disclosure of which is incorporated herein by reference, discloses navigation system

wherein a map display 30, shown in Figure 1C, includes one or more landmarks 32 indicated by an asterisk (31 () symbol in the vicinity of the present position of the user's vehicle 12. As disclosed by US Patent 4,646,089, the description of landmark 32 is provided in a legend 34 outside of the map area. However, this method of labeling requires the user to search back and forth between the map and legend trying to match the symbols with the descriptions. While this may be relatively simple when only one or two landmarks are displayed, the task may require excessive concentration when multiple landmarks are displayed and become dangerous if the navigator is also the vehicle pilot.

Figure ID illustrates another method of displaying useful information. In the display of map 40, in addition to general road map information 14, other graphic information, such as Kansas Airport 42A and Olathe Lake 42B, provide useful landmarks for travelers in the Olathe area of Kansas. The graphic representations are made more useful by attaching labels 44A, 44B, and 44C respectively to Kansas Airport 42A, Olathe Lake 42B, and highway 14. However, as shown in map 50 of Figure IE, when labels 52A, 52B, 52C,... are attached to useful landmarks 54A, 54B, 54C,... in crowded areas such as a downtown area, the number of labels obscure both the landmark locations and general road map information 14. Furthermore, in such crowded areas, the labels overlap one another. Such overlapping is unavoidable when the label positions are fixed relative to the corresponding landmarks. As shown in Figure IE, labels 52 are typically fixed in a position, such as to the immediate right of corresponding landmark 54, regardless of the presence of other landmarks or labels. Rather than providing information, the overlapping labels become unreadable and consequently just occupy space on the display screen without providing any useful information.

Therefore, what is needed is a method and apparatus for displaying sufficient useful general road map and landmark information while reducing the potential clutter of labels.

SUMMARY OF THE INVENTION The present invention solves the inefficient and overcrowded labeling problems of the prior art by providing an apparatus and method for decluttering labels on map displays.

According to one aspect of the invention, a method for locating labels on an electronic map is provided, the method determining multiple graphic objects for depiction on an electronic moving map, and defining one or more label location choices on the electronic map relative to at least one of the graphic objects. Relative to one of the graphic objects, the invention passes over label location choices that conflict with a label location for another of the graphic objects, and displays a label at one of the remaining label location choices.

According to another aspect of the invention, the function of the method that passes over label location choices for the one graphic object that conflict with a label location choice for another of the graphic objects includes passing over label location choices for a second or later graphic object that conflict with the label location already determined for a first or earlier one of the graphic objects.

According to another aspect of the invention, the label displayed at one of the remaining label location choices corresponds to the one graphic object relative to which the label location choices are defined.

According to another aspect of the invention, the number of possible label location choices on the electronic map relative to at least one of the graphic objects is limited to a predetermined number of choices. According to this aspect of the invention, the method also includes hiding or discarding the label corresponding to the second or later graphic object when all label location choices defined relative to it are passed over.

According to another aspect of the invention, the label location choices defined relative to the one graphic object are prioritized, and passing over label location choices for the one graphic object that conflict with a label location for another of the graphic objects includes testing each of the label location choices for the one graphic object in order of priority while conflicts with the label location for another of the graphic objects are determined. In other words, in order of precedence, the method of the invention tests each possible location choice until either a non-conflicting label location is determined and the label is placed, or all possible choices have been exhausted.

According to another aspect of the invention, determining conflict between a label location choice for the one graphic object and a label location for another of the graphic objects includes determining a coordinate position for both the label location

choice for the one graphic object and the already determined label location for another of the graphic objects.

According to another aspect of the invention, wherein determining conflict between a label location choice for the one graphic object and a label location for another of the graphic objects also includes determining a size of both the label for the one graphic object and the label for the other graphic object for which the label location is already determined.

More particularly, according to various aspects of the invention, the invention provides a method for locating graphic object labels on a moving electronic map, the method including: determining a plurality of electronic map symbols for depiction on a moving electronic map; determining a plurality of electronic labels, each of the electronic labels corresponding to one of the electronic map symbols; defining a predetermined plurality of possible label location choices on the electronic map corresponding to each of the electronic map symbols; choosing one of the label location choices corresponding to a first one of the electronic map symbols; locating the electronic label corresponding to the first electronic map symbol at the chosen label location choice corresponding to the first electronic map symbol. Next, the method compares the label location choices corresponding to a second one of the electronic map symbols to the chosen label location choice corresponding to the first one of the electronic map symbols; determines one of the label location choices corresponding to the second one of the electronic map symbols that is spaced away from the chosen label location choice corresponding to the first one of the electronic map symbols; and displays the electronic label corresponding the second one of the electronic map symbols at the label location choice that is spaced away from the chosen label location choice corresponding to the first one of the electronic map symbols.

According to other aspects of the invention, the method of the invention then repeats for each additional electronic map symbol and its corresponding electronic label each of actions performed on behalf of the second one of the electronic map symbols.

According to other aspects of the invention, the method of the invention includes deleting, i. e., hiding or discarding, the electronic label corresponding the second electronic map symbol when the comparing the label location choices corresponding to a second one of the electronic map symbols to the chosen label location choice

corresponding to the first one of the electronic map symbols fails to determine one of the label location choices that is spaced away from the chosen label location choice corresponding to the first electronic map symbol.

According to another aspect of the invention, the invention includes a display system for displaying moving electronic maps, the display system implementing the method of the invention.

According to yet another aspect of the invention, the invention includes a vehicle navigation system implementing the method of the invention.

According to still other aspects of the invention, the invention includes an electronic label for display on a moving electronic map, the label including: information corresponding to one of several graphic objects, or map symbols, for display on a view screen; a definition of one or more label location choices for each of the graphic objects; a function for determining whether a one of the label location choices for a later graphic object is sufficiently spaced away from the label location choice made for an earlier graphic object so that information displayed at both label locations is legible; and a function for displaying the information corresponding to each of the earlier and later graphic objects in the spaced away label location choices corresponding to the respective earlier and later graphic objects. Preferably, the function of the invention for displaying the information also includes displaying only the information corresponding to the earlier graphic object, if all label location choices for the later graphic object interfere, or conflict, with the label location choice made for an earlier graphic object.

According to yet other aspects of the invention, the invention includes a vehicle navigation system for displaying various navigational information, the system including an electrical display means, such as one of the well-known displays described in the prior art for displaying graphic objects representative of map information; means for displaying a vehicle position relative to the map information, such as one of the well-known displays described in the prior art for displaying a vehicle position relative to the map information; and novel and well ordered means for displaying information corresponding to the graphic objects.

According to yet other aspects of the invention, the novel and well ordered means of the invention for displaying information corresponding to the graphic objects includes: a function for determining multiple graphic objects for display on the system

view screen, a function for determining label information corresponding to one or more of the graphic objects, a function for defining multiple location choices corresponding to each graphic object for displaying the information corresponding to the respective graphic object, a function for defining one of the multiple location choices relative to a later one of the graphic objects that is spaced away from a location chosen for displaying information corresponding to an earlier one of the graphic objects, and a function for displaying the information corresponding to the earlier graphic object at the location chosen to display the information corresponding to the earlier graphic object and for displaying the information corresponding to the later graphic object at the location chosen to display the information corresponding to the later graphic object.

According to another aspect of the vehicle navigation system invention, the function for defining multiple location choices relative to each graphic object for displaying the information corresponding to the respective graphic object also includes prioritizing the location choices corresponding to each respective graphic object.

According to another aspect of the vehicle navigation system invention, the function for defining multiple location choices relative to each graphic object for displaying the information corresponding to the respective graphic object also includes defining the location choices as a function of the priority among the location choices.

According to yet another aspect of the vehicle navigation system invention, the function for displaying information corresponding to the graphic objects includes deleting, i. e., hiding or discarding, the information when the function for defining one of the plurality of location choices relative to a later one of the graphic objects that is spaced away from a location chosen for displaying information corresponding to an earlier one of the graphic objects does not define such a location.

BRIEF DESCRIPTION OF THE DRAWINGS The foregoing aspects and many of the attendant advantages of this invention will become more readily appreciated as the same becomes better understood by reference to the following detailed description, when taken in conjunction with the accompanying drawings, wherein:

Figure 1A illustrates a moving electronic map of the prior art for displaying information generated by a navigation system in which stored map information is displayed, including additional information that is useful to navigation; Figure 1 B illustrates another display of a moving electronic map of the prior art that shows general road map information along with additional road identification information useful in determining which road should be selected, including diverging direction indicators, respective destination labels, and a highway intersection; Figure 1C illustrates another moving electronic map of the prior art for displaying navigation system information, including one or more landmark symbols in the vicinity of a present position of a user's vehicle and a cooperative legend provided outside of the map area; Figure 1 D illustrates another method of the prior art for displaying useful information in which, in addition to general road map information, other labeled graphic information provide useful landmarks for travelers; Figure IE illustrates the limitations of the prior art illustration method described in Figure ID when used to display labeled landmarks in crowded downtown areas; Figure 2 illustrates the well ordered labeling method of the present invention; Figure 3 illustrates the major map symbol classes of the present invention; Figure 4 illustrates the inheritance diagram of the present invention; Figures 5A, 5B and 5C illustrate the label positioning of the present invention; Figure 6 illustrates the interrelationships among screen class, map symbol class, and label class of the present invention; Figure 7 illustrates a flow chart outlining the operation of one embodiment of the well ordered labeling method of the invention; and Figures 8A and 8B illustrate another way of outlining the operation of the method of the invention.

DETAILED DESCRIPTION OF PREFERRED EMBODIMENT In the Figures, like numerals indicate like elements.

The present invention is a well ordered method of labeling a crowded moving electronic map.

Figure 2 illustrates the well ordered labeling method of the invention by showing the labeling of the crowded area map illustrated in Figure 1E according to the present invention. As shown in Figure 2, the invention minimizes label overlapping. In Figure 2, the map 100 is provided with general road map information 14 and the map symbols 102A, 102B, 102C, 102D, and others, each representing various landmarks useful to navigation. As illustrated, the labeling method of the invention discards the previous practice of placing labels in a fixed position relative to the corresponding map symbol.

Rather, the labels 104A, 104B, 104C, 104D and others are placed in a manner that minimizes overlapping. Furthermore, when the number of useful landmarks displayed on the map is so great that label overlapping is otherwise unavoidable, the method of the invention intentionally discards or hides lower priority labels. For example, label 52A "Police Station"corresponding to landmark 54A and label 52B"Post Office" corresponding to landmark 54B, which are shown in Figure 1E, are discarded or not displayed in Figure 2 to avoid overlapping. Other labels 52 shown in Figure IE are also discarded or hidden in Figure 2 to provide well-ordered and legible map labeling.

Map Symbol Class Figure 3 is an unlabeled map 200 that illustrates the major map symbol classes of the invention. The map symbol class contains the shape information for the graphic object to be displayed on the view screen. The graphic object displayed on the view screen is referred to hereinafter interchangeably with the term"map symbol."The map symbol class also contains the list of the label location choices. Preferably, an abstract class of map symbols is used in the program code implementing the method of the invention. The abstract class is known here as the"Map Symbol"base class. The invention implementation is preferably program coded to operate on this abstract map symbol class without the necessity of knowing the specific map symbol class in use. In Figure 3, a derived class of map symbol is the"Point Symbol"class; a point symbol 202 is used to represent a specific location of map, such as an airport. Another derived map symbol class is the"Polyline Symbol"class; a polyline symbol 204 is used to represent a long, narrow, essentially one-dimensional geographic feature, such as a street, highway, or railroad. Yet another derived map symbol class is the"Polygon Symbol"class. As illustrated in Figure

3, a polygon symbol 206 represents larger, two-dimensional features, such as lakes. The "Poly Symbol"class (not shown) is a derived class that shares commonality between the polyline symbol and the polygon symbol classes.

Figure 4 illustrates the inheritance diagram 400 showing the interconnection of the various map symbol classes, as described above. Each of the Polyline Symbol 402 and the Polygon Symbol 404 input information for labeling the symbol, which is described below, into the Poly Symbol 406. Poly Symbol 406 inputs both label information and x, y turning point information used to draw the symbol on the display view screen into Map Symbol 408. The Point Symbol 410 inputs symbol position information into Map Symbol 408. The abstract Map Symbol 408 passes on the information for drawing the symbol, including the symbol class information, and additionally provides label position choice information to the labeling program.

Inheritance is an optional feature that allows the rest of the program code implementing the method of the invention to access a Map Symbol 408, without identifying the object accessed. The program can therefore treat all symbol objects uniformly. Furthermore, another new symbol class can be inherited from the Map Symbol class without changing other parts of the code.

Related to the map symbol classes are the"Rectangle"and"Position" classes. The Position class contains x and y coordinate values relative to the two-dimensional view screen. The Rectangle class includes two Position classes. One Position class represents a position of the rectangle, while the other Position class defines the size of the rectangle. For example, the first Position class defines the rectangle's upper-left corner position and the second Position class defines the rectangle's size. The relevance of the Rectangle and Position classes is explained below.

Label Class Figures 5A, 5B and 5C illustrate the label positioning of the invention. The Map Symbol derived class creates the various label classes. Each map symbol class is provided with a predetermined multiple number of possible label locations on the view screen relative to the corresponding map symbol. Preferably, the map symbol class defines the number of possible label locations. The label class information also includes the label two-dimensional size, i. e., its height and width. Figure 5A illustrates placement of the label relative to a member of the PointSymbol class. Figure 5A illustrates, for example, four

possible locations 502A, 502B, 502C, and 502D for placement of the label relative to a point symbol 202. As indicated, the invention further provides a preferred order of choice among possible label locations 502A, 502B, 502C, and 502D. Other orders of choice are alternatively used in practicing the invention. Other alternative locations (not shown) include vertically stacked label location choices both above and below point symbol 202.

Still other alternative locations include horizontally stacked label location choices both left and right of point symbol 202, as shown in Figure 2.

Figure 5B illustrates one example of labeling of the PolylineSymbol class according to the invention. For example, Figure 5B illustrates five label placement location choices 512A, 512B, 512C, 512D, and 512E relative to a polyline symbol 204. While the positioning and order of choice of label locations are optional according to the invention, the preferred positioning is on a relatively straight segment of polyline symbol 204. One or more possible label locations are provided along any relatively straight segment of polyline symbol 204, wherein a"straight"segment is defined as the segment between two adjacent x, y coordinate view screen positions. The adjacent x, y coordinate view screen positions represent either start/stop display positions or directional changes in the representation of polyline symbol 204. Preferably, one location choice is positioned on one straight segment between two adjacent x, y coordinate view screen positions, if the distance between them is at least a minimum predetermined distance capable of legibly displaying a useful label for a given view screen size. For example, in Figure 5B segment 514A fails to meet the minimum length criterion for legibly displaying a useful label. Therefore, segment 514A is an impermissible segment on which to place a label. Another straight segment 514B extends between a first xl, yl coordinate view screen position and an adjacent x, y position (not show) located at the intersection of segment 514A and 514B, under label location choice 512D. As illustrated, segment 514B is longer than the predetermined minimum length preferred for legibly displaying a useful label, but it is not long enough to provide multiple label choice locations. So, one label location choice 512A is positioned on segment 514B.

According to the invention, additional label location choices may be placed on a segment of polyline symbol 204, if its length provides sufficient space for multiple label locations, preferably without overlapping one another. Again referring to the example of Figure 5B, another straight segment 514C of polyline symbol 204 is defined between a

turning point (not shown) at an end of segment 514A, under label location choice 512E, and a display"stop"position at coordinate position x2, y2. As illustrated, straight segment 514C is both longer than the minimum predetermined length preferred for legibly displaying a useful label and at least long enough to provide two or more label location choices 512B and 512C, without overlapping the two label location choices. Other straight segments of polyline symbol 204 (not shown) are long enough for legibly displaying three or more useful labels. According to the invention, each segment intersection or turning point also provides a label location choice 512D and 512E.

The invention also preferably provides an order of preference among the various label location choices, as illustrated in Figure 5B. For example, a first label location choice is one placed on a straight segment 514 between two adjacent x, y coordinate positions, i. e., a segment intersection or turning point, having a length between a predetermined minimum and maximum lengths that is capable of legibly displaying a single useful label. The next label location choices in the order of preference are label location choices placed on a straight segment 514 between two adjacent x, y coordinate positions having a minimum predetermined length capable of legibly displaying multiple useful labels. Finally, the label location choices are the various segment intersections or turning points. Thus, in the example of Figure 5B, the order of choice among the possible label location choices is first choice location 512A on straight segment 514B. A second choice location 512B is near the midpoint of straight segment 514C. The third choice location 512C is near the endpoint of straight segment 514C. The fourth and fifth choice locations 512D and 512E are at the turning points of polyline symbol 204 at the respective intersections of straight segments 514A and 514B and straight segments 514B and 514C.

Figure 5C illustrates one example of labeling of the PolygonSymbol class according to the invention. Briefly, the invention determines a rectangle that fits an entire polygon symbol 206, then places a first choice label location at the center of the rectangle followed by additional alternate label location choices throughout the rectangle. In particular, the label location choices for a polygon symbol 206 are determined by first determining a rectangle which is sized to include the whole polygon symbol object 206, preferably without including other map area outside the minimum rectangular area. The invention next determines whether a minimum legible label size is smaller than the including rectangle. If the minimally sized label does not fit inside the rectangle, the

invention does not create a label for the PolygonSymbol. If, however, as illustrated in the example of Figure 5C, the rectangle 520 including polygon symbol 206 is sufficiently large to accept a minimally sized label, a first label location choice 522A is positioned at the center of including rectangle 520. Furthermore, if including rectangle 520 is sufficiently large to accept additional, vertically stacked, preferably non-overlapping label location choices, such location choices 522B and 522C are first made in vertically stacked positions respectively above and below first label location choice 522A. If including rectangle 520 is sufficiently large to accept additional, horizontally stacked, preferably non-overlapping label location choices, such location choices 522D and 522E are made in horizontally stacked positions respectively left and right of first label location choice 522A. In such instance, including rectangle 520 is sufficiently large to accept additional, vertically stacked, preferably non-overlapping label location choices 522F and 522G in vertically stacked positions respectively above and below first horizontally stacked label location choice 522D. Similarly, if including rectangle 520 is sufficiently large, additional, vertically stacked, preferably non-overlapping label location choices 522H and 522I are positioned in vertically stacked positions respectively above and below of second horizontally stacked label location choice 522E. Those of ordinary skill in the art will recognize that an including rectangle 520 sufficiently large in vertical and/or horizontal directions will accept additional respectively vertically stacked and horizontally stacked, non-overlapping label location choices (not shown).

As noted above, the first preferred label location choice 522A is positioned at the center of including rectangle 520. The invention also preferably provides an order of preference among the various remaining label location choices, as illustrated in Figure 5C.

For example, a second and third label location choices 522B and 522C are those placed vertically above and below first choice 522A. Thereafter, according to one embodiment of the invention, the order of precedence among label location choices 522D is left of center location choice 522A, followed by location choices 522F and 522G vertically stacked above and below left location choice 522D, respectively. In order of precedence, left location choice 522D is followed by location choice 522E right of center location choice 522A, which is followed in precedence by location choices 522H and 522I vertically stacked above and below right location choice 522E, respectively. Alternatively, location choices 522D and 522E respectively left and right of center location choice 522A follow

vertically stacked location choices 522B and 522C in order of precedence. Each of left location choice 522D and right location choice 522E are followed in precedence by respective vertically stacked location choices 522F and 522G and 522H and 522I. Those of ordinary skill in the art will recognize that precedence among the various label location choices is alternatively ordered in numerous other equally valid sequences, without materially affecting the practice of the invention.

Class Diagram Figure 6 illustrates the interrelationships among screen class 610, map symbol class 612, and label class 614. Screen class 610 contains information relating the number of graphic objects, defined above as"map symbols,"that are available for display on the view screen. Screen class 610 also contains the information relating the number of labels corresponding to the graphic objects. The function of screen class 610 is to use these two pieces of information to define conflicts or overlaps between a selected label location choice and a label already selected for display on the view screen.

Map symbol class 612 contains information describing the shape of the graphic object selected for display on the view screen, as well as information describing how to draw or display the corresponding label. Map symbol class 612 also contains a list of label location choices corresponding to the class of map symbol, as described above.

The label location choice is selected from this list by label class 610.

Label class 614 is derived from map symbol class 612. Label class 614 contains the label size, i. e., the label height and width. Label class 614 attempts to locate a label using screen class overlap information from screen class 610 as a function of label location choice information provided by the map symbol derived object.

Operation Figure 7 illustrates a flow chart 700 outlining the operation of one embodiment of the well ordered labeling method of the invention. Briefly, the method of the invention accesses all Map Symbol objects so that the screen object 710 has knowledge of every map symbol object intended for the present screen display. Screen object 710 asks every map symbol object to create its own corresponding label based on the information contained in respective map symbol objects. The actual procedure used to create the map label is generally well-known and constitutes no part of this invention. The invention rather is concerned with label size and location choice. Each label in turn begins the location

choice procedure, during which the order of label location choice is sorted by priority.

Each label object accesses its parent map symbol object to obtain the list of permissible label location choices, i. e., where the label can be located on the view screen. The label object obtains the first location choice from the list and accesses screen object 710 and provides the location choice and label size information. Screen object 710 combines this label size and location choice information with similar information from other already located labels to determine whether this first location choice conflicts or overlaps any already located label. If no conflicts are found, the present label is located successfully on the view screen. However, if at least one conflict occurs, the present label gives up the present location choice and determines the next choice from the list. The process is repeated using each next location choice until either a location choice is found that does not conflict with another already located label or all permissible location choices are found to conflict with at least one other already located label. If all location choices fail, the label does not locate itself on the view screen.

In detail, screen object 710 receives as input data defining the size of the view port to be filled and all of the screen class 610, map symbol class 612, and label class 614 information. As discussed above, the screen class data includes the number of objects to be displayed and the number of labels. The map symbol data includes a list of all the map symbols or graphic objects to displayed, including the size and shape data, and the list of permissible label location choices. The label class contains the label size data. The first map symbol is accessed 712 and the corresponding label is created 714. The list of permissible label location choices is accessed 716 as a function of the map symbol class, and a first or preferred label location choice is determined 718. If the present map symbol is the first map symbol to be located, decision block 720 transfers the information to a function 722 for locating the label on the view screen at the first location choice. Then, a next map symbol to be displayed is accessed 724. This"next"map symbol data is sent to function 714 to create a corresponding label and the process is repeated using this"next" map symbol. Again, the list of permissible label locations is accessed as a function of the map symbol class in function block 716, and a first preferred label location choice is determined from the list in function block 718. This"next"map symbol is not the first map symbol to be displayed in this screen, so the test in function block 720 fails. Because the "next"map symbol may be located near the first map symbol, the potential overlap of label

locations must be tested. The overlap test is further a function of the label class data, i. e., the label size. If the conflict test in function block 726 fails, no overlap exists and the label can be located on the screen at this first label location choice according to function block 722. Another"next"map symbol is accessed in function block 724, and the process for "next"map symbols is repeated.

If the map area to be displayed in the present screen is sufficiently crowded with useful navigational landmarks or other useful navigational aids, when an"n-th"map symbol is accessed in function block 724, and the process for"next"map symbols is repeated, a conflict will probably be detected in test block 726. When function block 726 returns a success, a conflict between the first label location choice for the present n-th "next"map symbol and one or more previously located map symbols has been detected. In other words, the first preferred label location choice for the current map symbol overlaps an already existing label for an earlier map symbol. In the event of a conflict with the first location choice, the method queries 728 whether an alternate label location choice is available from the list of permissible location choices for that class of map symbol. As described above, each class of map symbol includes multiple permissible label location choices. Therefore, at least on a first pass, alternate label location query 728 returns TRUE, and a"next"label location choice is determined 730 from the list of permissible locations.

Conflicts between this"next"label location choice and the locations of all of the already located labels are analyzed in function block 732. If the conflict test fails, i. e., no overlaps are found, the label location is acceptable. The label data is passed to function 722 for location of the label on the view screen. Function block 724 accesses an"n+1"map symbol and repeats the process.

However, if the map is sufficiently crowded, the conflict test of function block 732 may succeed, meaning that the first alternate label location choice also overlaps or interferes with at least one of the already located labels. In such case, the test 732 returns TRUE, and query function 732 returns the map symbol to function block 728 to determine whether second alternative location choice is available. If another location choice is available, function 728 returns TRUE, and function 730 retrieves the next location choice from the list. Again, conflict test 732 is operated on the current location choice. If no conflict is found, the location choice is passed to function block 722 for locating the label on the screen, and a next"n+2"map symbol is accessed and operated

upon by the method of the invention. If, however, the map is so crowded that this second alternative location choice overlaps one of the already located labels, conflict test 732 again returns TRUE. The n+1 map symbol is returned to function block 728 to determine whether a third alternative label location choice is available according to the map class of the n+1 map symbol. This third location choice is operated upon, and unless the conflict test fails, the process continues checking for additional alternative location choices until either a location choice is found that does not overlap any already located labels, or all of the label location choices permitted by the map class are exhausted. If the operation fails to find a permissible label location choice that does not overlap the location choice of an already located label, the invention stops trying to place the n+1 label on the current view screen and move on to function block 724 to access a next n+2 map symbol. The n+1 symbol is displayed on the view screen without benefit of a label, as were for example landmarks 54A and 54B in Figure 2.

Figures 8A and 8B are another way of illustrating the operation of the method of the invention. Figure 8A illustrates the operation of the method on a first map symbol. In the diagram of Figure 8A, all of screen class 610, map class 612, and label class 614 data are inputs to the label locating function 800. All of the map symbol objects are registered to the screen object so that every map symbol is known. Map symbol class 612 information is used in a function 810 to create a label corresponding to the first map symbol. Information from label class 614 is used to make a first choice of label location 812. The location choice is acted upon by screen class 610 to determine that the current map symbol is the first map symbol to have a label applied. When the test is successful, the label is located relative to the screen 814, and success 816 is reported to function 800.

Figure 8B illustrates the operation relative to an"n-th"choice label location sequence 820. N-th choice sequence 820 begins operations the same way that label locating function 800 operates on the first map symbol, detailed above in Figure 8A. The operation differs when the n-th map symbol is not found to be the first map symbol. In such instance, the first location choice must be tested for conflict with the location choice for the label corresponding to the first map symbol. As noted above, if the map area is sufficiently crowded with useful landmarks or other navigational aids that are preferably labeled, eventually the first location choice for an n-th map symbol will probably fail 822.

If such failure occurs, a next label location choice is made 824 and tested 826 for conflict

with already located labels. If such next choice is found to conflict with an already located label 828, another next choice 830 is determined from the list of permissible location choices for that class of map symbol and tested 832 for conflicts. The accessing of next label location choices from the list of permissible choices and testing for conflict is continued until either the list of permissible choices is exhausted, or a successful choice 834 is found, i. e., one that does not overlap any of the already located labels. If no acceptable label location choice is determined before the list of choices is exhausted, the invention stops trying to place a label on the view screen for that map symbol and begins operating on a next map symbol until all of the map symbols have been operated upon.

While the preferred embodiment of the invention has been illustrated and described, it will be appreciated that various changes can be made therein without departing from the spirit and scope of the invention. For example, as illustrated and described herein, the label locating invention is so efficient that it satisfies the real-time graphics requirements of most current avionics and cockpit displays. Therefore, the invention is useful in most current avionics and cockpit displays as well as automotive and marine displays.