[PATCH] Join overlapping areas produces bad results

[bilbo]

I noticed the "Join overlapping areas" tool sometimes produces bad results, often on more complex ways - results which are not a union of the two areas that should be joined.

See attached example. Select both ways in it and press Shift-J to join the areas. Result is one way, which is not the sum of the areas.

[bilbo]

Example that demonstrates the bug

[bilbo]

Another example where the algorithm misbehaves, though the results are not as bad as in the first one

[bilbo]

In the second example there is one overlapping way, where I can select it and then press Shift-J to create a multipolygon frmo it, however in this case it also does not work well, though the results are not as bad as in the first example.

[bastiK]

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

[bastiK]

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

[extropy]

Anoder example, two simple rectangles.

[extropy]

New implementation of findInnerWays, fixes reported problems.

[extropy]

Made a path that fixes all the problems.

The patch completely rewrites findInnerWays function. The new implementation properly traverses around the polygon rather than just tests for inside/outside.

Did not know where to put geometric utility functions, so feel free to move them out to some other file.

[stoecker]

Could you please update and check the join areas example file in data_nodist as well, so all cases are covered and you're sure nothing breaks?

[bastiK]

Replying to extropy:

Made a path that fixes all the problems. The patch completely rewrites findInnerWays function. The new implementation properly traverses around the polygon rather than just tests for inside/outside.

Yes, Weiler–Atherton is much better than the current strange method.

Did not know where to put geometric utility functions, so feel free to move them out to some other file.

There are some issues when the areas share nodes. I'll add the simplest case.

[bastiK]

Shows problem of the first version of the patch

[anonymous]

Thanks for the testing :)

Fixed a silly off by one error, now works for the adjacent areas too.

[extropy]

Improved patch.

[bastiK]

Found more pathological examples, that should be addressed by a new and shiny algorithm. ;)

(anonymous was me)

[extropy]

Keep them coming.

What is the expected behavior of example 3?

A multipolygon or the inner part removed?

[bastiK]

Replying to extropy:

Keep them coming.

What is the expected behavior of example 3?

A multipolygon or the inner part removed?

I'd say, just the outer way. But I'm not sure.

[extropy]

Okay, here is the next patch.

[extropy]

Improved patch.

[bastiK]

next example

[bastiK]

Why isn't there an error? It fails silently.

[extropy]

example 4 works fine for me.

What result does it produce for you?

[bastiK]

Sorry, you are right - example 4 works fine.

[bastiK]

example 4:2 - produces self overlapping way

[bastiK]

Also, is there a reason to ask if the way should be reversed?

[extropy]

Replying to bastiK:

Also, is there a reason to ask if the way should be reversed?

I guess no, as the orientation of resulting (outer) way is arbitrary anyway.

Give me an example and i'll try to the prompt.

[extropy]

remove the prompt.

[bastiK]

2.osm should show the promt

[stoecker]

As you do this anyway: The ways should not be joined or reversed in case they have not been joined before (e.g. if ways are streets or the like).

In these cases multiple ways should be added which represent the outlines when joined.

Logically the whole system should work with areas which already use this system. :-)

The current join areas command does handle such cases totally incorrect.

[extropy]

Fixed the ordering of outer segments - removes the prompt and self-overlapping ways. Had to make some changes in CombineWayAction, it used HashSets that made the order random and bad stuff happened.

There may still be similar problems with inner parts of multipolygons as they use the old code. I don't have any more brain power left today to pick that code apart.

[extropy]

Replying to stoecker:

As you do this anyway: The ways should not be joined or reversed in case they have not been joined before (e.g. if ways are streets or the like).

Join overlapping areas only works for areas (buildings, parking spaces, landuse,...). Non-area ways like streets are not target audience for this tool.

In these cases multiple ways should be added which represent the outlines when joined.

Logically the whole system should work with areas which already use this system. :-)

The current join areas command does handle such cases totally incorrect.

