[Patch] MultipolygonTest doesn't find some errors

[GerdP]

When the MultipolygonTest detects crossing ways it creates a new TestError
instance and passes all nodes of the ways as parameter highlighted.
When the user clicks on "Zoom to problem" (Shortcut "6") in the "Validation Results"
he expects to see the place where the lines cross, instead he sees both (joined) ways.
With complex mp this can be quite useless if a small inner way crosses the outer way.
Proably the best solution in this case would be to calculate the positions of the points where
the ways are crossing and zoom so that all are visible.
Don't know if this could be done, but the attached patch implements a compromise:
If the size of the bbox of one of the two ways is less than 10% of the other, highlight
only the nodes of the smaller one.

[GerdP]

sample osm file

[GerdP]

I noticed that the validator (MultipolygonTest.java) ignores all errors which are detected by the MultipolygonBuilder,
e.g. overlapping areas. I started a complete rewrite of this test to make it much faster and more reliable,
maybe I can also improve the "Zoom to problem" functionality, but I guess it will take a few days.
If anybody is already working on this, please let me know.

[GerdP]

I've now attached improve_MultipolygonTest_v1.patch which changes MultipolygonTest
so that it uses the same algo as CrossingWays.java to find intersecting polygons.
In many cases this will also improve the "zoom on error" functionality.
Besides that the test is much faster in case of complex mp.

The old (unpatched) code did not find intersections were none of the polygon points was inside
the intersecting area (see ways w5 + w6 in mp-val2..osm), also the result depended
on the order of ways in the relation (w3+w4).
It also did not find simple intersections (way w10)

Open questions:
a) Is way w9 a correct inner way? It would be easy to detect the simple
self intersection as well.
b) The unit test data file (\josm\core\data_nodist\multipolygon.osm) contains a few nested
mp, eg. "Example 8 (03)" (outer inside inner which is inside outer).
My understanding is that these are not correct, but the old code doesn't complain.

[GerdP]

Found a stupid typo in the patch, please use v2

[GerdP]

Argh, sorry, tested within Eclipse but changed the patch manually, v2 is also nonsense.
v3 is on the way.

[Don-vip]

The patch introduces 39 checkstyle violations, can you please configure Checkstyle plugin in your IDE? Or check them manually as described here: DevelopersGuide/StyleGuide#Howyourcodeshouldlooklike

[Don-vip]

