Add support for polygon label position

[andreynovikov]

Map writer has an option to compute label position for polygons that cover multiple tiles. Currently VTM lacks proper area name display. It would be nice to add support for it.

[devemux86]

I think neither Mapsforge supports area caption in render theme schema.
Is that what you mean?

[andreynovikov]

Yes. But as I see map writer has support for them. Is it unfinished?

[devemux86]

In both libraries there is support for caption rules on a way element, e.g. see the name and addr:housenumber in buildings.

[andreynovikov]

I was trying to add similar for lakes and landuse areas with poor result.

[andreynovikov]

I am currently investigating the subject. Foremost I want to mention that I have successfully implemented basic functionality with my forks of mapsforge and vtm libraries. But there are some issues and questions to discuss.

In general my task is to properly add captions and symbols to various polygons. For instance - water area names, airport and other notable area symbols, proper building numbers (see below).

This task can not be solved in general. The major problem is that the majority of polygons is split among several tiles but map renderer operates on a single tile. There is no way for the renderer to get full polygon information and to decide where to put it's label. Current implementation puts a label in the center of a clipped polygon in each tile. This affects even building numbers: if the building is split by tile its number is drawn several times. This can be seen even with raster mapsforge renderer.

Mapsforge map writer contains label-position option, but it behaves somewhat strange. If turned on it generates label position only for split polygons and only if it is inside the tile:
https://github.com/mapsforge/mapsforge/blob/master/mapsforge-map-writer/src/main/java/org/mapsforge/map/writer/MapFileWriter.java#L185
It is stated that "this is left to the renderer for more flexibility" but as I noted above, renderer can not determine if polygon is split or not. Another assumption is: "if the computed centroid is within the current tile, we add it as label position, this way we can make sure that a label position is attached only once to a clipped polygon". This is acceptable if we show labels only if polygon has defined label position. But this will break current vtm functionality as other tile sources will not provide that data. Having all this in mind I have decided to generate label positions in all cases.

This is working but is very excessive in terms of map data size and processing speed. There is no need to have this option map-wide and generate position for each and every polygon. I propose to make it settable for individual tags in mappings file.

Speaking about vtm this approach works good for building numbers and polygon symbols. But polygon labeling needs significant improvement. Currently labeling can be filtered only by zoom level. But if you need to label land areas (water, protected areas and similar objects of very varying sizes) labeling should be limited to polygon area. (You can see such behavior on OpenStreetMap) Technically this can be done but needs extending of style rules. So I want to discuss it also.

[devemux86]

@andreynovikov nice analysis! 👍
The whole issue requires careful checking as it expands in various modules.

Extensions to map-writer or Mapsforge / VTM renderers are always welcome (provided somehow backwards compatibility). 😄

BTW label-position option is by default enabled, so current maps have them?

[andreynovikov]

Yes, you have enabled it via mapsforge/mapsforge@f02aa93 but is looks like it was a wrong decision. :)

Are label positions currently used in MapsForge rendering code or it was made for future?

[andreynovikov]

I have played with filtering polygon labels based on its calculated area. It works well despite one irritating fact: when using mapsforge maps on zooms lower then base zoom polygons are split into many peaces, that prevents correct polygon area calculation.

As a matter of fact this behavior produces many rendering problems, the major one is contouring a polygon. May be we should join polygons in this case? There are ready to use solutions, such as:
http://www.cs.man.ac.uk/~toby/alan/software/
with a ready to use java port:
https://sourceforge.net/projects/geom-java/files/gpcj/

P.S. Even with split polygons area filtering works well but sometimes requires complex style rules (for zooms below and above 14).

[andreynovikov]

To conclusion: I will prettify the code and create a PR both for mapsforge and vtm. It will take some time though.

[devemux86]

As a matter of fact this behavior produces many rendering problems, the major one is contouring a polygon.

You mean the artifacts in zooms 12-13 coming from base zoom 14 grid, discussed many times in the forum, right?

BTW I remember @hjanetzek had mentioned 3 years ago an idea for that.

I will prettify the code and create a PR both for mapsforge and vtm

👍
Only the 2 clients require updating?
Also need third-party dependency and with what license?

And I suppose we should revert the label-position to its previous state and fix the map-writer docs?

[andreynovikov]

Only the 2 clients require updating?

