[Patch] Joining complex areas produces exception

[Stereo]

What steps will reproduce the problem?

1. Open ​http://openstreetmap.lu/complexareas.osm . In this case, the polygons were created by the areaselector plugin.
2. Select the three weird polygons
3. Join them with Tools > Join Overlapping Areas

What is the expected result?

Three weird polygons become one weird polygon

What happens instead?

The exception below, and the ways are mangled.

Please provide any additional information below. Attach a screenshot if
possible.

Revision: 7480
Repository Root: http://josm.openstreetmap.de/svn
Last Changed Author: Don-vip
Last Changed Date: 2014-08-31 23:51:24 +0200 (Sun, 31 Aug 2014)
Build-Date: 2014-08-31 21:55:55
URL: http://josm.openstreetmap.de/svn/trunk
Repository UUID: 0c6e7542-c601-0410-84e7-c038aed88b3b
Last Changed Rev: 7480

Identification: JOSM/1.5 (7480 en_GB) Mac OS X 10.9.4
Memory Usage: 898 MB / 3641 MB (461 MB allocated, but free)
Java version: 1.8.0_20, Oracle Corporation, Java HotSpot(TM) 64-Bit Server VM
VM arguments: [-Djava.library.path=/Applications/JOSM.app/Contents/MacOS, -DLibraryDirectory=/Users/stereo/Library, -DDocumentsDirectory=/Users/stereo/Documents, -DApplicationSupportDirectory=/Users/stereo/Library/Application Support, -DCachesDirectory=/Users/stereo/Library/Caches, -DSandboxEnabled=false, -Dapple.laf.useScreenMenuBar=true, -Dcom.apple.macos.use-file-dialog-packages=true, -Dcom.apple.macos.useScreenMenuBar=true, -Dcom.apple.mrj.application.apple.menu.about.name=JOSM, -Dcom.apple.hwaccel=false]
Dataset consistency test: No problems found

Plugins:
- AddrInterpolation (30416)
- CommandLine (30523)
- DirectDownload (30416)
- DirectUpload (30416)
- FixAddresses (30416)
- HouseNumberTaggingTool (30416)
- OpeningHoursEditor (30609)
- PicLayer (30436)
- RoadSigns (30495)
- alignways (30416)
- areaselector (1409913276)
- buildings_tools (30485)
- cadastre-fr (30416)
- conflation (0.1.7)
- contourmerge (1010)
- dataimport (30416)
- download_along (30416)
- geotools (30569)
- imagery_offset_db (30534)
- importvec (30416)
- jts (30416)
- livegps (30506)
- mapdust (30502)
- merge-overlap (30416)
- mirrored_download (30495)
- namemanager (30416)
- notes (v0.9.4)
- opendata (30607)
- pdfimport (30416)
- public_transport (30416)
- reverter (30521)
- scripting (30700)
- surveyor (30440)
- tageditor (30488)
- terracer (30614)
- turnlanes (30416)
- turnrestrictions (30454)
- undelete (30416)
- utilsplugin2 (30460)

Last errors/warnings:
- E: Failed to locate image ''
- E: Failed to locate image ''
- W: Detected deprecated 'canvas{background-color}' in 'https://josm.openstreetmap.de/josmfile?page=Styles/TreeCrownDiameter&style' which will be removed shortly. Use 'fill-color' instead.
- E: java.lang.RuntimeException: Join areas internal error.

