New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Labels of lakes #134

Open
der-stefan opened this Issue Dec 1, 2017 · 24 comments

Comments

Projects
None yet
4 participants
@der-stefan
Copy link
Owner

der-stefan commented Dec 1, 2017

@max-dn

This comment has been minimized.

Copy link
Contributor

max-dn commented Dec 19, 2017

At first glance, ApproximateMedialAxis is not what we need ;)
ApproximateMedialAxis
(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+)."

@der-stefan

This comment has been minimized.

Copy link
Owner Author

der-stefan commented Dec 19, 2017

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:
lake-lines

@max-dn

This comment has been minimized.

Copy link
Contributor

max-dn commented Dec 22, 2017

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.

otm_medialaxis_simplify
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"

@max-dn

This comment has been minimized.

Copy link
Contributor

max-dn commented Dec 29, 2017

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:
Chiemsee chess
(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:
Seeleitensee chess
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.

@der-stefan

This comment has been minimized.

Copy link
Owner Author

der-stefan commented Dec 29, 2017

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").

@max-dn

This comment has been minimized.

Copy link
Contributor

max-dn commented Jan 13, 2018

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 ;)

@max-dn

This comment has been minimized.

Copy link
Contributor

max-dn commented May 5, 2018

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)

@der-stefan

This comment has been minimized.

Copy link
Owner Author

der-stefan commented May 6, 2018

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:
lake1
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:
lake2

The algorithm has problems with long, verschlungenen forms like the Edersee, a typical shape for water reservoirs:
lake3
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.

@max-dn

This comment has been minimized.

Copy link
Contributor

max-dn commented May 6, 2018

good idea to add a buffer:
Machiner See

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.

@max-dn max-dn referenced this issue May 6, 2018

Merged

Lakelabel #154

@der-stefan

This comment has been minimized.

Copy link
Owner Author

der-stefan commented May 8, 2018

This looks very nice:
lake4

@imagico

This comment has been minimized.

Copy link

imagico commented May 11, 2018

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).

@max-dn

This comment has been minimized.

Copy link
Contributor

max-dn commented May 11, 2018

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:

Hofstätter See

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.

Chiemsee x+y/dist_to_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.

@imagico

This comment has been minimized.

Copy link

imagico commented May 11, 2018

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.

@max-dn

This comment has been minimized.

Copy link
Contributor

max-dn commented May 11, 2018

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.
Chiemsee islands

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 ;)

@max-dn

This comment has been minimized.

Copy link
Contributor

max-dn commented May 12, 2018

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...:
boken path in Chiemsee

With a 25x25 grid, 50x50 or 150x150 everything looks as expected. It does not with 100x100 or 99x99 or 80x80...

@imagico

This comment has been minimized.

Copy link

imagico commented May 12, 2018

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.

@Ircama

This comment has been minimized.

Copy link

Ircama commented May 13, 2018

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

@max-dn

This comment has been minimized.

Copy link
Contributor

max-dn commented May 17, 2018

I'll collect what we need for the next version:

  1. 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")
  2. A quality measurement for "centeredness" of the diagonal lines. If the line is too near to the shore, we will try a curve.
  3. 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
  4. 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.
@der-stefan

This comment has been minimized.

Copy link
Owner Author

der-stefan commented May 17, 2018

In the current style there is an issue with the text rendering:

<TextSymbolizer fontset-name="sans-oblique" fill="#2020ff" halo-radius="1" halo-fill="rgba(255,255,255,0.8)" horizontal-alignment="adjust" placement="line" size="15" placement-type="list">[name]

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

@Ircama

This comment has been minimized.

Copy link

Ircama commented May 20, 2018

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

@der-stefan

This comment has been minimized.

Copy link
Owner Author

der-stefan commented Jul 10, 2018

@Ircama Yes, it would make sense to use this algorithm for any kind of "natural=*" polynom. Let's see what comes next.

@max-dn

This comment has been minimized.

Copy link
Contributor

max-dn commented Jul 14, 2018

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 ;)

@der-stefan

This comment has been minimized.

Copy link
Owner Author

der-stefan commented Aug 7, 2018

@max-dn

This comment has been minimized.

Copy link
Contributor

max-dn commented Aug 7, 2018

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment