Patent ID: 12190421

DETAILED DESCRIPTION

Aspects disclosed herein present systems and methods for adjusting locations of map labels. In some cases, a map is automatically rendered with labels that are at pre-determined positions relative to corresponding map locations. For example, a first label identifying a first map location is at a first label location. The first label location corresponds to a particular position (e.g., a pre-determined distance, a pre-determined direction, or both) relative to the first map location. Similarly, a second label identifying a second map location is at a second label location. If the first label is overlaid on the second label, the second label is difficult to read.

A map generator, prior to generating the map, determines whether any conflicts are detected corresponding to overlapping labels. The map generator, in response to detecting a conflict between any pair of labels, performs deconfliction by determining an adjusted label location for at least one of the pair of labels. The map thus having fewer conflicting labels (e.g., none) is easier to read and aids in more reliable navigation. Resolving the conflicts prior to generating (e.g., rendering) the map is faster and uses fewer computing resources than moving labels in a rendered map. In some cases, the conflicts can be resolved prior to a time-critical rendering and use of the map.

The figures and the following description illustrate specific exemplary embodiments. It will be appreciated that those skilled in the art will be able to devise various arrangements that, although not explicitly described or shown herein, embody the principles described herein and are included within the scope of the claims that follow this description. Furthermore, any examples described herein are intended to aid in understanding the principles of the disclosure and are to be construed as being without limitation. As a result, this disclosure is not limited to the specific embodiments or examples described below, but by the claims and their equivalents.

Particular implementations are described herein with reference to the drawings. In the description, common features are designated by common reference numbers throughout the drawings. In some drawings, multiple instances of a particular type of feature are used. Although these features are physically and/or logically distinct, the same reference number is used for each, and the different instances are distinguished by addition of a letter to the reference number. When the features as a group or a type are referred to herein (e.g., when no particular one of the features is being referenced), the reference number is used without a distinguishing letter. However, when one particular feature of multiple features of the same type is referred to herein, the reference number is used with the distinguishing letter. For example, referring toFIG.1, multiple labels are illustrated and associated with reference numbers112A and112B. When referring to a particular one of these labels, such as the label112A, the distinguishing letter “A” is used. However, when referring to any arbitrary one of these labels or to these labels as a group, the reference number112is used without a distinguishing letter.

As used herein, various terminology is used for the purpose of describing particular implementations only and is not intended to be limiting. For example, the singular forms “a,” “an,” and “the” are intended to include the plural forms as well, unless the context clearly indicates otherwise. Further, some features described herein are singular in some implementations and plural in other implementations. To illustrate,FIG.2depicts a device202including one or more processors (“processor(s)”290inFIG.2), which indicates that in some implementations the device202includes a single processor290and in other implementations the device202includes multiple processors290. For ease of reference herein, such features are generally introduced as “one or more” features and are subsequently referred to in the singular unless aspects related to multiple of the features are being described.

The terms “comprise,” “comprises,” and “comprising” are used interchangeably with “include,” “includes,” or “including.” Additionally, the term “wherein” is used interchangeably with the term “where.” As used herein, “exemplary” indicates an example, an implementation, and/or an aspect, and should not be construed as limiting or as indicating a preference or a preferred implementation. As used herein, an ordinal term (e.g., “first.” “second.” “third,” etc.) used to modify an element, such as a structure, a component, an operation, etc., does not by itself indicate any priority or order of the element with respect to another element, but rather merely distinguishes the element from another element having a same name (but for use of the ordinal term). As used herein, the term “set” refers to a grouping of one or more elements, and the term “plurality” refers to multiple elements.

As used herein, “generating.” “calculating.” “using.” “selecting.” “accessing.” and “determining” are interchangeable unless context indicates otherwise. For example, “generating.” “calculating,” or “determining” a parameter (or a signal) can refer to actively generating, calculating, or determining the parameter (or the signal) or can refer to using, selecting, or accessing the parameter (or signal) that is already generated, such as by another component or device. As used herein, “coupled” can include “communicatively coupled.” “electrically coupled,” or “physically coupled,” and can also (or alternatively) include any combinations thereof. Two devices (or components) can be coupled (e.g., communicatively coupled, electrically coupled, or physically coupled) directly or indirectly via one or more other devices, components, wires, buses, networks (e.g., a wired network, a wireless network, or a combination thereof), etc. Two devices (or components) that are electrically coupled can be included in the same device or in different devices and can be connected via electronics, one or more connectors, or inductive coupling, as illustrative, non-limiting examples. In some implementations, two devices (or components) that are communicatively coupled, such as in electrical communication, can send and receive electrical signals (digital signals or analog signals) directly or indirectly, such as via one or more wires, buses, networks, etc. As used herein, “directly coupled” is used to describe two devices that are coupled (e.g., communicatively coupled, electrically coupled, or physically coupled) without intervening components.

FIG.1depicts a diagram100of an example130, an example132, an example134, and an example136of operations performed by a map generator104that is configured to adjust locations of map labels.

The map generator104determines that a plurality of labels112, such as a label112A and a label112B, are to be displayed in a map, as further described with reference toFIGS.2and3. Each of the plurality of labels112identifies a corresponding map location128. For example, a label112includes text, a symbol, a graphic, etc. identifying a map location128. The map generator104determines, based on offset data, label locations122of the plurality of labels112, as further described with reference toFIGS.2and4. In the example130, the label112A identifying a map location128A has a label location122A, and the label112B identifying a map location128B has a label location122B. In a particular aspect, the map location128A is indicated using a first map location symbol (e.g., ⋄), and the map location128B is indicated using a second map location symbol (e.g., +|).

The map generator104obtains label display data indicating how various types of labels112are to be displayed. For example, the label display data can indicate a font size, a font type, a buffer around the text, etc. The map generator104, based on the label display data, a zoom level, label locations122, or a combination thereof, determines bounding boxes124of the plurality of labels112, as further described with reference toFIGS.2and5. The map generator104determines whether any of the bounding boxes124overlap. In the example132, the map generator104determines a bounding box124A of the label112A and determines a bounding box124B of the label112B. The map generator104, based on detecting an intersection140of the bounding box124A and the bounding box124B, determines that the bounding box124A overlaps the bounding box124B, as further described with reference toFIGS.2,6A, and6B.

The map generator104, in response to determining that a pair of bounding boxes124overlap, determines a candidate label location for at least one of the pair of bounding boxes124based on the intersection140, as further described with reference toFIGS.2,6A, and6C. In the example134, the map generator104, in response to determining that the bounding box124A overlaps the bounding box124B, determines a candidate label location126A of the label112A and a candidate label location126B of the label112B. The candidate label location126A and the candidate label location126B are based on the intersection140. In some implementations, the map generator104determines whether label locations satisfy a selection criterion, as further described with reference toFIGS.2,6A, and6D. In the example134, the map generator104determines that the candidate label location126A satisfies a first selection criterion, and that the candidate label location126B fails to satisfy a second selection criterion.

In some examples, the selection criterion indicates that a label location (e.g., a label location122or a candidate label location126) of a label112is to be within a threshold distance of a map location128identified by the label112. In some examples, the selection criterion indicates that the label location is to be selected such that a corresponding bounding box does not overlap a map location symbol of the map location128. In the example134, the map generator104, in response to determining that a bounding box of the label112B at the candidate label location126B overlaps a map location symbol of the map location128B, determines that the candidate label location126B fails to satisfy a selection criterion.

In the example136, the map generator104, in response to determining that the candidate label location126B fails to satisfy the selection criterion, determines a candidate label location126C of the label112B that satisfies the selection criterion such that a bounding box of the label112B at the candidate label location126C does not overlap with a bounding box of the label112A at the candidate label location126A, as further described with reference toFIGS.2,6A, and6D.

In some implementations, the map generator104generates (e.g., renders) a map119with the label112A at the candidate label location126A and the label112B at the candidate label location126C. In some implementations, the map generator104generates map data indicating that the label112A and the label112B are to be rendered at the candidate label location126A and the candidate label location126C, respectively. In these implementations, another component or device may generate the map119based on the map data.

A technical advantage of the map119including the label112A at the candidate label location126A and the label112B at the candidate label location126C can include the map119being easier to read than a map that includes the label112A at the label location122A and the label112B at the label location122B. A technical advantage of resolving the conflicts prior to generating (e.g., rendering) the map119can include using less time and fewer computing resources as compared to moving labels in a rendered map. In some cases, a map is rendered in real-time as the map is being used. If a map is used for navigation of a vehicle in a rapidly changing landscape, adjusting labels after the map is rendered can take so long that the information on the map becomes obsolete for navigation as the vehicle has moved on to a different location. With conflicts resolved prior to rendering, the map119can be rendered with resolved conflicts faster and aid navigation in time-critical situations.

FIG.2depicts an example of a system200that includes the map generator104. In a particular aspect, the system200includes a device202that includes one or more processors290coupled to a memory292.

The memory292includes a computer-readable medium that stores instructions294that are executable by the one or more processors290. The instructions294are executable to initiate, perform or control operations to aid in adjusting locations of labels of a map. The one or more processors290include the map generator104that can be implemented at least in part by the one or more processors290executing the instructions294.

The one or more processors290can be implemented as a single processor or as multiple processors, such as in a multi-core configuration, a multi-processor configuration, a distributed computing configuration, a cloud computing configuration, or any combination thereof. In some implementations, one or more portions of the map generator104are implemented by the one or more processors290using dedicated hardware, firmware, or a combination thereof.

