Replacing isSolidTile() for vector tiles

[nyurik]

trafficstars

3.5 has removed the isSolidTile() we have been using to decide between storing the tile vs not storing and using overzoom on the fly. Now that it is gone, could you suggest some algorithm that would achieve a similar result?

My implementation attempt is to only save a vector tile if it either:

• empty() is true
• layers() returns nothing
• layers() returns exactly one element that I have whitelisted, e.g. "water"

I suspect that this won't work very well for the locations around the coasts - because land is not stored as a separate layer, only water and other land use is, so the tile may contain just the water and nothing, and thus it won't get saved even though it probably should.

cc: @springmeyer

[springmeyer]

@nyurik I have been discussing with @flippmoke about this. IsSolid was dropped because porting it to the vector tile spec v2 code would have been challenging and it was buggy/not complete. But there are rumblings of bringing it back in some form because alternatives are difficult. /cc @xrwang @ajashton

[nyurik]

@springmeyer thanks, that would be awesome. In the mean time, how wrong do you think the above logic would be? It would be fairly difficult for us to downgrade at this point.

[springmeyer]

I'm having trouble following your usage well enough to comment intelligently (brain power low at the moment) so I'll just explain how isSolid used to work as per https://github.com/mapbox/mapnik-vector-tile/blob/0.14.x/src/vector_tile_util.ipp#L76-L168:

• if tile has no layers then isSolid == true
• if tile looks like pure "squares" (one or more layers that all look like the resolve of a clipped polygon that extended outside of the tile bounds on all sides) then isSolid == true
• checks for data that don't look like "squares" are done to return fast for non-solid tiles:
  • if a geometry vertex falls within a tile extent, return early as isSolid == false
  • if the area of a geometry is less than the area of the tile, return early as isSolid == false
  • if a geometry intersects with a tile edge, return early as isSolid == false
  • we hope that if all the above geometry checks pass then what remains is likely a "square". @flippmoke found (or at least thinks) there are a lot of edge cases that were slipping through and getting called solid that were not and hence this code was removed.

[lightmare]

edge cases that were slipping through

Are we talking about polygons (without holes) somehow winding around the tile? If that's the case, I'd suggest adding these tests:

• check than an arbitrary point, e.g. the tile's center, lies within the polygon.
• while looking for edge intersections, also take note of which half-lines -- extensions of the tile's edges starting at its corners -- the polygon's edges touch. Basically divide the outside of the tile by extending its edges into 8 regions. A polygon cannot cover the whole tile unless it touches all the outer regions.

The area test should not be necessary then.

[springmeyer]

Are we talking about polygons (without holes) somehow winding around the tile?

@lightmare yes: we are talking about a situation like continuous land or water polygons getting tiled. All of the tiles that get created for those polygon layers that do not intersect with the geometry edges are going to be clipped squares representing the tile extent+buffer_size.

[nyurik]

@jkroll20, hi, while there is still a discussion about https://github.com/mapnik/mapnik/issues/1113, could you take a look at this issue? At some point a while back, the isSolidTile() was removed from the node's mapnik wrapper. This functionality is highly needed, and will help us significantly reduce storage requirements. Thanks!

[flippmoke]

@nyurik We removed isSolid after a lot of thought in 3.5. I will do my best to explain why this was done!

Vector tiles by their nature are approximations of data, the data is not exact copies of the source data. In the past we were using IsSolidto determine when we could possibly skip data below from being tiled and using the same data set.

Lets take the example below. Assume for simplicity that our vector tile coordinates are the grid below and we are creating a 6x6 tile (extent of 6) that is highlighted in red. The source data is in green and the rounding to coordinates is in blue.

According to the Vector Tile 2.0 Specification the blue spike inward into the polygon is not valid and therefore it must be removed. Therefore in this situation - the tile is "Solid" but the source data is not "Solid".

Unless the vector tile carried data about the "solidness" of the source data this is not something that the Vector Tile object in node-mapnik can use, as we load Vector Tiles in a variety of manners.

This also complicates situation where solidness might be used in pyramid tilling, because future levels below this might simply assume that no new tile must be rendered, but the source data shows otherwise!

[ajashton]

