[Patch] Improve MultipolygonBuilder

[GerdP]

I noticed that MultipolygonBuilder is doing a lot of costly Geometry.polygonIntersection() tests
to find out which polygons are inside/outside. Many of these tests can be omitted and thus complex
polygons could be processed much faster. Example: A (outer) polygon o with three inner ways a, b, c.
When the result of Geometry.polygonIntersection(a,b) is OUTSIDE, the result of Geometry.polygonIntersection(b,a) will also be OUTSIDE, so there is no need to do this calculation, but it is done. The reult FIRST_INSIDE_SECOND for a test of (a,b) also means
that (b,a) will return SECOND_INSIDE_FIRST.
The attached patch uses these presumptions to reduce the number of costly calculations by 50 or
more percent.

[GerdP]

The cache_Area_intersection_v1.patch blocked the multi-threading
as the complex area calculation was done in the synchronized part.
I've now attached improve_MultipolygonBuilder.patch
which solves this problem, typically this will reduce run time by > 50%.

[GerdP]

I've attached improve_MultipolygonBuilder_v2.patch which uses ConcurrentHashMap
instead of an additional field id in class JoinedPolygon. I think this is cleaner.

[GerdP]

Any comments on this?
I've attached a sample osm file with a complex mp-relation. This one was the reason why I started to
look for performance improvements in JOSM. When you run the Validator on it, r10877 shows
DEBUG: Test 'Multipolygon' completed in 54.4 s
while the patched version shows
DEBUG: Test 'Multipolygon' completed in 26.6 s

[GerdP]

I think v2 still wasn't theadsafe, in v3 I've used synchronized again.
Found no change in performance.

[simon04]

In 11119/josm:

fix #13289 - Cache polygonIntersection results in MultipolygonBuilder (patch by Gerd Petermann, modified)

[simon04]

Thank you. I can confirm the speedup of ≈2. Before committing, I reworked the patch and added computeIfAbsent as the main method for interaction with the IntersectionMatrix (similar to Map#computeIfAbsent).

[GerdP]

Cannot test right now,but doesn't this block the calculation for very complex polygons?

[GerdP]

No it probably will not block but might do the complex calc twice with bad luck.