I do not quite understand what you are saying here. Maybe make some examples?

[bastiK]

Replying to extropy:

Fixed the ordering of outer segments - removes the prompt and self-overlapping ways. Had to make some changes in CombineWayAction, it used HashSets that made the order random and bad stuff happened.

There may still be similar problems with inner parts of multipolygons as they use the old code. I don't have any more brain power left today to pick that code apart.

OK, I think it's in pretty good shape, already. :)

[bastiK]

As multipolygons are the area data type in osm (and a cosed way is only a simplification for the most common case) this tool should be able to join 2 multipolygons as well as 1 multiploygon and 1 closed way.

In this context, some multipolgons happen to have a highway as part of their outer way ring. This highway should probably be neither reversed, nor combined with other ways. (But can be split.)

[extropy]

Replying to bastiK:

As multipolygons are the area data type in osm (and a cosed way is only a simplification for the most common case) this tool should be able to join 2 multipolygons as well as 1 multiploygon and 1 closed way.

In this context, some multipolgons happen to have a highway as part of their outer way ring. This highway should probably be neither reversed, nor combined with other ways. (But can be split.)

Okay, this makes sense. But it's quite bigger project to join arbitrary multipolygons. Let me think on it.

[extropy]

Improved patch - preserves path orientation when possible.

[anonymous]

Replying to extropy:

Replying to bastiK:

As multipolygons are the area data type in osm (and a cosed way is only a simplification for the most common case) this tool should be able to join 2 multipolygons as well as 1 multiploygon and 1 closed way.

In this context, some multipolgons happen to have a highway as part of their outer way ring. This highway should probably be neither reversed, nor combined with other ways. (But can be split.)

Okay, this makes sense. But it's quite bigger project to join arbitrary multipolygons. Let me think on it.

Sure, it is more a general idea for every one, just thought that would be nice. ;)

Might be rather complicated: for outer rings it is a union and for inner inner rings a cut, what if they overlap, ...

[bastiK]

anonymous <- me

[extropy]

Replying to anonymous:

Replying to extropy:

Replying to bastiK:

As multipolygons are the area data type in osm (and a cosed way is only a simplification for the most common case) this tool should be able to join 2 multipolygons as well as 1 multiploygon and 1 closed way.

In this context, some multipolgons happen to have a highway as part of their outer way ring. This highway should probably be neither reversed, nor combined with other ways. (But can be split.)

Okay, this makes sense. But it's quite bigger project to join arbitrary multipolygons. Let me think on it.

Sure, it is more a general idea for every one, just thought that would be nice. ;)

Might be rather complicated: for outer rings it is a union and for inner inner rings a cut, what if they overlap, ...

The logic is quite simple - you split the overlapping polygons into basic regions, each region having zero or more polygons that fill it. If zero - it's a hole, if nonzero then filled. Then glue the filled regions back together.

The trick is getting the code right.

[bastiK]

Hi, I added 2 more examples, the latter takes quite some time to process (and the result is not right).

[extropy]

Fixes example 5 and 7

[extropy]

Fixed 5 and 7. To fix 6 more rewrite is needed.

This changeset is getting uncomfortably large for my first patch.

Maybe we can commit the changes as is (provided the code looks OK) and then I'll try to make it work with multipolygons/more than 2 polygons/example 6.

[bastiK]

(In [3445]) see #5179 (patch by viesturs) - Join overlapping areas produces bad results

[bastiK]

Did a little white space formatting - hope you don't mind.

Do you know the JTS Topology Suite? If you run JTSTestBuilder.java, it shows a nice GUI where you can play with it. Maybe one can copy a view tricks from there. ;)

[Ldp]

(Issue 1) With r3445, every join will produce a popup "No intersection found. Nothing was changed." Hitting OK will allow you to continue, and the areas are actually joined.

(Issue 2) Merging the top left and bottom right areas (only touching in a single shared node) in the t5179.osm example will also produce that popup, but the result is an '8' shaped way.

[Ldp]

Example to show the popup and "8" shape after join

[extropy]

Fixed nothing changed popup.

[extropy]

Finally got to a PC and some time.

Fixed "nothing changed" popup.

I think the 8 shaped way is expected behavior. Is it not? The old implementation did the same thing.

[bastiK]

(In [3449]) see #5179 (patch by viesturs) - Fixed "nothing changed" popup (Join overlapping areas produces bad results)

[bastiK]

Replying to extropy:

I think the 8 shaped way is expected behavior. Is it not?

Not sure, I asked it on talk:  http://lists.openstreetmap.org/pipermail/talk/2010-August/053216.html

[Ldp]

I know it used to do this before as well. With the current work on this, I saw an opportunity to get that 8 shaped way issue fixed as well.

I say fixed, as that's my personal take on this: areas touching each other in just 1 single shared node should not be considered candidates for joining. I consider those to be 2 separate areas.

I could point out what OGC Simple Features thinks of self-intersecting ways, but as that's not entirely relevant to OSM, I won't. :-) (it is relevant to postgis based users of OSM data, in some situations)

[extropy]

Replying to Ldp:

I know it used to do this before as well. With the current work on this, I saw an opportunity to get that 8 shaped way issue fixed as well.

Okay, let's fix it.

I say fixed, as that's my personal take on this: areas touching each other in just 1 single shared node should not be considered candidates for joining. I consider those to be 2 separate areas.

I could point out what OGC Simple Features thinks of self-intersecting ways, but as that's not entirely relevant to OSM, I won't. :-) (it is relevant to postgis based users of OSM data, in some situations)

I don't know OGC but have some common sense.

I propose this behavior:

• Areas overlap: join them
• Areas touching. Do not join them.
• Areas with common segment. Join them.

If areas have multiple places where they touch/overlap, treat each case independently. This results in:

• Touching in multiple places - do not join.
• Overlapping in one place, touching in other - join the overlapping part, leave the touching one as is.
• Overlapping in two places - join at both places, creating a multipolygon.

Sounds OK?

[bastiK]

Replying to extropy:

Replying to Ldp:

I know it used to do this before as well. With the current work on this, I saw an opportunity to get that 8 shaped way issue fixed as well.

Okay, let's fix it.

I say fixed, as that's my personal take on this: areas touching each other in just 1 single shared node should not be considered candidates for joining. I consider those to be 2 separate areas.

I could point out what OGC Simple Features thinks of self-intersecting ways, but as that's not entirely relevant to OSM, I won't. :-) (it is relevant to postgis based users of OSM data, in some situations)

I don't know OGC but have some common sense.

That's good to hear. ;)

I propose this behavior:

• Areas overlap: join them
• Areas touching. Do not join them.
• Areas with common segment. Join them.

If areas have multiple places where they touch/overlap, treat each case independently. This results in:

• Touching in multiple places - do not join.
• Overlapping in one place, touching in other - join the overlapping part, leave the touching one as is.
• Overlapping in two places - join at both places, creating a multipolygon.

Sounds OK?

Yes, sounds good.

What about fixing a single closed way with broken geometry? (E.g. self-overlapping segments, duplicate nodes except first and last.) Are you going to address this too or is it a different issue?

[extropy]

What about fixing a single closed way with broken geometry? (E.g. self-overlapping segments, duplicate nodes except first and last.) Are you going to address this too or is it a different issue?

Geometry cleanup is a prerequisite to sane joining. The current code already does some very crude cleanup. I'll try my best!

[bastiK]

Then I have a view invalid shapes for you to consider. :)

[anonymous]

Hi, the last example (and example 6) take ages on my computer. I tried 2 shapes of comparable complexity in the jts library, and it took only a split second to compute the union of shapes. So maybe some optimization is still possible...

[extropy]

Yeah, tons of optimization to do, but first, let's get the behavior right,

[Ldp]

When joining two areas, where one has the tags on a relation and the other on a way, and they differ, you get the popup where you can resolve the tagging conflicts. If you cancel that, you get an NPE.

The example file has two ways: 1 untagged which is an outer member in a multipolygon relation tagged a=1, and 1 tagged as a=2. Join them, and press cancel on the "Conflicts when combining ways" dialog. (Pressing OK works ok)

Build-Date: 2010-08-23 10:42:00 Revision: 3456 Is-Local-Build: true

Identification: JOSM/1.5 (3456 SVN en) Memory Usage: 32 MB / 989 MB (10 MB allocated, but free) Java version: 1.6.0_20, Sun Microsystems Inc., Java HotSpot(TM) Client VM Operating system: Windows XP Dataset consistency test: No problems found

Plugin: AddrInterpolation (21710) Plugin: ghost (2) Plugin: multipoly (22171) Plugin: terracer (22169) Plugin: validator (22688) Plugin: wmsplugin (22735)

java.lang.NullPointerException

at org.openstreetmap.josm.actions.JoinAreasAction.fixMultipolygons(JoinAreasAction.java:963) at org.openstreetmap.josm.actions.JoinAreasAction.joinAreas(JoinAreasAction.java:284) at org.openstreetmap.josm.actions.JoinAreasAction.actionPerformed(JoinAreasAction.java:216) at javax.swing.SwingUtilities.notifyAction(Unknown Source) at javax.swing.JComponent.processKeyBinding(Unknown Source) at javax.swing.KeyboardManager.fireBinding(Unknown Source) at javax.swing.KeyboardManager.fireKeyboardAction(Unknown Source) at javax.swing.JComponent.processKeyBindingsForAllComponents(Unknown Source) at javax.swing.JComponent.processKeyBindings(Unknown Source) at javax.swing.JComponent.processKeyEvent(Unknown Source) at java.awt.Component.processEvent(Unknown Source) at java.awt.Container.processEvent(Unknown Source) at java.awt.Component.dispatchEventImpl(Unknown Source) at java.awt.Container.dispatchEventImpl(Unknown Source) at java.awt.Component.dispatchEvent(Unknown Source) at java.awt.KeyboardFocusManager.redispatchEvent(Unknown Source) at java.awt.DefaultKeyboardFocusManager.dispatchKeyEvent(Unknown Source) at java.awt.DefaultKeyboardFocusManager.preDispatchKeyEvent(Unknown Source) at java.awt.DefaultKeyboardFocusManager.typeAheadAssertions(Unknown Source) at java.awt.DefaultKeyboardFocusManager.dispatchEvent(Unknown Source) at java.awt.Component.dispatchEventImpl(Unknown Source) at java.awt.Container.dispatchEventImpl(Unknown Source) at java.awt.Window.dispatchEventImpl(Unknown Source) at java.awt.Component.dispatchEvent(Unknown Source) at java.awt.EventQueue.dispatchEvent(Unknown Source) at java.awt.EventDispatchThread.pumpOneEventForFilters(Unknown Source) at java.awt.EventDispatchThread.pumpEventsForFilter(Unknown Source) at java.awt.EventDispatchThread.pumpEventsForHierarchy(Unknown Source) at java.awt.EventDispatchThread.pumpEvents(Unknown Source) at java.awt.EventDispatchThread.pumpEvents(Unknown Source) at java.awt.EventDispatchThread.run(Unknown Source)

[extropy]

Working on second version, stay tuned.

[extropy]

New shiny implementation, handles all cases up to date.

[extropy]

Finally completed the improvements.

In this patch:

• works on more than 2 polygons
• fixes broken geometry
• resolves tag conflicts before actual join
• splits into separate polygons when only one shared node.

One more thing to finalize: when a polygon is self-overlapping, OSM displays that the overlapping parts are holes. The current join implementation also makes holes there. Is it correct?

[stoecker]

Could you please update the join areas example file in data_nodist, so when we change code again, we can verify all cases are still working.

[anonymous]

On it.

It appears there are several multipolygon relation tests in there that still don't work properly. Some more work to do.

[extropy]

anonymous = me

[bastiK]

Is it supposed to join 2 multipolygons or multipolygon & way? This did not quite work for me.

There is a class Multipolygon.java that can identify inner and outer rings.

[extropy]

Improved existing multipolygon handling, added tests to data_nodist

[extropy]

Replying to bastiK:

Is it supposed to join 2 multipolygons or multipolygon & way? This did not quite work for me.

There is a class Multipolygon.java that can identify inner and outer rings.

With the latest patch joining two multipolygons also work, but you have to select all both inner and outer ways, otherwise they will be treated as simple polygons.

You cannot join a multipolygon and unclosed way right now. And I frankly don't understand the use case.

[bastiK]

Why should the inner and outer ways be selected if I could simply select the multipolygon relation itself?

Example: have a complex forest modeled as multipolygon and you like to extend it

• by a separate patch of forest
• by a small area touching one or more forest outer ways

In the first case, the user could simply add it as outer way to the multipolygon, in the second case by joining the forest outer ways with the new ring. However, in both cases, "Join Areas" (as I imagine it) should have the same result.

It says "Join (overlapping) Areas": In osm, an area is either a multipolygon or (for simple geometries) a closed way. The tool should be able to handle both the general and the simplified case without problems!

[bastiK]

(In [3504]) reworked reverseWay and combineWay such that it can be used by other actions without hack (see #5179 - Join overlapping areas rewrite)

[bastiK]

The whole makeCommitsOneAction stuff is an ugly hack and should not be there. I did a little rework for reverseWay & combineWay; does that help?

[bastiK]

Replying to bastiK:

Why should the inner and outer ways be selected if I could simply select the multipolygon relation itself?

Example: have a complex forest modeled as multipolygon and you like to extend it

• by a separate patch of forest
• by a small area touching one or more forest outer ways

In the first case, the user could simply add it as outer way to the multipolygon, in the second case by joining the forest outer ways with the new ring. However, in both cases, "Join Areas" (as I imagine it) should have the same result.

It says "Join (overlapping) Areas": In osm, an area is either a multipolygon or (for simple geometries) a closed way. The tool should be able to handle both the general and the simplified case without problems!

This is just a suggestion, if you like to keep it the way it is now - no problem.

[anonymous]

Replying to bastiK:

Why should the inner and outer ways be selected if I could simply select the multipolygon relation itself?

Good idea, we can add this at some point.

The current implementation especially ignores multipolygon relations when only one path of the relation is selected, because the behavior is different. (The relations themselves are preserved.)

For example, if you join a polygon with hole with another polygon, the result is union of filled areas (intersection of the holes).

But if you join the hole part of multipolygon with other polygon, the result is union of the holes.

[extropy]

Replying to bastiK:

The whole makeCommitsOneAction stuff is an ugly hack and should not be there. I did a little rework for reverseWay & combineWay; does that help?

I just used what was already there. I don't fully understand how the undo/redo stack works. What should be the correct way to fix this "hack"?

[bastiK]

The correct way to do that: create a number of Command objects, put them together in a SequenceCommand and send that package to Main.main.undoRedo.add(...). That's all, no manipulation of the undo/redo buffer should be done while generating the command.

Yes, it was like this before (it comes from a plugin), but I thought, you might be pretty familiar with the code by now. :)

[Ldp]

I should mention that for the people who rely on Join Areas, to stay on r3503 until it's patched to handle r3504, or you'll screw up your objects.

[bastiK]

