001// License: GPL. For details, see LICENSE file.
002package org.openstreetmap.josm.actions.mapmode;
003
004import java.util.ArrayList;
005import java.util.Arrays;
006import java.util.Collection;
007import java.util.Collections;
008import java.util.HashSet;
009import java.util.List;
010import java.util.Set;
011import java.util.function.IntConsumer;
012import java.util.stream.IntStream;
013
014import org.openstreetmap.josm.command.AddCommand;
015import org.openstreetmap.josm.command.Command;
016import org.openstreetmap.josm.command.SequenceCommand;
017import org.openstreetmap.josm.data.UndoRedoHandler;
018import org.openstreetmap.josm.data.coor.EastNorth;
019import org.openstreetmap.josm.data.osm.DataSet;
020import org.openstreetmap.josm.data.osm.Node;
021import org.openstreetmap.josm.data.osm.NodeGraph;
022import org.openstreetmap.josm.data.osm.OsmDataManager;
023import org.openstreetmap.josm.data.osm.Way;
024
025/**
026 * Helper for {@link ParallelWayAction}.
027 * <p>
028 * Computes a one-sided offset ("parallel") of a branchless path made of one or more ways.
029 * <p>
030 * The algorithm is a proper one-sided buffer, which also works when the offset is much larger than
031 * the length of the segments of the source path (e.g. a maritime boundary 22 km off a coastline):
032 * <ol>
033 * <li>Each segment is offset by the requested distance.</li>
034 * <li>At every vertex the two neighbouring offset segments are joined: on the inner side of a turn they are
035 * clipped at their intersection, on the outer side a mitre is used for gentle turns and a circular arc
036 * (approximated by chords) for sharp turns or when the mitre would overshoot too far.</li>
037 * <li>The resulting raw polyline is split at its self-intersections. Every piece is kept only if it lies at
038 * (at least) the offset distance from the source path. Pieces which are closer belong to inverted loops
039 * ("swallowtails") and are dropped. The remaining pieces are chained; the longest chain is the result.</li>
040 * </ol>
041 * All calculations are done in projected coordinates.
042 * <p>
043 * Contrary to earlier versions the nodes and ways are only created (and added to the data set) by
044 * {@link #commit()}, since the number of nodes of the result depends on the offset. Use
045 * {@link #getOffsetPoints()} to draw a preview while the offset is changed.
046 */
047public class ParallelWays {
048
049    /** Default angular step used to approximate circular arcs, in degrees */
050    public static final double DEFAULT_ARC_STEP_DEGREES = 10;
051
052    private static final int NO_NODE = -1;
053    /** marker for raw segments of the end caps, which are only used to trim the result and are never part of it */
054    private static final int CAP = -2;
055
056    private final List<Way> sourceWays;
057    private final boolean copyTags;
058    private final double arcStep;
059
060    /** the source nodes, in path order (duplicates by coordinate removed, oriented like the reference way) */
061    private final List<Node> sortedNodes;
062    private final boolean closed;
063    private final int nodeCount;
064
065    private final double[] px;
066    private final double[] py;
067    /** unit direction of segment i */
068    private final double[] dirX;
069    private final double[] dirY;
070    private final double[] segLen;
071    /** bounding boxes of the source segments, used to speed up distance computations */
072    private final double[] segMinX;
073    private final double[] segMinY;
074    private final double[] segMaxX;
075    private final double[] segMaxY;
076
077    /** whether the source way runs in the same direction as sortedNodes (aligned with sourceWays) */
078    private final boolean[] wayForward;
079    /** source way index for each source segment */
080    private final int[] segWay;
081
082    // Spatial index of the source segments (rebuilt for every offset, since the cell size depends on it)
083    private double gridCell;
084    private double gridMinX;
085    private double gridMinY;
086    private int gridCols;
087    private int gridRows;
088    private int[][] gridCells;
089    private int[] gridStamp;
090    private int gridQuery;
091
092    // Result of the last changeOffset call
093    private List<EastNorth> resultPts = Collections.emptyList();
094    private int[] resultPieceSeg = new int[0];
095    private int[] resultPointNode = new int[0];
096    private boolean resultClosed;
097
098    private List<Way> ways = Collections.emptyList();
099
100    /**
101     * Constructs a new {@code ParallelWays}.
102     * @param sourceWays source ways
103     * @param copyTags whether tags should be copied
104     * @param refWayIndex Need a reference way to determine the direction of the offset when we manage multiple ways
105     * @throws IllegalArgumentException if the ways do not form a branchless path
106     */
107    public ParallelWays(Collection<Way> sourceWays, boolean copyTags, int refWayIndex) {
108        this(sourceWays, copyTags, refWayIndex, DEFAULT_ARC_STEP_DEGREES);
109    }
110
111    /**
112     * Constructs a new {@code ParallelWays}.
113     * @param sourceWays source ways
114     * @param copyTags whether tags should be copied
115     * @param refWayIndex Need a reference way to determine the direction of the offset when we manage multiple ways
116     * @param arcStepDegrees angular step (in degrees) of the chords approximating arcs at convex corners
117     * @throws IllegalArgumentException if the ways do not form a branchless path
118     * @since 19624
119     */
120    public ParallelWays(Collection<Way> sourceWays, boolean copyTags, int refWayIndex, double arcStepDegrees) {
121        this.sourceWays = new ArrayList<>(sourceWays);
122        this.copyTags = copyTags;
123        this.arcStep = Math.toRadians(Math.max(1, Math.min(90, arcStepDegrees)));
124
125        // Find a linear ordering of the nodes. Fail if there isn't one.
126        NodeGraph nodeGraph = NodeGraph.createUndirectedGraphFromNodeWays(this.sourceWays);
127        List<Node> sortedNodesPath = nodeGraph.buildSpanningPath();
128        if (sortedNodesPath == null || sortedNodesPath.size() < 2)
129            throw new IllegalArgumentException("Ways must have spanning path"); // Create a dedicated exception?
130
131        List<Node> nodes = new ArrayList<>(sortedNodesPath.size());
132        for (Node n : sortedNodesPath) {
133            if (nodes.isEmpty() || !nodes.get(nodes.size() - 1).getEastNorth().equalsEpsilon(n.getEastNorth(), 1e-9)) {
134                nodes.add(n);
135            }
136        }
137        closed = nodes.size() > 2 && nodes.get(0) == nodes.get(nodes.size() - 1);
138        if (closed) {
139            nodes.remove(nodes.size() - 1);
140        }
141        if (nodes.size() < 2)
142            throw new IllegalArgumentException("Ways must have spanning path");
143
144        Way refWay = this.sourceWays.get(refWayIndex);
145        if (!isForward(nodes, refWay, closed)) {
146            Collections.reverse(nodes); // need to keep the orientation of the reference way.
147        }
148        if (closed) {
149            // rotate so that the path starts at a way boundary: every way is then a contiguous run of nodes
150            Node start = this.sourceWays.stream().map(Way::firstNode).filter(nodes::contains).findFirst().orElse(nodes.get(0));
151            Collections.rotate(nodes, -nodes.indexOf(start));
152            nodes.add(nodes.get(0));
153        }
154        sortedNodes = nodes;
155        nodeCount = nodes.size();
156
157        // Initialize the required parameters. (segment directions, etc.)
158        px = new double[nodeCount];
159        py = new double[nodeCount];
160        for (int i = 0; i < nodeCount; i++) {
161            EastNorth en = nodes.get(i).getEastNorth();
162            px[i] = en.getX();
163            py[i] = en.getY();
164        }
165        int segCount = nodeCount - 1;
166        dirX = new double[segCount];
167        dirY = new double[segCount];
168        segLen = new double[segCount];
169        segMinX = new double[segCount];
170        segMinY = new double[segCount];
171        segMaxX = new double[segCount];
172        segMaxY = new double[segCount];
173        for (int i = 0; i < segCount; i++) {
174            double dx = px[i + 1] - px[i];
175            double dy = py[i + 1] - py[i];
176            double len = Math.hypot(dx, dy);
177            segLen[i] = len;
178            dirX[i] = dx / len;
179            dirY[i] = dy / len;
180            segMinX[i] = Math.min(px[i], px[i + 1]);
181            segMaxX[i] = Math.max(px[i], px[i + 1]);
182            segMinY[i] = Math.min(py[i], py[i + 1]);
183            segMaxY[i] = Math.max(py[i], py[i + 1]);
184        }
185
186        // Map the source ways onto the path
187        int wayCount = this.sourceWays.size();
188        wayForward = new boolean[wayCount];
189        segWay = new int[segCount];
190        Arrays.fill(segWay, -1);
191        for (int w = 0; w < wayCount; w++) {
192            Way way = this.sourceWays.get(w);
193            Set<Node> wayNodes = new HashSet<>(way.getNodes());
194            // indices (without the closing duplicate) of the path nodes belonging to this way
195            boolean[] present = new boolean[nodeCount];
196            int first = -1;
197            int last = -1;
198            for (int i = 0; i < nodeCount - (closed ? 1 : 0); i++) {
199                if (wayNodes.contains(sortedNodes.get(i))) {
200                    present[i] = true;
201                    if (first < 0) {
202                        first = i;
203                    }
204                    last = i;
205                }
206            }
207            if (first < 0) {
208                first = 0;
209                last = 0;
210            } else if (closed && present[0] && present[nodeCount - 2]) {
211                // the run of this way wraps around the closing node: find where it starts
212                int i = nodeCount - 2;
213                while (i > 0 && present[i - 1]) {
214                    i--;
215                }
216                first = i;
217                last = nodeCount - 1;
218            }
219            wayForward[w] = isForward(sortedNodes.subList(first, last + 1), way, false);
220            for (int i = first; i < last; i++) {
221                segWay[i] = w;
222            }
223        }
224    }
225
226    /**
227     * Checks whether a way runs in the same direction as a node list.
228     * @param path the node list
229     * @param way the way
230     * @param cyclic whether the node list is a ring (without repeated closing node)
231     * @return {@code true} if the first segment of the way, found in the path, has the same orientation
232     */
233    private static boolean isForward(List<Node> path, Way way, boolean cyclic) {
234        int n = path.size();
235        for (int k = 0; k < way.getNodesCount() - 1; k++) {
236            int a = path.indexOf(way.getNode(k));
237            int b = path.indexOf(way.getNode(k + 1));
238            if (a >= 0 && b >= 0 && a != b) {
239                if (cyclic) {
240                    return ((b - a) % n + n) % n < n / 2.0;
241                }
242                return b > a;
243            }
244        }
245        return true;
246    }
247
248    /**
249     * Determines if the nodes graph form a closed path
250     * @return {@code true} if the nodes graph form a closed path
251     */
252    public boolean isClosedPath() {
253        return closed;
254    }
255
256    /**
257     * The point of the source path closest to a given point, see {@link #closestPoint(EastNorth)}.
258     * @since 19624
259     */
260    public static final class ClosestPoint {
261        /** the closest point on the source path */
262        public final EastNorth point;
263        /** start of the source segment the closest point lies on */
264        public final EastNorth segmentStart;
265        /** end of the source segment the closest point lies on */
266        public final EastNorth segmentEnd;
267        /** distance between the given point and the path; positive if the given point lies to the left of the path
268         * (in the direction of the reference way), i.e. the sign matches the offset of {@link #changeOffset(double)} */
269        public final double signedDistance;
270
271        ClosestPoint(EastNorth point, EastNorth segmentStart, EastNorth segmentEnd, double signedDistance) {
272            this.point = point;
273            this.segmentStart = segmentStart;
274            this.segmentEnd = segmentEnd;
275            this.signedDistance = signedDistance;
276        }
277    }
278
279    /**
280     * Finds the point of the source path closest to the given point. Used to relate the offset to the part of the
281     * path the mouse is currently next to (rather than to the segment where the drag started).
282     * @param p the point (projected coordinates)
283     * @return the closest point, the segment it lies on and the signed distance
284     * @since 19624
285     */
286    public ClosestPoint closestPoint(EastNorth p) {
287        double x = p.getX();
288        double y = p.getY();
289        int bestSeg = 0;
290        double bestSq = Double.POSITIVE_INFINITY;
291        double bestT = 0;
292        for (int i = 0; i < nodeCount - 1; i++) {
293            double rx = x - px[i];
294            double ry = y - py[i];
295            double t = Math.max(0, Math.min(segLen[i], rx * dirX[i] + ry * dirY[i]));
296            double ex = rx - t * dirX[i];
297            double ey = ry - t * dirY[i];
298            double dSq = ex * ex + ey * ey;
299            if (dSq < bestSq) {
300                bestSq = dSq;
301                bestSeg = i;
302                bestT = t;
303            }
304        }
305        int i = bestSeg;
306        // Side of the path: left of the closest segment is positive. If the closest point is a vertex between two
307        // segments, the point lies in the wedge outside the corner, where the two segments may disagree about the
308        // side (for turns sharper than 90°): the side is then the outside of the turn.
309        double side = dirX[i] * (y - py[i]) - dirY[i] * (x - px[i]);
310        int vertex = -1;
311        if (bestT <= 0) {
312            vertex = i;
313        } else if (bestT >= segLen[i]) {
314            vertex = i + 1;
315        }
316        if (vertex >= 0) {
317            int segCount = nodeCount - 1;
318            int prev = vertex - 1;
319            int next = vertex;
320            if (closed) {
321                prev = (vertex - 1 + segCount) % segCount;
322                next = vertex % segCount;
323            }
324            if (prev >= 0 && next < segCount) {
325                double turn = dirX[prev] * dirY[next] - dirY[prev] * dirX[next];
326                if (Math.abs(turn) > 1e-12) {
327                    side = -turn;
328                }
329            }
330        }
331        return new ClosestPoint(new EastNorth(px[i] + bestT * dirX[i], py[i] + bestT * dirY[i]),
332                new EastNorth(px[i], py[i]), new EastNorth(px[i + 1], py[i + 1]),
333                (side >= 0 ? 1 : -1) * Math.sqrt(bestSq));
334    }
335
336    /**
337     * Offsets the way(s) d units. Positive d means to the left (relative to the reference way)
338     * @param d offset
339     */
340    public void changeOffset(double d) {
341        if (d == 0 || Double.isNaN(d)) {
342            // no offset: the result is a copy (for a ring without the repeated closing node)
343            int pointCount = closed ? nodeCount - 1 : nodeCount;
344            resultPts = new ArrayList<>(pointCount);
345            for (int i = 0; i < pointCount; i++) {
346                resultPts.add(new EastNorth(px[i], py[i]));
347            }
348            resultPieceSeg = IntStream.range(0, nodeCount - 1).toArray();
349            resultPointNode = IntStream.range(0, pointCount).toArray();
350            resultClosed = closed;
351            return;
352        }
353        buildGrid(Math.abs(d));
354        RawPolyline raw = buildRawOffset(d);
355        trim(raw, Math.abs(d));
356    }
357
358    /**
359     * Builds a uniform grid over the source segments, with a cell size of (at least) r, so that all segments
360     * within distance r of a point are found in the 3x3 cells around it.
361     * @param r the (absolute) offset
362     */
363    private void buildGrid(double r) {
364        double minX = Double.POSITIVE_INFINITY;
365        double minY = Double.POSITIVE_INFINITY;
366        double maxX = Double.NEGATIVE_INFINITY;
367        double maxY = Double.NEGATIVE_INFINITY;
368        for (int i = 0; i < nodeCount; i++) {
369            minX = Math.min(minX, px[i]);
370            maxX = Math.max(maxX, px[i]);
371            minY = Math.min(minY, py[i]);
372            maxY = Math.max(maxY, py[i]);
373        }
374        double extent = Math.max(maxX - minX, maxY - minY);
375        gridCell = Math.max(r, extent / 128);
376        gridMinX = minX;
377        gridMinY = minY;
378        gridCols = (int) ((maxX - minX) / gridCell) + 1;
379        gridRows = (int) ((maxY - minY) / gridCell) + 1;
380        int[] counts = new int[gridCols * gridRows];
381        int segCount = nodeCount - 1;
382        for (int i = 0; i < segCount; i++) {
383            forEachCell(segMinX[i], segMinY[i], segMaxX[i], segMaxY[i], c -> counts[c]++);
384        }
385        gridCells = new int[counts.length][];
386        for (int c = 0; c < counts.length; c++) {
387            gridCells[c] = new int[counts[c]];
388            counts[c] = 0;
389        }
390        for (int i = 0; i < segCount; i++) {
391            final int seg = i;
392            forEachCell(segMinX[i], segMinY[i], segMaxX[i], segMaxY[i], c -> gridCells[c][counts[c]++] = seg);
393        }
394        gridStamp = new int[segCount];
395        gridQuery = 0;
396    }
397
398    private void forEachCell(double minX, double minY, double maxX, double maxY, IntConsumer consumer) {
399        int c0 = Math.max(0, (int) ((minX - gridMinX) / gridCell));
400        int c1 = Math.min(gridCols - 1, (int) ((maxX - gridMinX) / gridCell));
401        int r0 = Math.max(0, (int) ((minY - gridMinY) / gridCell));
402        int r1 = Math.min(gridRows - 1, (int) ((maxY - gridMinY) / gridCell));
403        for (int row = r0; row <= r1; row++) {
404            for (int col = c0; col <= c1; col++) {
405                consumer.accept(row * gridCols + col);
406            }
407        }
408    }
409
410    // ---------------------------------------------------------------------------------------------------------
411    // Step 1: raw offset polyline
412
413    /**
414     * The raw (untrimmed) offset polyline. Segment k runs from point k to point k+1 (or to point 0 for the last
415     * segment of a closed polyline). The attributes of a segment are stored at its end point.
416     */
417    private static final class RawPolyline {
418        double[] x = new double[64];
419        double[] y = new double[64];
420        /** index of the source node a point was derived from, or {@link #NO_NODE} */
421        int[] node = new int[64];
422        /** source segment index of the segment ending at this point, or {@link #CAP} */
423        int[] seg = new int[64];
424        /** if the segment ending at this point is an arc chord: the source node the arc is centered on, else NO_NODE */
425        int[] arcCenter = new int[64];
426        int size;
427
428        /** for each source node with an arc: raw index of the first arc point, else -1 */
429        final int[] arcStart;
430        /** number of chords of the arc at each source node */
431        final int[] arcChords;
432        /** whether the arc can be replaced by a mitre when it is not affected by the trimming */
433        final boolean[] arcMitre;
434        final double[] mitreX;
435        final double[] mitreY;
436
437        RawPolyline(int nodeCount) {
438            arcStart = new int[nodeCount];
439            Arrays.fill(arcStart, -1);
440            arcChords = new int[nodeCount];
441            arcMitre = new boolean[nodeCount];
442            mitreX = new double[nodeCount];
443            mitreY = new double[nodeCount];
444        }
445
446        void add(double px, double py, int srcNode, int srcSeg, int arc) {
447            if (size == x.length) {
448                int n = size * 2;
449                x = Arrays.copyOf(x, n);
450                y = Arrays.copyOf(y, n);
451                node = Arrays.copyOf(node, n);
452                seg = Arrays.copyOf(seg, n);
453                arcCenter = Arrays.copyOf(arcCenter, n);
454            }
455            x[size] = px;
456            y[size] = py;
457            node[size] = srcNode;
458            seg[size] = srcSeg;
459            arcCenter[size] = arc;
460            size++;
461        }
462    }
463
464    private RawPolyline buildRawOffset(double d) {
465        RawPolyline raw = new RawPolyline(nodeCount);
466        int segCount = nodeCount - 1;
467        if (closed) {
468            addJoin(raw, 0, segCount - 1, 0, d);
469        } else {
470            // Start cap: half circle on the back side of the first node. It is never part of the result, but
471            // trims pieces of the offset which come closer than d to the first node.
472            addCap(raw, 0, Math.atan2(-dirX[0] * d, dirY[0] * d), d > 0 ? -1 : 1, d, true);
473            raw.add(px[0] - dirY[0] * d, py[0] + dirX[0] * d, 0, CAP, NO_NODE);
474        }
475        for (int k = 1; k < segCount; k++) {
476            addJoin(raw, k, k - 1, k, d);
477        }
478        if (!closed) {
479            int s = segCount - 1;
480            raw.add(px[s + 1] - dirY[s] * d, py[s + 1] + dirX[s] * d, s + 1, s, NO_NODE);
481            // End cap: half circle on the front side of the last node
482            addCap(raw, s + 1, Math.atan2(dirX[s] * d, -dirY[s] * d), d > 0 ? -1 : 1, d, false);
483        } else {
484            // the closing segment ends at raw point 0
485            raw.seg[0] = segCount - 1;
486            raw.arcCenter[0] = NO_NODE;
487        }
488        return raw;
489    }
490
491    /**
492     * Adds the chords of a half circle around node {@code k}, starting at the given angle. The chords are marked
493     * as {@link #CAP}: they are only used to trim other pieces.
494     * @param raw the raw polyline
495     * @param k source node index
496     * @param startAngle angle of the first point of the half circle
497     * @param direction rotation direction (+1 counter clockwise)
498     * @param d the offset
499     * @param leading {@code true} if the cap precedes the offset path (the end point of the half circle is then
500     * added by the caller), {@code false} if it follows it (the start point has been added by the caller)
501     */
502    private void addCap(RawPolyline raw, int k, double startAngle, int direction, double d, boolean leading) {
503        double r = Math.abs(d);
504        int steps = (int) Math.ceil(Math.PI / arcStep - 1e-9);
505        for (int j = leading ? 0 : 1; j < (leading ? steps : steps + 1); j++) {
506            double angle = startAngle + direction * Math.PI * j / steps;
507            raw.add(px[k] + r * Math.cos(angle), py[k] + r * Math.sin(angle), NO_NODE, CAP, NO_NODE);
508        }
509    }
510
511    /**
512     * Adds the offset points at vertex {@code k}, where segment {@code prev} ends and segment {@code next} starts.
513     * @param raw the raw polyline
514     * @param k source node index
515     * @param prev index of the segment ending at k
516     * @param next index of the segment starting at k
517     * @param d the offset
518     */
519    private void addJoin(RawPolyline raw, int k, int prev, int next, double d) {
520        double r = Math.abs(d);
521        // offset end point of prev, offset start point of next
522        double bx = px[k] - dirY[prev] * d;
523        double by = py[k] + dirX[prev] * d;
524        double ax = px[k] - dirY[next] * d;
525        double ay = py[k] + dirX[next] * d;
526
527        double cross = dirX[prev] * dirY[next] - dirY[prev] * dirX[next];
528        double dot = dirX[prev] * dirX[next] + dirY[prev] * dirY[next];
529        double theta = Math.atan2(Math.abs(cross), dot); // turn angle in [0, pi]
530
531        if (theta < 1e-9) {
532            // collinear: the offset points coincide
533            raw.add(bx, by, k, prev, NO_NODE);
534            return;
535        }
536        boolean concave = cross * d > 0; // the turn goes towards the offset side
537        if (concave && theta < Math.PI - 1e-9) {
538            // Clip: intersect the two offset segments.
539            // X = b + t*dir[prev] with -len[prev] <= t <= 0 and X = a + s*dir[next] with 0 <= s <= len[next]
540            double ex = ax - bx;
541            double ey = ay - by;
542            double t = (ex * dirY[next] - ey * dirX[next]) / cross;
543            double s = (ex * dirY[prev] - ey * dirX[prev]) / cross;
544            if (-t <= segLen[prev] && s <= segLen[next] && t <= 1e-9 && s >= -1e-9) {
545                raw.add(bx + t * dirX[prev], by + t * dirY[prev], k, prev, NO_NODE);
546            } else {
547                // The offset is larger than the neighbouring segments allow: local inversion.
548                // Emit both points; the inverted part is removed when trimming.
549                raw.add(bx, by, k, prev, NO_NODE);
550                raw.add(ax, ay, NO_NODE, next, k);
551            }
552            return;
553        }
554        // Convex corner (or a hairpin): arc from b to a around the vertex. If the arc survives the trimming
555        // untouched, it may later be replaced by a mitre (for gentle corners, see arcMitre).
556        raw.add(bx, by, k, prev, NO_NODE);
557        int steps = (int) Math.ceil(theta / arcStep - 1e-9);
558        double angle0 = Math.atan2(by - py[k], bx - px[k]);
559        double delta;
560        if (Math.abs(cross) < 1e-12) {
561            // hairpin: rotate away from the segments, i.e. towards dir[prev]
562            delta = theta * (d > 0 ? -1 : 1);
563        } else {
564            delta = theta * (cross >= 0 ? 1 : -1);
565        }
566        raw.arcStart[k] = raw.size - 1;
567        raw.arcChords[k] = steps;
568        for (int j = 1; j < steps; j++) {
569            double angle = angle0 + delta * j / steps;
570            raw.add(px[k] + r * Math.cos(angle), py[k] + r * Math.sin(angle), NO_NODE, next, k);
571        }
572        raw.add(ax, ay, NO_NODE, next, k);
573
574        if (theta < Math.PI - 1e-6) {
575            double mitreDist = r / Math.cos(theta / 2);
576            double overshoot = mitreDist - r;
577            raw.arcMitre[k] = theta <= arcStep || overshoot <= 0.5 * Math.min(segLen[prev], segLen[next]);
578            // the mitre point lies on the bisector of the two normals
579            double mx = (bx - px[k]) + (ax - px[k]);
580            double my = (by - py[k]) + (ay - py[k]);
581            double ml = Math.hypot(mx, my);
582            raw.mitreX[k] = px[k] + mx / ml * mitreDist;
583            raw.mitreY[k] = py[k] + my / ml * mitreDist;
584        }
585    }
586
587    // ---------------------------------------------------------------------------------------------------------
588    // Step 2: trimming
589
590    /** Growable list of pieces (sub segments of the raw polyline) */
591    private static final class Pieces {
592        int[] start = new int[256];
593        int[] end = new int[256];
594        int[] rawSeg = new int[256];
595        boolean[] valid = new boolean[256];
596        int size;
597
598        void add(int s, int e, int seg, boolean v) {
599            if (size == start.length) {
600                int n = size * 2;
601                start = Arrays.copyOf(start, n);
602                end = Arrays.copyOf(end, n);
603                rawSeg = Arrays.copyOf(rawSeg, n);
604                valid = Arrays.copyOf(valid, n);
605            }
606            start[size] = s;
607            end[size] = e;
608            rawSeg[size] = seg;
609            valid[size] = v;
610            size++;
611        }
612    }
613
614    /** Point table used while trimming: raw points first, then intersection and transition points */
615    private static final class Points {
616        final List<double[]> xy = new ArrayList<>();
617        final List<Integer> node = new ArrayList<>();
618
619        int add(double x, double y, int srcNode) {
620            xy.add(new double[] {x, y});
621            node.add(srcNode);
622            return xy.size() - 1;
623        }
624
625        double[] get(int id) {
626            return xy.get(id);
627        }
628
629        double distance(int a, int b) {
630            double[] p = xy.get(a);
631            double[] q = xy.get(b);
632            return Math.hypot(q[0] - p[0], q[1] - p[1]);
633        }
634    }
635
636    private void trim(RawPolyline raw, double r) {
637        int m = raw.size;
638        int rawSegCount = closed ? m : m - 1;
639        if (rawSegCount < 1) {
640            setEmptyResult();
641            return;
642        }
643
644        Points points = new Points();
645        for (int i = 0; i < m; i++) {
646            points.add(raw.x[i], raw.y[i], raw.node[i]);
647        }
648        // Raw segments which lie completely inside the offset distance ("deep") can neither be part of the result
649        // nor trim it: skip them when looking for intersections. This is a huge saving for large offsets.
650        boolean[] deep = new boolean[rawSegCount];
651        double tolerance = r * 1e-7 + 1e-7;
652        double sagitta = r * (1 - Math.cos(arcStep / 2));
653        for (int i = 0; i < rawSegCount; i++) {
654            int endPoint = (i + 1) % m;
655            double mx = (raw.x[i] + raw.x[endPoint]) / 2;
656            double my = (raw.y[i] + raw.y[endPoint]) / 2;
657            double halfLen = Math.hypot(raw.x[endPoint] - raw.x[i], raw.y[endPoint] - raw.y[i]) / 2;
658            // every point of the segment is within halfLen (+ sagitta for a chord) of the middle
659            double cutoff = r - halfLen - tolerance - (raw.arcCenter[endPoint] != NO_NODE ? sagitta : 0);
660            deep[i] = cutoff > 0 && distanceToSource(mx, my, cutoff) < cutoff;
661        }
662
663        // breakpoints per raw segment: parallel lists of (param, pointId)
664        List<List<double[]>> breaks = new ArrayList<>(Collections.nCopies(rawSegCount, null));
665        findSelfIntersections(raw, rawSegCount, deep, points, breaks);
666
667        // Build the pieces and determine their validity: a piece must lie at (at least) distance r from the source
668        Pieces pieces = new Pieces();
669        boolean anyInvalid = false;
670        for (int i = 0; i < rawSegCount; i++) {
671            int endPoint = (i + 1) % m;
672            if (deep[i]) {
673                pieces.add(i, endPoint, i, false);
674                continue;
675            }
676            List<double[]> b = breaks.get(i);
677            int prevId = i;
678            if (b != null) {
679                b.sort((o1, o2) -> Double.compare(o1[0], o2[0]));
680                for (double[] bp : b) {
681                    classify(raw, r, points, pieces, i, prevId, (int) bp[1]);
682                    prevId = (int) bp[1];
683                }
684            }
685            classify(raw, r, points, pieces, i, prevId, endPoint);
686        }
687        for (int p = 0; p < pieces.size; p++) {
688            anyInvalid |= !pieces.valid[p];
689        }
690
691        // Chain the valid pieces. Consecutive valid pieces of the same component meet at a common point
692        // (self-intersection or transition), but pieces of other components (e.g. an excursion of the path, or an
693        // inner loop) may lie between them in raw order: a piece is therefore attached to whichever open chain ends
694        // where it starts. Chord approximations of arcs can leave small gaps - such gaps are bridged; larger gaps
695        // separate different components.
696        double bridgeTolerance = 2 * r * Math.sin(arcStep / 2);
697        double spikeTolerance = 2 * r * (1 - Math.cos(arcStep / 2)) + tolerance;
698        List<Chain> chains = new ArrayList<>();
699        int pieceCount = pieces.size;
700        int startPiece = 0;
701        if (closed && anyInvalid) {
702            while (pieces.valid[startPiece]) {
703                startPiece++;
704            }
705            startPiece = (startPiece + 1) % pieceCount;
706        }
707        for (int c = 0; c < pieceCount; c++) {
708            int p = (startPiece + c) % pieceCount;
709            if (!pieces.valid[p]) {
710                continue;
711            }
712            int srcSeg = raw.seg[(pieces.rawSeg[p] + 1) % m];
713            Chain chain = findChainEndingAt(chains, pieces.start[p], points, bridgeTolerance);
714            if (chain == null) {
715                chain = new Chain(pieces.start[p], spikeTolerance);
716                chains.add(chain);
717            } else if (chain.lastId != pieces.start[p]) {
718                chain.append(pieces.start[p], srcSeg, points);
719            }
720            chain.append(pieces.end[p], srcSeg, points);
721        }
722        // Join chains whose end meets the start of another chain (a ring may also close onto itself)
723        boolean merged = true;
724        while (merged && chains.size() > 1) {
725            merged = false;
726            for (int i = 0; i < chains.size() && !merged; i++) {
727                Chain a = chains.get(i);
728                for (int j = 0; j < chains.size(); j++) {
729                    Chain b = chains.get(j);
730                    int bFirst = b.ids.get(0);
731                    if (a != b && (a.lastId == bFirst || points.distance(a.lastId, bFirst) <= bridgeTolerance)) {
732                        if (a.lastId != bFirst) {
733                            a.append(bFirst, b.segs.get(0), points);
734                        }
735                        a.appendChain(b);
736                        chains.remove(j);
737                        merged = true;
738                        break;
739                    }
740                }
741            }
742        }
743        if (chains.isEmpty()) {
744            setEmptyResult();
745            return;
746        }
747        Chain best = chains.get(0);
748        for (Chain ch : chains) {
749            if (ch.length > best.length) {
750                best = ch;
751            }
752        }
753        if (closed && best.lastId != best.ids.get(0) && points.distance(best.lastId, best.ids.get(0)) <= bridgeTolerance) {
754            // close a ring which is open by a small gap only
755            best.append(best.ids.get(0), best.segs.get(best.segs.size() - 1), points);
756        }
757
758        // Convert to the result
759        boolean isRing = closed && best.ids.size() > 2 && best.ids.get(0) == best.lastId;
760        List<Integer> ids = new ArrayList<>(best.ids);
761        List<Integer> segs = new ArrayList<>(best.segs);
762        replaceIntactArcsByMitres(raw, points, ids, segs);
763        if (isRing) {
764            ids.remove(ids.size() - 1);
765            // rotate so that the ring starts at a way boundary
766            int n = segs.size();
767            int rot = 0;
768            for (int i = 0; i < n; i++) {
769                if (segWay[segs.get((i + n - 1) % n)] != segWay[segs.get(i)]) {
770                    rot = i;
771                    break;
772                }
773            }
774            Collections.rotate(ids, -rot);
775            Collections.rotate(segs, -rot);
776        }
777        resultPts = new ArrayList<>(ids.size());
778        resultPointNode = new int[ids.size()];
779        for (int i = 0; i < ids.size(); i++) {
780            int id = ids.get(i);
781            double[] pt = points.get(id);
782            resultPts.add(new EastNorth(pt[0], pt[1]));
783            resultPointNode[i] = points.node.get(id);
784        }
785        resultPieceSeg = segs.stream().mapToInt(Integer::intValue).toArray();
786        resultClosed = isRing;
787    }
788
789    private void setEmptyResult() {
790        resultPts = Collections.emptyList();
791        resultPieceSeg = new int[0];
792        resultPointNode = new int[0];
793        resultClosed = false;
794    }
795
796    /**
797     * Determines the validity of the piece of raw segment {@code i} between two points, and adds the resulting
798     * piece(s). The validity is sampled at both ends and in the middle; if it changes, the transition point is
799     * located and the piece is split there.
800     */
801    private void classify(RawPolyline raw, double r, Points points, Pieces pieces, int i, int sId, int eId) {
802        int endPoint = (i + 1) % raw.size;
803        if (raw.seg[endPoint] == CAP) {
804            pieces.add(sId, eId, i, false); // end caps are never part of the result
805            return;
806        }
807        int arc = raw.arcCenter[endPoint];
808        double[] s = points.get(sId);
809        double[] e = points.get(eId);
810        double tolerance = r * 1e-7 + 1e-7;
811        boolean vs = isValid(s[0], s[1], r, tolerance, arc);
812        boolean ve = isValid(e[0], e[1], r, tolerance, arc);
813        boolean vm = isValid(s[0] + (e[0] - s[0]) / 2, s[1] + (e[1] - s[1]) / 2, r, tolerance, arc);
814        if (vs == vm && vm == ve) {
815            pieces.add(sId, eId, i, vm);
816            return;
817        }
818        // Transitions very close to an end point are artefacts of the chord approximation (a point where two
819        // chords cross lies inside both circles): the validity of the middle is then used for the whole piece.
820        double snapTolerance = 2 * r * (1 - Math.cos(arcStep / 2)) + tolerance;
821        double len = Math.hypot(e[0] - s[0], e[1] - s[1]);
822        int prev = sId;
823        boolean state = vs;
824        if (vs != vm) {
825            double t1 = locateTransition(s, e, 0, 0.5, r, tolerance, arc);
826            if (t1 * len <= snapTolerance) {
827                state = vm;
828            } else {
829                int id = points.add(s[0] + (e[0] - s[0]) * t1, s[1] + (e[1] - s[1]) * t1, NO_NODE);
830                pieces.add(prev, id, i, state);
831                prev = id;
832                state = vm;
833            }
834        }
835        if (vm != ve) {
836            double t2 = locateTransition(s, e, 0.5, 1, r, tolerance, arc);
837            if ((1 - t2) * len > snapTolerance) {
838                int id = points.add(s[0] + (e[0] - s[0]) * t2, s[1] + (e[1] - s[1]) * t2, NO_NODE);
839                pieces.add(prev, id, i, state);
840                prev = id;
841                state = ve;
842            }
843        }
844        pieces.add(prev, eId, i, state);
845    }
846
847    /**
848     * Locates (by bisection) the parameter between {@code a} and {@code b} where the validity changes.
849     * @return the parameter of the transition
850     */
851    private double locateTransition(double[] s, double[] e, double a, double b, double r, double tolerance, int arc) {
852        boolean va = isValid(s[0] + (e[0] - s[0]) * a, s[1] + (e[1] - s[1]) * a, r, tolerance, arc);
853        for (int it = 0; it < 40 && b - a > 1e-12; it++) {
854            double mid = (a + b) / 2;
855            boolean vmid = isValid(s[0] + (e[0] - s[0]) * mid, s[1] + (e[1] - s[1]) * mid, r, tolerance, arc);
856            if (vmid == va) {
857                a = mid;
858            } else {
859                b = mid;
860            }
861        }
862        return (a + b) / 2;
863    }
864
865    /**
866     * Checks whether a point of the raw polyline lies at (at least) distance r from the source path.
867     * @param x point
868     * @param y point
869     * @param r offset
870     * @param tolerance allowed deficit
871     * @param arc if the point lies on an arc chord: the center node of the arc; the point is then projected onto
872     * the arc before testing, else {@link #NO_NODE}
873     * @return {@code true} if the point is valid
874     */
875    private boolean isValid(double x, double y, double r, double tolerance, int arc) {
876        if (arc != NO_NODE) {
877            double vx = x - px[arc];
878            double vy = y - py[arc];
879            double vl = Math.hypot(vx, vy);
880            if (vl > 0) {
881                x = px[arc] + vx / vl * r;
882                y = py[arc] + vy / vl * r;
883            }
884        }
885        return distanceToSource(x, y, r - tolerance) >= r - tolerance;
886    }
887
888    /**
889     * Replaces arcs which are completely part of the result by a mitre (where the corner is gentle enough).
890     */
891    private static void replaceIntactArcsByMitres(RawPolyline raw, Points points, List<Integer> ids, List<Integer> segs) {
892        int[] arcOfRawPoint = new int[raw.size];
893        Arrays.fill(arcOfRawPoint, NO_NODE);
894        for (int k = 0; k < raw.arcStart.length; k++) {
895            if (raw.arcStart[k] >= 0 && raw.arcMitre[k]) {
896                arcOfRawPoint[raw.arcStart[k]] = k;
897            }
898        }
899        for (int i = 0; i < ids.size(); i++) {
900            int id = ids.get(i);
901            if (id >= raw.size || arcOfRawPoint[id] == NO_NODE) {
902                continue;
903            }
904            int k = arcOfRawPoint[id];
905            int chords = raw.arcChords[k];
906            if (i + chords >= ids.size()) {
907                continue;
908            }
909            boolean intact = true;
910            for (int j = 1; j <= chords && intact; j++) {
911                intact = ids.get(i + j) == id + j;
912            }
913            if (!intact) {
914                continue;
915            }
916            int mitreId = points.add(raw.mitreX[k], raw.mitreY[k], k);
917            // the chord pieces i..i+chords-1 collapse into two pieces: (i-1 -> mitre), (mitre -> i+chords)
918            ids.set(i, mitreId);
919            ids.subList(i + 1, i + chords + 1).clear();
920            // segs.get(j) belongs to the piece ending at ids.get(j+1); keep the segment of the last chord for the
921            // piece leaving the mitre, and drop the others
922            segs.subList(i, i + chords).clear();
923        }
924    }
925
926    /**
927     * Finds the chain ending at (or within the tolerance of) the given point, preferring an exact match.
928     * @return the chain, or {@code null}
929     */
930    private static Chain findChainEndingAt(List<Chain> chains, int id, Points points, double tolerance) {
931        Chain near = null;
932        double nearDist = tolerance;
933        for (Chain ch : chains) {
934            if (ch.lastId == id) {
935                return ch;
936            }
937            double dist = points.distance(ch.lastId, id);
938            if (dist <= nearDist) {
939                near = ch;
940                nearDist = dist;
941            }
942        }
943        return near;
944    }
945
946    /** A chain of connected valid pieces */
947    private static final class Chain {
948        final List<Integer> ids = new ArrayList<>();
949        final List<Integer> segs = new ArrayList<>();
950        final double spikeTolerance;
951        int lastId;
952        double length;
953
954        Chain(int startId, double spikeTolerance) {
955            ids.add(startId);
956            lastId = startId;
957            this.spikeTolerance = spikeTolerance;
958        }
959
960        void append(int endId, int srcSeg, Points points) {
961            lastId = endId;
962            if (ids.size() >= 2 && points.distance(ids.get(ids.size() - 2), endId) <= spikeTolerance) {
963                // tiny out-and-back spike (an artefact of the chord approximation at a crossing): drop its tip
964                int tip = ids.remove(ids.size() - 1);
965                segs.remove(segs.size() - 1);
966                length -= points.distance(ids.get(ids.size() - 1), tip);
967            }
968            double len = points.distance(ids.get(ids.size() - 1), endId);
969            if (len < 1e-9) {
970                // zero length piece: keep the connectivity, but don't add a point
971                return;
972            }
973            length += len;
974            ids.add(endId);
975            segs.add(srcSeg);
976        }
977
978        void appendChain(Chain other) {
979            ids.addAll(other.ids.subList(1, other.ids.size()));
980            segs.addAll(other.segs);
981            lastId = other.lastId;
982            length += other.length;
983        }
984    }
985
986    /**
987     * Finds all intersections between non adjacent segments of the raw polyline (sweep on x).
988     * @param raw the raw polyline
989     * @param rawSegCount number of raw segments
990     * @param skip raw segments to ignore
991     * @param points point table, intersection points are appended
992     * @param breaks per raw segment list of (param, pointId), filled
993     */
994    private void findSelfIntersections(RawPolyline raw, int rawSegCount, boolean[] skip, Points points,
995            List<List<double[]>> breaks) {
996        int m = raw.size;
997        double[] minX = new double[rawSegCount];
998        double[] maxX = new double[rawSegCount];
999        double[] minY = new double[rawSegCount];
1000        double[] maxY = new double[rawSegCount];
1001        int count = 0;
1002        Integer[] order = new Integer[rawSegCount];
1003        for (int i = 0; i < rawSegCount; i++) {
1004            if (skip[i]) {
1005                continue;
1006            }
1007            int j = (i + 1) % m;
1008            minX[i] = Math.min(raw.x[i], raw.x[j]);
1009            maxX[i] = Math.max(raw.x[i], raw.x[j]);
1010            minY[i] = Math.min(raw.y[i], raw.y[j]);
1011            maxY[i] = Math.max(raw.y[i], raw.y[j]);
1012            order[count++] = i;
1013        }
1014        Arrays.sort(order, 0, count, (a, b) -> Double.compare(minX[a], minX[b]));
1015        double[] uv = new double[2];
1016        for (int oi = 0; oi < count; oi++) {
1017            int i = order[oi];
1018            for (int oj = oi + 1; oj < count; oj++) {
1019                int j = order[oj];
1020                if (minX[j] > maxX[i]) {
1021                    break;
1022                }
1023                if (minY[j] > maxY[i] || maxY[j] < minY[i]) {
1024                    continue;
1025                }
1026                int lo = Math.min(i, j);
1027                int hi = Math.max(i, j);
1028                if (hi - lo == 1 || (closed && lo == 0 && hi == rawSegCount - 1)) {
1029                    continue; // adjacent
1030                }
1031                int i2 = (i + 1) % m;
1032                int j2 = (j + 1) % m;
1033                if (segmentIntersection(raw.x[i], raw.y[i], raw.x[i2], raw.y[i2], raw.x[j], raw.y[j], raw.x[j2], raw.y[j2], uv)) {
1034                    int id = points.add(raw.x[i] + (raw.x[i2] - raw.x[i]) * uv[0], raw.y[i] + (raw.y[i2] - raw.y[i]) * uv[0], NO_NODE);
1035                    if (breaks.get(i) == null) {
1036                        breaks.set(i, new ArrayList<>(2));
1037                    }
1038                    if (breaks.get(j) == null) {
1039                        breaks.set(j, new ArrayList<>(2));
1040                    }
1041                    breaks.get(i).add(new double[] {uv[0], id});
1042                    breaks.get(j).add(new double[] {uv[1], id});
1043                }
1044            }
1045        }
1046    }
1047
1048    /**
1049     * Segment/segment intersection.
1050     * @param uv output: parameters along the first and the second segment
1051     * @return true if the segments intersect (touching end points count as intersection)
1052     */
1053    private static boolean segmentIntersection(double x1, double y1, double x2, double y2,
1054            double x3, double y3, double x4, double y4, double[] uv) {
1055        double a1 = x2 - x1;
1056        double a2 = y2 - y1;
1057        double b1 = x3 - x4;
1058        double b2 = y3 - y4;
1059        double c1 = x3 - x1;
1060        double c2 = y3 - y1;
1061        double det = a1 * b2 - a2 * b1;
1062        double uu = b2 * c1 - b1 * c2;
1063        double vv = a1 * c2 - a2 * c1;
1064        double mag = Math.abs(uu) + Math.abs(vv);
1065        if (det == 0 || Math.abs(det) <= 1e-12 * mag) {
1066            return false; // parallel or collinear
1067        }
1068        double u = uu / det;
1069        double v = vv / det;
1070        if (u < -1e-9 || u > 1 + 1e-9 || v < -1e-9 || v > 1 + 1e-9) {
1071            return false;
1072        }
1073        uv[0] = Math.max(0, Math.min(1, u));
1074        uv[1] = Math.max(0, Math.min(1, v));
1075        return true;
1076    }
1077
1078    /**
1079     * Distance from a point to the source path.
1080     * @param x point
1081     * @param y point
1082     * @param cutoff the search can stop as soon as a distance below this value is found
1083     * @return the distance (or any value below cutoff if such a distance exists)
1084     */
1085    private double distanceToSource(double x, double y, double cutoff) {
1086        // Only segments within the cutoff matter (the result is only compared against it); with a cell size of
1087        // at least the offset they all lie in the 3x3 cells around the point.
1088        int col = (int) Math.floor((x - gridMinX) / gridCell);
1089        int row = (int) Math.floor((y - gridMinY) / gridCell);
1090        if (col < -1 || col > gridCols || row < -1 || row > gridRows) {
1091            return Double.POSITIVE_INFINITY;
1092        }
1093        gridQuery++;
1094        double best = Double.POSITIVE_INFINITY;
1095        double bestSq = Double.POSITIVE_INFINITY;
1096        double cutoffSq = cutoff * cutoff;
1097        for (int rr = Math.max(0, row - 1); rr <= Math.min(gridRows - 1, row + 1); rr++) {
1098            for (int cc = Math.max(0, col - 1); cc <= Math.min(gridCols - 1, col + 1); cc++) {
1099                for (int i : gridCells[rr * gridCols + cc]) {
1100                    if (gridStamp[i] == gridQuery) {
1101                        continue;
1102                    }
1103                    gridStamp[i] = gridQuery;
1104                    if (x < segMinX[i] - best || x > segMaxX[i] + best || y < segMinY[i] - best || y > segMaxY[i] + best) {
1105                        continue;
1106                    }
1107                    double rx = x - px[i];
1108                    double ry = y - py[i];
1109                    double t = rx * dirX[i] + ry * dirY[i];
1110                    double dSq;
1111                    if (t <= 0) {
1112                        dSq = rx * rx + ry * ry;
1113                    } else if (t >= segLen[i]) {
1114                        double ex = x - px[i + 1];
1115                        double ey = y - py[i + 1];
1116                        dSq = ex * ex + ey * ey;
1117                    } else {
1118                        double c = rx * dirY[i] - ry * dirX[i];
1119                        dSq = c * c;
1120                    }
1121                    if (dSq < bestSq) {
1122                        bestSq = dSq;
1123                        best = Math.sqrt(dSq);
1124                        if (bestSq < cutoffSq) {
1125                            return best;
1126                        }
1127                    }
1128                }
1129            }
1130        }
1131        return best;
1132    }
1133
1134    // ---------------------------------------------------------------------------------------------------------
1135    // Result access and commit
1136
1137    /**
1138     * Returns the points of the offset path computed by the last call to {@link #changeOffset(double)}.
1139     * For a closed result the first point is not repeated at the end, see {@link #isResultClosed()}.
1140     * @return the offset points (projected coordinates), empty if nothing has been computed or nothing remains
1141     * @since 19624
1142     */
1143    public List<EastNorth> getOffsetPoints() {
1144        return Collections.unmodifiableList(resultPts);
1145    }
1146
1147    /**
1148     * Determines if the result of the last {@link #changeOffset(double)} call is a closed ring.
1149     * @return {@code true} if the offset path is a closed ring
1150     * @since 19624
1151     */
1152    public boolean isResultClosed() {
1153        return resultClosed;
1154    }
1155
1156    /**
1157     * Creates the nodes and ways of the offset path (as computed by the last call to {@link #changeOffset(double)}),
1158     * and adds them to the edit data set by adding a new sequence command to the undo/redo queue.
1159     * <p>
1160     * Does nothing if there is no offset path.
1161     */
1162    public void commit() {
1163        List<Command> commands = makeAddWayAndNodesCommandList();
1164        if (!commands.isEmpty()) {
1165            UndoRedoHandler.getInstance().add(new SequenceCommand("Make parallel way(s)", commands));
1166        }
1167    }
1168
1169    private List<Command> makeAddWayAndNodesCommandList() {
1170        DataSet ds = OsmDataManager.getInstance().getEditDataSet();
1171        List<Way> newWays = buildWays();
1172        ways = newWays;
1173        List<Command> commands = new ArrayList<>();
1174        if (newWays.isEmpty()) {
1175            return commands;
1176        }
1177        List<Node> added = new ArrayList<>();
1178        for (Way w : newWays) {
1179            for (Node n : w.getNodes()) {
1180                // don't add the same node twice, see #18386
1181                if (!added.contains(n)) {
1182                    added.add(n);
1183                    commands.add(new AddCommand(ds, n));
1184                }
1185            }
1186        }
1187        for (Way w : newWays) {
1188            commands.add(new AddCommand(ds, w));
1189        }
1190        return commands;
1191    }
1192
1193    /**
1194     * Builds the (not yet added) ways from the last computed offset path.
1195     * @return the ways, in the order of the source ways; ways swallowed by the offset are omitted
1196     */
1197    private List<Way> buildWays() {
1198        int pointCount = resultPts.size();
1199        List<Way> result = new ArrayList<>(sourceWays.size());
1200        if (pointCount < 2) {
1201            return result;
1202        }
1203        int pieceCount = resultPieceSeg.length;
1204        Node[] nodes = new Node[pointCount];
1205        for (int w = 0; w < sourceWays.size(); w++) {
1206            int first = -1;
1207            int last = -1;
1208            for (int p = 0; p < pieceCount; p++) {
1209                if (segWay[resultPieceSeg[p]] == w) {
1210                    if (first < 0) {
1211                        first = p;
1212                    }
1213                    last = p;
1214                }
1215            }
1216            if (first < 0) {
1217                continue; // way is swallowed by the offset
1218            }
1219            List<Node> wayNodes = new ArrayList<>(last - first + 2);
1220            for (int p = first; p <= last + 1; p++) {
1221                int idx = p % pointCount;
1222                if (nodes[idx] == null) {
1223                    nodes[idx] = makeNode(idx);
1224                }
1225                wayNodes.add(nodes[idx]);
1226            }
1227            if (!wayForward[w]) {
1228                Collections.reverse(wayNodes);
1229            }
1230            Way source = sourceWays.get(w);
1231            Way copy = new Way();
1232            copy.setNodes(wayNodes);
1233            if (copyTags) {
1234                copy.setKeys(source.getKeys());
1235            }
1236            result.add(copy);
1237        }
1238        return result;
1239    }
1240
1241    private Node makeNode(int idx) {
1242        Node n;
1243        int src = resultPointNode[idx];
1244        if (copyTags && src != NO_NODE) {
1245            n = new Node(sortedNodes.get(src), true);
1246        } else {
1247            n = new Node();
1248        }
1249        n.setEastNorth(resultPts.get(idx));
1250        return n;
1251    }
1252
1253    /**
1254     * Returns the resulting parallel ways, available after {@link #commit()}.
1255     * @return the resulting parallel ways (empty before commit)
1256     */
1257    public final List<Way> getWays() {
1258        return ways;
1259    }
1260}