java.lang.RuntimeException: Join areas internal error.
	at org.openstreetmap.josm.actions.JoinAreasAction.findBoundaryPolygons(JoinAreasAction.java:1088)
	at org.openstreetmap.josm.actions.JoinAreasAction.joinAreas(JoinAreasAction.java:572)
	at org.openstreetmap.josm.actions.JoinAreasAction.actionPerformed(JoinAreasAction.java:457)
	at javax.swing.AbstractButton.fireActionPerformed(AbstractButton.java:2022)
	at javax.swing.AbstractButton$Handler.actionPerformed(AbstractButton.java:2346)
	at javax.swing.DefaultButtonModel.fireActionPerformed(DefaultButtonModel.java:402)
	at javax.swing.DefaultButtonModel.setPressed(DefaultButtonModel.java:259)
	at javax.swing.plaf.basic.BasicButtonListener.mouseReleased(BasicButtonListener.java:252)
	at java.awt.AWTEventMulticaster.mouseReleased(AWTEventMulticaster.java:289)
	at java.awt.Component.processMouseEvent(Component.java:6525)
	at javax.swing.JComponent.processMouseEvent(JComponent.java:3321)
	at java.awt.Component.processEvent(Component.java:6290)
	at java.awt.Container.processEvent(Container.java:2234)
	at java.awt.Component.dispatchEventImpl(Component.java:4881)
	at java.awt.Container.dispatchEventImpl(Container.java:2292)
	at java.awt.Component.dispatchEvent(Component.java:4703)
	at java.awt.LightweightDispatcher.retargetMouseEvent(Container.java:4898)
	at java.awt.LightweightDispatcher.processMouseEvent(Container.java:4533)
	at java.awt.LightweightDispatcher.dispatchEvent(Container.java:4462)
	at java.awt.Container.dispatchEventImpl(Container.java:2278)
	at java.awt.Window.dispatchEventImpl(Window.java:2739)
	at java.awt.Component.dispatchEvent(Component.java:4703)
	at java.awt.EventQueue.dispatchEventImpl(EventQueue.java:746)
	at java.awt.EventQueue.access$400(EventQueue.java:97)
	at java.awt.EventQueue$3.run(EventQueue.java:697)
	at java.awt.EventQueue$3.run(EventQueue.java:691)
	at java.security.AccessController.doPrivileged(Native Method)
	at java.security.ProtectionDomain$1.doIntersectionPrivilege(ProtectionDomain.java:75)
	at java.security.ProtectionDomain$1.doIntersectionPrivilege(ProtectionDomain.java:86)
	at java.awt.EventQueue$4.run(EventQueue.java:719)
	at java.awt.EventQueue$4.run(EventQueue.java:717)
	at java.security.AccessController.doPrivileged(Native Method)
	at java.security.ProtectionDomain$1.doIntersectionPrivilege(ProtectionDomain.java:75)
	at java.awt.EventQueue.dispatchEvent(EventQueue.java:716)
	at java.awt.EventDispatchThread.pumpOneEventForFilters(EventDispatchThread.java:201)
	at java.awt.EventDispatchThread.pumpEventsForFilter(EventDispatchThread.java:116)
	at java.awt.EventDispatchThread.pumpEventsForHierarchy(EventDispatchThread.java:105)
	at java.awt.EventDispatchThread.pumpEvents(EventDispatchThread.java:101)
	at java.awt.EventDispatchThread.pumpEvents(EventDispatchThread.java:93)
	at java.awt.EventDispatchThread.run(EventDispatchThread.java:82)

[Don-vip]

Ticket #10291 has been marked as a duplicate of this ticket.

[Don-vip]

minimal dataset

[Don-vip]

In 7534/josm:

see #10511 - add unit test

[Don-vip]

@Balaitous: could you please have a look at this? You're more familiar with this part of code :)

[Don-vip]

In 7637/josm:

see #10511 - disable unit test until we fix the bug

[Don-vip]

@oligo: if you're interested, I'd really appreciate some help on this one :)

[Don-vip]

Ticket #10886 has been marked as a duplicate of this ticket.

[Don-vip]

Ticket #12576 has been marked as a duplicate of this ticket.

[Don-vip]

Ticket #12928 has been marked as a duplicate of this ticket.

[mdk]

I attached an other case (Join.osm). It has only one way. select the way and press SHIFT-J.
In this case there is only one self-intersecting way. I know joining a single way is not really a usecase, but never the less I would expect either an error message, a valid result or no action, but throwing a RuntimeException is the worst result.

URL:http://josm.openstreetmap.de/svn/trunk
Repository:UUID: 0c6e7542-c601-0410-84e7-c038aed88b3b
Last:Changed Date: 2016-11-29 02:39:12 +0100 (Tue, 29 Nov 2016)
Build-Date:2016-11-29 02:34:42
Revision:11344
Relative:URL: ^/trunk

Identification: JOSM/1.5 (11344 en) Linux Ubuntu 16.10
Memory Usage: 470 MB / 876 MB (121 MB allocated, but free)
Java version: 1.8.0_111-8u111-b14-2ubuntu0.16.10.2-b14, Oracle Corporation, OpenJDK Server VM
Screen: :0.0 1920x1080
Maximum Screen Size: 1920x1080
Java package: openjdk-8-jre:i386-8u111-b14-2ubuntu0.16.10.2
VM arguments: [-Djosm.restart=true, -Djosm.dir.name=JOSM-latest, -Djava.net.useSystemProxies=true]
Dataset consistency test: No problems found

