[Patch]Strange align nodes in circle behavior

[naoliv]

With the attached example, select the way tagged with FIXME=curve and then press o (align nodes in circle)
See how it wrongly transforms its shape

JOSM:

Repository Root: http://josm.openstreetmap.de/svn
Build-Date: 2014-06-26 01:35:33
Last Changed Author: bastiK
Revision: 7271
Repository UUID: 0c6e7542-c601-0410-84e7-c038aed88b3b
URL: http://josm.openstreetmap.de/svn/trunk
Last Changed Date: 2014-06-25 21:02:07 +0200 (Wed, 25 Jun 2014)
Last Changed Rev: 7271

Identification: JOSM/1.5 (7271 pt_BR) Linux Debian GNU/Linux unstable (sid)
Memory Usage: 824 MB / 1756 MB (429 MB allocated, but free)
Java version: 1.7.0_55, Oracle Corporation, OpenJDK 64-Bit Server VM
Java package: openjdk-7-jre:amd64-7u55-2.4.7-2
VM arguments: [-Djava.net.useSystemProxies=true, -Dawt.useSystemAAFontSettings=on]
Dataset consistency test: No problems found

Plugin: AddrInterpolation (30416)
Plugin: Create_grid_of_ways (30416)
Plugin: FixAddresses (30416)
Plugin: ImageryCache (30416)
Plugin: OpeningHoursEditor (30416)
Plugin: PicLayer (30436)
Plugin: SimplifyArea (30416)
Plugin: buildings_tools (30485)
Plugin: editgpx (30416)
Plugin: geochat (30416)
Plugin: geotools (30416)
Plugin: jts (30416)
Plugin: merge-overlap (30416)
Plugin: notes (v0.9.2)
Plugin: opendata (30436)
Plugin: pdfimport (30416)
Plugin: poly (30495)
Plugin: reverter (30436)
Plugin: tagging-preset-tester (30416)
Plugin: todo (29154)
Plugin: turnrestrictions (30454)
Plugin: undelete (30416)
Plugin: utilsplugin2 (30460)

[Balaitous]

Bug is due to collectNodesAnticlockwise algorithm.
It doesn't work because the polygon that close the way is self-crossing, and return nodes in clockwise order.
See bad-polygon.jpg

This function was introduce in r6919 for #8431 and #9839.

[Balaitous]

When the way is closed, it is not possible to determine anticlockwise order for nodes.

[GerdP]

Found this while working on #20041. Please check the result that you get when you select the nodes of the FIXME way instead of the way. Is that the result you expected?

[GerdP]

The current code adds a temporate node to calculate the direction of an unclosed way. This calculation fails when the resulting way is self-crossing. It is easy to detect the self-crossing but I am not sure what to do when it was detected.

• show a notification like "Selection could not be used to align in circle." or maybe
• ignore the direction and use the result that is calculated when the way nodes are selected.

[skyper]

Why are the end nodes moved in both cases?

Even with only nodes selected the result looks strange to me. The movement of the middle nodes is too much and the radius too small.

I would like to get a result similar to:

1. Select way and middle node with connection and Disconnect node from way
2. Select way and align in circle
3. Select previous disconnected node and move onto way

Nodes close to one end are weighted too much in my opinion.

Would show a notification and leave these situations for other action like circle arc or spline.

[GerdP]

Why are the end nodes moved in both cases?

What do you mean with both cases?
If only nodes are selected there is no "end node", the algo simply calculates the center of the four nodes, then the avg. distance of the nodes to that center as radius and then moves each node so that it lies on the virtual line with this center and radius.

Nodes close to one end are weighted too much in my opinion.

Hm, I don't think that we can simply ignore nodes which are close to the end, but you are right that the result is far from expected. I assume this is always the case when the nodes are almost on a straight line. A human probably recognizes the circular pattern because of the other ways but the algo just looks at the selected nodes.
I'll add the test to reject this selection as suggested in comment:3

[GerdP]

I assume this is always the case when the nodes are almost on a straight line.

It's quite strange, (both with tested and with r17386):

• When I select the 4 nodes of the original way and use "merge selection" so that I have only those nodes in a new layer the result looks very different and more like you expected.
• When I use copy & "paste at source position" the result looks as in the complete data.

Will look again at this tomorrow...

[GerdP]

Ah, quite simple. The order of the nodes changes and thus the calculation of the center. That's why the algo tries to sort the nodes in counter clockwise order.

[skyper]

Replying to GerdP:

Why are the end nodes moved in both cases?

What do you mean with both cases?
If only nodes are selected there is no "end node", the algo simply calculates the center of the four nodes, then the avg. distance of the nodes to that center as radius and then moves each node so that it lies on the virtual line with this center and radius.

Sorry, you are right, with only nodes it is just the wrong action to use.

Nodes close to one end are weighted too much in my opinion.

Hm, I don't think that we can simply ignore nodes which are close to the end, but you are right that the result is far from expected. I assume this is always the case when the nodes are almost on a straight line. A human probably recognizes the circular pattern because of the other ways but the algo just looks at the selected nodes.
I'll add the test to reject this selection as suggested in comment:3

Hmh, maybe, nodes on the "wrong" side can be ignored in these cases and only the nodes on the side with more distance to a straight line be used.

[GerdP]

It's quite tricky. The method Geometry.getCenter() is used to calculate the center of the circle. IIGTR the algo used in this method is meant to be used with the nodes of a polygon which is not self-intersecting, the order of the nodes would be that of a closed way (first node == last node)
If only nodes are selected the code in AlignInCircleAction doesn't sort the nodes and thus the result of the center calculation is more or less unpredictable. The code itself documents this a possible selection: "Align these nodes, all are fix" but obviously the code doesn't work well and this selection is also not documented in the wiki wiki:Help/Action/AlignInCircle
I see no real use case for this selection, so I think we should simply reject a selection that contains only nodes.

[GerdP]

The tested version r17329 as well as latest r17386 also don't complain when a P-shaped way is selected, result of action is garbage.

[GerdP]

reg. end nodes of an unclosed way:
The current code doesn't fix them completely, they may be moved to or away from the calculated center. This is now different to "More tools -> Circle arc" action from utilsplugin2.
This also happens for roundabout ways. Sonetimes "fixed" nodes have to be moved.
For unclosed ways sometimes the better solution seems to be creating a new circle as a temporary helper line and move the existing nodes closer to that.
It probably the same iteration process as rectifying angles in buildings where some angles are not 90°.

[GerdP]

work in progress

[skyper]

Ok, reg end nodes, it is just the wrong action for this use case and Circle arc is the one to use.
No doubt about moving "fixed nodes" but only to the arc without distributing preserving angles if possible.

Regarding only nodes, I still like the option. If finding the proper center is a problem, how about sticking to the selection order or define the first two as "diameter" and the rest are only corner nodes?

[GerdP]

Regarding only nodes, I still like the option. If finding the proper center is a problem, how about sticking to the selection order or define the first two as "diameter" and the rest are only corner nodes?

Do you have a use case? Something like natural=tree arranged in a circle maybe?

We can still allow it but it would require a different algo to calculate the center. I would simply calculate the avg. lat and avg. lon, similar to getNodesCenter()in source:/josm/trunk/src/org/openstreetmap/josm/command/TransformNodesCommand.java​

Edit: Problem with this simple algo is that a repeated action moves all nodes again. So, if you don't find a good use for this I'll remove the support.

[skyper]

A simple case is a pier as area with one end as circle arc or a big sundial with hour marks.

Many historical monuments with astronomical background are other examples and in architecture you will find polygons inside polygons. Vauban is famous for that, e.g. ​Neuf-Brisach

[GerdP]

I don't get it. In what situation do you select 4 or more nodes and press O to arrange them? And what do you expect?

[skyper]

playground with some examples

[skyper]

I would expect regular polygons just like if I select a way with these nodes.

I thought, it can help to preserve shapes of complex polygons and polygons only part of a way or even virtual polygons like the aligned walls and polygons in Neuf-Brisach. Playing around, I see that it does not work and I still have to use helper lines for the rectangles and the polygons.

Right now, I am not sure if this is the proper action to use. I do not like that all nodes are moved if only one or two of many have an offset but that is calling for a new action. On the other hand, we do not have any action for regular shapes besides Orthogonalize shape which fails completely with uneven corner nodes.

See my playground​ with some simple examples of regular shapes.

[GerdP]

I do not like that all nodes are moved if only one or two of many have an offset

That's what I thought. Without any selected way it is not possible to define the wanted center.

[GerdP]

• don't allow selection that contains no ways
• improve test coverage (todo: outside download area)
• simplify code
• patch adds test data with various combinations (alignCircleCases.osm), valid or not.

I wasn't sure how to handle the case that both a center is given and two nodes of the way(s) are selected. (sel=7) I decided that this means the two way nodes define only the diameter. The unpatched code ignored this special case.
The wiki doesn't yet document the special meaning of two selected way nodes.

[GerdP]

Reg. selection that contains only nodes: We could allow that if there is exactly one way which has all selected nodes as children.
No, I don't like that as well since the result is very different to the old current behaviour.
This action is really a brain teaser ;)
My understanding is this: the algo which caculates the move commands needs a center point and a radius and one or mode nodes which should be moved. My findings so far:

• We must reject all selections which don't allow to find the center and radius.
• the center can be specified by the user, either by selecting a single node that is not on the modified way(s) or by selecting one or more ways which form a closed ring and exactly two nodes of the way/these ways. This method gives the diameter and - if not yet known - the center for the circle.
• If the center is not known a 2nd algo Geometry.getCenter() tries to calculate it. This algo needs at least 4 nodes and the nodes must match certain criteria, e.g. a (virtually closed) way that is drawn along the nodes in the given order must not be self intersecting, else this 2nd algo may calculate a wrong center. So, the order of the move-nodes is important. Different methods to select the nodes may produce different orders, and the user has no way to check this order without a debugging tool :( The only way to select the nodes in a specific order seems to be to select them one after the other in the wanter order.
• if no center is given and the 2nd algo failed we must stop with a message like "Cannot determine center of circle for this geometry."
• if a center is known the radius is calculated as average distance to each node from the center
• selected move-nodes are fixed, means "angle relative to center should not be modified"

[GerdP]

10205.2.patch​ adds robustness and unit test

• if only nodes and no way are selected, order the nodes using the angle to the agv. east-north position. This should produce a predictable result
• a center node can be selected also when one unclosed way is selected. This allows to get a better result for example.osm.bz2​
• if way(s) are selected the order the nodes is determined by the occurence in the way(s). Self-Intersecting polygons are rejected if no center node is given

I'll commit this tomorrow if nobody complains.

[GerdP]

In 17393/josm:

see #10205: Strange align nodes in circle behavior

• allow to define center node also when a single unclosed way is selected
• add robustness and more unit tests for evaluation of valid selections
• if only nodes and no way are selected, order the nodes using the angle to the agv. east-north position. This should produce a predictable result
• if way(s) are selected the order the nodes is determined by the occurence in the way(s). Self-Intersecting polygons are rejected if no center node is given
• don't throw InvalidSelection when selection is valid but no point was moved, let buildCommand() return null instead

With a selection that gives a center point and way(s) which are not even close to a circular shape the result might still be surprising. Sometimes the way nodes are arranged around the center node, sometimes they are moved so that a circle arc with nearly the same length is produced. The result changes significantly when the way nodes are also selected. Subject to further improvements.

[skyper]

The difference is the result of using either a radius/diameter or a shorter chord.

I am wondering about the restriction to at least four nodes as three nodes already form a polygon.

[GerdP]

Replying to skyper:

The difference is the result of using either a radius/diameter or a shorter chord.

Not sure what you mean.

I am wondering about the restriction to at least four nodes as three nodes already form a polygon.

I agree that it looks strange, but when I allow just three nodes this will always return "nothing changed".

[skyper]

Replying to GerdP:

Replying to skyper:

The difference is the result of using either a radius/diameter or a shorter chord.

Not sure what you mean.

Sorry, I was off. Thought, that there are two different ways to calculate the diameter of the underlying circle and that it changes when we only look at (circle) segments like open ways.

What surprised me, is the fact that it produces self-intersecting ways, now.

I am wondering about the restriction to at least four nodes as three nodes already form a polygon.

I agree that it looks strange, but when I allow just three nodes this will always return "nothing changed".

I see. It works with a way with only three child nodes if you select two way nodes in addition. So I can create triangles, nice. Probably, nothing we can do but proper document.

[GerdP]

What surprised me, is the fact that it produces self-intersecting ways, now.

It should not unless the way(s) are already self-intersecting. Do you have an example?

[skyper]

example for self-intersecting results

[skyper]

Replying to GerdP:

What surprised me, is the fact that it produces self-intersecting ways, now.

It should not unless the way(s) are already self-intersecting. Do you have an example?

See attachment:josm_10205_self_intersecting_example.osm​​. Select the way and any one or two middle node(s) (B-E).

[GerdP]

Are we talking about r17393?

[GerdP]

Ah, yes, now I see. Result is the same for tested, right? I assume the method really only works well when the input is already close to the wanted geometry. I could add more tests to validate the result but we could also say garbage in -> garbage out ;)

[skyper]

Yes, same result with tested and latest (r17391), has nothing to do with r17393.

Think the result should never be an self-intersecting way. The problem is that the order of way nodes is not in sync with the order on the virtual circle.

Anyway, sounds like a new enhancement (ticket) as you are right, we do not care about a correct selection for e.g. align in line either.
I am thinking about a new action to create regular polygons but with fixed end nodes and an ellipsoid instead of a circle.

[GerdP]

I think the original ticket is fixed now. There is already a ticket for a new mapmode, see #2891. Maybe also #6385.