OpenTopoMap
OpenTopoMap copied to clipboard
der-stefan
Labels of lakes
The labeling of lakes should be improved. Here are some ideas: https://postgis.net/docs/ST_ApproximateMedialAxis.html https://eox.at/2015/12/curved-labels/ https://github.com/ungarj/label_centerlines
At first glance, ApproximateMedialAxis is not what we need ;)
(made with insert into planet_osm_line (osm_id,way,name,man_made) SELECT osm_id,(ST_Dump(ST_ApproximateMedialAxis(way))).geom as way,name,'lakeaxis' as man_made from planet_osm_polygon where osm_id=-32246;)
https://postgis.net/docs/ST_ApproximateMedialAxis.html : "Return an approximate medial axis for the areal input based on its straight skeleton. Uses an SFCGAL specific API when built against a capable version (1.2.0+). Otherwise the function is just a wrapper around ST_StraightSkeleton (slower case)." so I think we see the StraightSkeleton() because I don't have a "capable version (1.2.0+)."
Ok, that doesn't look that bad! I took your example and painted in GIMP the relevant lines in red and a smoothed line in orange:
It is the medial axis, what we see, not the skeleton as I thought. Its not what I expected, because "medial axis" is not "the one and only axis of a polygon" but "every point with same distance to any two points at the border" and the border of a lake may be very complicated...
I tried to simplify the polygon before AproximateMedialAxis()... Thats necessary, because it needs some seconds to calculate it for the Chiemsee and 1s/lake * 8M lakes=3 months. It seems AproximateMedialAxis has random results when we try to simplify the polygon with ST_SimplifyPreserveTopology(way,tolerance). I expected only small changes when I simplify the lake with tolerance=0,10,20m but I got completely different results... For simple lakes (small in west) it seems ok, but not for complex ones.
This area: https://opentopomap.org/#map=12/47.8782/12.3907
I think what we need first is a robust simplification for a lake, something like "10 big squares tiling the water" or "5 circles within this area"
I tested some medial axis (not with ST_ApproximateMedialAxis() but with some kind of routing on a chess board)...
Now the label line for the Chiemsee looks like that:
(larger image)
I think for performance reasons and for design reasons we need something much more simple, something like a part of a circle or a bezier curve with 4 points.
In some strange sense these are the medial axis of lakes:
But I think it's not the best choice for the label. The right one should have a label in a slight line, the left one maybe in a line, maybe even better a horizontal line like now at the broadest part of the lake. Very few lakes (like the Chiemsee) maybe should get a slightly curved line.
Ok, that's a cool approach. We would need to smoothen the line with a polynomial function with degree less or equal to three (auf deutsch tue ich mir leichter: "Polynomfunktion maximal dritter Ordnung").
I think the best smoothening is done with a moving average... I made a demo for all bavarian named natural=water with this still ugly program.
At first I try to get a horizontal line through the st_centroid() of the lake. If this failed I try to get a horizontal line anywhere near the middle, then a diagonal line and if all failed a complicated curve. There is a last step missing: If all failed (or got a too short line) we go back to step 1 and draw a horizontal line...
I still have to play with the criteria for "horizontal or diagonal is good enough"... the Staffelsee could get a better line and at the Sylvensteinsee we take the wrong part of the lake (because there is the point with the greatest distance to the shore). But "more horizontal" means "better performance", now I'm near "some days for all lakes" what is much more better than "some months" in V1 ;)
I made some tests with this program. It will take about 6 hours to get these lines for the labels. It's the question if we want to need such a long time after each database update... Doku for that is in the Wiki (german only)
Great work, @max-dn! By scrolling around over your map, I found some lakes where the result is not optimum.
The line of the "Malchiner See" is too close to its outline:
Especially when zoom out the letters would be placed outside the lake. So a buffer around the straight line should be checked if it intersects with the lake outline. If true, let's not use the simplified straight line, but calculate the full approach.
Something weird happens here:
The algorithm has problems with long, verschlungenen forms like the Edersee, a typical shape for water reservoirs:
But as a human I would not know better how to place the label...
Perhaps we should calculate two centerlines: One for low zoom levels (omitting smaller islands) and one for higher zoom levels with different buffer setting. On e.g. zoom 14 it would not be a problem to have a centerline of the Edersee over its complete length - the label may be repeated on it several times.
good idea to add a buffer:
The weird label in the second example is the fallback. It's a problem to get labels on areas which are more curved lines than areas like these oxbow lakes.
The grid based approach with an adaptive resolution grid is something i have never seen implemented so far - nice to see this works.
The code looks fairly obscure to me (which is largely due to the language not really being ideal for this kind of thing) - so it would be nice if someone could explain a few things:
- I don't quite understand your method of thinning the grid (Ausdünnen der Kästchen here). This step is central in defining the results because it pre-defines the path generated in the next steps.
- Looking over the code it seems you make a lot of assumptions regarding the simplicity of the geometry (or more precisely: of the distance landscape). But i am not actually sure if i interpret the meaning of
dist_to_*/way_to_*correctly.
You currently do not seem to make any provisions to ensure that not only the labeling line is within the lake but also the label. This would be possible to do with the grid based approach but you would need to have knowledge of the size of the label relative to the grid spacing (which would make the results specific to the zoom level).
The grid is thinned by all uninteresting points. Interesting points are all points with only neighbours which are nearer to the border. Uninteresting points are points where one neighbour is nearer to the border while the opposite neighbour is more far away. So
if(dist[i-1][j]<=dist[i][j] && dist[i+1][j]> dist[i][j]) -> node[i][j]=uninteresting
if(dist[i-1][j]> dist[i][j] && dist[i+1][j]<=dist[i][j]) -> uninteresting
if(dist[i][j-1]<=dist[i][j] && dist[i][j+1]> dist[i][j]) -> uninteresting
if(dist[i][j-1]> dist[i][j] && dist[i][j+1]<=dist[i][j]) -> uninteresting
(with j=row, j=column)
">" instead of ">=" because all points in the middle of the lake could have the same distance to the border. Yes that's central, because the shortest line should not touch the border:
way_to_middle/start is the index of the grid point which leads to the middle/start (in sense of "jump to that grid to reach the middle of the lake at the shortest way").
dist_to_middle/start is the cumulated length to the middle through the grid. It's not used now (but maybe in the future). I first defined the starting point of the label with max(dist_to_middle). That leaded to unnecessary long lines and to many curves when we tried to reach the last bay in a lake. More straight lines we get by defining the starting point with max(x^2+y^2) to the middle.
Yes, we don't consider the label text while calculating the lines. That leads to the situation that a short name overlaps the border, because the letters are too heigh.
I still have trouble wrapping my head around this. So dist_to_middle/start is not euclidean distance - i suppose it is meant to represent the shortest 4-connectivity or 8-connectivity walk to the edge. In my eyes it seems kind of weird that your interesting/uninteresting rule actually works (i.e. the interesting grid points always form a continuous line). Not sure if this is contingent to the non-euclidean norm or if it would also work based on euclidean distance. But it seems since your interesting/uninteresting rule is based on 4-connectivity it will only work reliably if there is a 4-connectivity connection in the original grid. In your Chiemsee example the grid point south of the Fraueninsel for example is marked as uninteresting although it would be essential for a label path between the islands there.
Is this method documented somewhere in computer science literature? Because my intuitive approach to this would be to to calculate the raster skeleton with the mid- and endpoints fixed. For a large raster this would likely be slower (since raster skeleton generation is iterative on the whole grid) but for 25x25 points it probably does not make a difference - maybe it would be even faster.
Right, dist_to_middle/start is the shortest 8-connectivity walk to the edge.
But this is only used for finding the start/end of the line (and by some means for the line itself, way_to_middle/start is the next step of this walk for each point, because it has min(dist_to_middle) in the 8-connetivity).
Yes, the interesting/uninteresting rule only works, if there is any 4-connectivity. Here I used the 4-connectivity, because also the dist_to_border is calculated with a 4-connectivity. I didn't try it with an euclidean distance or 8-connectivities, because I doubt that such small straits like between the islands in the Chiemsee are usefull for labels.
No, I didn't have a documentation anywhere. Its the result of starring at grids and lakes for some nights and yes, it looks fairly obscure ;)
Just to show that it doesn't work in all cases: I tried it with a 100x100-grid instead of 25x25. Now the path between the islands has some "interesting" grid points. Surprisingly this path is used because now the path through the main part of the lake is broken...:
With a 25x25 grid, 50x50 or 150x150 everything looks as expected. It does not with 100x100 or 99x99 or 80x80...
Yes, this is the kind of error i had in mind when i said it is weird that your method actually works.
But even without the specific flaw you circled this choice of path is to be expected. The grid does not only function as a method to efficiently implement a line generation algorithm, it also serves to ensure a minimum free space around the line implicitly. If you decrease the grid spacing you also decrease this minimum width. But you don't have explicit control over it.
There is quite a lot of literature on generating raster skeletons from a distance transform (which is essentially what you are doing here) so you might find other algorithms for this that work more reliably. Or as said you could try a simple iterative thinning from the edge method.
I checked some labels of lakes within different zones and this development in most cases appears to offer nice results, further improving the outstanding quality of this map; thank you @max-dn
I'll collect what we need for the next version:
- A more robust and established algorithm to thinn out the grid ;) (thanks to @imagico. I did not think about "vectorizing grids", only about "routes through the chessboard")
- A quality measurement for "centeredness" of the diagonal lines. If the line is too near to the shore, we will try a curve.
- If the last option (curve) does not yield a good result, we do not take the worst option (central horizontal) but e.g. also a reasonably good diagonal. This means that we need a measurement for the quality of the previously tried options
- In addition to the natural=bay, we also render natural=strait (both surfaces and paths) on our way to the award for Norwegian coast lines.
In the current style there is an issue with the text rendering: https://github.com/der-stefan/OpenTopoMap/blob/95f308d43c80f6d5ae03dc47527d139d1d9895b8/mapnik/styles-otm/text-water-lowzoom.xml#L5
In detail: horizontal-alignment="adjust" sometimes works as expected, sometimes it simply doesn't show any label.
Could be the same problem as mentioned here: mapnik/mapnik/issues/3662
we also render natural=strait (both surfaces and paths)
Would it be useful to render curved labels also for polygonal valleys (natural=valley on areas)? https://overpass-turbo.eu/s/yX1 https://opentopomap.org/#map=14/45.88538/10.24973
@Ircama Yes, it would make sense to use this algorithm for any kind of "natural=*" polynom. Let's see what comes next.
I will try to use this kind of label for some kind of areas (collected in #170). But perhaps I should improve this labels first. In this issue here there are some good ideas we didn't implement yet and somewhere in my mind there is a voice "do it with splines" but I don't know how to do it exactly ;)
OpenMapTile also creates center labels: https://openmaptiles.org/schema/#water_name from https://github.com/lukasmartinelli/osm-lakelines
OpenMapTile also creates center labels
They are using https://github.com/ungarj/label_centerlines and do a "ST_SimplifyPreserveTopology(geometry, 100)" for each lake and only for lakes with a size of 2*10^6 units... I have to find out why ;) I think the same processing is used for the natural areas at http://maps.eox.at/ There it looks fine.
Is there a generated shapefile or .sql file that could be used in other projects?
Not as a regular service, sorry. But if you need a sql file for testing, I can create a dump of lowzoom_lakelabel.