Plugins:
+ ColumbusCSV (32885)
+ FastDraw (33004)
+ HouseNumberTaggingTool (32699)
+ OpeningHoursEditor (33004)
+ RoadSigns (33088)
+ apache-commons (32994)
+ apache-http (32699)
+ buildings_tools (33004)
+ contourmerge (1030)
+ imagery-xml-bounds (33004)
+ imagery_offset_db (33004)
+ pbf (33004)
+ poly (33004)
+ public_transport (33088)
+ reltoolbox (33088)
+ reverter (33088)
+ terracer (33088)
+ turnlanes (33088)
+ turnrestrictions (33088)
+ undelete (32699)
+ utilsplugin2 (33088)

Tagging presets:
+ https://josm.openstreetmap.de/josmfile?page=Presets/OneClick&zip=1
+ https://josm.openstreetmap.de/josmfile?page=Presets/LaneAttributes&preset&zip=1

Map paint styles:
+ https://josm.openstreetmap.de/josmfile?page=Styles/Lane_and_Road_Attributes&zip=1
- https://josm.openstreetmap.de/josmfile?page=Styles/Traffic_signs&zip=1
+ https://josm.openstreetmap.de/josmfile?page=Styles/Maxspeed&zip=1

Last errors/warnings:
- W: java.io.IOException: Attribution is not loaded yet
- W: java.io.IOException: Attribution is not loaded yet
- W: java.io.IOException: Attribution is not loaded yet
- W: java.io.IOException: Attribution is not loaded yet
- W: java.io.IOException: Attribution is not loaded yet
- W: java.io.IOException: Attribution is not loaded yet
- E: Handled by bug report queue: java.lang.RuntimeException: Join areas internal error.
- E: Handled by bug report queue: java.lang.RuntimeException: Join areas internal error.
- E: Handled by bug report queue: java.lang.RuntimeException: Join areas internal error.
- E: Handled by bug report queue: java.lang.RuntimeException: Join areas internal error.


=== REPORTED CRASH DATA ===
BugReportExceptionHandler#handleException:
No data collected.

Warning issued by: BugReportExceptionHandler#handleException

=== STACK TRACE ===
Thread: AWT-EventQueue-0 (17) of main
java.lang.RuntimeException: Join areas internal error.
	at org.openstreetmap.josm.actions.JoinAreasAction.findBoundaryPolygons(JoinAreasAction.java:1127)
	at org.openstreetmap.josm.actions.JoinAreasAction.joinAreas(JoinAreasAction.java:602)
	at org.openstreetmap.josm.actions.JoinAreasAction.join(JoinAreasAction.java:486)
	at org.openstreetmap.josm.actions.JoinAreasAction.actionPerformed(JoinAreasAction.java:416)
	at javax.swing.SwingUtilities.notifyAction(SwingUtilities.java:1663)
	at javax.swing.JComponent.processKeyBinding(JComponent.java:2882)
	at javax.swing.KeyboardManager.fireBinding(KeyboardManager.java:307)
	at javax.swing.KeyboardManager.fireKeyboardAction(KeyboardManager.java:263)
	at javax.swing.JComponent.processKeyBindingsForAllComponents(JComponent.java:2974)
	at javax.swing.JComponent.processKeyBindings(JComponent.java:2966)
	at javax.swing.JComponent.processKeyEvent(JComponent.java:2845)
	at java.awt.Component.processEvent(Component.java:6310)
	at java.awt.Container.processEvent(Container.java:2236)
	at java.awt.Component.dispatchEventImpl(Component.java:4889)
	at java.awt.Container.dispatchEventImpl(Container.java:2294)
	at java.awt.Component.dispatchEvent(Component.java:4711)
	at java.awt.KeyboardFocusManager.redispatchEvent(KeyboardFocusManager.java:1954)
	at java.awt.DefaultKeyboardFocusManager.dispatchKeyEvent(DefaultKeyboardFocusManager.java:806)
	at java.awt.DefaultKeyboardFocusManager.preDispatchKeyEvent(DefaultKeyboardFocusManager.java:1074)
	at java.awt.DefaultKeyboardFocusManager.typeAheadAssertions(DefaultKeyboardFocusManager.java:945)
	at java.awt.DefaultKeyboardFocusManager.dispatchEvent(DefaultKeyboardFocusManager.java:771)
	at java.awt.Component.dispatchEventImpl(Component.java:4760)
	at java.awt.Container.dispatchEventImpl(Container.java:2294)
	at java.awt.Window.dispatchEventImpl(Window.java:2746)
	at java.awt.Component.dispatchEvent(Component.java:4711)
	at java.awt.EventQueue.dispatchEventImpl(EventQueue.java:758)
	at java.awt.EventQueue.access$500(EventQueue.java:97)
	at java.awt.EventQueue$3.run(EventQueue.java:709)
	at java.awt.EventQueue$3.run(EventQueue.java:703)
	at java.security.AccessController.doPrivileged(Native Method)
	at java.security.ProtectionDomain$JavaSecurityAccessImpl.doIntersectionPrivilege(ProtectionDomain.java:76)
	at java.security.ProtectionDomain$JavaSecurityAccessImpl.doIntersectionPrivilege(ProtectionDomain.java:86)
	at java.awt.EventQueue$4.run(EventQueue.java:731)
	at java.awt.EventQueue$4.run(EventQueue.java:729)
	at java.security.AccessController.doPrivileged(Native Method)
	at java.security.ProtectionDomain$JavaSecurityAccessImpl.doIntersectionPrivilege(ProtectionDomain.java:76)
	at java.awt.EventQueue.dispatchEvent(EventQueue.java:728)
	at java.awt.EventDispatchThread.pumpOneEventForFilters(EventDispatchThread.java:201)
	at java.awt.EventDispatchThread.pumpEventsForFilter(EventDispatchThread.java:116)
	at java.awt.EventDispatchThread.pumpEventsForHierarchy(EventDispatchThread.java:105)
	at java.awt.EventDispatchThread.pumpEvents(EventDispatchThread.java:101)
	at java.awt.EventDispatchThread.pumpEvents(EventDispatchThread.java:93)
	at java.awt.EventDispatchThread.run(EventDispatchThread.java:82)

