[PATCH] Sorting relation members by connectivity changes order multiple times

[skorbut]

While working with the relation editor, I noticed the following unexpected behaviour: If I use the function "Sort the relation members" multiple times, the order of elements changes the first few times, until it finally converges.

What steps will reproduce the problem?

You can see and reproduce the behaviour with the attached file: Open the file, select all ways, in the relation window click the + button ("Create a new relation"). Add the selection to the members list, then click "Sort the relation members" multiple times.

What is the expected result?

The order of objects should stay the same after the first sorting.

What happens instead?

The order of objects changes a few times before staying the same.

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

I wrote a small patch that sorts the ways by hashcode before doing the actual sorting. Sorting by way id or similar might be possible but would not provide any advantage AFAICS: The purpose is only to make the order of the objects the same for each call of sortMembersByConnectivity.

I also noticed that the sort function does not return a sequence with the minimum possible number of discontinuities. I plan to address that in another ticket.

Relative:URL: ^/trunk
Repository:UUID: 0c6e7542-c601-0410-84e7-c038aed88b3b
Last:Changed Date: 2022-12-05 23:37:01 +0100 (Mon, 05 Dec 2022)
Revision:18608
Build-Date:2022-12-06 02:30:56
URL:https://josm.openstreetmap.de/svn/trunk

Identification: JOSM/1.5 (18608 en) Linux Ubuntu 18.04.6 LTS
Memory Usage: 618 MB / 7976 MB (239 MB allocated, but free)
Java version: 11.0.17+8-post-Ubuntu-1ubuntu218.04, Ubuntu, OpenJDK 64-Bit Server VM
Look and Feel: javax.swing.plaf.metal.MetalLookAndFeel
Screen: :0.0 2560×1440 (scaling 1.00×1.00) :0.1 2560×1440 (scaling 1.00×1.00) :0.2 1050×1680 (scaling 1.00×1.00)
Maximum Screen Size: 2560×1680
Best cursor sizes: 16×16→16×16, 32×32→32×32
Environment variable LANG: en_US.UTF-8
System property file.encoding: UTF-8
System property sun.jnu.encoding: UTF-8
Locale info: en_US
Numbers with default locale: 1234567890 -> 1234567890
Desktop environment: MATE
Java package: openjdk-11-jre:amd64-11.0.17+8-1ubuntu2~18.04
Java ATK Wrapper package: libatk-wrapper-java:all-0.33.3-20ubuntu0.1
libcommons-compress-java: libcommons-compress-java:all-1.18-1~18.04
libcommons-logging-java: libcommons-logging-java:all-1.2-2
fonts-noto: fonts-noto:all-20171026-2
VM arguments: [--module-path=/usr/share/openjfx/lib, --add-modules=java.scripting,java.sql,javafx.controls,javafx.media,javafx.swing,javafx.web, -Djosm.restart=true, -Djosm.dir.name=JOSM-latest, -Djava.net.useSystemProxies=true, --add-exports=java.base/sun.security.action=ALL-UNNAMED, --add-exports=java.desktop/com.sun.imageio.plugins.jpeg=ALL-UNNAMED, --add-exports=java.desktop/com.sun.imageio.spi=ALL-UNNAMED]

Plugins:
+ KartaView (408)
+ Mapillary (2.0.2)
+ OpeningHoursEditor (35924)
+ apache-commons (36034)
+ apache-http (35924)
+ jna (36005)
+ measurement (35978)
+ pbf (36034)
+ todo (30306)

Map paint styles:
+ https://josm.openstreetmap.de/josmfile?page=Styles/Coloured_Streets&zip=1

Last errors/warnings:
- 00015.148 E: java.lang.NumberFormatException: For input string: "test"
- 00015.343 W: Cannot start IPv4 remotecontrol server on port 8111: Address already in use (Bind failed)
- 00015.344 W: Cannot start IPv6 remotecontrol server on port 8111: Address already in use (Bind failed)

[skyper]

updated example with some roles and different types

[skyper]

I wonder if it is possible to properly sort members without knowing the type of the relation. I have added an updated example (relation_sorting_benchmark_v2.osm​) with some relations which are proper sorted and sorting creates a mess with type=route. For multipolygons and boundaries it might make sense to have as many closed rings as possible.
Probably, it is better to recheck with some real world examples.

See also #20644 where sorting never stops and #6920, #14711 and #20605 for problems with dual-carriage.

[skorbut]

@skyper: Thanks for the interest!

In the file https://josm.openstreetmap.de/browser/josm/trunk/src/org/openstreetmap/josm/gui/dialogs/relation/sort/RelationSorter.java you can see the different sorting procedures for different types of relations. They are:

• AssociatedStreetRoleStreetSorter: Class that sorts the street members of type=associatedStreet and type=street relations.
• AssociatedStreetRoleAddressHouseSorter: Class that sorts the address house members of type=associatedStreet and type=street relations.
• PublicTransportRoleStopPlatformSorter: Class that sorts the platform and stop members of type=public_transport relations.
• FromViaToSorter: Class that sorts the from, via and to members of type=restriction relations.
• sortMembersByConnectivity(): Sorts a list of members by connectivity. (I believe this one is always being used when no other sorting procedure fits.)

[skorbut]

@skyper: According to my own interpretation, the example I gave should be traversed in one go (meaning all the ways should be connected, there would not be any gap). Would you agree to that?

If my example was to be used in a multipolygon, I'd say it's an (almost) mistake, since the borders should not cross and ideally also not touch each other, right?

[skyper]

@skorbut: Thanks for taking time trying to solve some of the problems of this complex task.
Yes, I agree that a general solution (without type=* and/or roles) should always sort by connectivity and sorting should be solved within one step and then stay consistent.

As far as I remember, touching in one node is allowed for boundaries and multipolygons. Crossing or sharing segments is invalid, though.