To be sure, is for (int i = 0; i+1 < outer.size(); i++) { what you meant to write?

[Don-vip]

v4 = v3 + checkstyle

[GerdP]

Replying to Don-vip:

To be sure, is for (int i = 0; i+1 < outer.size(); i++) { what you meant to write?

Oops, it should be for (int i = 0; i < outer.size(); i++) {
I first used for j = i+1 in the inner loop, then found out that that doesn't work,
ad forgot to change the outer loop.

And sorry for the style problems, I used the default formatter in Eclipse. Will check
the checkstyle plugin tomorrow.

[GerdP]

v5 : like v4, but added some javadoc

BTW: I'd prefer not to nearly duplicate the code in CrossingWays.java, but that
might be done in a 2nd refactoring step.

[anonymous]

v6 also implements a test for repeated multipolygon members and adds a command to fix them.

[GerdP]

I've created v6 of the patch to address the problem discussed in the German forum:
​http://forum.openstreetmap.org/viewtopic.php?id=55275
The attached file rel6040654.osm.bz2 shows the original data with all the duplicated members.
Some of the performance problems mentioned in the discussion are already solved.

[GerdP]

v7 based on changes in 13086.patch (see #13086), reduces code duplication a bit.

[GerdP]

v8 also finds intersections at nodes, this fixes #13518. Make sure to apply 13086.patch first.

[GerdP]

improve_MultipolygonTest_v8b.patch : like v8, but with josm/core as base directory

[GerdP]

I've now attached a modified version of multipolygon.osm which is used in MultipolygonTestTest. I've added some relations which are not flagged by the current code in r10982. The patch improve_MultipolygonTest_v9.patch fixes these issues
(and also some false positives from previous patches).
It still requires 13086.patch from #13086.

[GerdP]

v10 removes the dependency on MultipolygonCache as this may contain out-aged data (see #13591), instead it create a new Multipolygon instance and uses its EastNorth polygons instead of calculating new LatLon polygons.
The changes in class Multipolygon are optional. Without them MultipolygonTest will report "Multipolygon ways share node(s)" when the MP contains duplicate members.

[bastiK]

What is the state of the last patch? I found a TODO entry and commented code. It seems that the patch is a collection of multiple improvements. You can split it into multiple parts if one is still work in progress. This way at least some parts can be applied.

One comment about RemoveRepeatedRelationMembersCommand: Unless it is needed at other places or it is absolutely required for performance reasons, it would be simpler to use ChangeCommand instead. The reason is that code in the undo/redo area is error prone and we should avoid maintenance burden caused by lots of different commands.

Replying to Gerd Petermann <gpetermann_muenchen@…>:

Open questions:
a) Is way w9 a correct inner way? It would be easy to detect the simple
self intersection as well.

This is borderline, but I think we should allow it.

b) The unit test data file (\josm\core\data_nodist\multipolygon.osm) contains a few nested
mp, eg. "Example 8 (03)" (outer inside inner which is inside outer).
My understanding is that these are not correct, but the old code doesn't complain.

Nested multipolygons are correct and commonly used (For example borders with nested exclaves/enclaves).

[GerdP]

Thanks for reviewing.
Reg. the TODO: I'd prefer to activate the commented if statement because it would suppress
some tests (and error messages) which are more or less duplicates to other errors reported by previous checks.
If you agree the fie multipolygon.osm file has to be changed so that these errror messages are not expected to make the unit tests work.
Reg. ChangeCommand: I did not see that before, I have to look at it.
Reg. your answers: I agree in both points.

[GerdP]

v11 uses ChangeCommand (much simpler) and applies to 11151. I left the TODO and the comments code for now.

[bastiK]

Okay, could you extend the data_nodist/multipolygon.osm file, so that it has examples of errors that are detected with your patch, but not before? The "Inner inside inner" test is new, but should be removed, right? Also, the javadoc for checkCrossingWay should be completed for all parameters.

[GerdP]

I've already attached a modified version of multipolygon.osm here, did you see that?

[bastiK]

Replying to Gerd Petermann <gpetermann_muenchen@…>:

I've already attached a modified version of multipolygon.osm here, did you see that?

Oh, missed that!

It is good that 6/9, 8/10 and 9/10 are now covered, but I think 7/10 and 7/11 are valid and should not be reported by the validator. See also ​OGC multipolygon examples for reference.

Regarding changes in Multipolygon.java: It seems okay when an invalid multipolygon is rendered in a strange way. No need to cover up the problem.

[GerdP]

OK, no time today. I'll work on a new patch tomorrow.

[GerdP]

OK, I think 7/10 is probably okay )should not produce a warning)

The warning for 7/11 seems valid because of the last item in the english wiki:
​http://wiki.openstreetmap.org/wiki/Relation:multipolygon#Valid_Multipolygon_conditions
"Inner polygons must not overlap with outer polygons or touch them"
but the german wiki says the opposite:
​http://wiki.openstreetmap.org/wiki/DE:Relation:multipolygon#Ein_Au.C3.9Fen-_und_ein_Innenring_-_jeweils_geschlossene_Linienz.C3.BCge
"Hinweis: Der innere Ring darf den äußeren höchstens in einem Knoten (Punkt) berühren!"

Which wiki can we trust here?

[bastiK]

Replying to Gerd Petermann <gpetermann_muenchen@…>:

The warning for 7/11 seems valid because of the last item in the english wiki:
​http://wiki.openstreetmap.org/wiki/Relation:multipolygon#Valid_Multipolygon_conditions
"Inner polygons must not overlap with outer polygons or touch them"

This is a contradiction to the statement that OSM-Multipolygons are basically OGC-Simple-Feature Multipolygons with the sole exception of touching inner rings. The OGC Multipolygon allows touching inner ring at one point, see also ​this document.

That inconsistency is not so much a problem for JOSM though: We simply don't produce a warning unless it is unambiguously documented as an error and there is a certain community consensus and / or common sense to this decision.

[GerdP]

to be used with improve_MultipolygonTest_v12.patch

[GerdP]

OK, the changes in Multipolygon.java were coded to avoid false positives in the validator. In v12 these tests are skipped when duplicate members are found.
Reg. 7/10 and 7/11: They are now considered okay.
The new content for multipolygon.osm is in multipolygon.2.osm, the upload process renamed the file.

BTW: I'd prefer to create a patch containing the data file, but since JOSM renumbers all elements when you load a file with negative ids the patch is huge. Is this renumbering intended?

[bastiK]

Replying to Gerd Petermann <gpetermann_muenchen@…>:

OK, the changes in Multipolygon.java were coded to avoid false positives in the validator. In v12 these tests are skipped when duplicate members are found.

Okay, this is a good solution. I still see the "Inner inside inner" and "Outside inside outside" warnings which are false positives. Regarding the rolesWereChecked condition which is commented out: I cannot commit the code like this. Please decide one way or another or alternatively explain the advantages/disadvantages in more detail. It is clear that we should avoid duplicate or nearly duplicate warnings.

The new content for multipolygon.osm is in multipolygon.2.osm, the upload process renamed the file.

I don't see a difference, what has changed? Can you add an example for checkIntersectionAtNodes()?

BTW: I'd prefer to create a patch containing the data file, but since JOSM renumbers all elements when you load a file with negative ids the patch is huge. Is this renumbering intended?

Yes, it is current policy that negative ids are arbitrary and volatile. Better to attach a separate .osm file!

[bastiK]

In 11157/josm:

see #13307 - validator/MultipolygonTest: add check for duplicate members (extracted from patch by Gerd Petermann, minor style and javadoc changes)

[bastiK]

In 11158/josm:

see #13307 - validator/MultipolygonTest: increase robustness by not using MultipolygonCache (extracted from patch by Gerd Petermann)

[bastiK]

I've started to commit individual features from your patch. Sorry for the inconvenience when updating to current svn version.

[GerdP]

Replying to bastiK:

Replying to Gerd Petermann <gpetermann_muenchen@…>:

The new content for multipolygon.osm is in multipolygon.2.osm, the upload process renamed the file.

I don't see a difference, what has changed? Can you add an example for checkIntersectionAtNodes()?

The changes were small, I just removed unwanted error codes or replaced them by "none". I'll try to add one for
`checkIntersectionAtNodes()' now.

BTW: I'd prefer to create a patch containing the data file, but since JOSM renumbers all elements when you load a file with negative ids the patch is huge. Is this renumbering intended?

Yes, it is current policy that negative ids are arbitrary and volatile. Better to attach a separate .osm file!

OK

[GerdP]

I forgot the "inner inside inner" etc. problem. Working on it now.

[GerdP]

to be used with improve_MultipolygonTest_v13.patch

[GerdP]

Reg. rolesWereChecked : I came to the conclusion that many tests make no sense when MultiPolygonBuilder is not able to interpret the data, so in v13 I've removed a lot of code which tries to produce the same messages as the unpatched version. Since you agree that we should not produce multiple messages for one problem this seems the better way. For example, if we have intersecting or crossing ways it doesn't help much to report also an "inner way is outside" problem as in 07/04.
The only problem that I see with this solution is that we don't report that the fact that CreateMultipolygonAction.createMultipolygonRelation() failed (or why). It might be better to store this fact and make sure that at least one error was found for the relation and if not to report a kind of "something is wrong" error.

[bastiK]

The wiki mentions the OGC simple features as a reference for the definition of OSM multipolygons. In the JOSM validator, we should not be more strict than the OGC standard. multipolygon.3.osm, example 07/10 is a valid OGC multipolygon, so should not be reported. In fact, this shape can show up for real world areas, so naturally there must be a way to represent them in OSM.
I think the following errors should be detected:

• A segment used by multiple multipolygon way members
• true crossings at a node (one ring is ...,A,B,C,... and another ...,X,B,Z,...; X is inside the first ring and Z outside, or the other way around)

Apart from that, I don't think we should report rings touching at a single node, since these shapes can always be converted to valid multipolygons simply by splitting all ways at the touching points.

Further things:

• checkGeometry and checkCrossingWays have unused parameters.
• Have you thought about integrating the MultipolygonTest.checkCrossingWay bits into the CrossingWays class?

[GerdP]

Replying to bastiK:

The wiki mentions the OGC simple features as a reference for the definition of OSM multipolygons. In the JOSM validator, we should not be more strict than the OGC standard. multipolygon.3.osm, example 07/10 is a valid OGC multipolygon, so should not be reported. In fact, this shape can show up for real world areas, so naturally there must be a way to represent them in OSM.

Agreed, while creating this example I thought it looks valid.

I think the following errors should be detected:

• A segment used by multiple multipolygon way members

Agreed

• true crossings at a node (one ring is ...,A,B,C,... and another ...,X,B,Z,...; X is inside the first ring and Z outside, or the other way around)

Argh, seems I forgot this case :-(

Apart from that, I don't think we should report rings touching at a single node, since these shapes can always be converted to valid multipolygons simply by splitting all ways at the touching points.

OK, I'll try to add unit tests to make sure that this doesn't happen.
I fear the crossing ways test will always report the case when a node lies exactly on a way segment.

Further things:

• checkGeometry and checkCrossingWays have unused parameters.

Yes, sorry, I wonder why Eclipse did not mark them. Seems that an unused parm with javadoc is considered okay :-(
I also noticed that I forgot to install the checkstyle plugin during my last eclipse update :-(

• Have you thought about integrating the MultipolygonTest.checkCrossingWay bits into the CrossingWays class?

Yes, I thought about this for a while but did not find enough common code. Maybe Java 8 allows more but I am not yet familiar with that.

[GerdP]

Please check multipolygon.4.osm.
1) Three new polygons in the upper right "Outer ways share nodes but do not cross" is reported by r10966 with "Intersection between multipolygon ways (1)". My understanding is now that these are all valid and should not be flagged. Right?
2) 07/10 is the "true crossing" case

While I am working on a new patch please add more if you miss something.

[GerdP]

Sorry, multipolygon.4.osm was old, meant the content of multipolygon.5.osm

[bastiK]

Replying to Gerd Petermann <gpetermann_muenchen@…>:

1) Three new polygons in the upper right "Outer ways share nodes but do not cross" is reported by r10966 with "Intersection between multipolygon ways (1)". My understanding is now that these are all valid and should not be flagged. Right?

Yes, but the third one "touching outer without shared node" can have a warning if you like. It is bad practice to place a way node exactly on the segment of another way without sharing a node (unless they are completely unrelated, like a boundary and a highway). If the user wants the rings to touch, they should add a shared node. Otherwise there should be a visible gap. Anyway, this is debatable.

2) 07/10 is the "true crossing" case

Right.

While I am working on a new patch please add more if you miss something.

I've added 3 more test cases in multipolygon_b.6.osm (upper right). The building and the grass should be valid and the library should not be valid.

[GerdP]

OK, thanks. I'll modify this further so that all polygons have a josm_error_codes tag. This should help to find wrong positives in a slightly modified MultipolygonTestTest.

[GerdP]

to be used with improve_MultipolygonTest_v14.patch

[GerdP]

Comments to v14 and multipolygon.6.osm:
1) I've removed the "touching outer without shared node" example. As expected it is found by the crossing way test and it would require a lot of additional code to eliminate this false (?) positive.
2) I kept MultipolygonTestTest as is because most of the other polygons are testing style dependent results. Maybe
we should add some "okay" examples with a name starting with "01" and pass them to the test as well.
3) The buiding example from multipolygon_b.6.osm is quite special. The MultipolygonBuilder failes because Geometry.polygonIntersection returns the wrong result "CROSSING" for it. This seems to be an edge case in the java.awt.geom.Area code.
4) Please review the changes reg. the styles field. I assume that MapPaintStyles.getStyles() used to be a slow operation, but nowadays it simply returns a field value, so I see no need to use the hack with the static field.

[bastiK]

Okay, works quite well!

Replying to Gerd Petermann <gpetermann_muenchen@…>:

2) I kept MultipolygonTestTest as is because most of the other polygons are testing style dependent results. Maybe
we should add some "okay" examples with a name starting with "01" and pass them to the test as well.

Good idea!

3) The buiding example from multipolygon_b.6.osm is quite special. The MultipolygonBuilder failes because Geometry.polygonIntersection returns the wrong result "CROSSING" for it. This seems to be an edge case in the java.awt.geom.Area code.

Do you mean inner shares multiple nodes with outer or 07/12 Multipolygon ways share segment(s)? The Tools > Create Multipolygon feature works for both.

4) Please review the changes reg. the styles field. I assume that MapPaintStyles.getStyles() used to be a slow operation, but nowadays it simply returns a field value, so I see no need to use the hack with the static field.

I don't think it makes a difference.

Further comments:

• Could you add an example for Multipolygon way inside other multipolygon way with same role, currently I don't see how this is triggered.
• In multipolygon_b.7.osm, 07/10 there is a duplicate warning. This is caused by the way you loop over all pairs of outer polygons. Better do

          for (int i = 0; i < outerPolygons.size(); i++) {
              for (int j = i + 1; j < outerPolygons.size(); j++) {
  

  or similar.
• Please add curly brackets after if also for single statements (except return), as mentioned in the StyleGuide.

[GerdP]

Replying to bastiK:

Okay, works quite well!

Great :-)

Replying to Gerd Petermann <gpetermann_muenchen@…>:

2) I kept MultipolygonTestTest as is because most of the other polygons are testing style dependent results. Maybe
we should add some "okay" examples with a name starting with "01" and pass them to the test as well.

Good idea!

OK, working on it.

3) The buiding example from multipolygon_b.6.osm is quite special. The MultipolygonBuilder failes because Geometry.polygonIntersection returns the wrong result "CROSSING" for it. This seems to be an edge case in the java.awt.geom.Area code.

Do you mean inner shares multiple nodes with outer or 07/12 Multipolygon ways share segment(s)? The Tools > Create Multipolygon feature works for both.

I meant the one you added, name="inner shares multiple nodes with outer" in multipolygon_b.6.osm. The problem doesn't occur with later versions, I guess that's because I moved the two ways a little bit. Sorry, did not test again after that.

4) Please review the changes reg. the styles field. I assume that MapPaintStyles.getStyles() used to be a slow operation, but nowadays it simply returns a field value, so I see no need to use the hack with the static field.

I don't think it makes a difference.

OK

Further comments:

• Could you add an example for Multipolygon way inside other multipolygon way with same role, currently I don't see how this is triggered.
• In multipolygon_b.7.osm, 07/10 there is a duplicate warning. This is caused by the way you loop over all pairs of outer polygons. Better do

          for (int i = 0; i < outerPolygons.size(); i++) {
              for (int j = i + 1; j < outerPolygons.size(); j++) {
  

  or similar.

OK, looks better. Tried it and found that checkSharedNodes() depends on the order of the two polygons, so I have to work on this as well.

• Please add curly brackets after if also for single statements (except return), as mentioned in the StyleGuide.

OK, will try to remember that as Checkstyle doesn't complain.

[GerdP]

I am not yet sure what to do with the failing "Create Multipolygon" problem. I can also reproduce it with other MP where an inner
way shares nodes with an outer. At one place, the problem occurs, after moving all ways together a bit the problem may disappear. I guess it is caused by rounding problems or by the fact that we use 2D methods with spherical data.
The "Multipolygon way inside other multipolygon way with same role" problem can only occurs if "Create Multipolygon" fails,
but in this case we also don't know much about the correctness of the roles :-(
Any ideas how Geometry.polygonIntersection() could be fixed? The problem occurs in the inter.equals(a1) or inter.equals(a2) part which should return true but doesn't.

[bastiK]

Replying to Gerd Petermann <gpetermann_muenchen@…>:

I am not yet sure what to do with the failing "Create Multipolygon" problem. I can also reproduce it with other MP where an inner
way shares nodes with an outer. At one place, the problem occurs, after moving all ways together a bit the problem may disappear. I guess it is caused by rounding problems or by the fact that we use 2D methods with spherical data.

These are two pretty unrelated areas:

1. Create Multipolygon-tool / MultipolygonBuilder.java: Helper tool to create a multipolygon from scratch given a set of ways with no roles assigned. For borderline-valid cases it is somewhat expected and acceptable that the tool will fail. The user can still assemble the multipolygon relation manually.
2. A Validation tool (MultipolygonTest.java / Multipolygon.java): It will point out errors of existing multipolygon relations with roles assigned, possibly created by another editor like iD. Here the objective is to find all problems, but avoid false positives. Therefore somewhat valid cases must be accepted.

There is no reason to tackle both areas at the same time, lets finish your validator enhancements first. :-)

The "Multipolygon way inside other multipolygon way with same role" problem can only occurs if "Create Multipolygon" fails,
but in this case we also don't know much about the correctness of the roles :-(

I don't understand. If Create Multipolygon fails, there will be no multipolygon relation to validate. Are you saying it is dead code and can be removed?

Any ideas how Geometry.polygonIntersection() could be fixed? The problem occurs in the inter.equals(a1) or inter.equals(a2) part which should return true but doesn't.

Cannot comment without a simple example where Geometry.polygonIntersection() gives an incorrect result + context of how this is a problem for what you are trying to do.

[GerdP]

Replying to bastiK:

Replying to Gerd Petermann <gpetermann_muenchen@…>:

I am not yet sure what to do with the failing "Create Multipolygon" problem. I can also reproduce it with other MP where an inner
way shares nodes with an outer. At one place, the problem occurs, after moving all ways together a bit the problem may disappear. I guess it is caused by rounding problems or by the fact that we use 2D methods with spherical data.

These are two pretty unrelated areas:

1. Create Multipolygon-tool / MultipolygonBuilder.java: Helper tool to create a multipolygon from scratch given a set of ways with no roles assigned. For borderline-valid cases it is somewhat expected and acceptable that the tool will fail. The user can still assemble the multipolygon relation manually.
2. A Validation tool (MultipolygonTest.java / Multipolygon.java): It will point out errors of existing multipolygon relations with roles assigned, possibly created by another editor like iD. Here the objective is to find all problems, but avoid false positives. Therefore somewhat valid cases must be accepted.

There is no reason to tackle both areas at the same time, lets finish your validator enhancements first. :-)

Yes, but up to now the validator depends on the results of the creator tool to validate the correctness of the roles.
I'd be happy to remove the dependency between validator and "Create Multipolygon" tool, but the verification of the roles will need more code, and I fear that I start to duplicate the code in MultipolygonBuilder. I have to think about this a bit more...

The "Multipolygon way inside other multipolygon way with same role" problem can only occurs if "Create Multipolygon" fails,
but in this case we also don't know much about the correctness of the roles :-(

I don't understand. If Create Multipolygon fails, there will be no multipolygon relation to validate. Are you saying it is dead code and can be removed?

See above.

Any ideas how Geometry.polygonIntersection() could be fixed? The problem occurs in the inter.equals(a1) or inter.equals(a2) part which should return true but doesn't.

Cannot comment without a simple example where Geometry.polygonIntersection() gives an incorrect result + context of how this is a problem for what you are trying to do.

As I wrote above, the building polygon which you added in multipolygon_b.6.osm shows the problem. Relation id is -17952 in that file.
When I mark the two ways of the relation and press Ctrl+B I see a popup "There is an intersection between ways". When you move these two ways a little bit the problem may disappear. Maybe I'll open a new ticket for this.

[GerdP]

to be used with improve_MultipolygonTest_v15.patch

[GerdP]

In v15 I implemented the changes regarding checkstyle, loop control, and "01 okay" tests. For now I've removed most of the code which tries to verify the "polygon1 inside polygon2 with same role" cases to avoid false positives. If I got that right the tests which are now implemented allow to calculate the nesting levels if no crossing or intersection at shared node is found. I am working on this now. Might be ready in a day or in a week, so if you think that v15 is good, commit it with the new test data.

[bastiK]

Replying to Gerd Petermann <gpetermann_muenchen@…>:

Replying to bastiK:

Replying to Gerd Petermann <gpetermann_muenchen@…>:

I am not yet sure what to do with the failing "Create Multipolygon" problem. I can also reproduce it with other MP where an inner
way shares nodes with an outer. At one place, the problem occurs, after moving all ways together a bit the problem may disappear. I guess it is caused by rounding problems or by the fact that we use 2D methods with spherical data.

These are two pretty unrelated areas:

1. Create Multipolygon-tool / MultipolygonBuilder.java: Helper tool to create a multipolygon from scratch given a set of ways with no roles assigned. For borderline-valid cases it is somewhat expected and acceptable that the tool will fail. The user can still assemble the multipolygon relation manually.
2. A Validation tool (MultipolygonTest.java / Multipolygon.java): It will point out errors of existing multipolygon relations with roles assigned, possibly created by another editor like iD. Here the objective is to find all problems, but avoid false positives. Therefore somewhat valid cases must be accepted.

There is no reason to tackle both areas at the same time, lets finish your validator enhancements first. :-)

Yes, but up to now the validator depends on the results of the creator tool to validate the correctness of the roles.
I'd be happy to remove the dependency between validator and "Create Multipolygon" tool, but the verification of the roles will need more code, and I fear that I start to duplicate the code in MultipolygonBuilder. I have to think about this a bit more...

Okay, I wasn't aware of the way the validator makes use of the CreateMultipolygonAction class. Now the rolesWereChecked flag makes a whole lot more sense to me. ;-)

Replying to Gerd Petermann <gpetermann_muenchen@…>:

In v15 I implemented the changes regarding checkstyle, loop control, and "01 okay" tests. For now I've removed most of the code which tries to verify the "polygon1 inside polygon2 with same role" cases to avoid false positives. If I got that right the tests which are now implemented allow to calculate the nesting levels if no crossing or intersection at shared node is found. I am working on this now. Might be ready in a day or in a week, so if you think that v15 is good, commit it with the new test data.

Will do, but we have a release scheduled for this weekend and bigger changes are usually avoided in the days before. It can be committed after the release of the next tested version.

[GerdP]

okay, I am making good progess with the removement of the CreateMultipolygonAction.
I'll use the time to review the code and add more cases to the unit test data.

[GerdP]

I was succesfull with the removal of the CreateMultipolygonActioncode and fixed some performance issues with v15.
The good news is that the code is now much faster for very complex polygons, but I also found some new special cases which might require additional code.

Please review some more possible problem cases in multipolygon.8.osm:
07/17: I was surprised to find that the code in the Multipolygon class connects the 4 inner ways so that they form one inner ring. While writing this I thought of a variant with two inner ways connected at the upper and lower node, the other two at the left and right nodes. These are special because we want to allow that inner ways share way segments.
I think MultipoygonTest should
a) flag two inner rings which share all way segments. Right?
b) flag a single ring which repeats one or more segments. This might also happen with spikes like a-b-c-d-c-a. Right?

07/18: A rather normal intersection at shared nodes, r10966 doesn't report it. I think it should produce a 1606 code. Right?
07/19 and 07/20 are variants of inner "8-shaped" ways which intersect. r10966 flags only 07/19. I think both describe similar cases, but I am not shure if they should be considered okay or not.

What about a single 8-shaped inner ring? Do you think this should be flagged? I think no.

When you look at 07/20: One may create an 8-shaped (closed) way so that it starts and ends at the "middle" node or somewhere else. Do you agree that the result of the tests should not depend on this? The current code in SelfIntersectingWay flags all 8-shaped ways which don't start at the middle node.

[GerdP]

v16 is based on r11223. I think it works pretty well for real world data and also for most of the rather theoretical cases in the test dataset. The code in PolygonLevelFinder is more or less duplicating the code in MultipolygonBuilder, but with a simpler structure and much better performance.
In a 2nd step I'd suggest to move most of the new code into class Multipolygon and refactor MultipolygonTest and MultipolygonBuilder to use it.

[bastiK]

In 11227/josm:

applied #13307 - various improvements to MultipolygonTest (patch by Gerd Petermann)

[bastiK]

Replying to Gerd Petermann <gpetermann_muenchen@…>:

Please review some more possible problem cases in multipolygon.8.osm:
07/17: I was surprised to find that the code in the Multipolygon class connects the 4 inner ways so that they form one inner ring. While writing this I thought of a variant with two inner ways connected at the upper and lower node, the other two at the left and right nodes. These are special because we want to allow that inner ways share way segments.
I think MultipoygonTest should
a) flag two inner rings which share all way segments. Right?

Sure, in particular two inner rings at the same nesting level must not overlap (i.e. one inside the other).

b) flag a single ring which repeats one or more segments. This might also happen with spikes like a-b-c-d-c-a. Right?

Yes.

07/18: A rather normal intersection at shared nodes, r10966 doesn't report it. I think it should produce a 1606 code. Right?

I would say it is not valid.

07/19 and 07/20 are variants of inner "8-shaped" ways which intersect. r10966 flags only 07/19. I think both describe similar cases, but I am not shure if they should be considered okay or not.

Also not valid. My take on this would be, whenever this happens:

A
 \     B
  \   /
   \ /
    C
   /|
  / |
 D  |
    E

with A-C-E being part of one ring and B-C-D part of another ring, it is invalid. (When the rings are touching, i.e. A-C-D and B-C-E, it is okay.)

What about a single 8-shaped inner ring? Do you think this should be flagged? I think no.

By this principle not.

When you look at 07/20: One may create an 8-shaped (closed) way so that it starts and ends at the "middle" node or somewhere else. Do you agree that the result of the tests should not depend on this? The current code in SelfIntersectingWay flags all 8-shaped ways which don't start at the middle node.

Not sure. One approach would be to assemble the ways to closed rings first and disregard at which nodes the ways forming the ring start and end.

[GerdP]

Thanks for reviewing and committing. It seems that multipolygon.9.osm did not work with the unit test, sorry for that.
Please commit the changes in multipolygon.10.osm.

[bastiK]

In 11228/josm:

see #13307 - fix unit test (patch by Gerd Petermann)

[Don-vip]

Milestone renamed

[bastiK]

See #14500 for an example that does not work.

[GerdP]

I'll have a look.

[GerdP]

In 11837/josm:

improve MultipolygonTest to fix #13307, add special case to unit test input file

Use complex Geometry.polygonIntersection test if simple tests cannot find a result.
This is very unlikely so it should not happen often.

[Klumbumbus]

The test fails https://josm.openstreetmap.de/jenkins/job/JOSM/2523/jdk=JDK8/testReport/org.openstreetmap.josm.data.validation.tests/MultipolygonTestTest/testMultipolygonFile/