(In [3510]) fix rework [3504] (see #5179)

[bastiK]

didn't mean to break anything...

[bastiK]

Sorry it took so long to get back, I wanted wait for the 3522 release before including the new code.

Now I tested a little and found some minor issues:

• In the test file line 7 column 1 it produces duplicate nodes.
• line 8 column 1: The inner way that is created, looks odd. I think each closed way should have the following properties: (1) No duplicate nodes except first and last. (2) No self intersection of any kind.
• l. 9 /c. 2 (tricky islands): Under certain circumstances, after Joining, the outer or one of the inner ways stays selected. It happens randomly and I couldn't find a way to reproduce reliably.
• l. 10 /c. 2 (multipolygon): I don't see what is wrong with that multipolygon. (Execpt that both the outer way and the relation are tagged natural=water, where one would suffice.) When you do Join Action, it creates an irregular and complex polygon.

Otherwise I think it is quite good, already.

[extropy]

Fixed duplicate nodes when joining.

[extropy]

Hi!

Fixed L7C1.

L9C2 is funny. What is more funny that different ways is selected each time.

L8C1 - working on a fix.

About L10C2. It's a bit tricky to define the correct behavior. See l7c3, that is very similar to L10C2. Also see http://josm.openstreetmap.de/ticket/5179#comment:39

[extropy]

Split touching inner polygons.

[bastiK]

after join, one way is still selected

[bastiK]

the screenshot demonstrates, that a way remains selected directly after join operation

[bastiK]

Remaining things:

• l7c3 / l10c2 still not optimal, i guess it's not so easy ;)

• l3c2 - should be multipolygon with 2 inner ways

• when i select the 2 multipolygons on the bottom, it says "please select at least one closed way..."

• bottom: for specific selection order the the result is wrong: 1. left inner way 2. left outer way 3. right outer way 4. right inner way ---> it produces multiple multipolygons

For 99% of cases it works quite well, i think. Unfortunately there is a variety of odd examples and you can be sure that power user get to the limits. :)

I'd prefer if it was a little more stable, but i would also commit the current state of the patch.

Sebastian

[extropy]

Outer ways also get split when only touching.

[extropy]

Hi!

Replying to bastiK:

Remaining things:

• l7c3 / l10c2 still not optimal, i guess it's not so easy ;)

This was on purpose. I was thinking that they should be part of outer polygon. Fixed.

• l3c2 - should be multipolygon with 2 inner ways

Same as above.

• when i select the 2 multipolygons on the bottom, it says "please select at least one closed way..."

Could not reproduce.

• bottom: for specific selection order the the result is wrong: 1. left inner way 2. left outer way 3. right outer way 4. right inner way ---> it produces multiple multipolygons

Fixed.

For 99% of cases it works quite well, i think. Unfortunately there is a variety of odd examples and you can be sure that power user get to the limits. :)

I'd prefer if it was a little more stable, but i would also commit the current state of the patch.

Sebastian

Also I made a patch for the extrude tool. Can you take a look at #5427 ?

[bastiK]

(In [3554]) see #5179 (patch by viesturs) - improve join areas

[bastiK]

Hi, the tests seem to work now, only l7c1 is strange. Please try to stick to JOSM coding style, even if you don't like it :)

e.g.

for␣(Integer i␣:␣list)␣{
    ...
}

(no newline instead of last space)

Cheers, Sebastian

[anonymous]

Replying to bastiK:

Hi, the tests seem to work now, only l7c1 is strange.

There is a bug in there (wrong multipolygon). I will fix it.

Please try to stick to JOSM coding style, even if you don't like it :)

e.g.

for␣(Integer i␣:␣list)␣{
    ...
}

(no newline instead of last space)

I'm trying, I'm trying.

Cheers, Sebastian

[extropy]

anonymous <- me

[extropy]

Separate multipolygon relations for each resulting multipolygon.

[stoecker]

What is this last attachment? Adding an attachment to a fixed bug is usually useless.

[extropy]

I did not mean to close the bug, it was an accident.

The last attachment fixes the bug mentioned in comment 70.

It seems it's not been committed.

Please commit the osm-join-areas-6.6.1.patch

[bastiK]

In [3595/josm]:

applied #5179 (patch by bilbo) - Join overlapping areas / Separate multipolygon relations for each resulting multipolygon