CoverageSimplifier does not preserve degree-4 boundary nodes

[dr-jts]

Degree-4 Boundary Nodes are vertices which occur in 2 rings which touch only at the vertex. This situation only occurs when the vertex and its adjacent segments are all on the boundary of the coverage.

Degree-4 Boundary Nodes occur where:

• two polygons touch at a single point
• an empty hole touches its shell

(Note that in the case of a hole touching its shell and containing another polygon, the vertex occurs in 3 rings and so is identified as a node.)

These nodes should (probably) be preserved during coverage simplification. Currently the CoverageSimplifier does not recognize that the common vertex is a node, and thus may remove it during simplification.

Example - Touching shells

Simplification tolerance = 4

POLYGON ((0 0, 0 5, 5 6, 10 5, 10 0, 0 0))
POLYGON ((0 10, 5 6, 10 10, 0 10))

Example - Shell touching empty hole

Simplification tolerance = 4

POLYGON ((0 0, 0 20, 10 19, 20 20, 20 0, 0 0), (5 18, 10 19, 15 18, 10 10, 5 18))

[mukoki]

Hey, this case is not exactly the same as the #961 The intersection point between two shells is not identified as a "node" as it is shared by two geometries only ! Not easy to identify this particular case. We can avoid the separation of the two polygons using simplifyInner (nice option indeed!), but this is not exactly the same thing. And unfortunately there is also a case with a hole touching the shell. In the test case of #961, there is such a thing and the test is OK, but I now think this is a strike of luck. To solve it, we may have to change the way unmodifiable nodes are identified. Not sure how to do though.

[dr-jts]

Hey, this case is not exactly the same as the #961

Yes, it's a different issue.

And unfortunately there is also a case with a hole touching the shell.

RIght. I"ve added that as an example.

To solve it, we may have to change the way unmodifiable nodes are identified.

Agreed, that is the problem. The current way of identifying nodes is too simplistic to handle this situation. But it is fast! The challenge is to allow these kinds of nodes to be identified, with decent performance.

[dr-jts]

It may not always be a requirement to preserve nodes between two rings. This could be left as an option. That will allow keeping the faster performance of the current approach.

[dr-jts]

A key point is that Degree-4 Boundary Nodes lie on the boundary of the coverage. This means the segments adjacent them lie on the coverage boundary. Boundary segments are identified during the coverage preparation process. So it may be possible to determine Degree-4 Boundary Nodes by inspecting the boundary segments.

[mukoki]

Maybe an alternative would be to enhance the VertexCounter. If beside the vertex count, we associate a Set gathering all previous/next coordinates, the size of this set should give the degree of th node, isn't it ? The map computation would be heavier but hopefully, it would not change the magnitude of the global time computation. Will have a try.

[dr-jts]

Maybe an alternative would be to enhance the VertexCounter. If beside the vertex count, we associate a Set gathering all previous/next coordinates, the size of this set should give the degree of th node, isn't it ?

I guess this could work. What is needed is for vertices with ring-count = 2, distinguish between ones which are not on the boundary versus ones which are. A vertex with ring-count = 2 has 2, 3, or more incident unique segments. if it only has 2 incident segments, it is not on the boundary; otherwise it is. As you say, counting the number of unique adjacent vertices gives the number of incident segments.

I am concerned about the memory and perhaps processing time for this approach, however. This requires creating a Set for each vertex in the input - of which there can be a very large number.

[dr-jts]

Here's a more concrete design for my idea above.

The vertices of concern are ones which are in boundary segments. The set of boundary segments is already computed (and it is generally much smaller in size than the total number of segments). So it's sufficient to scan the vertices in the boundary segments and determine which ones lie in more than one ring - equivalently, which ones occur in more than 2 segments.

This can be done with a Map<Coordinate, Integer> boundaryVertexSegmentCounter. The set of boundary segments is scanned and the counter is incremented for each segment end vertex. The coordinates with a count > 2 are node points.