[kde-edu]: Label placing in Marble

[Jason Harris]

Hi Torsten,

Thanks for letting us know about your labeling strategy in Marble.  We
had actually considered the four-corners method too, but our
requirements for KPlotWidget are a little different.  It's usually not
so clear how to "rank" points, so in cases of unavoidable collision,
we'd have to drop labels arbitrarily.  And I think the people using
KPlotWidget would rather see all of the defined labels positioned in
the plot, even if it makes the plot very crowded.

Still, perhaps we could speed up the algorithm a bit by first
attempting the 4-corners method, and when that becomes saturated, fall
back to our cost-based algorithm.  I've also been considering having a
variable size for the grid of positions searched in the cost-based
method: start with a very small grid, and expand it incrementally as
needed if no acceptable label position is found.  This may speed up
the cost-based algorithm considerably.

We may use a 4-corners strategy for the skymap in KStars, though.  In
that case, we have similar requirements to Marble: we don't care if
every object is labeled, and it's easy to rank objects in order of
labeling priority, by their brightness and object type.

By the way, if anyone hasn't seen Marble yet, you should really check
it out [1].  It's a very nice program, and I imagine it would be quite
easy to base geographical Edu apps on the exportable mapping widget
provided by Marble.  I'm planning to adapt the KSatrs GeoLocation
selector to use Marble :)

regards,
Jason

[1]: http://www.kdedevelopers.org/node/2412


On 10/29/06, Torsten Rahn <torsten.rahn at credativ.de> wrote:
> 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
>
>
>
> _______________________________________________
> kde-edu mailing list
> kde-edu at mail.kde.org
> https://mail.kde.org/mailman/listinfo/kde-edu
>