Real-time collision avoidance for map labels and symbols

A wireless communications device for enabling a user of the device to display a map on the device, the wireless device comprising:

• an input device for enabling the user to cause the device to obtain map data for rendering the map to be displayed on a display of the device by downloading the map data over a wireless link, the map data including label data for rendering labels on the map for identifying one or more map features, wherein the labels comprise at least one symbol or icon;
• and
• a memory for storing code to instruct a processor to:
• generate a collision-avoidance array representative of the map to be rendered for testing potential label positions prior to actually rendering the labels on the map;
• populate the collision-avoidance array by provisionally designating, for each successive label to be rendered, a label space in the collision-avoidance array that corresponds to a map space that is to be occupied by the label on the map and by determining whether each successive label to be rendered collides in the collision-avoidance array with any previously designated label spaces;
• and
• render the labels on the map in the map spaces corresponding to the label spaces designated in the collision-avoidance array;
• wherein the processor populates the collision-avoidance array by:
• for each successive label to be rendered, provisionally designating the label space in the collision-avoidance array such that a midpoint of the corresponding map space aligns with a midpoint of a map feature to which the label relates;
• determining whether the provisionally designated label space collides with any previously designated label spaces in the collision-avoidance array;
• if the provisionally designated label space does not collide with any previously designated label spaces in the collision-avoidance array, then definitively designating the label space for rendering the label at the corresponding map space on the map;
• and
• if the provisionally designated label space collides with any previously designated label spaces in the collision-avoidance array, then testing a new label space by repositioning the label space either beyond a collision point for cases where less than half of the label space fits before the collision point or before the collision point for cases where more than half of the label space fits before the collision point.