The map generator104includes a label selector212coupled, via a label location generator214and a bounding box generator216, to a conflict analyzer218. The label selector212is configured to select labels213from labels211based on a label selection criterion204, as further described with reference toFIG.3. The label location generator214is configured to determine label location data215of the labels213based on offset data233, as further described with reference toFIG.4. The label location data215indicates label locations122of the labels213.

The bounding box generator216is configured to generate bounding box data217of the labels213based on label display data235, a zoom level, the label location data215, or a combination thereof, as further described with reference toFIG.5. The bounding box data217indicates dimensions and locations of bounding boxes124of the labels213. The conflict analyzer218is configured to perform deconfliction in response to detecting any conflicts among the labels213to generate the map119, as further described with reference toFIGS.6A-6D.

During operation, the device202activates the map generator104to generate a map119. In a particular aspect, the map generator104is activated responsive to the device202receiving a user input, a command from another device, or both. The label selector212selects labels213from labels211that satisfy a label selection criterion204, as further described with reference toFIG.3. The labels213are to be included in the map119. In some examples, the label selection criterion204is indicated by a user input, a command, a configuration setting, default data, or a combination thereof.

The label location generator214generates label location data215of the labels213based on offset data233, as further described with reference toFIG.4. In an example, the offset data233indicates where labels213of a particular label type are to be displayed relative to corresponding map locations128. In some implementations, different label types (e.g., labels associated with different types of information) are associated with different offset data233. In a particular aspect, the offset data233is based on a user input, a configuration setting, default data, or a combination thereof.

The bounding box generator216generates bounding box data217of the labels213based on label display data235, the label location data215, a zoom level, or a combination thereof, as further described with reference toFIG.5. In an example, the label display data235indicates that labels213of a particular label type are to be displayed with a font type, a font size, etc. The bounding box generator216determines the bounding box data217indicating dimensions (e.g., width and height) of a bounding box124of a label112of the labels213based at least in part on the label display data235associated with a label type of the label112.

The conflict analyzer218performs deconfliction in response to detecting any conflicts among the labels213to generate the map119, as further described with reference toFIGS.6A-6D. For example, the conflict analyzer218, based on determining that a first bounding box124of a label112A of the labels213overlaps a second bounding box124of a label112B of the labels213, detects a conflict between the label112A and the label112B. The conflict analyzer218, based on an intersection between the first bounding box124and the second bounding box124, determines a candidate label location of the label112A, a candidate label location of the label112B, or both. The conflict analyzer218designates, for each of the labels213, a corresponding label location indicated by the label location data215or a corresponding candidate label location determined by the conflict analyzer218to resolve a conflict.

In some implementations, the conflict analyzer218, based on determining that a conflict between the label112A and the label112B is not resolvable within a threshold count of deconfliction attempts, that a designated label location of at least one of the label112A or the label112B fails to satisfy a selection criterion, or both, generates a notification indicating the conflict, the failure to satisfy the selection criterion, or both. In a particular aspect, the conflict analyzer218displays the notification, generates (e.g., renders) the map119including the notification, sends the notification to another device, or a combination thereof.

In some aspects, the map generator104, in response to receiving a user input indicating a particular label location of a label112, updates a designated label location of the label112to indicate the particular label location. For example, a user can override a label location automatically designated by the map generator104. In a particular aspect, the map generator104generates (e.g., renders) the map119including the labels213at the designated label locations. In a particular implementation, the map generator104generates map data indicating that the labels213are to be displayed (e.g., rendered) at the designated label locations, and another device (or component) generates the map119based on the map data.

A technical advantage of the system200resolving the conflicts prior to generating (e.g., rendering) the map119can include using less time and fewer computing resources as compared to moving labels in a rendered map. In some cases, a map is rendered in real-time as the map is being used. If a map is used for navigation of a vehicle in a rapidly changing landscape, adjusting labels after the map is rendered can take so long that the information on the map becomes obsolete for navigation as the vehicle has moved on to a different location. With conflicts resolved prior to rendering, the map119can be rendered with resolved conflicts faster and aid navigation in time-critical situations.

Although the label selector212, the label location generator214, the bounding box generator216, and the conflict analyzer218are depicted as separate components, in other implementations the described functionality of two or more of the label selector212, the label location generator214, the bounding box generator216, and the conflict analyzer218can be performed by a single component. In some implementations, each of the label selector212, the label location generator214, the bounding box generator216, the conflict analyzer218, and the map generator104can be represented in hardware, such as via an application-specific integrated circuit (ASIC) or a field-programmable gate array (FPGA), or the operations described with reference to the elements may be performed by a processor executing computer-readable instructions.

Referring toFIG.3, a diagram300is shown of examples of operations performed by the label selector212. The label selector212has access to labels211. For example, the labels211include a label112A, a label112B, one or more additional labels, or a combination thereof.

The label112A identifies a map location128A. For example, the label112A includes text350A that identifies the map location128A. The label112A including the text350A identifying the map location128A is provided as an illustrative example. In other examples, the label112A can include the text350A, an image, a graphic, another type of identifier, or a combination thereof, that identifies the map location128A. In a particular aspect, the label112A includes a label type352A indicating that the label112A identifies a particular type of map location. For example, the label type352A can include a navigation aid (navaid) label type, a way point label type, a route label type, an airport label type, an airway label type, an airspace label type, or another label type.

Similarly, the label112B includes text350B, an image, a graphic, another type of identifier, or a combination thereof, that identifies the map location128B. In a particular aspect, the label112B includes a label type352B indicating that the label112B identifies a particular type of map location.

In a particular aspect, the label selector212selects a subset of the labels211that is to be included in the map119. To illustrate, the label selector212selects, based on a label selection criterion204, labels213from labels211. For example, the label selector212, in response to determining that the label112A satisfies the label selection criterion204, includes the label112A in the labels213. In a particular example, the label selector212, in response to determining that one or more additional labels of the labels211satisfy the label selection criterion204, includes the one or more additional labels in the labels213.

In a particular aspect, the label selection criterion204indicates a region criterion corresponding to a region331(e.g., a geographical region), a zoom criterion corresponding to a zoom level333, a label type criterion corresponding to one or more label types335, or a combination thereof. For example, the label selection criterion204indicates that the map119(to be generated) is of the region331. A first set of map locations128are included in the region331. In a particular aspect, the label selector212filters the labels211based on the first set of map locations128. For example, the label selector212, in response to determining that labels341of the labels211identify the first set of map locations128of the region331, determines that the labels341satisfy the region criterion indicated by the label selection criterion204.

In some examples, the label selection criterion204indicates that the map119(to be generated) is to correspond to the zoom level333. Labels of one or more label types are to be displayed at the zoom level333. For example, at a first zoom level, labels (e.g., airway labels) corresponding to airways between cities are to be displayed. At a second zoom level, labels (e.g., airport labels) corresponding to runways at an airport are to be displayed. In a particular aspect, the label selector212filters the labels211based on the one or more label types. For example, the label selector212, in response to determining that labels343of the labels211are of the one or more label types associated with the zoom level333, determines that the labels343satisfy the zoom criterion indicated by the label selection criterion204.

In some examples, the label selection criterion204indicates that the map119(to be generated) is to include labels of the one or more label types335. In a particular aspect, the label selector212filters the labels211based on the one or more label types335. For example, the label selector212, in response to determining that labels345of the labels211are of the one or more label types335indicated by the label selection criterion204, determines that the labels345satisfy the label type criterion indicated by the label selection criterion204.

In a particular aspect, the label selection criterion204indicates a single one of the region criterion, the zoom criterion, or the label type criterion, and the label selector212selects the labels (e.g., the labels341, the labels343, or the labels345) that satisfy the single one of the region criterion, the zoom criterion, or the label type criterion as the labels213.

In a particular aspect, the label selection criterion204indicates multiple of the region criterion, the zoom criterion, or the label type criterion, and the label selector212selects an intersection of corresponding labels as the labels213. For example, the label selector212, in response to determining that the label selection criterion204indicates the region criterion, the zoom criterion, and the label type criterion, selects an intersection of the labels341, the labels343, and the labels345as the labels213.

In a particular aspect, the label selection criterion204indicates multiple of the region criterion, the zoom criterion, or the label type criterion, and the label selector212selects a combination of corresponding labels as the labels213. For example, the label selector212, in response to determining that the label selection criterion204indicates the region criterion, the zoom criterion, and the label type criterion, selects a combination of the labels341, the labels343, and the labels345as the labels213. In some aspects, a configurations setting, a user input, default data, or a combination thereof, indicates whether an intersection or a combination of labels are to be selected.

Referring toFIG.4, a diagram400is shown of examples of operations performed by the label location generator214. The label location generator214is configured to generate, based on the offset data233, label location data215indicating label locations122of the labels213.

In a particular aspect, the offset data233indicates a direction offset454, a distance offset456, or both, associated with a label type352. For example, the offset data233indicates that a direction offset454A, a distance offset456A, or both, are associated with a label type352A. As another example, the offset data233indicates that a direction offset454B, a distance offset456B, or both, are associated with a label type352B. The offset data233including offsets for two label types is provided as an illustrative example. In other examples, the offset data233can indicate offsets for a single label type or for more than two label types.