[Don-vip]

In 11427/josm:

fix #14185 - see #10511 - robustness when joining algorithm fails during boundaries database initialization

[Don-vip]

this needs to be fixed, now, due to frequent occurrences of the problem (see #14185)

[Don-vip]

Ticket #14302 has been marked as a duplicate of this ticket.

[Don-vip]

Ticket #14312 has been marked as a duplicate of this ticket.

[michael2402]

I think I fixed this one by re-writing parts of the joining algorithm to be more robust against polygons that contain way segments multiple times.

I noticed that JoinAreasActionTest#testTicket11992 failed with my changes - After merging I have a multipolygon with that ref. I'll have to look into this case.

[michael2402]

In 11729/josm:

Fix #10511: Use new algorithm to check which side of the way is the inner/outer side.

[Klumbumbus]

(this was reverted in r11822)

[Don-vip]

Ticket #15583 has been marked as a duplicate of this ticket.

[cmuelle8]

Please see attachment:josm-joinAreasAction-minimal-set-of-boundaries.patch:ticket:14528​

It solves test-cases attached to this ticket, and the one by Klumbumbus in ticket:14528,
may fix other things as well, it relies heavily on the old code, so does hopefully
not introduce regressions (but please test).

[GerdP]

I wonder why the code for JoinAreasAction is so complex. My first thought how I would implement it was this:
Create a Path2D for each way. Append them all to one. Create Java.awt.Area from that path to get the joined area.
Something like

        Path2D.Double combined = new Path2D.Double();
        for (Way w : ways) {
            Geometry.buildPath2DLatLon(w.getNodes(), combined);
        }
        Area a = new Area(combined);

Iterate over the corners of that joined area to find the necessary nodes and finally create delete/modify actions for the corresponding objects. This last step might be a bit more complex as it has to take care to preserve history of the older objetcs and maybe relations are causing trouble.
I would expect 250-400 lines of code for that. Did anybody try that approach?
I see lots of code to handle Multipolygons but the current implementation doesn't work with rather simple samples, e.g.
when the MP ring is not a single closed way. I also saw corrupted UndoRedoTrees while playing with this action (undoing the join action removed also a way that existed before).
I found no unit tests, so I am not sure what the expected result would be, and up to now I only used it with very simple cases.

[GerdP]

Ticket #17969 has been marked as a duplicate of this ticket.

[GerdP]

In 15852/josm:

fix #10511: Joining complex areas produces exception

• detect case where a single closed way contains the same segment twice or more and fix the "inside" flag
• enable and correct unit test (it "destroyed" preferences.xml)
• init cmdsCount to prevent corrupted undo/redo stacks after a "Join areas internal error."
• make sure that a single command is placed on the undo/redo stack in case of successfull execution. The old code sometimes created two, the latter one "Move tags from ways to relations". I found no good reason for that.
• Try to clean up undo/redo stack if user cancelled operation in 2nd popup asking about relations. Still a dirty hack but a less dangerous one.

[GerdP]

In 15854/josm:

see #10511: correct @since javadoc