Determining means, terminal device, system and method for point label placement on a map

• US 6,940,530 B2
• Filed: 05/20/2003
• Issued: 09/06/2005
• Est. Priority Date: 05/21/2002
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Chen, Ying, Yu, Xiu Lan, Rao, Fang Yan
• Primary Examiner(s): Lefkowitz, Sumati
• Assistant Examiner(s): HARRISON, CHANTE E
• Application Number:
  US10/442,022
• Publication Number:
  US 20040032417A1
• Time in Patent Office: 840 Days
• Field of Search: 345/440, 345/629, 345/619, 345/660, 345/672, 345/665, 345/636, 345/680, 715/517, 703/2, 701/212
• US Class Current: 345/660
• CPC Class Codes: G01C 21/3673 Labelling using text of road map data items, e.g. road names, POI names
• CPC Class Codes: G06T 17/05 Geographic models
• CPC Class Codes: G06T 19/00 Manipulating 3D models or images for computer graphics
• CPC Class Codes: G06T 2219/004 Annotating, labelling
• CPC Class Codes: G09B 29/106 using electronic means

Abstract

Provides point label placement determining methods, apparatus and systems. A point label placement determining method and system are used in map browsing service based on session mode. In an example embodiment, initial label placement data in a scale is calculated by a static point label determining method. When a user requires a map browsing service, the requirement are met by using an incremental label placement method on the base of said initial label placement data. The incremental point label placement method dramatically reduces the cost for service process. Therefore, the simultaneous requirements of a large number of users can be met. The present invention is successfully used in location based service systems.

Claims

1. A method for determining point label placement in a network system wherein a terminal unit requests a point label placement determining device to provide a map display service in a specific display scale via a communication link, and the point label placement determining device sends map information on the specific display scale to the terminal unit for displaying a map, the method comprising:

determining and saving at least one set of static point label placement results in at least one predetermined scale;

responding to an application by the terminal unit for the display service displaying points and labels on the map, and comparing the specific display scale with at least one predetermined scale;

if the display scale of the terminal unit is identical to a predetermined scale, sending the at least one static point label placement at this predetermined scale to the terminal unit;

if the specific display scale of the terminal unit is different from the at least one predetermined scales of the saved static point label placement, the point label placement determining a device determining new point label placement in the specific display scale of the terminal unit by an incremental point label placement method according to the saved static point label placement results, and sending the determined new point label placement to the terminal unit, wherein;

if the display scale of the terminal unit is different from any predetermined scales of the static point label placements saved in the point label placement determining device, further comprising selecting a maximal predetermined scale in the scales that is smaller than the display scale of the terminal unit, and determining the label placement based on the results of the predetermined point label placement corresponding to the selected predetermined scale by the incremental label placement method;

if the display scale of the terminal unit is smaller than all the predetermined scales saved in the point label placement determining device, further comprising determining the label placement displayed on the terminal unit based on the results of predetermined point label placement corresponding to a smallest predetermined scale.

2. The method of claim 1, wherein each point on the map has a plurality of candidate label positions, the static point label placement determining step comprising:

step 1;

checking whether any candidate label position of each point is beyond a label area, if there is a candidate label position that is beyond the label area, then this candidate label position is deleted from the results set;

step 2;

checking whether there are other points that are within the remaining candidate label positions of a point, if there are any other points, then this candidate label position is deleted from the results set; and

wherein when calculating a conflict between the candidate label positions of any points in step 2, only the conflict between the candidate label position of a particular point and the candidate label position of other points located in a neighborhood region of the particular point is calculated;

the neighborhood region is a rectangle area with 4 times a maximal length and a maximal width of all labels on the map as its sides, and with the particular point as the center of the region.

3. The method of claim 1, wherein said map is a map taken from a group of maps consisting of:

a geographical map, a circuit diagram and a mechanical drawing, and

wherein said label is taken from a group of labels consisting of;

a label in a geographical map, a label in a circuit diagram and a label in a mechanical drawing.

4. The method of claim 1, further comprising:

a. if said display scale of the terminal unit is larger than said predetermined scale, then processing according to the following three conditions;

a1) if a label position of a particular point is within a sub-region displayed on the terminal unit, adding the particular point into a point set that can be labeled;

a2) if a label position of a the particular point is beyond the sub-region displayed on the terminal unit, replacing this label position with other candidate label positions of the said particular point according to a predetermined priority;

if a candidate label position is within the sub-region displayed on the terminal unit, there is no other point within the candidate label position, and it has no effect on the label position of it'"'"'s neighborhood points, then adding said particular point to the point set which can be labeled;

otherwise add said particular point to the point set which can not be labeled;

a3) using the step in a2) to determine the label position for the point which cannot be labeled in the predetermined scale; and