The label location generator214determines label locations122of the labels213based on the map locations128and the offsets indicated by the offset data233. In an example430, the label location generator214, in response to determining that the labels213include a label112A identifying a map location128A that is of a label type352A and that the offset data233indicates that the label type352A is associated with the direction offset454A, the distance offset456A, or both, determines a label location122A based on applying the direction offset454A, the distance offset456A, or both, to the map location128A. In an example, the direction offset454A (e.g., a value greater than or equal to 0 degrees and less than 360 degrees) indicates a direction of the label location122A relative to the map location128A. In another example, the distance offset456A indicates a distance of the label location122A from the map location128A. To illustrate, the distance offset456A indicates a Cartesian distance between coordinates of the label location122A and coordinates of the map location128A.

Similarly, the label location generator214, in response to determining that the labels213include a label112B identifying a map location128B that is of a label type352B and that the offset data233indicates that the label type352B is associated with the direction offset454B, the distance offset456B, or both, determines a label location122B based on applying the direction offset454B, the distance offset456B, or both, to the map location128B.

The label location generator214generates the label location data215indicating that the label112A has the label location122A, the label112B has the label location122B, one or more additional labels of the labels213have corresponding label locations, or a combination thereof. In a particular aspect, the label locations122correspond to default locations of the labels213in the map119(to be generated).

Referring toFIG.5, a diagram500illustrates examples of operations performed by the bounding box generator216. The bounding box generator216is configured to generate, based on the label location data215, the zoom level333, the label display data235, or a combination thereof, bounding box data217indicating bounding boxes124of the labels213.

The label display data235indicates display settings535associated with the label types352. For example, the label display data235indicates display settings535A of the label type352A, display settings535B of the label type352B, display settings of one or more additional label types or a combination thereof. To illustrate, the display settings535A indicates that a label of the label type352A is to be displayed with a font type510A, a font size512A, a buffer514A, a text alignment516A, a text filter520A, a map location symbol522A, or a combination thereof. In a particular implementation, the label display data235includes display settings associated with various zoom levels. For example, the display settings535A are associated with the zoom level333and indicate how labels of the label type352A are to be displayed for the zoom level333.

In a particular aspect, the label112A is of the label type352A. The bounding box generator216, based on the display settings535A, determines that the buffer514A indicates space to be included around text (or another type of identifier) to be displayed for the label112A. In some implementations, the buffer514A includes a top buffer, a bottom buffer, a left side buffer, a right side buffer, or a combination thereof. The text alignment516A (e.g., a value greater than or equal to 0 and less than 360, a value indicating horizontal or vertical alignment, etc.) indicates an alignment of the text (or another type of identifier) to be displayed for the label112A. The text filter520A indicates how the text350A is to be processed to generate the text to be displayed for the label112A. For example, the text filter520A can indicate that a word included in the text350A (e.g., “runway”) is to be substituted with one or more characters (e.g., “RWY”).

The bounding box generator216, based on the display settings535A and the text350A, determines dimensions (e.g., a width542A, a height544A, or both) of a bounding box124A of the label112A. Similarly, the bounding box generator216, based on the display settings535B and the text350B, determines dimensions (e.g., a width542B, a height544B, or both) of a bounding box124B of the label112B. In some aspects, the display settings535A can have one or more settings in common with the display settings535B. In some aspects, the display settings535A can have one or more settings that are distinct from the display settings535B.

The bounding box generator216determines, based on the label location122A, the bounding box124A of the label112A. For example, the label location122A has coordinates including a horizontal coordinate (XL) and a vertical coordinate (YL). A top-left vertex of the bounding box124A has a horizontal coordinate (XTL) that is based on the horizontal coordinate (XL) of the label location122A and the width542A (e.g., XTL=XL−0.5 (width542A)). The top-left vertex of the bounding box124A has a vertical coordinate (YTL) that is based on the vertical coordinate (YL) of the label location122A and the height544A (e.g., YTL=YL+0.5 (height544A)).

A bottom-right vertex of the bounding box124A has a horizontal coordinate (XBR) that is based on the horizontal coordinate (XL) of the label location122A and the width542A (e.g., XBR=XL+0.5 (width542A)). The bottom-right vertex of the bounding box124A has a vertical coordinate (YBR) that is based on the vertical coordinate (YL) of the label location122A and the height544A (e.g., YBR=YL−0.5 (height544A)). Similarly, the bounding box generator216determines, based on the label location122B, the bounding box124B of the label112B.

The bounding box generator216generates the bounding box data217indicating that the label112A has the bounding box124A, the label112B has the bounding box124B, one or more additional labels of the labels213have corresponding bounding boxes124, or a combination thereof. In an example530, the bounding box generator216generates the bounding box data217indicating that the label112A has the bounding box124A at the label location122A and that the label112B has the bounding box124B at the label location122B.

Referring toFIG.6A, a diagram600illustrates examples of operations performed by the conflict analyzer218. The conflict analyzer218includes the conflict detector612coupled via a deconflictor614to a selection criterion analyzer616.

The conflict detector612is configured to determine, based on the bounding box data217, whether a conflict exists between at least a pair of the labels213, as further described with reference toFIG.6B. The deconflictor614is configured to generate candidate label locations of the pair of the labels213to resolve the conflict, as further described with reference toFIG.6C. The selection criterion analyzer616is configured to determine whether a candidate label location satisfies a selection criterion, as further described with reference toFIG.6D.

In a particular implementation, the conflict analyzer218, in response to receiving the bounding box data217from the bounding box generator216, performs a conflict analysis602until a stop condition622is detected. In a particular aspect, the stop condition622includes detecting that a threshold count of iterations have been performed, detecting that a timer has expired, determining that no conflicts are detected between any pair of the labels213, or a combination thereof.

In a particular aspect, the conflict analysis602corresponds to a comparison of each of the labels213with others of the labels213to determine whether a conflict is detected. In a particular implementation, the conflict analyzer218initializes first labels680to include the labels213. The first labels680correspond to labels that are remaining for the conflict analysis602. The conflict analyzer218performs one or more analysis iterations604during the conflict analysis602to compare each of the labels213to others of the labels213.

The conflict analyzer218, in response to determining that the first labels680include at least one label, determines that an analysis iteration604is to be performed. During an analysis iteration604, the conflict analyzer218performs a conflict analysis of one of the first labels680. As an example, the conflict analyzer218removes a particular label112(e.g., the label112A) from the first labels680, and designates the particular label112as a first label690. The first label690corresponds to a label that is being analyzed during the analysis iteration604. The conflict analyzer218initializes second labels682with all labels from the labels213other than the first label690. The second labels682correspond to labels that are to be compared with the first label690during the analysis iteration604.

The conflict analyzer218performs one or more label comparison iterations606during the analysis iteration604to compare the first label690to the second labels682. During a label comparison iteration606, the conflict analyzer218performs a comparison of the first label690with one of the second labels682. As an example, the conflict analyzer218removes a particular label112(e.g., the label112B) from the second labels682, and designates the particular label112as a second label692. The first label690is compared to the second label692during the label comparison iteration606. The conflict analyzer218provides the first label690and the second label692to the conflict detector612.

The conflict detector612performs a comparison of the first label690and the second label692based on the bounding box data217, as further described with reference toFIG.6B. The conflict analyzer218, in response to determining that the conflict detector612indicates no conflict between the first label690and the second label692, determines that the label comparison iteration606has ended successfully. Alternatively, the conflict analyzer218, in response to determining that the conflict detector612indicates a conflict between the first label690and the second label692, provides the bounding boxes of the first label690and the second label692to the deconflictor614.

The deconflictor614determines candidate label locations of the first label690and the second label692based on bounding boxes of the first label690and the second label692, as further described with reference toFIG.6C. In a particular example, the first label690includes the label112A and the second label692includes the label112B. In this example, the deconflictor614determines the candidate label location126A and the candidate label location126B based on the bounding box124A of the label112A and the bounding box124B of the label112B.

The conflict analyzer218provides candidate label locations (e.g., the candidate label location126A and the candidate label location126B) to the selection criterion analyzer616. The selection criterion analyzer616determines whether each of the candidate label locations satisfies a corresponding selection criterion, as further described with reference toFIG.6D.

The conflict analyzer218, in response to determining that each of the candidate label locations (e.g., the candidate label location126A and the candidate label location126B) satisfies a corresponding selection criterion, determines that a label location of at least one of the first label690or the second label692is to be updated. For example, the conflict analyzer218, in response to determining that the label location122A is distinct from the candidate label location126A, updates the bounding box data217to set the label location122A of the bounding box124A to indicate the candidate label location126A, and resets the second labels682to include all of the labels213other than the first label690(e.g., the label112A). To illustrate, since the first label690(e.g., the label112A) has moved, the second labels682are reset so that subsequent label comparison iterations606also include any of the labels213to which the label112A has already been compared. As another example, the conflict analyzer218, in response to determining that the label location122B is distinct from the candidate label location126B, updates the bounding box data217to set the label location122B to indicate the candidate label location126B and, if the label112B is not included in the first labels680, adds the label112B to the first labels680. To illustrate, since the label112B has moved, if an analysis iteration604of the label112B has already been performed, the label112B is added back to the first labels680so that an analysis iteration604of the label112B can be performed again. The conflict analyzer218, in response to determining that each of the candidate label locations (e.g., the candidate label location126A and the candidate label location126B) satisfies a corresponding selection criterion, determines that the label comparison iteration606has ended.

In some implementations, the conflict analyzer218, in response to determining that at least one of the candidate label locations (e.g., the candidate label location126A and the candidate label location126B) fails to satisfy a corresponding selection criterion, uses the deconflictor614, the selection criterion analyzer616, or both, to process the first label690and the second label692again. For example, the conflict analyzer218provides the bounding boxes of the first label690and the second label692to the deconflictor614. In some examples, the conflict analyzer218provides the candidate label locations of the first label690and the second label692to the deconflictor614.

