Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Label Placement System for Geographic Information System

IP.com Disclosure Number: IPCOM000126927D
Original Publication Date: 2005-Aug-12
Included in the Prior Art Database: 2005-Aug-12
Document File: 4 page(s) / 21K

Publishing Venue

IBM

Abstract

A program is disclosed that gives a new solution to the Node Label Placement (NLP) problem area in Geographic Information System (GIS).

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 47% of the total text.

Page 1 of 4

Label Placement System for Geographic Information System

 The Node Label Placement (NLP) problem is known as one of the optimization problems in GIS. GIS gives an ability to visualize geographical distribution of business objects e.g. which are some results of database retrieval. Then, usually the object's name or ID is attached as a label to the object in order to get linkage to its attributes retrieved from database.

 However, in case objects are very crowded at a small area, a problem of visibility occurs. In such case, labels and objects are overlapping each other and label texts are not readable, furthermore the object positions are invisible.

 Therefore, the label placement optimization to place labels so as not to overlap each other is needed, and which is called as NLP in GIS.

As a general technique, it takes the way of scattering labels by tying each object and its label with a leader line. And as it is seen in a paper [1], as one of solutions to scatter labels, a technique applying a mechanics model among the overlapping objects was proposed, but there are some problems as followings;

1. Non-reproducibility: due to randomness of initialization, the results are different each time
2. Non-completeness: sometimes there remain non-fixed labels after maximum repetition

 In that former algorithm, random numbers are used in order to determine the starting position of objects which have completely the same position as given initial position, which are not processable as they are because such two objects derive no dynamic force. So, the result is different every time it executed even for the same object set.

Furthermore, there remains a post-process problem. In the technique of mechanics model, label movement is simulated by repeating to calculate velocity vectors and their uniform motion in a microscopic time interval, but it is impossible to estimate initially the number of repetition times for fixing all the objects. So, usually, a relevant large number is set as the maximum repetition number but when the repetition reach to the maximum number, there may remain some non-fixed objects. Then additional process for them is needed after repetition over. There are no discussions about this second effort so far.

Note that NLP is known as NP-hard (nondeterministic polynomial time - hard), so it is impossible to guarantee the completeness of results, even if any second efforts were executed. But some effective second efforts are needed to reduce the number of non-fixed objects.

This program realizes the reproducibility and reduces the non-fixed objects after repetition by enhancing and extending the calculation model, for example; dynamical alteration of mechanics models.

In detail, the main idea is based on the gradual movement of objects acting on a sort of motion equation resulting from a repulsive force defined between all the labels to labels or labels to object points.

There is a known past technique based on a similar idea succee...