Yes, mapwriter and vtm. Can't talk about mapsforge renderer because I do not use it. Anyway all updates to mapwriter are back compatible.

Also need third-party dependency and with what license?

Not at this point. It was only the suggestion.

And I suppose we should revert the label-position to its previous state and fix the map-writer docs?

Yes, this will be the part of PR as I implemented per-tag configuration.

[andreynovikov]

I have created both PRs. Have tested them on my custom map. This is what I used for testing:

<m e="way">
    <m closed="yes" k="natural" v="water">
        <caption k="name" fill="#3d59ab" size="16" stroke="#cae1ff"
            stroke-width="2.0" area-size="0.3" />
    </m>
    <m k="aeroway">
        <m closed="yes" v="aerodrome">
            <m zoom-min="12">
                <caption dy="18" fill="#000000" k="name" priority="5"
                    size="19" stroke="#ffffff" stroke-width="2.0" area-size="0.05"/>
            </m>
            <m zoom-max="12">
                <caption dy="18" fill="#000000" k="ref" priority="6"
                    size="19" stroke="#ffffff" stroke-width="2.0" />
            </m>
            <symbol src="assets:symbols/transport/airport.svg" />
        </m>
    </m>
</m>

And default building styles, of course.

[devemux86]

Thanks @andreynovikov very clean work! 👍

• Should we postpone VTM 0.6.0-rc2 to merge this?
• I see in the two PolyLabel that Cell has different precisions (float vs double)
• Could MaxComparator probably use epsilon, i.e. |a - b| < epsilon?

[andreynovikov]

1. Up to you. Anyway it requires maps generation which would not be quick.
2. Yes, VTM uses floats for geometries while JTS uses doubles. I didn't want to introduce unnecessary type conversions.
3. It uses built-in comparison, why not?

[devemux86]

In my tests the client has serious performance issues with the calculations.
CPU is consumed completely and the map stops responding after a while.

[andreynovikov]

At what particular cases? I am working on it a week already and use VTM sample app heavily for testing but did not notice any issues.

[devemux86]

Areas with buildings with many house numbers. I even got an OOM on Android.
Trying to isolate the issue..

[andreynovikov]

Strange. I have added PolyLabel to VTM first and didn't notice any performance problems during tests. But if this is the issue we can simplify the logic - take centroid and only if it is outside the polygon, calculate alternative position for label.

[devemux86]

@andreynovikov you can try Mapsforge luxembourg.map (2016-03-03) inside the capital.

@Longri could you test branch issue_204 too?

[Longri]

Yes, of course. But what should I look out for?

[devemux86]

@Longri try issue_204 branch with e.g. older luxembourg.map and zoom inside the capital.

In my tests on Android and Desktop, older maps after a little zoom / pan become unresponsive, too much GC and CPU utilization.

[devemux86]

Furthermore the label calculation needs more checks.
For example zooming on a natural=water, I don't see labels in all tiled areas, though the ratio (area / tile) visually is sufficient.
Also at water areas where there are labels at 1st zoom, if I leave and zoom / pan a lot returning to them later, their labels don't appear anymore.

[andreynovikov]

1. I've checked out https://github.com/mapsforge/vtm/tree/issue_204 branch, and tested luxemburg map. I've played with it about 5 minutes and on my Nexus 5 CPU never raised higher then 50%. I could not find any performance issues.
2. As for natural=water labels they would not work as expected unless map will contain precalculated label positions. So current styles should not include this. Anyway, I do see lake names on a map and get performance problems only if I completely remove area-size from the rule.

[devemux86]

1. Can you check the log during tests? When inside capital (zoom 16-17) the log starts filling with continuous GC and at the end comes an OOM.

org.oscim.android.test I/art: Background partial concurrent mark sweep GC freed 65267(2039KB) AllocSpace objects, 0(0B) LOS objects, 1% free, 378MB/382MB, paused 385us total 453.072ms
org.oscim.android.test I/art: Background sticky concurrent mark sweep GC freed 0(0B) AllocSpace objects, 0(0B) LOS objects, 0% free, 383MB/383MB, paused 71.898ms total 282.771ms

Also please check with the MapsforgeTest on desktop.

2. I performed water tests with a fresh map.

[Longri]

I tested this branch under iOS with luxembourg.map.

