Opened 8 years ago

Closed 8 years ago

Last modified 8 years ago

#13289 closed enhancement (fixed)

[Patch] Improve MultipolygonBuilder

Reported by: GerdP Owned by: team
Priority: normal Milestone: 16.10
Component: Core validator Version:
Keywords: MultipolygonTest, performance Cc:


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.

Attachments (5)

cache_Area_intersection_v1.patch (9.9 KB ) - added by GerdP 8 years ago.
improve_MultipolygonBuilder.patch (9.4 KB ) - added by GerdP 8 years ago.
improve_MultipolygonBuilder_v2.patch (8.8 KB ) - added by GerdP 8 years ago.
rel1956189.osm.bz2 (1.1 MB ) - added by GerdP 8 years ago.
improve_MultipolygonBuilder_v3.patch (9.9 KB ) - added by GerdP 8 years ago.

Download all attachments as: .zip

Change History (14)

by GerdP, 8 years ago

comment:1 by GerdP, 8 years ago

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%.

comment:2 by GerdP, 8 years ago

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

by GerdP, 8 years ago

Attachment: rel1956189.osm.bz2 added

comment:3 by GerdP, 8 years ago

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

comment:4 by GerdP, 8 years ago

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

comment:5 by GerdP, 8 years ago

Component: CoreCore validator
Keywords: MultipolygonTest performance added; Multipolygon Validator removed

comment:6 by simon04, 8 years ago

Resolution: fixed
Status: newclosed

In 11119/josm:

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

comment:7 by simon04, 8 years ago

Milestone: 16.10

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).

comment:8 by GerdP, 8 years ago

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

comment:9 by GerdP, 8 years ago

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

Modify Ticket

Change Properties
Set your email in Preferences
as closed The owner will remain team.
as The resolution will be set.
The resolution will be deleted. Next status will be 'reopened'.

Add Comment

E-mail address and name can be saved in the Preferences .
Note: See TracTickets for help on using tickets.