b. if said display scale of the terminal unit is less than all said predetermined scale, then determining the label position of points by a static point label placement determining step.

10. An article of manufacture comprising a computer usable medium having computer readable program code means embodied therein for causing determination of point label placement, the computer readable program code means in said article of manufacture comprising computer readable program code means for causing a computer to effect the steps of claim 1.

11. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for determining point label placement, said method steps comprising the steps of claim 1.

5. A system for determining label placement of points on a map, comprising:

a point label placement determining device;

a terminal unit;

a communication link between the point label placement determining device and the terminal unit;

storage means for storing the data of static point label placement on the whole map on one or more predetermined scales;

comparing means for comparing a display scale of the terminal unit with said predetermined scales;

selecting means for selecting an appropriate predetermined scale as the base for determining incremental label placements; and

incremental label placement determining means for determining the point label placement on the display scale that is different from said predetermined scales, wherein if said comparing means determines that said display scale is identical with one of the predetermined scales, said selecting means selects said one of the predetermined scales;

if said display scale is different from any of the predetermined scales, and there are predetermined scales which are smaller than said display scale, said selecting means selecting the maximal predetermined scale from the predetermined scales that are smaller than said display scale;

otherwise, said selecting means selects the smallest predetermined scale.

6. The system of claim 5, wherein said terminal unit comprising:

a communication port for exchanging data with said point label placement determining device;

storage means for storing label position data from said point label placement determining device;

a controller for transmitting the display scale to said point label determining device, requiring said point label determining device to determine the label positions for displaying, and controlling the display according to the label positions from said point label determining device; and

a display means for displaying points and their labels in the scale designated by said terminal unit according to the label position data stored in the storage means.

7. The system of claim 5, wherein said incremental label placement determining device includes a judging means, which makes a judgment according to the following conditions:

a. if said predetermined scale selected by said selecting means is less than said display scale of the terminal unit, then processing according to the following three conditions;

a1) if a label position of a point is within a sub-region displayed on the terminal unit, adding the point into 9 point set that can be labeled;

a2) if a label position of a point is beyond the sub-region displayed on the terminal unit, replace this label position with other candidate label positions of the same point according to a predetermined priority;

if a candidate label position is within the sub-region displayed on the terminal unit, there is no any other point within the candidate label position, and it has no effect on the label position of it'"'"'s neighborhood points, then adding this point to the point set which can be labeled;

otherwise add this point to the point set which can not be labeled;

a3) using the step in a2) to determine the label position for the point that cannot be labeled in the predetermined scale; and

b. if said display scale of the terminal unit less than all said predetermined scales, then determining the label position of points by a static point label placement determining method.

12. A computer program product comprising a computer usable medium having computer readable program code means embodied therein for causing determination of point label placement, the computer readable program code means in said computer program product comprising computer readable program code means for causing a computer to effect the functions of claim 5.

8. A point label placement determining device, comprising:

storage means for storing data of static point label placement on a whole map in at least one predetermined scale;

comparing means for comparing a display scale from a terminal unit with said at least one predetermined scale in response to a service request from the terminal unit;

selecting means for selecting an appropriate predetermined scale as a base for determining an incremental point label placement;

incremental label placement determining means for determining the point label placement in a display scale that is different from said at least one predetermined scale, wherein if said comparing means determines that said display scale is identical with one of the at least one predetermined scale, said selecting means selects said one of the at least one predetermined scale;

if said display scale is different from said at least one predetermined scale, and there are predetermined scales which are smaller than said display scale, said selecting means selects a maximal predetermined scale from said at least one predetermined scale being smaller than said display scale;

otherwise, said selecting means selects a smallest predetermined scale.

9. The point label placement determining device of claim 8, wherein said incremental paint label placement determining device includes a judging means for making a judgment according to the following conditions:

a. if said at least one predetermined scale selected by said selecting means is less than said display scale, then processing according to the following three conditions;

a1) if a label position of a point is within a sub-region displayed on the terminal unit, adding the point into a point set that can be labeled;

a2) if a label position of a point is beyond the sub-region displayed on the terminal unit, replace this label position with other candidate label positions of the same point according to a predetermined priority if a candidate label position is within the sub-region displayed on the terminal unit, there is no any other point within the candidate label position, and it has no effect on the label position of its neighborhood points, then adding this point to the point set which can be labeled;

otherwise adding this point to the point set which can not be labeled;

a3) using the step in a2) to determine the label position for the point that cannot be labeled in the predetermined scale;

b. if said determining display scale of the terminal unit is smaller than all predetermined scales, then determining the label position of points employing a static point label placement determining method.

13. A computer program product comprising a computer usable medium having computer readable program code means embodied therein for causing label placement, the computer readable program code means in said computer program product comprising computer readable program code means for causing a computer to effect the functions of claim 8.