[PATCH] Parallel ways: compute a proper one-sided buffer so large offsets work

[wangi]

Parallel mode produces spikes and loops when the offset exceeds the local radius of curvature (e.g. a maritime boundary 22 km off a coastline)

What steps will reproduce the problem?

1. Load a way with many short segments and some sharp turns, e.g. a natural=coastline way with a few hundred nodes and segments of 50-300 m.
2. Switch to Parallel mode (Shift+P) and start dragging the way sideways.
3. Keep dragging until the offset is a few times the length of the segments (a few km for a coastline; a 12 nm / 22 km territorial water boundary is a typical use).

What is the expected result?

A parallel way at the requested distance, everywhere at least that distance from the source way, following the envelope of the source: straight parts are shifted, convex corners are rounded (or mitred where that is harmless), concave corners are clipped, and parts of the source which are "swallowed" by the offset (bays narrower than twice the offset, small notches) disappear from the result. The same shape a GIS buffer operation yields, restricted to one side of the way.

What happens instead?

As soon as the offset is larger than the length of the neighbouring segments (more precisely: the local radius of curvature at a concave corner), the result explodes into spikes and loops which cover the whole screen and beyond, see the attached screenshots (first: 250 m offset, fine; second: 12 nm offset, unusable). The resulting way is useless and has to be undone.

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

Cause: ParallelWays.changeOffset() places every node of the copy at the intersection of the two neighbouring offset *lines*, unconditionally. Whenever the offset exceeds the local radius of curvature that intersection lies far away on the wrong side of the corner ("swallowtail"), which produces the spikes. For the same reason the method cannot produce a correct result at all, since a correct offset of a polyline in general has a different number of nodes than the source.

The attached patch (against r19621) rewrites ParallelWays as a proper one-sided buffer:

• every segment is offset; concave corners are clipped at the intersection of the two offset segments (only when it lies on both), convex corners are joined by a circular arc approximated by chords (new preference edit.make-parallel-way-action.arc-step-degrees, default 10°),
• the raw polyline is split at its self-intersections and against half-circle caps at both ends, every piece is kept only if it lies at (at least) the offset distance from the source, the surviving pieces are chained and the longest chain is the result,
• arcs that survive untouched at gentle corners are collapsed back to the classic mitre point, so the behaviour for the usual dual-carriageway use (small offset) is unchanged: same node count, same positions, tags copied,
• a uniform grid over the source segments and pruning of raw segments which lie entirely inside keep it interactive: a 1600-node path recomputes in 15-70 ms on a laptop.

Since the number of nodes of the result now depends on the offset, ParallelWayAction creates the nodes and ways on mouse release (single undoable command, result selected as before) and draws a preview of the parallel on the temporary layer while dragging (new stroke preference edit.make-parallel-way-action.stroke.preview). Several selected ways still yield one way each, sharing the boundary nodes and keeping their direction; a way completely swallowed by the offset is omitted; if nothing remains a notification is shown.

ParallelWays public API: the constructor, isClosedPath(), changeOffset(), commit() and getWays() are kept (getWays() is empty before commit()), getOffsetPoints() and isResultClosed() are added for the preview.

Tests: new ParallelWaysTest (small/large offsets of a line, a square inside/outside/swallowed, a sawtooth "coast" from 10 m to 22 km, a seeded 1600-node random coastline, multi-way commit with tags/direction/undo, a ring made of two ways) checking that every vertex is at least the offset away from the source and that the result has no self-intersections. Existing ParallelWayActionTest (incl. the #20908 regression) passes unchanged. Checkstyle is clean.

Known limitations of the patch: the preview during the drag is a plain line rather than the styled rendering of a real way (the way did not exist before release); when the inward offset of a closed way splits into several lobes only the longest lobe is kept; arcs are chords, so vertices can lie inside the true offset by up to about 2·r·(1−cos 5°) ≈ 0.8 %.

[wangi]

Good outcome at 250m

[wangi]

Bad outcome at 12nm

[wangi]

Good outcome at 12nm, with new code

[GerdP]

I didn't look at the code in detail, result looks very promising.

[GerdP]

Would it be possible to allow illegal geometries like ways going from points a - b- c- d - c - b - e - f?
I get these geometries when I convert a downloaded gpx track containing excursions to OSM data.
My use case: Have a gpx track containing possibly multiple excursions and a geojson file containing many thousands of POI. I want to select those POI which are close to the track and remove all others. My approch is to use the parallel ways to quickly draw a polygon around the gpx track with eg. 100m distance and than use the "All inside [testing]" method to select the wanted points.
It doesn't work because the patched code silently drops parts of the way after an excursion.

[wangi]

Replying to GerdP:

Would it be possible to allow illegal geometries like ways going from points a - b- c- d - c - b - e - f?

Can you share a test data set and I'll have a look.

Thanks/L

[GerdP]

Example GPX with some excursions

[GerdP]

If the invalid geometry causes too much trouble for the parallel way mode, maybe the code can be reused to implement a new action like "Calculate buffer" or "Calculate halo"?

[stoecker]

When you are fixing that action: The red distance line was already a bit strange and gets worse after the fix. It currently seems relative to the way segment which started the drag, which makes it somehow strange when you move the cursor away from that segment.

Can you improve that as well? Possible solutions:

• Don't let it leave original segment (probably easy to do, but may looks strange, conflicts with segment dropping)
• Draw it at current cursor position, but shift it between line and parallel segment (but: line can move completely away from cursor)
• Something better?

Also it looks strange when the line-basing segment gets removed in parallel way in your fixed method...

• In that case: Move line to a position where it is still exact (but: line can move completely away from cursor)?

Any fix should should keep the behavior for small movements as best as possible (i.e. relative to segment to see what's happening), but I assume that is automatically the case.

[wangi]

Parallel around retraced excursion

[wangi]

Replying to GerdP:

If the invalid geometry causes too much trouble for the parallel way mode, maybe the code can be reused to implement a new action like "Calculate buffer" or "Calculate halo"?

The retraced-excursion case was a bug in the chain assembly, fixed in the updated patch. Also covered by a new test. The parallel now runs the full length of demo.gpx, while the excursions on the far side of the route are correctly not part of a one-sided parallel.

I think a two-sided "buffer" action is a reasonable follow-up issue, that could reuse this code by offsetting both sides and joining them with the end caps.

Just saw the other comment - let me look at the offset red line.

[wangi]

Updated patch: excursions, helper line, selection

[wangi]

Replying to stoecker:

The red distance line was already a bit strange and gets worse after the fix. It currently seems relative to the way segment which started the drag, which makes it somehow strange when you move the cursor away from that segment.

Updated patch now relates the helper line to the nearest point on the original segment.

Also fixed a selection issue I'd seen before, in the current code, but could never pin down... In you were in parallel ways mode already then doing Shift-W to select all non-branching, wouldn't get picked up.

Any fix should should keep the behavior for small movements as best as possible (i.e. relative to segment to see what's happening), but I assume that is automatically the case.

It is.

[stoecker]

In 19624/josm:

fix #24891 - major improvements of parallel way action - patch by wangi

[stoecker]

P.S. Thanks for the improvement. Hope to see you back with other changes...

[wangi]

Replying to stoecker:

P.S. Thanks for the improvement. Hope to see you back with other changes...

Thanks, will do. Let's me know if GerdP's buffer proposal is worth doing and i can address that.

Busy now with the OpenGeofiction migration (the other two tickets I opened), but hopeful can looks at some items after that.