In a particular aspect, the deconflictor614generates an output indicating that all available candidate label locations for the first label690, the second label692, or both, have been previously generated during the label comparison iteration606. The conflict analyzer218, in response to receiving the output from the deconflictor614, determines that the label comparison iteration606has ended unsuccessfully. Alternatively, the deconflictor614generates an updated version of the candidate label locations, as further described with reference toFIG.6C, and the conflict analyzer218provides the updated candidate label locations to the selection criterion analyzer616. The label comparison iteration606continues with the selection criterion analyzer616determining whether each of the updated candidate label locations satisfies the corresponding selection criterion.

In some implementations, the conflict analyzer218, in response to determining that one (e.g., the candidate label location126A) of the candidate label locations satisfies a corresponding selection criterion and that the other (e.g., the candidate label location126B) of the candidate label locations fails to satisfy the second selection criterion, generates an updated version of the candidate label location126B based on the candidate label location126A and the candidate label location126B, and provides the updated version of the candidate label location126B to the selection criterion analyzer616. In these implementations, the conflict analyzer218refrains from generating an updated version of the candidate label location126A in response to determining that the candidate label location126A satisfies the first selection criterion. The label comparison iteration606continues with the selection criterion analyzer616determining whether the updated candidate label location satisfies the corresponding selection criterion.

In some implementations, the conflict analyzer218, in response to determining that the label comparison iteration606has ended unsuccessfully, refrains from updating the label locations of the first label690(e.g., the label112A) and the second label692(e.g., the label112B). In these implementations, the conflict analyzer218generates a notification indicating a conflict between the label112A at the label location122A and the label112B at the label location122B.

In some implementations, the conflict analyzer218, in response to determining that the label comparison iteration606has ended unsuccessfully, sets the label locations of the first label690and the second label692to the candidate label locations, and generates a notification indicating that a corresponding selection criterion is not satisfied. For example, the conflict analyzer218, in response to determining that the candidate label location126A is distinct from the label location122A, updates the bounding box data217to set the label location122A of the bounding box124A to indicate the candidate label location126A and resets the second labels682to include all of the labels213other than the first label690(e.g., the label112A). Similarly, the conflict analyzer218, in response to determining that the candidate label location126B is distinct from the label location122B, updates the bounding box data217to set the label location122B to indicate the candidate label location126B and, if the label112B is not included in the first labels680, adds the label112B to the first labels680.

The conflict analyzer218generates a notification indicating that the label112B at the candidate label location126B fails to satisfy the second selection criterion. In a particular aspect, the conflict analyzer218adds the notification (e.g., of a detected conflict or failure to satisfy a selection criterion) to the bounding box data217. The conflict analyzer218, when generating the map119(or map data), includes the notification in the map119, the map data, an alert, or a combination thereof.

In some implementations, the conflict analyzer218, in response to determining that the label comparison iteration606has ended, determines whether the stop condition622is detected. In some examples, the conflict analyzer218, in response to determining that at least a threshold count of label comparison iterations606have been performed, a timer has expired, or both, determines that the stop condition622is detected. The conflict analyzer218, in response to determining that the stop condition622is detected, determines that the conflict analysis602has ended and generates (e.g., renders) the map119, the map data, an alert, or a combination thereof, based on the bounding box data217. In a particular aspect, the conflict analyzer218provides the map119, the map data, the alert, or a combination thereof, to another component or device.

In a particular example, the map119is generated based on the label display data235. For example, the map generator104generates the map119to display the label112A based on the font type510A, the font size512A, the buffer514A, the text alignment516A, the text filter520A, or a combination thereof. As another example, the map generator104generates the map119to display the map location symbol522A at the map location128A.

In a particular aspect, the conflict analyzer218, in response to determining that the label comparison iteration606has ended and that the stop condition622is not detected, determines whether another label comparison iteration606is to be performed with the first label690. For example, the conflict analyzer218, in response to determining that the second labels682include at least one label to be compared to the first label690, initiates another label comparison iteration606. To illustrate, the conflict analyzer218removes a particular label112from the second labels682and designates the particular label112as the second label692. The conflict analyzer218provides the first label690and the second label692to the conflict detector612. Alternatively, the conflict analyzer218, in response to determining that there are no labels in the second labels682, determines that the analysis iteration604has ended.

In some implementations, the conflict analyzer218, in response to determining that the analysis iteration604has ended, determines whether the stop condition622is detected. In some examples, the conflict analyzer218, in response to determining that at least a threshold count of analysis iterations604have been performed, a timer has expired, or both, determines that the stop condition622is detected. The conflict analyzer218, in response to determining that the stop condition622is detected, determines that the conflict analysis602has ended and generates (e.g., renders) the map119, the map data, an alert, or a combination thereof, based on the bounding box data217. In a particular aspect, the conflict analyzer218provides the map119, the map data, the alert, or a combination thereof, to another component or device.

In a particular aspect, the conflict analyzer218, in response to determining that the analysis iteration604has ended and that the stop condition622is not detected, determines whether another analysis iteration604is to be performed with another label selected as the first label690. For example, the conflict analyzer218, in response to determining that the first labels680include at least one label to be analyzed, initiates another analysis iteration604. To illustrate, the conflict analyzer218removes a particular label112(e.g., the label112B) from the first labels680and designates the particular label112as the first label690. The conflict analyzer218initializes the second labels682with all labels from the labels213other than the first label690. The conflict analyzer218performs one or more label comparison iterations606to compare the first label690to the second labels682.

The conflict analyzer218, in response to determining that there are no labels in the first labels680, determines that the conflict analysis602has ended and generates the map119, map data, an alert, or a combination thereof, based on the bounding box data217. For example, the map119includes the label112A at the label location122A indicated by the bounding box data217, the label112B at the label location122B indicated by the bounding box data217, one or more additional labels112at label locations122indicated by the bounding box data217, one or more notifications, or a combination thereof. In some examples, the label location122A indicated by the bounding box data217corresponds to the label location122A generated by the label location generator214. For example, the label location122A has not been updated by the conflict analyzer218. In some examples, the label location122A indicated by the bounding box data217corresponds to the candidate label location126A generated by the deconflictor614. For example, the label location122A has been updated by the conflict analyzer218to resolve a conflict.

In a particular aspect, the conflict analyzer218provides the map119, the map data, an alert (e.g., including a notification), or a combination thereof, to another component or device (e.g., a display device, a user device, a network device, etc.).

A technical advantage of the conflict analyzer218resolving the conflicts prior to generating (e.g., rendering) the map119can include using less time and fewer computing resources as compared to moving labels in a rendered map. With conflicts resolved prior to rendering, the map119can be rendered with resolved conflicts faster and aid navigation in time-critical situations.

Referring toFIG.6B, a diagram610illustrates examples of operations performed by the conflict detector612. The conflict detector612is configured to generate a conflict indicator672indicating whether a conflict is detected between the first label690and the second label692.

The conflict detector612performs a comparison of the first label690and the second label692based on the bounding box data217. In an example, the first label690is the label112A and the second label692is the label112B. In this example, the conflict detector612determines whether the bounding box124A of the label112A overlaps the bounding box124B of the label112B. In a particular aspect, the conflict detector612determines that the bounding box124A overlaps the bounding box124B in response to determining that at least one vertex of the bounding box124A is within the bounding box124B, at least one vertex of the bounding box124B is within the bounding box124A, or both. In a particular aspect, the conflict detector612determines that the bounding box124A overlaps the bounding box124B in response to determining that the label location122A is the same as the label location122B and that the bounding box124A has the same dimensions as the bounding box124B (e.g., the width542A is the same as the width542B and the height544A is the same as the height544B).

The conflict detector612determines whether a particular vertex is within a bounding box based on comparing vertex coordinates of the bounding box with coordinates of the particular vertex. For example, the conflict detector612determines coordinates (XTL, YTL) of the top-left vertex of the bounding box124A based on coordinates (XL, YL) of the label location122A, the width542A, and the height544A, as described with reference toFIG.5. The conflict detector612determines coordinates (XBR, YBR) of the bottom-right vertex of the bounding box124A based on coordinates (XL, YL) of the label location122A, the width542A, and the height544A, as described with reference toFIG.5. The conflict detector612determines that a vertex (X, Y) of the bounding box124B is within the bounding box124A based on determining that X is greater than XTLand less than XBRand Y is greater than YBRand less than YTL. In an example630, a top-left vertex of the bounding box124B is within the bounding box124A and a bottom-right vertex of the bounding box124A is within the bounding box124B.

The conflict detector612, in response to determining that the bounding box124A overlaps the bounding box124B, generates the conflict indicator672having a first value (e.g., 1) indicating a conflict between the first label690and the second label692. Alternatively, the conflict detector612, in response to determining that the bounding box124A does not overlap the bounding box124B, generates the conflict indicator672having a second value (e.g., 0) indicating no conflict between the first label690and the second label692.

Referring toFIG.6C, a diagram650is shown that illustrates examples of operations performed by the deconflictor614. The deconflictor614is configured to generate a pair of candidate label locations126to resolve a conflict between a pair of bounding boxes124.

The deconflictor614determines an intersection140of the bounding boxes of the first label690and the second label692. In an example in which the first label690is the label112A and the second label692is the label112B, the deconflictor614determines the intersection140of the bounding box124A and the bounding box124B.

