v. generalize fails to generalize polygons in a random manner

[dido]

Trying to generalize Greece shoreline + landmass, polygons fishnet'ed with cell size of 5000 m. Random polygons are not being generalized while they should be. If fishnet is made bigger (e.g 50 km cell size), then more non-generalized polygons are visible.

Input is topologically error-free (no overlaps or gaps in input data). v.generalize output is as follows:

v.generalize --overwrite input=c100_sea_dis_fish@Greece_UTM output=c100_sea_G120 method=douglas threshold=120
WARNING: Vector map <c100_sea_G120> already exists and will be overwritten
Copying features...
Building topology for vector map <c100_sea_G120@Greece_UTM>...
Registering primitives...
105726 primitives registered
832947 vertices registered
Building areas...
36099 areas built
2921 isles built
Attaching islands...
Attaching centroids...
Number of nodes: 36449
Number of primitives: 105726
Number of points: 0
Number of lines: 0
Number of boundaries: 69627
Number of centroids: 36099
Number of areas: 36099
Number of isles: 2921
-----------------------------------------------------
Generalization (douglas)...
Using threshold: 120 meters
WARNING: 1953 boundaries were not modified because modification would damage topology
WARNING: 1951 lines/boundaries were not modified due to over-simplification
-----------------------------------------------------
Building topology for vector map <c100_sea_G120@Greece_UTM>...
Registering primitives...
105726 primitives registered
323843 vertices registered
Building areas...
36099 areas built
2921 isles built
Attaching islands...
Attaching centroids...
Number of nodes: 36449
Number of primitives: 105726
Number of points: 0
Number of lines: 0
Number of boundaries: 69627
Number of centroids: 36099
Number of areas: 36099
Number of isles: 2921
-----------------------------------------------------
v.generalize complete. Number of vertices for selected features reduced from 796848 to 287744 (36% remaining)
(Mon May 09 22:54:11 2016) Command finished (1 min 42 sec)

[dido]

Added attachments with generalized data over the original data, where the non-generalized polygons are well-visible.

Dataset can be provided upon request. GRASS version is 7.0.4 (missing in the list). How can I modify the description -- looks ugly after I pasted the GRASS output :-)

[neteler]

Replying to dido:

Added attachments with generalized data over the original data, where the non-generalized polygons are well-visible.

Dataset can be provided upon request. GRASS version is 7.0.4 (missing in the list).

Thanks for the hint, added to the list.

How can I modify the description -- looks ugly after I pasted the GRASS output :-)

You need to encapsulate code in triple "{" ... "}" chars as per WikiFormatting. Updated as well.

[mmetz]

Replying to dido:

Added attachments with generalized data over the original data, where the non-generalized polygons are well-visible.

Area boundaries are not generalized if the modification would damage topology or if the boundaries would be over-generalized (zero-length boundaries). In your output, you see

Generalization (douglas)...
Using threshold: 120 meters
WARNING: 1953 boundaries were not modified because modification would damage topology
WARNING: 1951 lines/boundaries were not modified due to over-simplification

That means the not generalized boundaries are not random, instead their generalization would cause errors, they should not be generalized and they are copied unmodified to the output. Try a smaller threshold or stepwise increase the threshold using the output of the previous simplification as input for the next simplification.

[dido]

Hi,

the reason why non-generalized polygons appear in the output is certainly clear. My point is that none of these polygons will be damaged due to generalization over-simplification, so I suspect a v.generalize algorithm problem here.

As an example find attached 4 pairs of shapefiles that produce non-simplified polygons.

[mmetz]

Replying to dido:

Hi,

the reason why non-generalized polygons appear in the output is certainly clear. My point is that none of these polygons will be damaged due to generalization over-simplification, so I suspect a v.generalize algorithm problem here.

As an example find attached 4 pairs of shapefiles that produce non-simplified polygons.

I modified v.generalize a bit in my local copy to write out those modified boundaries that would damage topology. In each of your test cases. v.generalize is correct in not generalizing these boundaries. They would collapse to a point, intersect with themselves, intersect with another boundary, or produce a zero-size area. See screenshots in attached topo_errors.zip.

[mmetz]

topological errors for v_generalize_test_polygons.zip

[dido]

OK, I get what's breaking up generalization.

Talking about test1.png - it's a piece of polygon boundary that's several hundred meters in length, unfortunately causing a self-intersection. Why v.generalize discards the whole polygon side that's several kilometers long but not the problematic sector only?

Actually in my first tryout the whole area was not fishnet'ed to 5000x5000 m cells so small problematic sectors resulted to tens and hundreds of kilometers of shoreline being not generalized at all, making the tool completely unpredictable in the output.

[mmetz]

Replying to dido:

OK, I get what's breaking up generalization.

Talking about test1.png - it's a piece of polygon boundary that's several hundred meters in length, unfortunately causing a self-intersection. Why v.generalize discards the whole polygon side that's several kilometers long but not the problematic sector only?

Because implementing such a feature would slow down v.generalize considerably, it is already rather slow for complex vectors. Splicing in an original part of the boundary into the modified version could also cause quite a few other problems (no common vertex to start with), and topological correctness is not guaranteed. Note that boundaries and polygons are not the same.

Actually in my first tryout the whole area was not fishnet'ed to 5000x5000 m cells so small problematic sectors resulted to tens and hundreds of kilometers of shoreline being not generalized at all, making the tool completely unpredictable in the output.

As I suggested previously, try stepwise generalization, starting with a small threshold, then increasing the threshold and using the output of the previous run as input for the next run. In your case, a threshold of 120 seems rather large considering the vertex density of the boundaries.

I suggest to close the ticket as invalid because v.generalize correctly discards boundary modifications that would result in errors.

[dido]

OK, I will close the issue due to the fact that an algo rework of v.generalize not to leave too long non-generalized boundaries behind will be too costly to be implemented.

Still this particular use-case needs a good explanation in the v.generalize manual. I could not find any clue that the generalize algorithm will simply stop and retain the boundary untouched IF any topology damage occurs during processing. The good workarounds must also find a way to the manual -- to slice-down the input adequately, then to apply v.generalize and v.dissolve, or to apply multiple v.generalize steps with increasing distance.

Regards, Dido

[neteler]

Replying to dido:

Still this particular use-case needs a good explanation in the v.generalize manual. I could not find any clue that the generalize algorithm will simply stop and retain the boundary untouched IF any topology damage occurs during processing. The good workarounds must also find a way to the manual -- to slice-down the input adequately, then to apply v.generalize and v.dissolve, or to apply multiple v.generalize steps with increasing distance.

Please consider to write a few sentences for the manual page (post here, I'll merge it in).

Thanks!

[mmetz]

Replying to neteler:

Replying to dido:

Still this particular use-case needs a good explanation in the v.generalize manual. I could not find any clue that the generalize algorithm will simply stop and retain the boundary untouched IF any topology damage occurs during processing. The good workarounds must also find a way to the manual -- to slice-down the input adequately, then to apply v.generalize and v.dissolve, or to apply multiple v.generalize steps with increasing distance.

Please consider to write a few sentences for the manual page (post here, I'll merge it in).

I have updated the manual and changed the error output to contain errors in trunk r68451. The error output now allows to understand why a particular feature was not generalized.