Geometry clipping

[ARolek]

Possible algos:

• Efficient Parallel and Distributed Algorithms for
  GIS Polygon Overlay Processing
• Vatti clipping algorithm
  p56-vatti.pdf

[ARolek]

@gdey

[gdey]

Quick update. Have clipping working for most tiles. However, there are a few polygons that get clipped to nothing, that I believe should not be.

As you can see from the missing tile:

I'm currently working on tooling to help me debug what is going on here. Once this is solved, clipping will be merged in for fuller testing. Initially, we will be rolling it out disabled. Enabled the setting by setting the environment variable TEGOLA_CLIPPING to yes.

[ARolek]

@gdey I was able to extract the geometries from the OSM database that were causing clipping issues as shown in the following screen shots:

Using the following SQL

SELECT
  ST_AsBinary(geometry) AS geometry, 
  id, 
  osm_id, 
  name, 
  type 
FROM 
  osm_waterways 
WHERE 
  geometry && ST_MakeEnvelope(254382.43009765446,5310233.228288574,256828.4150024396,5307787.243383789)

The attached output has 3 geometries in WKB format with their accompanying attributes.

osm-waterway-output.txt

[ARolek]

One more isolated test case

Using the following SQL

SELECT 
  id, 
  osm_id, 
  name, 
  type, 
  ST_AsBinary(geometry) AS geometry
FROM 
  osm_roads
WHERE 
  geometry && ST_MakeEnvelope(-1.3644926791343994e+07,5.657563084768066e+06,-1.3644315295117797e+07,5.65695158854187e+06)

The attached output has 2 geometries in WKB format with their accompanying attributes.

osm-roads-output.txt

[allspatial]

Hi @ARolek and @gdey, I am getting the same type of errors with my line layers frequently. I am also getting (occasionally) the polygon error described by @gdey above, so whole tiles would be completely missing from my map. If I can help with anything (logged SQL statements, etc.) to solve that issue faster please let me know. The clipping issue is the main reason that prevents me from going fully live with my page currently. I would provide a link early next week after updating my server so you can test on my mapbox-gl-js application/page if this is of help. Many thanks for your great efforts!

[gdey]

Hi @allspatial !

First off, thank you for using the software!

Have you tried the latest build from this branch? I push up a few more fixes late last night. Also, be aware that by default the clipping is turned off and you have to setting the environmental variable TEGOLLA_CLIPPING to mvt, TEGOLA_CLIPPING="mvt" not to yes as I had in said in a different comment.

I'm looking into more bugs that @ARolek ARolek has pointed out to me. I, also, have pushed out a small utility to help me get test cases. I'll write up a quick usage guide for it after I make some improvements to make generating the test cases easier.

[allspatial]

Hi @gdey, thanks for your swift reply! The changes from last night I haven't tried yet. Will do so right now. The "mvt" I already figured out.

[allspatial]

Hi @gdey, I tested the latest clipping_3 branch. Line clipping seems to work better now, polygons still disappear (see screenshot). And I can now see the tile boundaries, I assume you are showing them for testing purposes. Many thanks!

[gdey]

@allspatial No, those gray lines should not be there. I think I have to increase the overlap buffer for that. I've got a few more fix coming with a new push.

Thank you for looking into this.

[allspatial]

Hi @gdey and @ARolek, issues #90, #100 and #56 could probably be merged since they all refer to the clipping. It would reduce the number of issues at once without much effort ;-). Taking into account also issue #102 which would be the recommended Tegola version to test now with regard to improved geometry clipping and MVT specification compliance? By the way, here is the link to the application I am working on, just to have another test case:
https://www.webgis.gov.sc/mobile/

Thanks again!

[allspatial]

Hi @gdey, I just pulled and tested the latest v0.4.0 branch. The line clipping works much better and there are no fictive lines anymore crossing the screen. However, there is one issue I found where a part of the line would be completely missing (screenshot "shot3" attached). Regarding the polygons I still get the issue of tiles completely missing. And currently I am seeing the tile boundaries. If you need any geometries from my side to test please let me know. Many thanks!!

[ARolek]

@allspatial thanks for testing out the v0.4.0 branch and providing the screen shots. We have a lot of effort going into clipping right now and we believe we have identified the clipping issues you're showing screenshots 1 and 2. The primary issue has to do with scaling and what happens to the geometries at lower zoom levels. After scaling the geometries can become invalid which causes the clipping algorithm fail in certain situations (as you're seeing). For the most part we only see the issue at low zooms. Do you see issues when zoomed in?

The second issue has to do with our tile buffer which we're also working on. The tile buffer needs to extend past the tile extent to ensure smooth transitions from tile to tile. We're already on it and hope to have a solution soon. Would you like me to ping you next time the v0.4.0 branch is updated?

[gdey]

@allspatial Thanks for the update. I found some issues with the way I have been doing things, that is requiring a deeper change. So, I am working through that change right now.

The issue with the borders is because my buffer zone around the title is not large enough. I will be increasing that as soon as I get better handle of the clipping.

One of the issue is that once we scale the polygons to the the correct zoom level. The polygon becomes invalid, the clipping also expects valid polygons (concave, non-intersecting) so it ends up not clipping things correctly.

I'm working through these things.

Thank you for all the info.

[allspatial]

Hi @ARolek and @gdey, many thanks for your efforts! The issue with the missing tiles for the polygon layer I also get at higher zoom levels. And yes, please let me know once the v0.4.0 branch has been updated. However, I am frequently checking anyway ;-). Thanks again!!!

