Re-running Wagyu on its own output sometimes makes additional changes

[e-n-f]

tests/geometry-test-data/input-polyjson/croatia1.json is an uncleaned border polygon for Croatia at z0, the one that Tippecanoe calls Wagyu to clean when you run

grep Croatia tests/border/in.json | ./tippecanoe -z1 --detect-shared-borders -f -o foo.mbtiles

If you run Wagyu on this polygon:

./fixture-tester -t union -f positive tests/geometry-test-data/input-polyjson/croatia1.json

you get the cleaned polygon in tests/geometry-test-data/input-polyjson/croatia2.json. However, if you rerun Wagyu on that second polygon:

./fixture-tester -t union -f positive tests/geometry-test-data/input-polyjson/croatia2.json

you get a third polygon, the one in tests/geometry-test-data/input-polyjson/croatia3.json. If you run Wagyu again on the third polygon, it is stable and you get an identical polygon back.

I had expected that giving Wagyu a strictly simple polygon that was previously the output of Wagyu would return the identical polygon rather than making additional changes to it.

[e-n-f]

It looks like the first-stage output may actually have some overlapping rings:

but ./tests/run-geometry-tests.sh ./fixture-tester does not complain.

[e-n-f]

It looks like fixture-tester only guarantees that each outer ring of a MultiPolygon is valid with respect to its inner rings, not that the outer rings are free from conflict with each other.

[flippmoke]

This has been really hard to test properly due to #34 but it is something I have been concerned about! Good find!

[e-n-f]

Thanks. I just made a PR (#61) to test for stability (after putting the rings in a canonical order) that I hope will help track down some other similar problems.

[e-n-f]

The stability test finds 1105 of 3120 outputs to be unstable, which is far more than the 105 that boost::is_valid complains about, so instability is not necessarily an indicator of invalidity.

[springmeyer]

Stability seems like a critical issue - thanks for raising this @ericfischer and for adding a test harness for it. What are the next steps to getting wagyu to have stable output the first run?

[flippmoke]

In order to really pursue this with vigor we would need to have #34 properly sorted so that we can actually debug properly with out have all the false negatives. I would also be curious how many of these differences are simply due to a change in the initial position of the ring of a polygon. So we might have a large number of "stability" issues that aren't really anything more then the order of the points.

[e-n-f]

@flippmoke I did already make my test code normalize the order of points within each ring, so these are cases where it changes in some other way.

[springmeyer]

In order to really pursue this with vigor we would need to have #34 properly sorted so that we can actually debug properly with out have all the false negatives.

Hrm, this feels important to de-couple from #34 and possible boost bugs. Why not write our own function to determine validity and stability?

[flippmoke]

Why not write our own function to determine validity and stability?

@springmeyer I have considered such a think already, but this could be a big undertaking I am afraid.

[springmeyer]

@flippmoke - wagyu internally already has code to detect self intersections. What more would be required past that? What makes it a big undertaking?

…

On Jan 9, 2017, at 2:37 PM, Blake Thompson ***@***.***> wrote: Why not write our own function to determine validity and stability? @springmeyer I have considered such a think already, but this could be a big undertaking I am afraid. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub, or mute the thread.

[flippmoke]

@springmeyer we have code to detect where rings meet at the same point, not any code that actually does intersection testing against different segments. Additionally the code within Wagyu might not be ideal to port to an algorithm such as this (although the knowledge from writing Wagyu would help in writing the validity algorithm).

This is its own algorithm in some aspect, which is why I have always trusted the boost geometry, because up until this point it was always very good.

[flippmoke]

I dug into some of the results of these tests and they have to do with two seperate situations:

The first is a situation where the snap rounding when repeated multiple times will result in more snapping then originally occurs. This results in features changing in shapes over time due to this, and unless we ran snap rounding until it stabilized it will continue to be this way. However, our current limited use of snap rounding preserves the original shapes of rings in a better fashion IMO. Therefore, it is likely a speed savings and a good technical reason not to expect stable results when repeatedly running Wagyu.

Additionally, there are sometimes additional points that are kept during processing of wagyu that are collinear in nature. This occurs in the output because it is possible that other rings or vectors might touch these points and these points are important to keep because currently the validity results will throw due to rounding errors in a false manner at these points. During a repeated run, the situation where these are not touching is removed. We could consider this as a possible feature to add to the topology correction portion of wagyu, however, I do not view it as something that is urgent to fix as it might degrade performance.