The deconflictor614determines vertex coordinates of the intersection140based on vertex coordinates of the bounding box124A and the bounding box124B. In an example, the deconflictor614determines the coordinates (XATL, YATL) of the top-left vertex and the coordinates (XABR, YABR) of the bottom-right vertex of the bounding box124A, as described with reference toFIG.5. Similarly, the deconflictor614determines coordinates (XBTL, YBTL) of the top-left vertex and coordinates (XBBR, YBBR) of the bottom-right vertex of the bounding box124B.

The deconflictor614determines coordinates (XITL, YITL) of a top-left vertex of the intersection140based on the coordinates (XATL, YATL) of the top-left vertex of the bounding box124A and the coordinates (XBTL, YBTL) of the top-left vertex of the bounding box124B (e.g., XITL=max (XATL, XBTL), where max (a, b) corresponds to the higher of a or b, and YITL=min (YATL, YBTL), where min (a, b) corresponds to the lower of a or b).

The deconflictor614determines coordinates (XIBR, YIBR) of a bottom-right vertex of the intersection140based on the coordinates (XABR, YABR) of the bottom-right vertex of the bounding box124A and the coordinates (XBBR, YBBR) of the bottom-right vertex of the bounding box124B (e.g., XIBR=min (XABR, XBBR), and YIBR=max (YABR, YBBR)). In a particular aspect, the intersection140is indicated by the top-left vertex coordinates (XITL, YITL) and the bottom-right vertex coordinates (XIBR, YIBR).

The deconflictor614determines a movement offset based on dimensions of the intersection140(e.g., as indicated by the coordinates). The movement offset includes a vertical movement offset642, a horizontal movement offset644, or both. In some implementations, the deconflictor614determines the vertical movement offset642based on a difference between a vertical coordinate of the top-left vertex of the intersection140and a vertical coordinate of the bottom-right vertex of the intersection140(e.g., the vertical movement offset642=YITL−YIBR). In some implementations, the deconflictor614determines the horizontal movement offset644based on a difference between a horizontal coordinate of the bottom-right vertex of the intersection140and a horizontal coordinate of the top-left vertex of the intersection140(e.g., the horizontal movement offset644=XIBR−XITL).

The deconflictor614applies a first portion of the movement offset to the label location122A to determine a candidate label location126A of the label112A, a second portion of the movement offset to the label location122B to determine a candidate label location126B of the label112B, or both. In some implementations, the first portion, the second portion, or both, are based on relative priorities associated with the label type352A of the label112A and the label type352B of the label112B. For example, the first portion is higher than the second portion if a first priority of the label type352A is lower than a second priority of the label type352B.

A candidate bounding box624A of the label112A is at the candidate label location126A and has the same dimensions as the bounding box124A. A candidate bounding box624B of the label112B is at the candidate label location126B and has the same dimensions as the bounding box124B. The candidate bounding box624A does not overlap the candidate bounding box624B.

In an example632A, the movement offset includes the vertical movement offset642and the horizontal movement offset644. In an example632B, the movement offset includes the vertical movement offset642and does not include the horizontal movement offset644. In an example632C, the movement offset includes the horizontal movement offset644and does not include the vertical movement offset642. In each of the example632A, the example632B, and the example632C, the deconflictor614applies half of the movement offset to the label location122A to determine the candidate label location126A and half of the movement offset to the label location122B to determine the candidate label location126B.

In the example632A, coordinates (XACL, YACL) of the candidate label location126A are based on coordinates (XAL, YAL) of the label location122A, half of the horizontal movement offset644, and half of the vertical movement offset642(e.g., XACL=XAL−0.5 (the horizontal movement offset644), and YACL=YAL+0.5 (the vertical movement offset642)). Similarly, coordinates (XBCL, YBCL) of the candidate label location126B are based on coordinates (XBL, YBL) of the label location122B, half of the horizontal movement offset644, and half of the vertical movement offset642(e.g., XBCL=XBL+0.5 (the horizontal movement offset644), and YBCL=YBL−0.5 (the vertical movement offset642)).

In the example632B, coordinates (XACL, YACL) of the candidate label location126A are based on coordinates (XAL, YAL) of the label location122A and half of the vertical movement offset642(e.g., XACL=XALand YACL=YAL+0.5 (the vertical movement offset642)). Similarly, coordinates (XBCL, YBCL) of the candidate label location126B are based on coordinates (XBL, YBL) of the label location122B and half of the vertical movement offset642(e.g., XBCL=XBL, and YBCL=YBL−0.5 (the vertical movement offset642)).

In the example632C, coordinates (XACL, YACL) of the candidate label location126A are based on coordinates (XAL, YAL) of the label location122A and half of the horizontal movement offset644(e.g., XACL=XAL−0.5 (the horizontal movement offset644), and YACL=YAL). Similarly, coordinates (XBCL, YBCL) of the candidate label location126B are based on coordinates (XBL, YBL) of the label location122B and half of the horizontal movement offset644(e.g., XBCL=XBL+0.5 (the horizontal movement offset644), and YBCL=YBL).

The example632A, the example632B, and the example632C are provided as illustrative, non-limiting, examples of applying portions of movement offsets to the label location122A and the label location122B to determine the candidate label location126A and the candidate label location126B, respectively. In other examples, other types of movement offsets can be applied to the label location122A, the label location122B, or both.

In some implementations, the deconflictor614has a set of available movement offset combinations that can be performed. For example, a first movement offset combination includes a vertical movement offset642and a horizontal movement offset644. A second movement offset combination includes the vertical movement offset642and not the horizontal movement offset644. A third movement offset combination includes the horizontal movement offset644and not the vertical movement offset642. The set of available movement offset combinations can include one or more of the first movement offset combination, the second movement offset combination, the third movement offset combination, or another type of movement offset combination. In a particular aspect, the deconflictor614selects one of the available movement offset combinations from the set to generate candidate label locations126.

In a particular implementation, the deconflictor614initializes a set of remaining movement offset combinations to include each of the available movement offset combinations at a start of the label comparison iteration606of the first label690and the second label692. The deconflictor614, in response to receiving a request from the conflict analyzer218to generate candidate label locations during the label comparison iteration606, selects one of the movement offset combinations from the set of remaining offset movement combinations to generate the candidate label locations126and removes the selected movement offset combination from the set of remaining offset movement combinations. The deconflictor614, in response to determining that the set of remaining movement combinations is empty, determines that all available candidate label locations for the first label690and the second label692have been previously generated.

In a particular implementation, the deconflictor614receives previously generated candidate label locations (e.g., the candidate label location126A and the candidate label location126B) of the first label690and the second label692from the conflict analyzer218with an indication that least one of the candidate label locations fails to satisfy a corresponding selection criterion. The deconflictor614determines the candidate bounding box624A corresponding to the candidate label location126A and the candidate bounding box624B corresponding to the candidate label location126B. The deconflictor614determines updated versions of the candidate label location126A and the candidate label location126B based on the candidate bounding box624A and the candidate bounding box624B. For example, the deconflictor614determines updated versions of the candidate label location126A and the candidate label location126B such that there is no conflict between corresponding updated versions of the candidate bounding box624A and the candidate bounding box624B.

Referring toFIG.6D, a diagram660illustrates examples of operations performed by the selection criterion analyzer616. The selection criterion analyzer616is configured to determine whether the candidate label location126A satisfies a first selection criterion, the candidate label location126B satisfies a second selection criterion, or both.

The selection criterion analyzer616determines, based on the candidate label location126A, a candidate bounding box624A of the label112A. For example, the candidate bounding box624A is at the candidate label location126A and has the same dimensions (e.g., the width542A, the height544A, or both) as the bounding box124A. Similarly, the selection criterion analyzer616determines, based on the candidate label location126B, a candidate bounding box624B of the label112B. For example, the candidate bounding box624B is at the candidate label location126B and has the same dimensions (e.g., the width542B, the height544B, or both) as the bounding box124B.

In a particular aspect, the selection criterion analyzer616determines that the candidate label location126A satisfies the first selection criterion based at least in part on determining that the candidate label location126A is greater than or equal to a first threshold distance from the map location128A (or the map location symbol522A), less than or equal to a second threshold distance from the map location128A (or the map location symbol522A), or both. In a particular aspect, the selection criterion analyzer616determines that the candidate label location126A satisfies the first selection criterion based at least in part on determining that the candidate bounding box624A is at least a first threshold distance from the map location128A (or the map location symbol522A), is within a second threshold distance from the map location128A (or the map location symbol522A), or both. One or more of the threshold distances are based on a user input, a configuration setting, default data, the zoom level333ofFIG.3, a corresponding label type352, or a combination thereof.

Similarly, the selection criterion analyzer616determines that the candidate label location126B satisfies the second selection criterion based at least in part on determining that the candidate label location126B is greater than or equal to a first threshold distance from the map location128B (or a second map location symbol of the label type352B), less than or equal to a second threshold distance from the map location128B (or the second map location symbol), or both. In a particular aspect, the selection criterion analyzer616determines that the candidate label location126B satisfies the second selection criterion based at least in part on determining that the candidate bounding box624B is at least a first threshold distance from the map location128B (or the second map location symbol), is within a second threshold distance from the map location128B (or the second map location symbol), or both.