[gdey]

@allspatial Just pushed up some more changes to the v0.4.0 branch. Let me know if that works better. It is slower, and will work on speeding things up once I have things working correctly.

[allspatial]

Hi @gdey, much better now! Lines look all good and tile boundaries don't show anymore. The only remaining issue is the tiles for polygon layers that are still missing sometimes. Many thanks!

[jj0hns0n]

@ARolek is this the same thing we see at low zo in the OSM

…

On Sat, Apr 15, 2017 at 10:36 Michael Wagner ***@***.***> wrote: Ho @gdey <https://github.com/gdey>, much better now! Lines look all good and tile boundaries don't show anymore. The only remaining issue is the tiles for polygon layers that are still missing sometimes. Many thanks! [image: shot] <https://cloud.githubusercontent.com/assets/12534211/25065593/8e004f1c-2223-11e7-833d-f37c431077ec.png> — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#56 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAe43kU75nz1qyz5Mroo1TmG10FemLz4ks5rwQAfgaJpZM4JbLym> .

[ARolek]

@allspatial thanks again for the tests. What zoom level are you at? Also we have a new tool that can dump WKB for our test suite. @gdey would it be helpful to have a dump of the tile for a test case?

[allspatial]

Hi @ARolek and @gdey , I observed the issue at zoom levels 12 to 16 mostly in my case:
Seychelles WebGIS

And yes, let me know if you need a geometry dump.
Many thanks!

[allspatial]

Hi @gdey and @ARolek, after updating to the latest v0.4.0 version it seems the number of geometry issues has increased again. mapbox-gl-js also shows a warning that the tiles are not tile spec v2 conform which could cause rendering issues. I can't tell though how serious this warning is and if it really causes some of the issues you can see in the attached screenshots or if all results from the clipping. Many thanks!

[ARolek]

@allspatial the warnings in the console are because we changed our spec version to 1 per the issue opened by the creator of the spec (Following V2 Specification). Once we're compliant with V2 spec we will change the version encoding on those warnings will go away.

Now for the clipping changes. In order to match the suggested steps to handle clipping correctly we have had to implement geometry simplification, scaling and validity checking / make valid steps. You probably noticed some performance slowdown in the newest version rev on v0.4.0. The new processing steps position us for producing better clipping results, smaller tiles and OGC compliant geometries. We have not optimized the new processing pipeline hence the performance hit. Also the new pipeline is causing some regressions in clipping which you're seeing here.

We're going to start our refactor efforts next week. I will give you a heads up on the next code push. Thanks for all the help with your testing.

[allspatial]

Hi @ARolek, many thanks for the clarification! That sounds all good and I am very much looking forward. Tegola is a great tool and with the clipping fixed it will be perfect ;-).

[allspatial]

Hi @ARolek and @gdey, did you by chance find the time to do some refactoring/improvement on the clipping part? If so - in what branch would I find that? With the current version of v0.4.0 I can't go live (see attached). Many thanks!!!

[ARolek]

@allspatial we have some major clipping improvements coming queued up. Hoping to merge into his ranch next week. In the mean time I think what you're seeing is the clipping is not turned on. Can you check if the environment var TEGOLA_CLIPPING="mvt" is set?

[allspatial]

Hi @ARolek, I indeed forgot to set the clipping parameter this time. I apologise for the "false alarm".

[gdey]

@allspatial No worries, always appreciate people keeping an eye out for possible regressions. I've got more changes, coming. Need to push up the changes I have from last week to the issue-56 branch( https://github.com/terranodo/tegola/tree/issue-56 ). I have gotten few more fixes. I'm still seeing issues that I am working through one by one.

[gdey]

@allspatial Hey I have the latest version of the clipping code pushed to issue_56 branch. Be warned it's slow now, and I have to go through a round of optimizations. I believe I have it clipping most things correctly now. At least things looked good when I did a quick skim.

I have not had a chance to zoom around the global map searching for issues.

[Wykks]

Hi !
Thanks you for this software !
I have the same issue as allspatial, I'm gettings something like this (#56 (comment)) in the master branch.

I tried the issue-56 branch (with and without your latest changes) and it's worse, nothing appears, even with TEGOLA_CLIPPING="mvt". How can I help to debug this ?

edit : I'm using 4326 srid

[gdey]

@Wykks Could you post an image. Also, with my latest changes, it takes a long while to generate the tiles. The reason being the validation process checks every segment in a feature against every other segment in that feature to make sure that no two segments that are not direct neighbors cross. The crossing can occur after simplification — this was the source of some of the clipping issues. I will be profiling and see how I can speed this up as it's unusable at current. I am trying to get clipping correct first before optimizing it.

[Wykks]

Sure !

With issue-56 without TEGOLA_CLIPPING="mvt" :

With issue-56 with TEGOLA_CLIPPING="mvt" :

With master :

With master + zoom :

(Mapbox-gl only, work fine with leaflet vectorgrid)

Data used : https://github.com/gregoiredavid/france-geojson/blob/master/departements.geojson (imported to postgis with ogr2ogr)

[gdey]

@Wykks Thanks! I'll take a look at it later today. I really need to get some sleep. :P

[skinkie]

#132 seem to show the same issue. At mapbox the suggestion is done that it is due to the 'buffer-size' of the tiles. Would that ring a bell?

[skinkie]

Please take a peak at this comment:
mapbox/mapbox-gl-js#5175 (comment)

[gdey]

This is now done.