[kde-edu]: Label placing in Marble

[Torsten Rahn]

Hi,

I only found out this morning that placing labels had been a topic during the 
last few days. 
If you followed my blog/SVN commits you might have seen that I had worked on 
that same topic independently with regard to Marble during the past 2 weeks.

http://developer.kde.org/~tackat/marble/marble7.jpg

While the API might not be very pretty or generic, the algorithm might be of 
interest. My personal predefined requirements were:

- placemarks are allowed to be in four corner positions only. This has the 
disadvantage that in very, very rare circumstances for a map, labels might 
row up in the same horizontal line like Benoit had pointed out. However if 
you allow too many or random positions for the labels around the labeled 
points itself then it's actually harder in practice for the reader to assign 
the label correctly unless the label density is low. I also don't want lines 
to connect labels to the placemarks either (you usually don't see such in 
printed maps either). Also random positions make it harder to calculate the 
best position as you need expensive stuff like calculating the manhattan 
length, etc.  
- placemarks should be placed in order of importance (as a criteria I take the 
population) and should rather be "dropped" from the map than painted 
overlapping.
- labels should be placed in one go

I used a similar method as the 100x100 grid you're using to speed up 
calculation:
As I allow two possible positions above the labeled point and two below, that 
takes up 2*fontheight ((+x pixels if you want some distance between)) in 
terms of possibly covered height. So I divide the whole screen into 
horizontal rows of the height 2*fontheight. While assigning positions I sort 
each labeled position into one of those rows and compare the subsequent 
points only with the "own" row and the two direct neighbour rows.
(I also thought about optimizing in terms of horizontal space, but that turned 
out not to save any significant time)
That whole procedure is pretty fast and hence serves my needs. :-)

Next algorithm I plan to extend this to is rivers and oceans (which I intend 
to handle the same way).

Torsten