System and method for abstracting and visualizing a route map

Claim 2

A computer implemented method, executed by a computing device for positioning a plurality of labels in a route map, the computer implemented method comprising, for each label in said plurality of labels: associating by the computing device, a plurality of constraint definitions with said label, each constraint definition in said plurality of constraint definitions uniquely defining a bounding box, label orientation, and layout style, and wherein said plurality of constraint definitions constitute a continuous range of positions, and wherein a center of said label within each unique bounding box is located at a different point for each of the constraint definitions in the continuous range of positions, and wherein the plurality of constraint definitions are not limited by placement on the map to relation to a road; selecting, by the computing device, an initial constraint definition from said plurality of constraint definitions; positioning, by the computing device, the center of said label at a location within the bounding box defined by said initial constraint definition in accordance with the label orientation and layout style defined by said initial constraint definition; the computer implemented method further comprising: choosing, by the computing device, a label in said plurality of labels; determining, by the computing device, a first score (S 1 ) using a target function, wherein the score is determined by a position of said chosen label in said route map; applying, by the computing device, a different constraint definition from the plurality of constraint definitions associated with said selected label, said applying step including the step of repositioning a center of said label inside the bounding box defined by said different constraint definition in accordance with the label orientation and layout style defined by said different constraint definition; calculating, by the computing device, a second score (S 2 ) using said target function, wherein the score is determined by the repositioned label position; accepting, by the computing device, the new position for said label in accordance with a function that is determined by a comparison of S 1 and S 2 ; repeating, by the computing device, said choosing, determining, applying, calculating, and accepting steps until a first occurrence of an exit condition.

Claim 3

The computer implemented method of claim 1 wherein said function comprises accepting the repositioned label position: (1) when S 2 is less than S 1; (2) with a probability P(ΔS), when S 2 is greater than S 1 , where P(ΔS) is a probability function that is dependent upon an effective temperature t that is reduced by an amount after each execution of said repeating step.

Claim 4

The computer implemented method of claim 2 where: P (Δ S )=exp −[(ΔS)/(k*t)] ΔS =( S 1 )−( S 2 ), and k is a constant.

Claim 5

The computer implemented method of claim 1 , wherein said positioning step further comprises fixing a label in said plurality of labels in said route map when said label does not intersect with any other label in said route map; and said choosing step does not choose a label that has been fixed.

Claim 6

The computer implemented method of claim 1 , wherein each constraint definition in said plurality of constraint definitions includes a scoring strategy that is used by said target function in said determining and calculating steps.

Claim 7

The computer implemented method of claim 1 , wherein each said layout style is selected from the group consisting of a simple layout style, a combination of an arrow image with the primary name for one of a street and a highway, a combination of a primary name for one of a street and a highway with a mileage along the road, a highway number as text stacked on top of a shielding image, a word-wrapped name, and a highway number stacked on top of a shield image with a mileage along a corresponding road.

Claim 8

A computer storage medium containing computer executable instructions that when executed by a computing device provide: a label placement module for positioning a plurality of labels in a route map, the label placement module comprising, for each label in said plurality of labels: instructions for associating a plurality of constraint definitions with said label, each constraint definition in said plurality of constraint definitions uniquely defining a bounding box, label orientation, and layout style, wherein said plurality of constraint definition constitute a continuous range of positions, wherein a center of said label within each unique bounding box is located at a different point for each of the constraint definitions in the continuous range of positions, and wherein the plurality of constraint definitions are not limited by placement on the map in relation to a road; instructions for selecting an initial constraint definition from said plurality of constraint definitions; instructions for positioning a center of said label at a location within the bounding box defined by said initial constraint definition in accordance with the label orientation and layout style defined by said initial constraint definition; the module further including: instructions for choosing a label in said plurality of labels; instructions for determining a first score (S 1 ) using a target function, wherein the score is determined by a position of said chosen label in said route map; instructions for applying a different constraint definition, from the plurality of constraint definitions associated with said selected label, said instructions for applying including instructions for repositioning a center of said label inside the bounding box defined by said different constraint definition in accordance with the label orientation and layout style defined by said different constraint definition; instructions for calculating a second score (S 2 ) using said target function, wherein the score is determined by the repositioned label position; instructions for accepting the new position for said label in accordance with a function that is determined by a comparison of S 1 and S 2 ; and instructions for repeating said instructions for choosing, determining, applying, calculating, and accepting until a first occurrence of an exit condition.

