Force Directed Map Labeling
Overview:
Due to its numerous applications, e.g., in cartography, geographic information systems, point pattern analysis, spatial statistics, and graphical interfaces, automated map labeling attracts still many researchers in computer science. A major problem in map labeling is the point-feature label placement problem, where the task is to place labels adjacent to point-features so that only a few or no labels overlap. The growing amount of data leads to an increasing need for fast and efficient map labeling algorithms that produce well readable labelings in a small amount of time.
We present a new and very efficient heuristical approach in the most general of the labeling models, the four-slider model. This page offers access to a number of test instances and a demo application to compare our method to other known algorithms in the four-slider and four-position model. The application has been developed using Java and can be obtained in the download section. Furthermore this sections enables access to a Technical Report, which describes the algorithm and contains a large section of computational results.
Authors
- Ebner Dietmar
- Gunnar W. Klau
- René Weiskircher
Contact Information
If you have any suggestions or questions, feel free to contact one of the authors using {ebner | gunnar | weiskircher} @ ads.tuwien.ac.at.
|
|
|
Downloads:
We decided to release the source code of the program under the terms of the GNU GPL licence. You are free to download, modify and distribute it as long as you agree to the terms of the GPL. The full text of which can be found here.
Since we are always interested in improvements, please let us know if you find the program useful and/or have any extensions for the given application. Developers can download a precompiled version of the documentation (created using Javadoc) or access it online here. Since it is quite easy to extend the framework by further algorithms, we would be glad if people do so to compare the performance and solution quality of different methods.
 |
Demo application | PFLP.jar (95Kb) | md5: fe829a66d20fb9e4b6fc4e353e69ad1f |
|
Technical Report | fdl_tr.pdf (coming soon) | md5: xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx |
|
Random Benchmark set
This benchmark set is generated according to the rules described in (J. Christensen, J. Marks, and S. Shieber, An Empirical Study of Algorithms for Point Feature Label Placement, ACM Trans. on Graphics, 14(3):203-232, 1995) |
cms.tar.gz (5,3Mb) | md5: 89065c4c09299a61c60febb2404c3ffa |
|
Munich Drillholes Benchmark set
Alexander Wolff collects and maintains a lot of information about map labeling on his map labeling pages, including real-world labeling instances. The Munich Drillholes Benchmark set contains points corresponding to coordinates in the city of Munich (original source) |
md.tar.gz (3,7Mb) | md5: 9996e910d8f85b5f1dfe0aabb5d7a082 |
|
Source code | pflp_src.tar.gz (49Kb) | md5: 81d1bcbd698e18540d158ecd774f5cfc |
|
Source code documentation | pflp_doc.tar.gz (57Kb) | md5: be0919349ca9506fb95073a317c97c48 |
> java -jar PFLP.jarThe appliction allows to export solutions to the EPS format. Therefore it uses EpsGraphics2D written by Paul James Mutton, which is also Open Source and included in the package. To run benchmarks without using the user interface use the following command line arguments:
> java -jar PFLP.jar --help
PFLPApp
[ --batch <filename>
[--retries <n>]
[--disable-point-selection]
[--solution <file_prfx>]
[--algorithm {fdl|fdlcu|sa|hirsch|leftmost|random}]
]
[--dump-min-dist <filename.sol> -o <outfile.dist>]
Since we can't measure the real user time without using JNI one should
use the time command to obtain precise results. The application has
been developed and tested with the SUN JDK 1.4.2_03, but it is
expected to work also with anterior versions.
Last modification: May 2004