With zoom the app freezes and then crashes after a short time.
Unfortunately without any error messages! (This is unfortunately still a RoboVM problem)

[andreynovikov]

I've got the issue (using memory allocation tracking). Sometimes for unknown reason this limitation:
https://github.com/mapsforge/vtm/blob/issue_204/vtm/src/org/oscim/utils/geom/PolyLabel.java#L88
does not work and algorithm goes into infinite recursion. Currently looking why.

[devemux86]

@Longri thanks for the feedback.

@andreynovikov since this is an important feature and would need good testing, I'll proceed with 0.6.0-rc2 and merge this when it's stable afterwards.

[andreynovikov]

Agree.

[andreynovikov]

In PolyLabel class I didn't check for geometry type, I've thought that element.type == POLY is sufficient to ensure that class is used on true polygons only. But it appeared that strange polygons with only two points were fed to PolyLabel class (I assume this is due to tile clipping). Algorithm failed to calculate polygon area and produced NaN, that resulted in infinite recursion. So, the following diff should be applied:

diff --git a/vtm/src/org/oscim/utils/geom/PolyLabel.java b/vtm/src/org/oscim/utils/geom/PolyLabel.java
index 7eb40ca..c822492 100644
--- a/vtm/src/org/oscim/utils/geom/PolyLabel.java
+++ b/vtm/src/org/oscim/utils/geom/PolyLabel.java
@@ -45,6 +45,10 @@ public class PolyLabel {

         int n = polygon.index[0];

+        // if polygon is clipped to a line, return invalid label point
+        if (n < 6)
+            return new PointF(-1f, -1f);
+
         for (int i = 0; i < n; ) {
             float x = polygon.points[i++];
             float y = polygon.points[i++];

[andreynovikov]

Nice city - Luxembourg! Have found another issue - building polygon consisting of three points in a line (with equal Y coordinate). So, disregard my previous diff, here is the correct one:

diff --git a/vtm/src/org/oscim/utils/geom/PolyLabel.java b/vtm/src/org/oscim/utils/geom/PolyLabel.java
index 7eb40ca..cf328d7 100644
--- a/vtm/src/org/oscim/utils/geom/PolyLabel.java
+++ b/vtm/src/org/oscim/utils/geom/PolyLabel.java
@@ -43,6 +43,13 @@ public class PolyLabel {
         // find the bounding box of the outer ring
         float minX = Float.MAX_VALUE, minY = Float.MAX_VALUE, maxX = Float.MIN_VALUE, maxY = Float.MIN_VALUE;

+        // take centroid as the first best guess
+        Cell bestCell = getCentroidCell(polygon);
+
+        // if polygon is clipped to a line, return invalid label point
+        if (Float.isNaN(bestCell.x) || Float.isNaN(bestCell.y))
+            return new PointF(-1f, -1f);
+
         int n = polygon.index[0];

         for (int i = 0; i < n; ) {
@@ -69,9 +76,6 @@ public class PolyLabel {
             }
         }

-        // take centroid as the first best guess
-        Cell bestCell = getCentroidCell(polygon);
-
         // special case for rectangular polygons
         Cell bboxCell = new Cell(minX + width / 2, minY + height / 2, 0, polygon);
         if (bboxCell.d > bestCell.d) bestCell = bboxCell;

[devemux86]

Thanks @andreynovikov works nice!
Do you want to update your PR (then I can cherry pick it) or post a new PR on branch?

BTW do we need the same fix on map-writer?

Trying now the heavy netherlands.map at small zoom levels 8-9, I notice that master seems more responsive to map panning compared to branch issue_204 (with the fix)?

[andreynovikov]

I will update my PR.

Map-writer checks for geometries thoroughly. I can not think how bad polygons can pass.

Yes, as I said you should not add captions for water polygons to default styles until maps will contain calculated label positions. Or add zoom filter to show them only on higher zooms.

[devemux86]

Yes, as I said you should not add captions for water polygons to default styles until maps will contain calculated label positions.

That could happen if we use label-position=true for all in map-writer or for some in tag-mapping (where now we have it only for buildings)?

[andreynovikov]

Yes. My intent was to leave everything as it was, and add more styles carefully in future. As currently only building polygons have labeling I have added corresponding label-position=true to them.

[andreynovikov]

I have added three extra commits to my branch, have a look.