Claim 9

A computer storage medium containing computer executable instructions that when executed by a computing device provide: a label placement module for positioning a plurality of labels in a route map, the label placement module comprising, for each label in said plurality of labels: instructions for associating a plurality of constraint definitions with said label, each constraint definition in said plurality of constraint definitions uniquely defining a bounding box, label orientation, and layout style, wherein said plurality of constraint definition constitute a continuous range of positions, wherein a center of said label within each unique bounding box is located at a different point for each of the constraint definitions in the continuous range of positions, and wherein the plurality of constraint definitions are not limited by placement on the map in relation to a road; instructions for selecting an initial constraint definition from said plurality of constraint definitions; instructions for positioning a center of said label at a location within the bounding box defined by said initial constraint definition in accordance with the label orientation and layout style defined by said initial constraint definition; the module further including: instructions for choosing a label in said plurality of labels; instructions for determining a first score (S 1 ) using a target function, wherein the score is determined by a position of said chosen label in said route map; instructions for applying a different constraint definition, from the plurality of constraint definitions associated with said selected label, said instructions for applying including instructions for repositioning a center of said label inside the bounding box defined by said different constraint definition in accordance with the label orientation and layout style defined by said different constraint definition; instructions for calculating a second score (S 2 ) using said target function, wherein the score is determined by the repositioned label position; instructions for accepting the new position for said label in accordance with a function that is determined by a comparison of S 1 and S 2 ; and instructions for repeating said instructions for choosing, determining, applying, calculating, and accepting until a first occurrence of an exit condition.

Claim 10

The computer storage medium of claim 7 wherein said function comprises instructions for accepting the repositioned label position: (1) when S 2 is less than S 1 ; and (2) with the probability P(ΔS), when S 2 is greater than S 1 , where P(ΔS) is a probability function that is dependent upon an effective temperature t that is reduced by an amount after each execution of said repeating step.

Claim 11

The computer storage medium of claim 8 where: P (Δ S )=exp −[(ΔS)/(k*t)] ΔS =( S 1 )−( S 2 ), and k is a constant.

Claim 12

The computer storage medium of claim 7 , wherein said instructions for positioning further comprises instructions fixing a label in said plurality of labels in said route map when said label does not intersect with any other label in said route map; and said choosing step does not choose a label that has been fixed.

Claim 13

The computer storage medium of claim 7 , wherein each constraint definition in said plurality of constraint definitions includes a scoring strategy that is used by said target function coded by said instructions for determining and calculating steps.

Claim 14

The computer storage medium of claim 7 , wherein each said layout style is selected from the group consisting of a simple layout style, a combination of an arrow image with the primary name for one of a street and a highway, a combination of a primary name for one of a street and a highway with a mileage along the road, a highway number as text stacked on top of shielding image, a word-wrapped name, and a highway number stacked on top of a shield image with a mileage along a corresponding road.

Claim 15

A computer system for positioning a plurality of labels in a route map, the computer system comprising: a central processing unit; a memory, coupled to said central processing unit; a viewport for displaying said route map; a program module, executable by said central processing unit, said program module comprising: a label refinement module for refining the plurality of labels in a route map, the label refinement module comprising, for each label in said plurality of labels: instructions for associating a plurality of constraint definitions with said label, each constraint definition in said plurality of constraint definitions uniquely defining a bounding box, label orientation, and layout style, and wherein said plurality of constraint definitions constitute a continuous range of positions, wherein a center of said label within each unique bounding box is located at a different point for each of the constraint definitions in the continuous range of positions, and wherein the plurality of constraint definitions are not limited by placement on the map in relation to a road; instructions for selecting an initial constraint definition from said plurality of constraint definitions; instructions for positioning the center of said label at a location within the bounding box defined by said initial constraint definition in accordance with the label orientation and layout style defined by said initial constraint definition; the label refinement module further including: instructions for choosing a label in said plurality of labels; instructions for determining a first score (S 1 ) using a target function, wherein the score is determined by a position of said chosen label in said route map; instructions for applying a different constraint definition, from the plurality of constraint definitions associated with said selected label, said instructions for applying including instructions for repositioning a center of said label inside the bounding box defined by said different constraint definition in accordance with the label orientation and layout style defined by said different constraint definition; instructions for calculating a second score (S 2 ) using said target function; wherein the score is determined by the repositioned label position; instructions for accepting the new position for said label in accordance with a function that is determined by a comparison of S 1 and S 2 ; and instructions for repeating said instructions for choosing, determining, applying, calculating, and accepting until a first occurrence of an exit condition.