In some implementations, the selection criterion analyzer616determines that the candidate label location126A of the label112A satisfies the first selection criterion based at least in part on determining that the candidate bounding box624A does not overlap bounding boxes (e.g., as indicated by the bounding box data217) of any of the other labels of the labels213. Similarly, the selection criterion analyzer616determines that the candidate label location126B of the label112B satisfies the second selection criterion based at least in part on determining that the candidate bounding box624B does not overlap bounding boxes (e.g., as indicated by the bounding box data217) of any of the other labels of the labels213.

An example634A corresponds to the candidate label location126A and the candidate label location126B of the example632A ofFIG.6B. An example634B corresponds to the candidate label location126A and the candidate label location126B of the example632B ofFIG.6B. An example634C corresponds to the candidate label location126A and the candidate label location126B of the example632C ofFIG.6C.

In each of the example634A, the example634B, and the example634C, the selection criterion analyzer616, in response to determining that the candidate bounding box624A is at least a first threshold distance from the map location128A and less than a second threshold distance from the map location128A, determines that the candidate label location126A satisfies the first selection criterion.

In each of the example634A and the example634B, the selection criterion analyzer616, in response to determining that the candidate bounding box624B is less than a first threshold distance from the map location128B, determines that the candidate label location126B fails to satisfy the second selection criterion. In the example634C, the selection criterion analyzer616, in response to determining that the candidate bounding box624B is at least the first threshold distance from the map location128B and is within a second threshold distance from the map location128B, determines that the candidate label location126B satisfies the second selection criterion.

In each of the example634A, the example634B, and the example634C, the selection criterion analyzer616generates a criterion met indicator620indicating that the candidate label location126A satisfies a corresponding selection criterion. In the each of the example634A and the example634B, the criterion met indicator620indicating that the candidate label location126B fails to satisfy a corresponding selection criterion. In the example634C, the criterion met indicator620indicates that the candidate label location126B satisfies a corresponding selection criterion.

Referring toFIG.7, an example is shown of a method700of an example of adjusting locations of map labels. In a particular aspect, one or more operations of the method700are performed by the map generator104ofFIG.1, the label selector212, the label location generator214, the bounding box generator216, the conflict analyzer218, the one or more processors290, the device202, the system200ofFIG.2, or a combination thereof.

For example, at702, the bounding box generator216ofFIG.2obtains (e.g., generates) the bounding box data217indicating label locations and bounding box dimensions, as described with reference toFIGS.2and5.

At704, the conflict analyzer218ofFIG.2determines whether the first labels680include at least one label, as described with reference toFIG.6A. At716, the conflict analyzer218, in response to determining that there are no labels in the first labels680and that the bounding box data217includes at least one bounding box, generates the map119, map data, an alert, or a combination thereof, based on the bounding box data217. Alternatively, the conflict analyzer218, in response to determining that there are no labels in the first labels680and that there are no bounding boxes indicated in the bounding box data217, generates an output indicating that no map is generated.

The conflict analyzer218, in response to determining that the first labels680include at least one label, initiates an analysis iteration604, as described with reference toFIG.6A. For example, at706, the conflict analyzer218designates one of the first labels680as the first label690and designates all of the labels213other than the first label690as the second labels682, as described with reference toFIG.6A. At708, the conflict analyzer218determines whether the second labels682include at least one label, as described with reference toFIG.6A. The conflict analyzer218, in response to determining that there are no labels in the second labels682, determines that the analysis iteration604has ended and, at704, determines whether the first labels680include at least one label to initiate a next analysis iteration.

Alternatively, the conflict analyzer218, in response to determining that the second labels682include at least one label, initiates a label comparison iteration606, as described with reference toFIG.6A. For example, the conflict analyzer218selects one of the second labels682as the second label692, and the conflict detector612determines, at710, whether the first label690conflicts with the second label692, as described with reference toFIG.6B.

The conflict analyzer218, in response to determining that no conflict is detected between the first label690and the second label692, determines that the label comparison iteration606has ended successfully, as described with reference toFIG.6A, and, at708, determines whether the second labels682include at least one label to initiate a next label comparison iteration.

Alternatively, at712, the conflict analyzer218, in response to determining that the first label690conflicts with the second label692, determines an intersection between the first label690and the second label692. For example, the conflict analyzer218, in response to determining that the conflict detector612detected a conflict between the first label690and the second label692, provides bounding boxes of the first label690and the second label692to the deconflictor614, as described with reference toFIG.6A. The deconflictor614determines the intersection140between the first label690and the second label692, as described with reference toFIG.6C.

At714, the conflict analyzer218moves the first label690, the second label692, or both. For example, the deconflictor614generates candidate label locations of the first label690and the second label692based on the intersection140, as described with reference toFIG.6C. The selection criterion analyzer616determines whether each of the candidate label locations satisfies a corresponding selection criterion, as described with reference toFIG.6D. The conflict analyzer218updates the bounding box data217to designate a candidate label location as a label location based at least in part on the candidate label location satisfying the selection criterion, as described with reference toFIG.6A. At706, the conflict analyzer218, responsive to moving the first label690, resets the second labels682to include all of the labels213other than the first label690, as described with reference toFIG.6A.

Referring toFIG.8, an example is shown of a method800of an example of adjusting locations of map labels. In a particular aspect, one or more operations of the method800are performed by the map generator104ofFIG.1, the label selector212, the label location generator214, the bounding box generator216, the conflict analyzer218, the one or more processors290, the device202, the system200ofFIG.2, or a combination thereof.

The method800includes, at802, determining a first label location of a first label that identifies a first map location. For example, the label location generator214ofFIG.2determines the label location122A of the label112A that identifies the map location128A, as described with reference toFIGS.2and4.

The method800also includes, at804, determining a first label location of a second label that identifies a second map location. For example, the label location generator214ofFIG.2determines the label location122B of the label112B that identifies the map location128B, as described with reference toFIGS.2and4.

The method800further includes, at806, determining, based on the first label location of the first label, a first bounding box of the first label. For example, the bounding box generator216ofFIG.2determines, based on the label location122A, the bounding box124A of the label112A, as described with reference toFIGS.2and5.

The method800also includes, at808, determining, based on the first label location of the second label, a first bounding box of the second label. For example, the bounding box generator216ofFIG.2determines, based on the label location122/b, the bounding box124B of the label112B, as described with reference toFIGS.2and5.

The method800further includes, at810, determining whether the first bounding box of the first label overlaps the first bounding box of the second label. For example, the conflict detector612ofFIG.6Adetermines whether the bounding box124A overlaps the bounding box124B, as described with reference toFIGS.6A and6B.

The method800also includes, at812, based on determining that the first bounding box of the first label overlaps the first bounding box of the second label, determining a first candidate label location of the first label and a first candidate label location of the second label based on an intersection of the first bounding box of the first label and the first bounding box of the second label. For example, the deconflictor614ofFIG.6B, based on determining that the bounding box124A overlaps the bounding box124B, determines the candidate label location126A and the candidate label location126B based on the intersection140of the bounding box124A and the bounding box124B, as described with reference toFIGS.6A and6C.

The method800further includes, at814, based on determining that the first candidate label location of the first label satisfies a first selection criterion and that the first candidate label location of the second label satisfies a second selection criterion, generating a map including the first label at the first candidate label location of the first label and the second label at the first candidate label location of the second label. For example, the selection criterion analyzer616ofFIG.6Adetermines that the candidate label location126A satisfies a first criterion and the candidate label location126B satisfies a second criterion, as described with reference to the example634C ofFIG.6D. The conflict analyzer218, in response to determining that each of the candidate label location126A and the candidate label location126B satisfies a corresponding selection criterion, generates the map119including the label112A at the candidate label location126A and the label112B at the candidate label location126B, as described with reference toFIG.6A.

A technical advantage of the method800can include that the label112A at the candidate label location126A and the label112B at the candidate label location126C is easier to read than the label112A at the label location122A and the label112B at the label location122B.

FIG.9is a block diagram of a computing environment900including a computing device910configured to support aspects of computer-implemented methods and computer-executable program instructions (or code) according to the present disclosure. For example, the computing device910, or portions thereof, is configured to execute instructions to initiate, perform, or control one or more operations described with reference toFIGS.1-8.

The computing device910includes the one or more processors290. The one or more processors290are configured to communicate with system memory930, one or more storage devices940, one or more input/output interfaces950, one or more communications interfaces960, or any combination thereof. The system memory930includes volatile memory devices (e.g., random access memory (RAM) devices), nonvolatile memory devices (e.g., read-only memory (ROM) devices, programmable read-only memory, and flash memory), or both. The system memory930stores an operating system932, which may include a basic input/output system for booting the computing device910as well as a full operating system to enable the computing device910to interact with users, other programs, and other devices. The system memory930stores system (program) data936, such as data used or generated by the map generator104.

The system memory930includes one or more applications934(e.g., sets of instructions) executable by the one or more processors290. As an example, the one or more applications934include the instructions294executable by the one or more processors290to initiate, control, or perform one or more operations described with reference toFIGS.1-8. To illustrate, the one or more applications934include the instructions294executable by the one or more processors290to initiate, control, or perform one or more operations described with reference to the map generator104.

