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.

Description:
FIELD OF THE INVENTION 
   The present invention relates to a system and method for point label placement on maps. Specifically, a determining means, terminal device, system and method for point label placement on maps of web geographical information systems. 
   BACKGROUND OF THE INVENTION 
   Point labeling on maps is a traditional research topic. It&#39;s a classical problem to label points on maps in cartology and a key problem in geography information system. What is the so-called point labeling on maps? Try to put the corresponding names of cities on their right positions on a map of China, this process is called labeling.  FIG. 1  shows a map of some region near Beijing(           )  10 , all the points on said map are labeled. However, the labeling results of the map is not an optimized solution. For example, the “         ”  20 , on the up left corner, as well as the “         ”  30  on the down right corner, should not be labeled since the points are not on the map and these two labels are meaningless; the label “         ”  40  lies near two points, and it is easy to lead to misunderstandings.
   Generally speaking, labeling is used to help users understand the meaning of the corresponding point easily, thereby the label is generally very close to the point. And there are always many positions applicable. For example, there are four applicable positions called candidate label positions in FIG.  2  and  FIG. 3  respectively. Obviously, there are many other candidate label positions too, such as the combination of candidate label positions in FIG.  2  and  FIG. 3 , or arbitrary slides and rotations of candidate label positions near the point, and so on. 
   After the candidate label set of points is determined, choices of different label positions should coincide with certain viewpoints of aesthetics. For example, in  FIG. 2 , the visual comfort index decreases in the sequence of position  1 ,  2 ,  3  and  4 . Therefore, if possible, the position with high visual comfort index should be chosen, which means different candidate positions have different priorities when labeling points on maps. This is possible by referring to the cases showed in FIGS.  4  and  5 : if P 1 , a candidate label position of point P have some other points (FIG.  4 ), or the position has been determined by other points as a label position (FIG.  5 ), labeling point P on the position of P 1  definitely leads to misunderstanding when displaying. Therefore, when evaluating a method for determining point label position on maps, the criterion should include labeling as many points as possible without overlap and meeting the requirements of aesthetics as well. 
   When browsing a map on computer, the point label is usually needed for helping understanding contents of the map. For example, there are coordinates (e.g. longitudes and latitudes) and contents of map points (that is, their labels) stored in geographical information systems. When displaying the map in a computer, the position and the rectangle size (that the widths and the lengths of the rectangles in  FIG. 2  to  FIG. 5 ) of the point label can be determined according to contents of map points, the display scale and the size of monitor users defined in advance. After the label positions of each point according to rules of point labeling, the points and the contents thereof on the map can be well displayed on the computer screen. 
     FIG. 6  shows a simplified model of WebGIS map browsing service of the present invention. In  FIG. 6 , browser A sends a request to WebGIS server B for browsing a map. After receiving the request, the WebGIS server B sends pertinent map data back to browser A. 
   When browsing the map through the network, taking the web geographical information system (WebGIS) as an example, the server in WebGIS is usually a computer with large storage capacity and excellent computing ability. Therefore, the geographical information is always stored in the server. Clients can be simple computers, mobile telephones, or PDAs and so on. The working pattern is as follows. A client requests for service from a server first, for example, displaying all the book stores near Tsinghua University with display scale S on the monitor whose width is W, and height, H. Then the server responses to request of the client by sending back the point positions, the point label positions and label contents after determining the position of points and points&#39; labels according to the data supplied by the client on the client screen. Thereby all the bookstores near Tsinghua University will be displayed on the client side. This is a service application of single client. The server can deal with it in real time. The time needed for the server to determine the label position can be approximately ignored, and the time delay can be ignored on the client side as well. However, when a plurality of clients (such as 10,000 clients) apply for such services simultaneously, the time needed for determining the label position by the server cannot be ignored. This will lead to the case in which, the client cannot receive the response for a long time after applying for the service, and the quality of service will be decreased as well. 
     FIG. 7  shows a general working flow chart of WebGIS server. As shown in the drawings, it starts at Step S 1 , and waits for a users&#39; request at Step S 2 . Then goes to Step S 3  if there is a service request sent by a user. It reads in the display scale, point positions and size of label of the user, determining the label positions with traditional methods, and sends the determined result back to the user. 
   In traditional point labeling methods, the research target of map point labeling is the point set in a given area as well as the candidate label position set of each point. The candidate label position set of the unlabeled points can be classified into two categories: 
   1. Limited candidate label positions; 
   2. Unlimited sliding label positions. 
   No matter how large the number of the candidate label set is, the label determining method has been proved to be a NP problem. Example of point label methods that have been disclosed include: Expert System, Simulated Annealing method, Greedy method, Discrete Gradient method, Exhaustive Search method, Heuristic Method, etc. According to the research results of Jon Christonson et al., the way of point label with the best quality is the one of Simulated Annealing. Its label efficiency has priority to that of Exhaustive Search, Greedy, Discrete Gradient, and so on. However, the time consumption of Simulated Annealing is great. 
   When browsing maps on the web, under a certain label quality, users care more about the label efficiency, that is, the time complexity of the point label determine method. Especially in the pop Location-based Services (LBS) in WebGIS, it is possible for a large number of people to apply for the service of browsing the same map at the same time. This is a challenge to the capability of the map label determining method. And great effort is needed to smooth the system and the method for determining map point label on the web. 
   By far a better heuristic way for determining point label used on web is the one provided by Wagner (cf: Frank Wagner, Alexander Wolff, Vikas Kapoor and Tycho Strijk. Three rules suffice for good label placement. Algorithmica Special Issue on GIS, 2000. http://www.math-inf.uni-greifswald.de/map-labeling/bibliography, the following is called reference 1). While using the point label determining method to determine point label position on WebGIS map in real time, the time needed for determining can be largely reduced with little loss of labeling efficiency compared with Simulated Annealing methods. 
   LBS is generally used in urban areas where the population densities are always high and the activity areas of human being are relatively concentrated. It is obvious that, the displayed map areas which users care for are identical with the activity areas. When different users apply for the service of point label of local area, there are a larger number of area overlaps in multi-user service requests. If each user obtains label positions via real-time determining, the repeated determination will consume much time of the server; furthermore, when the number of points through real-time determining is large, the determining time needed for a single user cannot be ignored. A similar problem lies in other maps browsing services through networks, such as browsing the distribution of electronic components on circuit board stored in servers via networks, and so on. 
   The long time consumption in real-time computation indicates that a point label result of certain area can be pre-determined with certain display scale and stored in the server in advance. When users request for map displaying service (label), they only need to recall the results in the server, and this can save much time. However, when the display scale is changed, it will lead to label overlaps, the deduction of labeling efficiency, etc, though simple recall stories in the server. 
   SUMMARY OF THE INVENTION 
   As far as the shortcomings of above methods for determining point label position concerned, one aspect of the present invention is to provide means, a terminal unit, systems and methods for determining point label positions when browsing maps through network. 
   The point label in WebGIS is taken as an example as follows, and the process is similar to the point label of other map systems. In the typical interaction process of WebGIS, maps share much relevancy with each other. For example, when the scale of the current map is increased, the content of the new map comprises that of the old one. Based on this kind of relevancy and the demands of WebGIS applications, the present invention especially provides a method for determining the increment of point label position on the map used in WebGIS. After describing the point label problem, a method for determining map point static label in integrated area stored in the server under a certain scale is given first. Then an incremental method for determining the label positions of local area points based on the initial label results in the server is provided. 
   According to a first aspect of the present invention, there is provided a method for determining point label position on a map in a network system, comprising point label position determining means, a terminal unit and a communication link between them, the terminal unit sends the map display service request to the point label position determining means with a specific display scale via the communication links. Then the point label position determining means sends back map information with specific display scale to the terminal unit for displaying. 
   An example of the method comprises the following steps: saving one or more sets of static point label position results with one or more predetermined scales in the point label position determining means; comparing the request display scale with the predefined display scales on the point label position means when the terminal unit requests points and point label display services ; using the predetermined point label positions saved in point label position means if the display scale requested by the terminal unit is identical to a predetermined scale; determining new point label positions with the requested display scale using the incremental point label position determining method by the point label position determining means if the requested display scale of the terminal unit is different from any predetermined scales of the saved static point label positions, and sending the determined label positions to the terminal unit. 
   According to another aspect of the present invention, there is a system for determining points label positions on a map. An example system comprising a point label position determining means, a terminal unit and a communication link between the point label position determining means and the terminal unit, wherein the system further comprising: storage means for storing the data of static point label positions of the map with one or more predetermined scales; and comparing means for comparing a requested display scales of the terminal unit with the predetermined scales; selecting means for selecting an appropriate predetermined scale as the base for incremental label position determining method; determining means connected with the storage means and the selecting means for incremental label position determining with the display scale that is different from the predetermined scales; communication interfaces used for data interchange among the terminal means via the communication link, wherein the terminal means further comprising: communication means for receiving point label request from terminal units and send back the point label position determining results via communication interfaces; storage means for saving the data from the point label position determining means in local storage; and display means for displaying the map points and their labels with requested display scale saved in the local storage. 
   Through applying the point label methods based on rules in the invention, the initial point label positions with certain display scales can be obtained first. When browsing the map, the user&#39;s requests for point labeling can be fulfilled through the increment label determining method. The incremental label determining method largely reduces the consumption of processing service, so as to meet the concurrent request of large number of users. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
     According to the following, combined with the drawings, other aspects and advantages of the present invention will become clearer. The detailed description and specified examples are provided for illustration only. Those skilled in the art may add and improve these examples within the spirit and scope of the present invention. 
       FIG. 1  shows a map, which is not in conformity with the request of point label; 
       FIGS. 2 and 3  show possible candidate label positions; 
       FIG. 4  shows the case that one point lies within the candidate label position of another point; 
       FIG. 5  shows the case that the candidate label positions of two points lap over; 
       FIG. 6  shows a simplified model of WebGIS map browsing service; 
       FIG. 7  shows a general operation flow chart of a server; 
       FIG. 8  shows the candidate label positions of one point for describing the point label problem; 
       FIG. 9  shows an operation flow chart when using the increment determining method, according to an example of the present invention; 
       FIG. 10  shows an operation flow chart of the static determining method based on the present invention; 
       FIG. 11  shows a diagram of area-limited rules; 
       FIG. 12  shows a diagram of uncover rules; 
       FIG. 13  shows a diagram of Rule R 3 ; 
       FIG. 14  shows a diagram of Rule R 4 ; 
       FIG. 15  shows a diagram of Rule R 5 ; 
       FIG. 16  shows a chart of increment determining method used by an example of the present invention; 
       FIG. 17  shows a system for determining the label position of the present invention; 
       FIG. 18  shows relevant components for determining label position within the server in the label position determining system of the present invention; 
       FIG. 19  shows relevant components of the client in the label position determining system of the present invention; 
       FIG. 20  shows a structure diagram of the increment label determining means within the server in the label position determining system of the present invention; 
       FIG. 21  is the relation curve of running time versus number of points in real-time determining method with display scale S; 
       FIG. 22  shows a graph including the label position determining time of real-time determining method and that of the increment determining method when the display scale of the point set is  2 S in  FIG. 21 ; 
       FIG. 23  shows a diagram of initial label results of certain point set; and 
       FIG. 24  shows the increment label result of sub-area of  FIG. 23  with the display scale  2 S. 
   

   DETAILED DESCRIPTION 
   In the following example, the server is set as the point label position determining means for determing the point label position. 
   Mathematical symbols used in the point labeling problem are described in the following: 
   Assuming that the size of label window R is W×H. P={p 1 , p 2 , . . . , p n } is unlabeled points set in 2-D space. The coordinate of p i  is (x i , y i ), which meets the condition: 0≦x i ≦W, 0≦y i ≦H . Assuming that each point p i  has four candidate label positions (1, 2, 3, 4). C i  is the candidate label position set of p i , here, unifying C i =C={1,2,3,4}, that is, using four rectangle label positions of symmetrical axis. As shown in  FIG. 8 , from the point of aesthetic, the four label positions of one point have different priorities. And the position, which has lower serial number, has higher priority in FIG.  8 . These four rectangles are respectively expressed as r i   (1) , r i   (2) , r i   (3) , r i   (4) , the size of the label rectangle r i  of point p i  is w i ×h i . If meeting the condition: r 1   c     1   ∩r 2   c     2   ≠Ø, there is collision between two points p 1  and p 2  at c 1 , c 2  (∈C) (that is, overlap). 
   One label result of P L={(p i , c i )|i=1,2, . . . , n, c i ∈C∪{0}} meets the following conditions: 
   1. No collisions. The formula is ∀i, j=1,2, . . . , n, i≠j→r i   (c     i     ) ∩r j   (c     j     ) =Ø, wherein c i =0 means the point is not labeled, the area of the corresponding rectangle r i   (0)  is 0. 
   2. Limited area. Expressed as r i   (c     i     ) ⊂R, i=1,2, . . . , n. 
   L is called optimized label result, if meeting the following condition: 
   3. There is no other label result L′ of P, making L⊂L′ come to be true. 
   Two label results L 1  and L 2  meet the condition of L 1 ⊂L 2 , which is called that, L 2  is superior to L 1 . The process from L 1  to L 2  is called the extension of L 1 . It is obvious that, the optimized label result is obtained from the extension from some starting label result to a fixed point (a label result that cannot be extended any more). Furthermore, P may have multiple optimized results. The label number N(L) of the label result L is the number that c i  is not 0 in L. It is obvious that, N(L) may be regarded as a criterion to weigh label quality. Therefore, different optimized results of P have different qualities. However, it is difficult to find out one optimized result, which has the highest quality from all the optimized label results (the NP hard problem). The point label determining method associated with the present invention requests as follows: 
   Input: W, H, p i , r i (i=1,2, . . . , n) 
   Output: optimized label result L 
   There is no request for optimal solutions in the point label determining methods. Thereby the object of the determining method of the present invention is to improve the quality as much as possible under the WebGIS circumstance. 
   According to an example of the present invention,  FIG. 9  shows that a working chart of the server when using the increment determining method, which comprises the following steps: 
   At Step S 32 , the server choosing the proper scales, determining all the point label positions using the static determining method of the present invention; 
   At Step S 33 , waiting for the service requests from users; 
   At Step S 34 , reading in the display scale of the user; 
   At Step S 35 , comparing the display scale read in here with the proper scales used by the server in predetermining the point label positions; 
   If the scales are the same, turning to Step S 36 , sending the positions predetermined by the server to the user; 
   If all scales are different, turning to Step S 37 , determining the label position using the increment determining method of the present invention, and sending the result to the user. 
   The static point label position determining method and the increment determining method used during the working period of the server are described respectively as follows: 
   Static Point Label Position Determining Method 
     FIG. 10  shows the static point label position determining method based on the present invention. Because WebGIS requests high performance of the point label position determining method, the static label determining method of the present invention is similar to the revelatory method based on rules of Reference  1 . Reference  1  uses a series of rules to reduce candidate label positions in the first phase, and obtains the optimized label result by revelatory rules in the second phase. 
   In order to accelerate the computation, besides the three rules in reference 1, we incorporate two additional rules for initiating the candidate label position of label point. Thereby, the whole point label position determining method can be divided into three phases: 
   The first is initial phase: initialize the candidate label position of each point with rule R 1  and R 2  (Step S 22 ); 
   1. Rule R 1 : the rule of limited area. If r i   (j) ∉R, the candidate position j is deleted from the candidate label set. As shown in  FIG. 11 , wherein the gray part expresses the available label candidate positions. If the candidate position of one point goes beyond the label area, the candidate position will be canceled. Position  2  remained in  FIG. 11  is the candidate label position, the other positions cannot be used. 
   2. Rule R 2 : the rule of non-overlap. If ∃k, p k ⊂r i   (j) , the candidate position j is deleted from the candidate label set. As shown in  FIG. 12 , wherein the gray part expresses the available label candidate positions. If the candidate position of one point goes beyond the label area, the candidate position will be canceled. Positions  2  and  4  remained in FIG.  12  are the candidate label positions, the other positions cannot be used. 
   The incorporation of rules R 1  and R 2  leads to the deletion of unusable candidate label positions in a considerable measure, which reduces the successive processing time as well. 
   The second and the third phase correspond to the two phases of the determining method in reference  1 . The difference lies in that all the collisions among candidate label positions are determined in real-time instead of directly inputted collision figures. The second phase uses rules R 3 -R 5  (corresponding to rules L 1 -L 3  in reference  1 ), labeling the points without collisions, and passing through all the points, until no point meeting R 3 -R 5 . The third phase searches the label positions of all the points unlabeled, finds out the points having the most candidate positions, and deletes the candidate label positions of the points having the most collision (step S 23 ); applies R 3 -R 5  again. Repeating the process above till all the points labeled or unable to be labeled, that is, obtaining an optimized label result (step  24 ). 
   The following is a brief description about rules R 3 -R 5 , according to  FIGS. 13-15 . 
   Rule R 3 : as shown in  FIG. 13 , if point p has a candidate label position p i  without collisions with other label positions. Then p i  is the label position of point p, delete other candidate label positions of point p; 
   Rule R 4 : as shown in  FIG. 14 , if point p has a candidate label position p i , p i  collides with only one candidate label position of point q, and point q has a candidate label position q j (j≠k) which only overlaps candidate label position p l (l≠i) of point p. p i  and q j  are respectively the label positions of points p and q, delete other candidate label positions of points p and q; 
   Rule R 5 : as shown in  FIG. 15 , if there is only one candidate label position p i  of point p, delete the candidate label positions which collide with p i . And p i  is the label position of point p. 
   The pseudo code of determining method is shown as follows. Line  9  determines the adjacent area of point p, the size thereof is determined by the maximal label width and height which are determined in line  2 . The modifications of candidate label of point p lead to the re-employ of rules R 3 , R 4  and R 5  to the adjacent area. 
   The pseudocode of the static point label position determining method is the following: 
                                         PointLabel(W i , H i , p i , r i (i = 1, 2, . . . , n)) ; W i  is the width of label frame                of point i, H i  is the width           of label frame of point i, p i  is           the coordinate of point i, r i  is           the radius of point i                        
// Phase One
 
   1. L←Ø; L is the label set, initializing L into NULL set, that is, the point label positions of all points are not determined. 
   2. 
           w   max     ←         max   n       i   =   1       ⁢     (     w   i     )         ,       h   max     ←         max   n       i   =   1       ⁢     (     h   i     )         ,       
 
determining the maximum widths and maximum heights of all point labels, quadruple of which are the width and height of the collision area.
 
   3. Using rules R 1  and R 2  to initialize the candidate label set of point p i , and modifying L 
   // Phase Two 
   4. Using rules R 3 , R 4  and R 5  to modify the candidate label set of for all p i , and modifying L 
   // Phase Three 
   5. Repeating 
   6. p← the point which has most candidate label positions in unlabeled point set 
   7. c←p the candidate label which has most collision in candidate label set 
   8. Deleting c 
   9. Γ← a rectangle in which p is central point, the width and height are respectively 4×w max  and 4×h max ; depositing the points in small collision area 
   10. Using R 3 , R 4  and R 5  to the points unlabeled in Γ, and modifying L 
   11. Till L can not be modified any more 
   12. Output L 
   Increment Point Label Position Determining Method 
   Though the label efficiency in the above-mentioned point label determining method is slightly lower than that of Simulated Annealing method, from the viewpoint of time consumption, the determining method has much advantage. However, when the number of points is large, and there are many users applying for the service, it will take much time to determine the point label positions in real time by means of the determining method. Concerning the service based on locations, the places in which many users take activities are fixed (for example, in certain cities). We may use the above-mentioned determining method to determine the global label position results with certain display scales in advance and save the results. Based on these results, the local area concerned by each user is a subset of the fixed areas. The point labels inside local area is a subset of the global label position results, in case that the scale is unchanged. If the scale of local area is changed, the point label positions of the area will be changed. The increment determining method of point label in local area, as follows, can be used to quickly determine point label results of local area, in case that the scale is unchanged or decreased (assuming that the size of label will not change with the scale). 
   The pseudocode of the increment determining method can be written down based on that of the static point label position determining method mentioned above. In the following paragraph, the increment determining method of the present invention is characterized upon results of the static point label position determining method with FIG.  16 . 
     FIG. 16  shows a flow chart of the increment determining method used by an example of the present invention. If the scale Φ requested by a user, is different from the scale S of the server used in predetermining label, determining that the scale Φ of the user is larger or smaller than S (step S 41 ). Assuming that, L is an optimized label result of point set P of the whole area, which is obtained from the static determining method under the scale of S. In order to obtain the label result of sub-region R (a subset of P) with the scale Φ(≠S), it can be divided into two cases, considering the relationships of Φ and S. 
   1. Φ&gt;S (step S 43 ). The increase in scale is equivelent to the Zoom In operation to the map, the displayed distance between opposite points becomes large, therefore the number of labeled points is no less than L. Then point P in sub-region can be divided into three cases according the label position C: 
   (I) c&gt;0 and r (c) ⊂R. That is, the label position lies inside the sub-region, adding (p, c′) in L(Φ); 
   (II) c&gt;0 and r (c) ∉R. That is the label position partly lies outside the sub-region. Replacing the other candidate label positions of P one by one in a sequence of priority. If some new candidate label position c′ meets R 1  and R 2 , and takes no effect on the label position of adjacent area point in L, then adding (p, c′) into L(Φ); otherwise, adding (p,0) into L(Φ) (unlabeled); 
   (III) c=0. Because the point, which cannot be labeled under original scale, can probably be labeled under new scale, then labeling by the method similar to (II). 
   2. Φ&lt;S (step S 42 ). The decrease of scale is equivelent to the Zoom Out operation to the map, the displayed distance between opposite points becomes small, the point which can be labeled will probably become unlabeled. Therefore, the static determining method should be applied to the labeled points in L. However, in practice, when the scale decreases, grade labeling should be put into consideration, so as to avoid the case that, there are full of points inside the displayed area, while only a very few points can be labeled. 
   It is obvious that, the increment determining method largely reduces the determining time when the scale increases. Practically, the choice of initial scale S is very important, because it determines the scale range that can be used by the increment determining method. Therefore, it&#39;s due to the application demand. Concerning cases that the range of the scale variation is large, the method of multiple initial scales may be used, that is, determining the static label results with the scale S 1 , S 2 , . . . , S M , here the demand of initial results to storage should be put into consideration. 
   Here only an increment determining method is supplied. However, as long as the following functions can be fulfilled, other different increment determining method can be realized. On the basis of the label positions determined in advance of the server, after making sure about the changes of scales, judging whether there are points having no original label positions but being labeled now (the scale decreases); or originally having label positions, and no label positions now (the scale increases); there is no need for the increment determining method to pass through all the points, it reduces the determining time comparing with the traditional point label determining method. When large numbers of users request for service at the same time, the time that can be saved is considerable. The idea of the present invention lies in that, the increment determining method can be applied on the basis of static determining method, it is not limited to the specific increment point label determining method, the design of any increment point label determining method can fulfill this purpose. 
   A system using the above-mentioned increment label determining method is described as follows. As shown in  FIG. 17 , a server B communicates with many clients A 1 , A 2 , . . . , An. Client A may be a portable device, for example, a cellular phone, a palm computer, PDA, or a computer. Server B may be a computer or a professional device. Client A and server B communicate with each other by means of wire or wireless. As shown in  FIG. 18 , the server B comprises: static label storing means  21 , for storing the point static label position data of the map under one or multiple predetermined scales; comparing means  22 , for comparing the display scale of the client with the predetermined scales of the server; choosing means  23 , for choosing proper predetermined scale as the base to determine increment label, according to compared results; increment label determining means  24 , which connects with the means for storing static label position data and choosing means, according to the static label position data, determining the difference between label data and the static label position data under other scales except the predetermined scale; and communication interface  25 , for connecting with the client via the communication chain, and exchanging data with the client. As shown in  FIG. 19 , the client A comprises: communication interface  14 , for exchanging data with the server; label position storing means  11 , for storing label position data from server; display controller  13 , for sending absolute or relative display scales of monitor to server B via communication interface  14 , requesting server for determining label position for display, and controlling monitor  12  to display based on the data from server B, when receiving determining label position results from server; monitor  12 , for displaying the points of the map and the label thereof based on the scale indicated by client, according the label position data stored in the memory. 
   The display scale sent from client A to server B may be an absolute scale, or a relative one on the basis of former display scale. If what server B receives is a relative scale, the server B obtains the absolute scale requested by client A for display service by adding the relative scale to current display scale of the client, and processing as above according to the absolute scale. 
   As shown in  FIG. 20 , the increment label determining means  24  comprises memory  243 , for storing labeled points and label position set from static label storing means under predetermined scale, according to the predetermined scale chosen by the choosing means; and memory  242 , for storing unlabeled point position set. 
   If comparing means  22  judges that the display scale is identical with a predetermined scale, the choosing means  23  chose the predetermined scale. If display scale is different from all predetermined scales, and there are predetermined scales smaller than the display scale, among them the maximum predetermined scale will be chosen, otherwise, the minimum predetermined scale will be chosen. 
   The increment label determining means  24  also comprises judging means  241 , 
   a. If the proper predetermined scale chosen by choosing means  23  is smaller than display scale, the judgment is: 
   a1)if one label position of one point lies inside the sub-region browsed by client, the label position will be added into memory  242  for storing labeled set; 
   a2) if one label position of one point lies outside the sub-region browsed by client, other candidate label positions of the point will be replaced one by one in the sequence of priority. If a certain new candidate label position does not go beyond the label area in which there is no other points, and takes no effect on the point label position of the adjacent area in the labeled label set, then the label position of the point will be added into memory  243  for storing labeled label set; otherwise the point will be added into memory  242  for storing unlabeled label set; 
   a3) for the unlabeled point under predetermined scale, its label position is determined by the steps in (a2) above; 
   b. If the display scale requested by the client is smaller than the predetermined scale, then the label position of the labeled points in the original labeled point memory should be determined by the static label position determining method. 
   The label data are respectively stored in unlabeled point memory and labeled point memory, with the display scale of client determined by the judgment of judging means  241 , and the results are sent to the client for displaying via communication interface. 
   Experimental Data And Label Results 
   Experimental data comes from www.math.inf.uni-greifswald.de/map-labeling. Program language is JAVA, running under the circumstance of JDK on IBM Thinkpad 770ED. The scale of area when 80 percent of all point set can be labeled, is chosen as the scale S which determined the point label results stored in server. 
   As far as the time consumption of determining method concerned, it can be divided into two parts for discussing. First real-time point label position determining method. Rule  2 , which is added into determining method, dramatically reduces computing time. For example, it takes 220 seconds to run the real time point label position determining method with the three rules of Wagner and only 1 second after adding Rule  2  (the consumption of our determining time in the lab is larger than that in the paper of Wagner, one reason is that, in order to simulate browsing the practical condition of WebGIS map, we determine collision in real time instead of directly inputting collision figure; another reason is that, program in JAVA is slower than that in C, and our computer for testing is slower).  FIG. 21  shows the time consumption of point label determining method in real-time. Though it is acceptable for a single user, it is obvious too slow for the applications of WebGIS.  FIG. 22  shows the time consumption of the point set in  FIG. 21  under the scale  2 S employing both real-time determining method and increment determining method. Obviously, compared with real-time determining method, the time consumption of increment determining method can be ignored, completely meeting the requirements of multiple users at the same time. 
   The label result of some point set is provided too.  FIGS. 23 and 24  are results using real-time point label position determining method of the point set and increment determining method of half the point set respectively. The points expressed by x in figures stand for the unlabeled points. Obviously, the decrease of scale make many points labeled, which are originally unlabeled. 
   Thus the present invention provides a point label determining method suitable for the massive service requests simultaneously, associated with the main controversy of labeling a map in WebGIS on the basis of conversation pattern service, wherein the increment determining method largely reduces time consumption, and improves real-time response extend. Based on this method, a quick area label system can be obtained to fulfill the whole label process of WebGIS. 
   Also, a determining method and a system for labeling points in the web geographical information system according to the embodiments of the present invention are described with reference to the drawings. Though the present invention describes applications for the web geographical information system, it is obvious to apply the idea of the present invention to label display all kinds of maps, such as circuit diagram and mechanical diagram. These equivalent replacements are included in the scope of the present invention. In case that does not go beyond the spiritual essential and scope of the present invention, it is obvious for those skilled in the art to amend and change the present invention a lot. All the amendment and change are covered by the scope of the present invention. The protection scope of the present invention should be defined by the attaching claims. 
   Variations described for the present invention can be realized in any combination desirable for each particular application. Thus particular limitations, and/or embodiment enhancements described herein, which may have particular advantages to a particular application need not be used for all applications. Also, not all limitations need be implemented in methods, systems and/or apparatus including one or more concepts of the present invention. 
   The present invention can be realized in hardware, software, or a combination of hardware and software. A visualization tool according to the present invention can be realized in a centralized fashion in one computer system, or in a distributed fashion where different elements are spread across several interconnected computer systems. Any kind of computer system—or other apparatus adapted for carrying out the methods and/or functions described herein—is suitable. A typical combination of hardware and software could be a general purpose computer system with a computer program that, when being loaded and executed, controls the computer system such that it carries out the methods described herein. The present invention can also be embedded in a computer program product, which comprises all the features enabling the implementation of the methods described herein, and which—when loaded in a computer system—is able to carry out these methods. 
   Computer program means or computer program in the present context include any expression, in any language, code or notation, of a set of instructions intended to cause a system having an information processing capability to perform a particular function either directly or after conversion to another language, code or notation, and/or reproduction in a different material form. 
   Thus the invention includes an article of manufacture which comprises a computer usable medium having computer readable program code means embodied therein for causing a function described above. The computer readable program code means in the article of manufacture comprises computer readable program code means for causing a computer to effect the steps of a method of this invention. Similarly, the present invention may be implemented as a computer program product comprising a computer usable medium having computer readable program code means embodied therein for causing a function described above. The computer readable program code means in the computer program product comprising computer readable program code means for causing a computer to affect one or more functions of this invention. Furthermore, the present invention may be implemented as a program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for causing one or more functions of this invention. 
   It is noted that the foregoing has outlined some of the more pertinent objects and embodiments of the present invention. This invention may be used for many applications. Thus, although the description is made for particular arrangements and methods, the intent and concept of the invention is suitable and applicable to other arrangements and applications. It will be clear to those skilled in the art that modifications to the disclosed embodiments can be effected without departing from the spirit and scope of the invention. The described embodiments ought to be construed to be merely illustrative of some of the more prominent features and applications of the invention. Other beneficial results can be realized by applying the disclosed invention in a different manner or modifying the invention in ways known to those familiar with the art.