Claim 16

A computer system for positioning a plurality of labels in a route map, the computer system comprising: a central processing unit; a memory, coupled to said central processing unit; a viewport for displaying said route map; a program module, executable by said central processing unit, said program module comprising: a label refinement module for refining the plurality of labels in a route map, the label refinement module comprising, for each label in said plurality of labels: instructions for associating a plurality of constraint definitions with said label, each constraint definition in said plurality of constraint definitions uniquely defining a bounding box, label orientation, and layout style, and wherein said plurality of constraint definitions constitute a continuous range of positions, wherein a center of said label within each unique bounding box is located at a different point for each of the constraint definitions in the continuous range of positions, and wherein the plurality of constraint definitions are not limited by placement on the map in relation to a road; instructions for selecting an initial constraint definition from said plurality of constraint definitions; instructions for positioning the center of said label at a location within the bounding box defined by said initial constraint definition in accordance with the label orientation and layout style defined by said initial constraint definition; the label refinement module further including: instructions for choosing a label in said plurality of labels; instructions for determining a first score (S 1 ) using a target function, wherein the score is determined by a position of said chosen label in said route map; instructions for applying a different constraint definition, from the plurality of constraint definitions associated with said selected label, said instructions for applying including instructions for repositioning a center of said label inside the bounding box defined by said different constraint definition in accordance with the label orientation and layout style defined by said different constraint definition; instructions for calculating a second score (S 2 ) using said target function; wherein the score is determined by the repositioned label position; instructions for accepting the new position for said label in accordance with a function that is determined by a comparison of S 1 and S 2 ; and instructions for repeating said instructions for choosing, determining, applying, calculating, and accepting until a first occurrence of an exit condition.

Claim 17

The computer system of claim 13 wherein said function comprises instructions for accepting the repositioned label position: (1) when S 2 is less than S 1 ; and (2) with the probability P(ΔS), when S 2 is greater than S 1 , where P(ΔS) is a probability function that is dependent upon an effective temperature t that is reduced by an amount after each execution of said repeating step.

Claim 18

The computer system of claim 14 where: P (Δ S )=exp −[(ΔS)—/(k*t)] ΔS =( S 1 )−( S 2 ), and k is a constant.

Claim 19

The computer system of claim 13 , wherein said instructions for positioning further comprises instructions fixing a label in said plurality of labels in said route map when said label does not intersect with any other label in said route map; and said instructions for choosing includes instructions for not choosing a label that has been fixed.

Claim 20

The computer system of claim 13 , wherein each constraint definition in said plurality of constraint definitions includes a scoring strategy that is used by said target function function coded by said instructions for determining and calculating.

Claim 21

The computer system of claim 13 , wherein each said layout style is selected from the group consisting of a simple layout style, a combination of an arrow image with the primary name for one of a street and a highway, a combination of a primary name for one of a street and a highway with a mileage along the road, a highway number as text stacked on top of a shielding image, a word-wrapped name, and a highway number stacked on top of a shield image with a mileage along a corresponding road.

Claim 22

The method of claim 1 , further comprising extending the road when a length of the label exceeds the length of the road, wherein the road is extended by an amount equal to the length at which the length of the label exceeds the length of the road.

Claim 23

The method of claim 1 , wherein the score determined by the target function includes a determination of at least one of: a number of roads each label intersects, a number of labels each label intersects, a distance the label is from a center of the road associated with the label, whether the label is above the road, and whether the label is below the road.