In a particular implementation, the system memory930includes a non-transitory, computer readable medium storing the instructions294that, when executed by the one or more processors290, cause the one or more processors290to determine a first label location (e.g., the label location122A) of a first label (e.g., the label112A) that identifies a first map location (e.g., the map location128A). The instructions, when executed by the one or more processors, also cause the one or more processors to determine a first label location (e.g., the label location122B) of a second label (e.g., the label112B) that identifies a second map location (e.g., the map location128B). The instructions, when executed by the one or more processors, further cause the one or more processors to determine, based on the first label location of the first label, a first bounding box (e.g., the bounding box124A) of the first label. The instructions, when executed by the one or more processors, also cause the one or more processors to determine, based on the first label location of the second label, a first bounding box (e.g., the bounding box124B) of the second label. The instructions, when executed by the one or more processors, further cause the one or more processors to determine whether the first bounding box of the first label overlaps the first bounding box of the second label. The instructions, when executed by the one or more processors, also cause the one or more processors to, based on determining that the first bounding box of the first label overlaps the first bounding box of the second label, determine a first candidate label location (e.g., the candidate label location126A) of the first label and a first candidate label location (e.g., the candidate label location126B) of the second label based on an intersection of the first bounding box of the first label and the first bounding box of the second label. The instructions, when executed by the one or more processors, further cause the one or more processors to, based on determining that the first candidate label location of the first label satisfies a first selection criterion and that the first candidate label location of the second label satisfies a second selection criterion, generate a map (e.g., the map119) including the first label at the first candidate label location of the first label and the second label at the first candidate label location of the second label.

The one or more storage devices940include nonvolatile storage devices, such as magnetic disks, optical disks, or flash memory devices. In a particular example, the storage devices940include both removable and non-removable memory devices. The storage devices940are configured to store an operating system, images of operating systems, applications (e.g., one or more of the applications934), and program data (e.g., the program data936). In a particular aspect, the system memory930, the storage devices940, or both, include tangible computer-readable media. In a particular aspect, one or more of the storage devices940are external to the computing device910.

The one or more input/output interfaces950enable the computing device910to communicate with one or more input/output devices970to facilitate user interaction. For example, the one or more input/output interfaces950can include a display interface, an input interface, or both. For example, the input/output interface950is adapted to receive input from a user, to receive input from another computing device, or a combination thereof. In some implementations, the input/output interface950conforms to one or more standard interface protocols, including serial interfaces (e.g., universal serial bus (USB) interfaces or Institute of Electrical and Electronics Engineers (IEEE) interface standards), parallel interfaces, display adapters, audio adapters, or custom interfaces (“IEEE” is a registered trademark of The Institute of Electrical and Electronics Engineers, Inc. of Piscataway, New Jersey). In some implementations, the input/output device970includes one or more user interface devices and displays, including some combination of buttons, keyboards, pointing devices, displays, speakers, microphones, touch screens, and other devices.

The one or more processors290are configured to communicate with devices or controllers980via the one or more communications interfaces960. For example, the one or more communications interfaces960can include a network interface. The devices or controllers980can include, for example, a user device, a display device, one or more other devices, or any combination thereof.

In conjunction with the described systems and methods, an apparatus for adjusting locations of map labels is disclosed that includes means for determining a first label location of a first label that identifies a first map location. In some implementations, the means for determining the first label location of the first label corresponds to the map generator104ofFIG.1, the label location generator214, the one or more processors290, the device202, the system200ofFIG.2, the computing device910, one or more other circuits or devices configured to determine the first label location of the first label, or a combination thereof.

The apparatus also includes means for determining a first label location of a second label that identifies a second map location. In some implementations, the means for determining the first label location of the second label corresponds to the map generator104ofFIG.1, the label location generator214, the one or more processors290, the device202, the system200ofFIG.2, the computing device910, one or more other circuits or devices configured to determine the first label location of the second label, or a combination thereof.

The apparatus further includes means for determining a first bounding box of the first label based on the first label location of the first label. In some implementations, the means for determining the first bounding box of the first label corresponds to the map generator104ofFIG.1, the bounding box generator216, the one or more processors290, the device202, the system200ofFIG.2, the computing device910, one or more other circuits or devices configured to determine the first bounding box of the first label, or a combination thereof.

The apparatus also includes means for determining a first bounding box of the second label based on the first label location of the second label. In some implementations, the means for determining the first bounding box of the second label corresponds to the map generator104ofFIG.1, the bounding box generator216, the one or more processors290, the device202, the system200ofFIG.2, the computing device910, one or more other circuits or devices configured to determine the first bounding box of the second label, or a combination thereof.

The apparatus further includes means for determining whether the first bounding box of the first label overlaps the first bounding box of the second label. In some implementations, the means for determining whether the first bounding box of the first label overlaps the first bounding box of the second label corresponds to the map generator104ofFIG.1, the conflict analyzer218, the one or more processors290, the device202, the system200ofFIG.2, the conflict detector612ofFIG.6A, the computing device910, one or more other circuits or devices configured to determine whether the first bounding box of the first label overlaps the first bounding box of the second label, or a combination thereof.

The apparatus also includes means for determining a first candidate label location of the first label and a first candidate label location of the second label based on an intersection of the first bounding box of the first label and the first bounding box of the second label, the first candidate label location and the second candidate label location determined based on determining that the first bounding box of the first label overlaps the first bounding box of the second label. In some implementations, the means for determining the first candidate label location of the first label and the first candidate label location of the second label corresponds to the map generator104ofFIG.1, the conflict analyzer218, the one or more processors290, the device202, the system200ofFIG.2, the deconflictor614ofFIG.6A, the computing device910, one or more other circuits or devices configured to determine the first candidate label location of the first label and the first candidate label location of the second label, or a combination thereof.

The apparatus further includes means for generating a map including the first label at the first candidate label location of the first label and the second label at the first candidate label location of the second label, the map generated based on determining that the first candidate label location of the first label satisfies a first selection criterion and that the first candidate label location of the second label satisfies a second selection criterion. In some implementations, the means for generating the map corresponds to the map generator104ofFIG.1, the conflict analyzer218, the one or more processors290, the device202, the system200ofFIG.2, the selection criterion analyzer616ofFIG.6A, the computing device910, one or more other circuits or devices configured to generate the map, or a combination thereof.

In some implementations, a non-transitory, computer readable medium stores instructions that, when executed by one or more processors, cause the one or more processors to initiate, perform, or control operations to perform part or all of the functionality described above. For example, the instructions may be executable to implement one or more of the operations or methods ofFIGS.1-8. In some implementations, part or all of one or more of the operations or methods ofFIGS.1-8may be implemented by one or more processors (e.g., one or more central processing units (CPUs), one or more graphics processing units (GPUs), one or more digital signal processors (DSPs)) executing instructions, by dedicated hardware circuitry, or any combination thereof.

Particular aspects of the disclosure are described below in sets of interrelated Examples:

According to Example 1, a device includes: one or more processors configured to: determine a first label location of a first label that identifies a first map location; determine a first label location of a second label that identifies a second map location; determine, based on the first label location of the first label, a first bounding box of the first label; determine, based on the first label location of the second label, a first bounding box of the second label; determine whether the first bounding box of the first label overlaps the first bounding box of the second label; based on determining that the first bounding box of the first label overlaps the first bounding box of the second label, determine a first candidate label location of the first label and a first candidate label location of the second label based on an intersection of the first bounding box of the first label and the first bounding box of the second label; and based on determining that the first candidate label location of the first label satisfies a first selection criterion and that the first candidate label location of the second label satisfies a second selection criterion, generate a map including the first label at the first candidate label location of the first label and the second label at the first candidate label location of the second label.

Example 2 includes the device of Example 1, wherein the one or more processors are configured to: determine a movement offset based on dimensions of the intersection; determine the first candidate label location of the first label based on the first label location of the first label and the movement offset; and determine the first candidate label location of the second label based on the first label location of the second label and the movement offset.

Example 3 includes the device of Example 1 or Example 2, wherein the one or more processors are configured to apply a first portion of a movement offset to the first label location of the first label to determine the first candidate label location of the first label, the movement offset based on dimensions of the intersection.

Example 4 includes the device of Example 3, wherein the first portion is based at least in part on a first label type of the first label.

Example 5 includes the device of Example 4, wherein the first label type includes a navigation aid (navaid) label type, a way point label type, a route label type, an airport label type, an airway label type, or an airspace label type.

Example 6 includes the device of any of Example 1 to Example 5, wherein the one or more processors are configured to: determine, based on the first candidate label location of the first label, a first candidate bounding box of the first label; and based at least in part on determining that the first candidate bounding box of the first label is within a threshold distance of the first map location, determine that the first candidate label location of the first label satisfies the first selection criterion.

Example 7 includes the device of Example 6, wherein the threshold distance is based on a zoom level of the map.

Example 8 includes the device of Example 6, wherein the one or more processors are configured to, based on determining that the first candidate bounding box of the first label exceeds the threshold distance of the first map location, determine a second candidate label location of the first label and a second candidate label location of the second label based on the first candidate bounding box of the first label and the first candidate bounding box of the second label.

Example 9 includes the device of Example 8, wherein the one or more processors are configured to, based on determining that the second candidate label location of the first label satisfies the first selection criterion and the second candidate label location of the second label satisfies the second selection criterion, generate the map including the first label at the second candidate label location of the first label and the second label at the second candidate label location of the second label.

Example 10 includes the device of Example 9, wherein the one or more processors are configured to: determine, based on the second candidate label location of the first label, a second candidate bounding box of the first label; and based at least in part on determining that the second candidate bounding box of the first label is within a threshold distance of the first map location, determine that the second candidate label location of the first label satisfies the first selection criterion.

Example 11 includes the device of Example 6, wherein the one or more processors are configured to, based on determining that the first candidate bounding box of the first label is within the threshold distance of the first map location and that the first candidate bounding box of the first label overlaps a first candidate bounding box of a third label that identifies a third map location, determine a second candidate label location of the first label and a second candidate label location of the third label based on the first candidate bounding box of the first label and the first candidate bounding box of the third label.