@flippmoke in practice the issue you're illustrating has not been an issue for our use case of rendering world maps due to the multiple data layers involved, buffers outside the tile bounds, the reasonable resolution a 4096 grid provides, and avoiding pyramid rendering at lower zoom levels. We're finding the increased time, processing power, and storage requirements without issolid to be quite significant. This is even after taking manual steps to avoid rendering large solid areas such as oceans and the Greenland & Antarctic ice sheets.

[flippmoke]

@ajashton It has not been an issue for some of the geographic features in OSM, however, in other datasets this has definitely been an issue.

[nyurik]

@flippmoke are you basically saying that isSolid() for vector tiles is not 100% perfect for some use cases? If so, lets enable it for those of us who are ok with imperfection, but need the massive storage and simplicity benefit it provides, and put a big warning on it that in some corner cases it is not ideal - allowing each developer to decide for themselves if they want to use it or not. Otherwise people will be forced to fork this lib or to add this one little feature in some crazy node + c++ workaround, which won't be good for anyone.

[flippmoke]

@nyurik @ajashton

In the past we relied on 3 different flags to describe how a vector tile was created. They are solid, empty, and painted.

Definitions

Solid is a check to see if the current tile contains a set of information that is constant across its entire area such that any tiles created below it with a pyramid tiling scheme will be the same as the tile that is solid.

Empty is a check to see if the current tile contains no information and therefore the tiles below it do not need to be processed when using the pyramid tiling scheme.

Painted is a check to see if data exists in the source dataset in a tile. This is important because in pyramid tiling it is possible to have empty tiles that might contain data at higher zoom levels.

Solid vs Empty

Geometry	Can Be Empty	Can Be Solid
Point	Yes	No
Line	Yes	No
Polygon	Yes	Yes

We can never use solid logic on points and lines, because by definition they can never envelope the entire tile.

Painted

Geometry	Requires Painted Logic
Point	No
Line	Yes
Polygon	Yes

Points do not require painting logic because they will never be reduced away. Therefore if a point exists the layer in the tile is always painted.

• Lines
  • Can be reduced to points and discarded
• Polygons
  • Can be reduced to points and discarded
  • Can be reduced to lines and discarded

Different geometry types complicate everything

Lets consider a vector tile that has a single layer that contains both cities and states. Features will either be a city or a state.

• Cities are point data
• States are polygons

Assuming you have a point within the tile is it ever solid? Should solid be only true if a vector tile only contains polygon data?

What about buffers?

Should the area around a vector tile be solid or not if the buffer is not described for the vector tile and the buffered area is not a perfect square?

If you do not consider a buffer, then rounding near the edges will result in solidness such at this example where the green box has been rounded to the edge where it is on edges. But it does not fit the definition of "solid" above. That is the intent is it not?

Putting the logic into the encoder

Clearly the encoder is the place this logic should lie, not within node-mapnik (so mapnik-vector-tile). However, after considering this we realized that to properly deal with this problem it involved doing complex checks and complex logic. The real goal / requirement here is:

Do not make more vector tiles if:

• The data is the same for all zoom levels higher
• There is no data in the higher zoom levels

So back to your question:

@flippmoke are you basically saying that isSolid() for vector tiles is not 100% perfect for some use cases? If so, lets enable it for those of us who are ok with imperfection, but need the massive storage and simplicity benefit it provides, and put a big warning on it that in some corner cases it is not ideal - allowing each developer to decide for themselves if they want to use it or not.

I do not think that this problem should be solved where it is in node-mapnik. The decision and control of this should be done at a higher level either in the decision process of which tiles to create not as logic tied to a tile after it is created. If we do not we are being forced to make a ton of non trivial assumptions that are not easy to document in an IsSolid functionality.

[nyurik]

@ajashton, do you have a workaround for this in the mean time? I'm thinking of how to improve our tilegen. Thx

[ajashton]

We have a partial workaround for very large solid areas such as oceans and the Greenland ice sheet. We are basically pre-calculating tiled versions of these shapes in a PostGIS database and marking solid tiles based on their shape. These areas are then excluded from our query to force the solid tiles into being truly empty tiles.

A lot of extra work has to be done in order to make sure "solid" shapes get marked as not solid if they intersect with any shapes from other tables, and even then some problems still arise. And we are still rendering & storing many more tiles than we need to due to other polygons such as forests and lakes.