Example 12 includes the device of Example 11, wherein the one or more processors are configured to, based on determining that the second candidate label location of the first label satisfies the first selection criterion, that the first candidate label location of the second label satisfies the second selection criterion, and that the second candidate label location of the third label satisfies a third selection criterion, generate the map including the first label at the second candidate label location of the first label, the second label at the first candidate label location of the second label, and the third label at the second candidate label location of the third label.

Example 13 includes the device of Example 12, wherein the one or more processors are configured to: determine, based on the second candidate label location of the third label, a second candidate bounding box of the third label; and based at least in part on determining that the second candidate bounding box of the third label is within a threshold distance of the third map location, determine that the second candidate label location of the third label satisfies the third selection criterion.

Example 14 includes the device of any of Example 1 to Example 13, wherein the one or more processors are configured to: determine, based on the first candidate label location of the first label, a first candidate bounding box of the first label; and based at least in part on determining that the first candidate bounding box of the first label does not overlap any other bounding boxes of other labels, determine that the first candidate label location of the first label satisfies the first selection criterion.

Example 15 includes the device of any of Example 1 to Example 14, wherein the one or more processors are configured to: determine that a plurality of label types is associated with a zoom level of the map; select a first set of labels from a plurality of labels, each label of the first set of labels having a label type that is included in the plurality of label types, wherein the first set of labels includes the first label and the second label; and generate the map including the first set of labels.

Example 16 includes the device of any of Example 1 to Example 15, wherein the first bounding box of the first label is based on a font size of the first label, text of the first label, a zoom level of the map, or a combination thereof.

Example 17 includes the device of any of Example 1 to Example 16, wherein the first label location of the first label is based on default data.

Example 18 includes the device of any of Example 1 to Example 17, wherein the one or more processors are configured to determine the first label location based on a label offset and the first map location, wherein the label offset includes a distance offset, a direction offset, or both.

According to Example 19, a method includes: determining, at a device, a first label location of a first label that identifies a first map location; determining, at the device, a first label location of a second label that identifies a second map location; determining, based on the first label location of the first label, a first bounding box of the first label; determining, based on the first label location of the second label, a first bounding box of the second label; determining, at the device, whether the first bounding box of the first label overlaps the first bounding box of the second label; based on determining that the first bounding box of the first label overlaps the first bounding box of the second label, determining a first candidate label location of the first label and a first candidate label location of the second label based on an intersection of the first bounding box of the first label and the first bounding box of the second label; and based on determining that the first candidate label location of the first label satisfies a first selection criterion and that the first candidate label location of the second label satisfies a second selection criterion, generating a map including the first label at the first candidate label location of the first label and the second label at the first candidate label location of the second label.

Example 20 includes the method of Example 19, further including: determining a movement offset based on dimensions of the intersection; determining the first candidate label location of the first label based on the first label location of the first label and the movement offset; and determining the first candidate label location of the second label based on the first label location of the second label and the movement offset.

Example 21 includes the method of Example 19 or Example 20, further including applying a first portion of a movement offset to the first label location of the first label to determine the first candidate label location of the first label, the movement offset based on dimensions of the intersection.

Example 22 includes the method of Example 21, wherein the first portion is based at least in part on a first label type of the first label.

Example 23 includes the method of Example 22, wherein the first label type includes a navigation aid (navaid) label type, a way point label type, a route label type, an airport label type, an airway label type, or an airspace label type.

Example 24 includes the method of any of Example 19 to Example 23, further including: determining, based on the first candidate label location of the first label, a first candidate bounding box of the first label; and based at least in part on determining that the first candidate bounding box of the first label is within a threshold distance of the first map location, determining that the first candidate label location of the first label satisfies the first selection criterion.

Example 25 includes the method of Example 24, wherein the threshold distance is based on a zoom level of the map.

Example 26 includes the method of Example 24, further including, based on determining that the first candidate bounding box of the first label exceeds the threshold distance of the first map location, determining a second candidate label location of the first label and a second candidate label location of the second label based on the first candidate bounding box of the first label and the first candidate bounding box of the second label.

Example 27 includes the method of Example 26, further including, based on determining that the second candidate label location of the first label satisfies the first selection criterion and the second candidate label location of the second label satisfies the second selection criterion, generating the map including the first label at the second candidate label location of the first label and the second label at the second candidate label location of the second label.

Example 28 includes the method of Example 27, further including: determining, based on the second candidate label location of the first label, a second candidate bounding box of the first label; and based at least in part on determining that the second candidate bounding box of the first label is within a threshold distance of the first map location, determining that the second candidate label location of the first label satisfies the first selection criterion.

Example 29 includes the method of Example 24, further including, based on determining that the first candidate bounding box of the first label is within the threshold distance of the first map location and that the first candidate bounding box of the first label overlaps a first candidate bounding box of a third label that identifies a third map location, determining a second candidate label location of the first label and a second candidate label location of the third label based on the first candidate bounding box of the first label and the first candidate bounding box of the third label.

Example 30 includes the method of Example 29, further including, based on determining that the second candidate label location of the first label satisfies the first selection criterion, that the first candidate label location of the second label satisfies the second selection criterion, and that the second candidate label location of the third label satisfies a third selection criterion, generating the map including the first label at the second candidate label location of the first label, the second label at the first candidate label location of the second label, and the third label at the second candidate label location of the third label.

Example 31 includes the method of Example 30, further including: determining, based on the second candidate label location of the third label, a second candidate bounding box of the third label; and based at least in part on determining that the second candidate bounding box of the third label is within a threshold distance of the third map location, determining that the second candidate label location of the third label satisfies the third selection criterion.

Example 32 includes the method of any of Example 19 to Example 31, further including: determining, based on the first candidate label location of the first label, a first candidate bounding box of the first label; and based at least in part on determining that the first candidate bounding box of the first label does not overlap any other bounding boxes of other labels, determining that the first candidate label location of the first label satisfies the first selection criterion.

Example 33 includes the method of any of Example 19 to Example 32, further including: determining that a plurality of label types is associated with a zoom level of the map; select a first set of labels from a plurality of labels, each label of the first set of labels having a label type that is included in the plurality of label types, wherein the first set of labels includes the first label and the second label; and generating the map including the first set of labels.

Example 34 includes the method of any of Example 19 to Example 33, wherein the first bounding box of the first label is based on a font size of the first label, text of the first label, a zoom level of the map, or a combination thereof.

Example 35 includes the method of any of Example 19 to Example 34, wherein the first label location of the first label is based on default data.

Example 36 includes the method of any of Example 19 to Example 35, further including determining, at the device, the first label location based on a label offset and the first map location, wherein the label offset includes a distance offset, a direction offset, or both.

According to Example 37, a device includes: a memory configured to store instructions; and a processor configured to execute the instructions to perform the method of any of Example 19 to 36.

According to Example 38, a non-transitory computer-readable medium stores instructions that, when executed by a processor, cause the processor to perform the method of any of Example 19 to Example 36.

According to Example 39, an apparatus includes means for carrying out the method of any of Example 19 to Example 36.

According to Example 40, a non-transitory computer-readable medium stores instructions that, when executed by one or more processors, cause the one or more processors to: determine a first label location of a first label that identifies a first map location; determine a first label location of a second label that identifies a second map location; determine, based on the first label location of the first label, a first bounding box of the first label; determine, based on the first label location of the second label, a first bounding box of the second label; determine whether the first bounding box of the first label overlaps the first bounding box of the second label; based on determining that the first bounding box of the first label overlaps the first bounding box of the second label, determine a first candidate label location of the first label and a first candidate label location of the second label based on an intersection of the first bounding box of the first label and the first bounding box of the second label; and based on determining that the first candidate label location of the first label satisfies a first selection criterion and that the first candidate label location of the second label satisfies a second selection criterion, generate a map including the first label at the first candidate label location of the first label and the second label at the first candidate label location of the second label.

The illustrations of the examples described herein are intended to provide a general understanding of the structure of the various implementations. The illustrations are not intended to serve as a complete description of all of the elements and features of apparatus and systems that utilize the structures or methods described herein. Many other implementations may be apparent to those of skill in the art upon reviewing the disclosure. Other implementations may be utilized and derived from the disclosure, such that structural and logical substitutions and changes may be made without departing from the scope of the disclosure. For example, method operations may be performed in a different order than shown in the figures or one or more method operations may be omitted. Accordingly, the disclosure and the figures are to be regarded as illustrative rather than restrictive.

Moreover, although specific examples have been illustrated and described herein, it should be appreciated that any subsequent arrangement designed to achieve the same or similar results may be substituted for the specific implementations shown. This disclosure is intended to cover any and all subsequent adaptations or variations of various implementations. Combinations of the above implementations, and other implementations not specifically described herein, will be apparent to those of skill in the art upon reviewing the description.

The Abstract of the Disclosure is submitted with the understanding that it will not be used to interpret or limit the scope or meaning of the claims. In addition, in the foregoing Detailed Description, various features may be grouped together or described in a single implementation for the purpose of streamlining the disclosure. Examples described above illustrate but do not limit the disclosure. It should also be understood that numerous modifications and variations are possible in accordance with the principles of the present disclosure. As the following claims reflect, the claimed subject matter may be directed to less than all of the features of any of the disclosed examples. Accordingly, the scope of the disclosure is defined by the following claims and their equivalents.