Changeset 19624 in josm


Ignore:
Timestamp:
2026-09-16T10:31:15+02:00 (10 hours ago)
Author:
stoecker
Message:

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

Location:
trunk
Files:
1 added
3 edited

Legend:

Unmodified
Added
Removed

  • trunk/src/org/openstreetmap/josm/actions/mapmode/ParallelWayAction.java

    r19307 r19624  
    3131import org.openstreetmap.josm.data.coor.EastNorth;
    3232import org.openstreetmap.josm.data.coor.ILatLon;
    33 import org.openstreetmap.josm.data.osm.Node;
    3433import org.openstreetmap.josm.data.osm.OsmPrimitive;
    3534import org.openstreetmap.josm.data.osm.Way;
    … …  
    5150import org.openstreetmap.josm.gui.util.ModifierExListener;
    5251import org.openstreetmap.josm.tools.CheckParameterUtil;
    53 import org.openstreetmap.josm.tools.Geometry;
    5452import org.openstreetmap.josm.tools.ImageProvider;
    5553import org.openstreetmap.josm.tools.Logging;
    … …  
    102100    private static final CachingProperty<Double> SNAP_DISTANCE_CHINESE  = new DoubleProperty(prefKey("snap-distance-chinese"), 1).cached();
    103101    private static final CachingProperty<Double> SNAP_DISTANCE_NAUTICAL = new DoubleProperty(prefKey("snap-distance-nautical"), 0.1).cached();
     102    private static final CachingProperty<Double> ARC_STEP_DEGREES
     103            = new DoubleProperty(prefKey("arc-step-degrees"), ParallelWays.DEFAULT_ARC_STEP_DEGREES).cached();
     104    private static final CachingProperty<BasicStroke> PREVIEW_STROKE = new StrokeProperty(prefKey("stroke.preview"), "2").cached();
    104105    private static final CachingProperty<Color> MAIN_COLOR = new NamedColorProperty(marktr("make parallel helper line"), Color.RED).cached();
    105106
    … …  
    141142    private EastNorth helperLineStart;
    142143    private EastNorth helperLineEnd;
     144    /** the source segment the current offset relates to (the one closest to the mouse) */
     145    private transient ParallelWays.ClosestPoint helperSegment;
    143146
    144147    private final ParallelWayLayer temporaryLayer = new ParallelWayLayer();
    … …  
    192195        sourceWays = null;
    193196        referenceSegment = null;
     197        helperSegment = null;
    194198    }
    195199
    … …  
    332336        } else if (mode == Mode.DRAGGING) {
    333337            clearSourceWays();
    334             MainApplication.getMap().statusLine.setDist(pWays.getWays());
     338            if (pWays != null) {
     339                // The nodes and ways are only created now, since their number depends on the offset
     340                pWays.commit();
     341                List<Way> newWays = pWays.getWays();
     342                if (newWays.isEmpty()) {
     343                    new Notification(tr("Parallel Way:\n" +
     344                            "The offset is too large, nothing remains of the parallel way(s)"))
     345                            .setIcon(JOptionPane.INFORMATION_MESSAGE)
     346                            .show();
     347                    pWays = null;
     348                } else {
     349                    getLayerManager().getEditDataSet().setSelected(newWays);
     350                    MainApplication.getMap().statusLine.setDist(newWays);
     351                }
     352            }
    335353        }
    336354
    … …  
    383401        }
    384402
    385         // Calculate distance to the reference line
     403        // Calculate the distance to the source path: the offset relates to the part of the path closest to the
     404        // mouse, so that the helper line stays meaningful when the mouse moves along the way.
    386405        Point p = e.getPoint();
    387406        EastNorth enp = mv.getEastNorth((int) p.getX(), (int) p.getY());
    388         EastNorth nearestPointOnRefLine = Geometry.closestPointToLine(referenceSegment.getFirstNode().getEastNorth(),
    389                 referenceSegment.getSecondNode().getEastNorth(), enp);
     407        ParallelWays.ClosestPoint closest = pWays.closestPoint(enp);
     408        EastNorth nearestPointOnPath = closest.point;
    390409
    391410        // Note: d is the distance in _projected units_
    392         double d = enp.distance(nearestPointOnRefLine);
     411        double d = Math.abs(closest.signedDistance);
    393412        double realD = mv.getProjection().eastNorth2latlon(enp).greatCircleDistance(
    394                 (ILatLon) mv.getProjection().eastNorth2latlon(nearestPointOnRefLine));
     413                (ILatLon) mv.getProjection().eastNorth2latlon(nearestPointOnPath));
    395414        double snappedRealD = realD;
    396415
    397         boolean toTheRight = Geometry.angleIsClockwise(
    398                 referenceSegment.getFirstNode(), referenceSegment.getSecondNode(), new Node(enp));
     416        boolean toTheRight = closest.signedDistance < 0;
    399417
    400418        if (snap) {
    … …  
    425443            }
    426444        }
    427         d = snappedRealD * (d/realD); // convert back to projected distance. (probably ok on small scales)
    428         helperLineStart = nearestPointOnRefLine;
     445        if (realD > 0) {
     446            d = snappedRealD * (d/realD); // convert back to projected distance. (probably ok on small scales)
     447        }
     448        helperLineStart = nearestPointOnPath;
    429449        helperLineEnd = enp;
     450        helperSegment = closest;
    430451        if (toTheRight) {
    431452            d = -d;
    … …  
    507528
    508529        sourceWays.removeIf(w -> w.isIncomplete() || w.isEmpty());
     530
     531        // The selection may have been changed by other means while in this mode (e.g. Selection > Non-branching way
     532        // sequences): if it contains the way under the mouse, the selected ways are the source ways.
     533        Set<Way> selectedWays = new LinkedHashSet<>(getLayerManager().getEditDataSet().getSelectedWays());
     534        selectedWays.removeIf(w -> w.isIncomplete() || w.isEmpty());
     535        if (selectedWays.contains(referenceSegment.getWay()) && !selectedWays.equals(sourceWays)) {
     536            clearSourceWays();
     537            for (Way w : selectedWays) {
     538                addSourceWay(w);
     539            }
     540        }
    509541
    510542        if (!sourceWays.contains(referenceSegment.getWay())) {
    … …  
    523555                i++;
    524556            }
    525             pWays = new ParallelWays(sourceWays, copyTags, referenceWayIndex);
    526             pWays.commit();
    527             getLayerManager().getEditDataSet().setSelected(pWays.getWays());
     557            pWays = new ParallelWays(sourceWays, copyTags, referenceWayIndex, ARC_STEP_DEGREES.get());
    528558            return true;
    529559        } catch (IllegalArgumentException e) {
    530560            Logging.debug(e);
    531             new Notification(tr("ParallelWayAction\n" +
     561            new Notification(tr("Parallel Way:\n" +
    532562                    "The ways selected must form a simple branchless path"))
    533563                    .setIcon(JOptionPane.INFORMATION_MESSAGE)
    … …  
    629659                g.setColor(mainColor);
    630660                MapViewPath line = new MapViewPath(mv);
    631                 line.moveTo(referenceSegment.getFirstNode());
    632                 line.lineTo(referenceSegment.getSecondNode());
     661                if (helperSegment != null) {
     662                    line.moveTo(helperSegment.segmentStart);
     663                    line.lineTo(helperSegment.segmentEnd);
     664                } else {
     665                    line.moveTo(referenceSegment.getFirstNode());
     666                    line.lineTo(referenceSegment.getSecondNode());
     667                }
    633668                g.draw(line.computeClippedLine(g.getStroke()));
    634669
    … …  
    639674                line.lineTo(helperLineEnd);
    640675                g.draw(line.computeClippedLine(g.getStroke()));
     676
     677                // Preview of the parallel way(s)
     678                if (pWays != null) {
     679                    List<EastNorth> pts = pWays.getOffsetPoints();
     680                    if (pts.size() > 1) {
     681                        g.setStroke(PREVIEW_STROKE.get());
     682                        line = new MapViewPath(mv);
     683                        line.moveTo(pts.get(0));
     684                        for (int i = 1; i < pts.size(); i++) {
     685                            line.lineTo(pts.get(i));
     686                        }
     687                        if (pWays.isResultClosed()) {
     688                            line.lineTo(pts.get(0));
     689                        }
     690                        g.draw(line.computeClippedLine(g.getStroke()));
     691                    }
     692                }
    641693            }
    642694        }

  • trunk/src/org/openstreetmap/josm/actions/mapmode/ParallelWays.java

    r16438 r19624  
    33
    44import java.util.ArrayList;
     5import java.util.Arrays;
    56import java.util.Collection;
    67import java.util.Collections;
    7 import java.util.HashMap;
    88import java.util.HashSet;
    99import java.util.List;
    10 import java.util.Map;
    1110import java.util.Set;
     11import java.util.function.IntConsumer;
    1212import java.util.stream.IntStream;
    1313
    … …  
    2222import org.openstreetmap.josm.data.osm.OsmDataManager;
    2323import org.openstreetmap.josm.data.osm.Way;
    24 import org.openstreetmap.josm.tools.Geometry;
    25 import org.openstreetmap.josm.tools.Utils;
    2624
    2725/**
    2826 * Helper for {@link ParallelWayAction}.
    29  *
    30  * @author Ole Jørgen Brønner (olejorgenb)
     27 * <p>
     28 * Computes a one-sided offset ("parallel") of a branchless path made of one or more ways.
     29 * <p>
     30 * The algorithm is a proper one-sided buffer, which also works when the offset is much larger than
     31 * the length of the segments of the source path (e.g. a maritime boundary 22 km off a coastline):
     32 * <ol>
     33 * <li>Each segment is offset by the requested distance.</li>
     34 * <li>At every vertex the two neighbouring offset segments are joined: on the inner side of a turn they are
     35 * clipped at their intersection, on the outer side a mitre is used for gentle turns and a circular arc
     36 * (approximated by chords) for sharp turns or when the mitre would overshoot too far.</li>
     37 * <li>The resulting raw polyline is split at its self-intersections. Every piece is kept only if it lies at
     38 * (at least) the offset distance from the source path. Pieces which are closer belong to inverted loops
     39 * ("swallowtails") and are dropped. The remaining pieces are chained; the longest chain is the result.</li>
     40 * </ol>
     41 * All calculations are done in projected coordinates.
     42 * <p>
     43 * Contrary to earlier versions the nodes and ways are only created (and added to the data set) by
     44 * {@link #commit()}, since the number of nodes of the result depends on the offset. Use
     45 * {@link #getOffsetPoints()} to draw a preview while the offset is changed.
    3146 */
    3247public class ParallelWays {
    33     private final List<Way> ways;
     48
     49    /** Default angular step used to approximate circular arcs, in degrees */
     50    public static final double DEFAULT_ARC_STEP_DEGREES = 10;
     51
     52    private static final int NO_NODE = -1;
     53    /** marker for raw segments of the end caps, which are only used to trim the result and are never part of it */
     54    private static final int CAP = -2;
     55
     56    private final List<Way> sourceWays;
     57    private final boolean copyTags;
     58    private final double arcStep;
     59
     60    /** the source nodes, in path order (duplicates by coordinate removed, oriented like the reference way) */
    3461    private final List<Node> sortedNodes;
    35 
     62    private final boolean closed;
    3663    private final int nodeCount;
    3764
    38     private final EastNorth[] pts;
    39     private final EastNorth[] normals;
     65    private final double[] px;
     66    private final double[] py;
     67    /** unit direction of segment i */
     68    private final double[] dirX;
     69    private final double[] dirY;
     70    private final double[] segLen;
     71    /** bounding boxes of the source segments, used to speed up distance computations */
     72    private final double[] segMinX;
     73    private final double[] segMinY;
     74    private final double[] segMaxX;
     75    private final double[] segMaxY;
     76
     77    /** whether the source way runs in the same direction as sortedNodes (aligned with sourceWays) */
     78    private final boolean[] wayForward;
     79    /** source way index for each source segment */
     80    private final int[] segWay;
     81
     82    // Spatial index of the source segments (rebuilt for every offset, since the cell size depends on it)
     83    private double gridCell;
     84    private double gridMinX;
     85    private double gridMinY;
     86    private int gridCols;
     87    private int gridRows;
     88    private int[][] gridCells;
     89    private int[] gridStamp;
     90    private int gridQuery;
     91
     92    // Result of the last changeOffset call
     93    private List<EastNorth> resultPts = Collections.emptyList();
     94    private int[] resultPieceSeg = new int[0];
     95    private int[] resultPointNode = new int[0];
     96    private boolean resultClosed;
     97
     98    private List<Way> ways = Collections.emptyList();
    4099
    41100    /**
    … …  
    44103     * @param copyTags whether tags should be copied
    45104     * @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
    46106     */
    47107    public ParallelWays(Collection<Way> sourceWays, boolean copyTags, int refWayIndex) {
    48         // Possible/sensible to use PrimitiveDeepCopy here?
    49 
    50         // Make a deep copy of the ways, keeping the copied ways connected
    51         // TODO: This assumes the first/last nodes of the ways are the only possible shared nodes.
    52         Map<Node, Node> splitNodeMap = new HashMap<>(Utils.hashMapInitialCapacity(sourceWays.size()));
    53         for (Way w : sourceWays) {
    54             copyNodeInMap(splitNodeMap, w.firstNode(), copyTags);
    55             copyNodeInMap(splitNodeMap, w.lastNode(), copyTags);
    56         }
    57         ways = new ArrayList<>(sourceWays.size());
    58         for (Way w : sourceWays) {
    59             Way wCopy = new Way();
    60             wCopy.addNode(splitNodeMap.get(w.firstNode()));
    61             for (int i = 1; i < w.getNodesCount() - 1; i++) {
    62                 wCopy.addNode(copyNode(w.getNode(i), copyTags));
    63             }
    64             wCopy.addNode(splitNodeMap.get(w.lastNode()));
    65             if (copyTags) {
    66                 wCopy.setKeys(w.getKeys());
    67             }
    68             ways.add(wCopy);
    69         }
     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)));
    70124
    71125        // Find a linear ordering of the nodes. Fail if there isn't one.
    72         NodeGraph nodeGraph = NodeGraph.createUndirectedGraphFromNodeWays(ways);
     126        NodeGraph nodeGraph = NodeGraph.createUndirectedGraphFromNodeWays(this.sourceWays);
    73127        List<Node> sortedNodesPath = nodeGraph.buildSpanningPath();
    74         if (sortedNodesPath == null)
     128        if (sortedNodesPath == null || sortedNodesPath.size() < 2)
    75129            throw new IllegalArgumentException("Ways must have spanning path"); // Create a dedicated exception?
    76130
    77         // Fix #8631 - Remove duplicated nodes from graph to be robust with self-intersecting ways
    78         Set<Node> removedNodes = new HashSet<>();
    79         sortedNodes = new ArrayList<>();
    80         for (int i = 0; i < sortedNodesPath.size(); i++) {
    81             Node n = sortedNodesPath.get(i);
    82             if (i < sortedNodesPath.size()-1 && sortedNodesPath.get(i+1).getCoor().equals(n.getCoor())) {
    83                 removedNodes.add(n);
    84                 for (Way w : ways) {
    85                     w.removeNode(n);
    86                 }
    87                 continue;
    88             }
    89             if (!removedNodes.contains(n)) {
    90                 sortedNodes.add(n);
    91             }
    92         }
    93 
    94         // Ugly method of ensuring that the offset isn't inverted. I'm sure there is a better and more elegant way
    95         Way refWay = ways.get(refWayIndex);
    96         boolean refWayReversed = IntStream.range(0, sortedNodes.size() - 1)
    97                 .noneMatch(i -> sortedNodes.get(i) == refWay.firstNode() && sortedNodes.get(i + 1) == refWay.getNode(1));
    98         if (refWayReversed) {
    99             Collections.reverse(sortedNodes); // need to keep the orientation of the reference way.
    100         }
    101 
    102         // Initialize the required parameters. (segment normals, etc.)
    103         nodeCount = sortedNodes.size();
    104         pts = new EastNorth[nodeCount];
    105         normals = new EastNorth[nodeCount - 1];
    106         int i = 0;
    107         for (Node n : sortedNodes) {
    108             EastNorth t = n.getEastNorth();
    109             pts[i] = t;
    110             i++;
    111         }
    112         for (i = 0; i < nodeCount - 1; i++) {
    113             double dx = pts[i + 1].getX() - pts[i].getX();
    114             double dy = pts[i + 1].getY() - pts[i].getY();
    115             double len = Math.sqrt(dx * dx + dy * dy);
    116             normals[i] = new EastNorth(-dy / len, dx / len);
    117         }
    118     }
    119 
    120     private static void copyNodeInMap(Map<Node, Node> splitNodeMap, Node node, boolean copyTags) {
    121         if (!splitNodeMap.containsKey(node)) {
    122             splitNodeMap.put(node, copyNode(node, copyTags));
    123         }
     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;
    124246    }
    125247
    … …  
    129251     */
    130252    public boolean isClosedPath() {
    131         return sortedNodes.get(0) == sortedNodes.get(sortedNodes.size() - 1);
     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));
    132334    }
    133335
    … …  
    137339     */
    138340    public void changeOffset(double d) {
    139         // This is the core algorithm:
    140         /* 1. Calculate a parallel line, offset by 'd', to each segment in the path
    141          * 2. Find the intersection of lines belonging to neighboring segments. These become the new node positions
    142          * 3. Do some special casing for closed paths
    143          *
    144          * Simple and probably not even close to optimal performance wise
    145          */
    146 
    147         EastNorth[] ppts = new EastNorth[nodeCount];
    148 
    149         EastNorth prevA = pts[0].add(normals[0].scale(d));
    150         EastNorth prevB = pts[1].add(normals[0].scale(d));
    151         for (int i = 1; i < nodeCount - 1; i++) {
    152             EastNorth a = pts[i].add(normals[i].scale(d));
    153             EastNorth b = pts[i + 1].add(normals[i].scale(d));
    154             if (Geometry.segmentsParallel(a, b, prevA, prevB)) {
    155                 ppts[i] = a;
     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);
    156546            } else {
    157                 ppts[i] = Geometry.getLineLineIntersection(a, b, prevA, prevB);
    158             }
    159             prevA = a;
    160             prevB = b;
    161         }
    162         if (isClosedPath()) {
    163             EastNorth a = pts[0].add(normals[0].scale(d));
    164             EastNorth b = pts[1].add(normals[0].scale(d));
    165             if (Geometry.segmentsParallel(a, b, prevA, prevB)) {
    166                 ppts[0] = a;
     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;
    167828            } else {
    168                 ppts[0] = Geometry.getLineLineIntersection(a, b, prevA, prevB);
    169             }
    170             ppts[nodeCount - 1] = ppts[0];
    171         } else {
    172             ppts[0] = pts[0].add(normals[0].scale(d));
    173             ppts[nodeCount - 1] = pts[nodeCount - 1].add(normals[nodeCount - 2].scale(d));
    174         }
    175 
    176         for (int i = 0; i < nodeCount; i++) {
    177             sortedNodes.get(i).setEastNorth(ppts[i]);
    178         }
    179     }
    180 
    181     /**
    182      * Performs the action by adding a new sequence command to the undo/redo queue.
     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.
    1831161     */
    1841162    public void commit() {
    185         UndoRedoHandler.getInstance().add(new SequenceCommand("Make parallel way(s)", makeAddWayAndNodesCommandList()));
     1163        List<Command> commands = makeAddWayAndNodesCommandList();
     1164        if (!commands.isEmpty()) {
     1165            UndoRedoHandler.getInstance().add(new SequenceCommand("Make parallel way(s)", commands));
     1166        }
    1861167    }
    1871168
    1881169    private List<Command> makeAddWayAndNodesCommandList() {
    1891170        DataSet ds = OsmDataManager.getInstance().getEditDataSet();
    190 
    191         List<Command> commands = new ArrayList<>(sortedNodes.size() + ways.size());
    192         Set<Node> dupCheck = new HashSet<>();
    193         for (int i = 0; i < sortedNodes.size() - (isClosedPath() ? 1 : 0); i++) {
    194             Node n = sortedNodes.get(i);
    195             // don't add the same node twice, see #18386
    196             if (dupCheck.add(n)) {
    197                 commands.add(new AddCommand(ds, n));
    198             }
    199         }
    200         for (Way w : ways) {
     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) {
    2011188            commands.add(new AddCommand(ds, w));
    2021189        }
    … …  
    2041191    }
    2051192
    206     private static Node copyNode(Node source, boolean copyTags) {
    207         if (copyTags)
    208             return new Node(source, true);
    209         else {
    210             Node n = new Node();
    211             n.setCoor(source.getCoor());
    212             return n;
    213         }
    214     }
    215 
    216     /**
    217      * Returns the resulting parallel ways.
    218      * @return the resulting parallel ways
     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)
    2191256     */
    2201257    public final List<Way> getWays() {

  • trunk/test/unit/org/openstreetmap/josm/actions/mapmode/ParallelWayActionTest.java

    r19227 r19624  
    1313import org.openstreetmap.josm.data.coor.LatLon;
    1414import org.openstreetmap.josm.data.osm.DataSet;
     15import org.openstreetmap.josm.data.osm.Node;
     16import org.openstreetmap.josm.data.osm.Way;
    1517import org.openstreetmap.josm.gui.MainApplication;
    1618import org.openstreetmap.josm.gui.MapFrame;
    … …  
    7173
    7274    /**
     75     * Several selected ways connected by common nodes are offset together, one result way per source way.
     76     */
     77    @Test
     78    void testMultipleSelectedWays() {
     79        Node a = new Node(LatLon.ZERO);
     80        Node b = new Node(new LatLon(0, 0.0001));
     81        Node c = new Node(new LatLon(0, 0.0002));
     82        Way w1 = new Way();
     83        w1.addNode(a);
     84        w1.addNode(b);
     85        Way w2 = new Way();
     86        w2.addNode(b);
     87        w2.addNode(c);
     88        for (Node n : new Node[] {a, b, c}) {
     89            this.dataSet.addPrimitive(n);
     90        }
     91        this.dataSet.addPrimitive(w1);
     92        this.dataSet.addPrimitive(w2);
     93        this.dataSet.setSelected(w1, w2);
     94        this.map.selectMapMode(mapMode);
     95        MapModeUtils.dragFromTo(new LatLon(0, 0.00005), new LatLon(0.00005, 0.00005));
     96        assertEquals(2, this.dataSet.getWays().size() - 2, "two parallel ways expected: " + this.dataSet.getWays());
     97        assertEquals(3 + 3 + 2 + 2, this.dataSet.allPrimitives().size());
     98    }
     99
     100    /**
     101     * The selection changed while in the mode (e.g. by Selection > Non-branching way sequences, after a first
     102     * parallel way has been created) is used as source.
     103     */
     104    @Test
     105    void testSelectionChangedInMode() {
     106        Node a = new Node(LatLon.ZERO);
     107        Node b = new Node(new LatLon(0, 0.0001));
     108        Node c = new Node(new LatLon(0, 0.0002));
     109        Way w1 = new Way();
     110        w1.addNode(a);
     111        w1.addNode(b);
     112        Way w2 = new Way();
     113        w2.addNode(b);
     114        w2.addNode(c);
     115        for (Node n : new Node[] {a, b, c}) {
     116            this.dataSet.addPrimitive(n);
     117        }
     118        this.dataSet.addPrimitive(w1);
     119        this.dataSet.addPrimitive(w2);
     120        this.dataSet.setSelected(w1);
     121        this.map.selectMapMode(mapMode);
     122        // first parallel of the single selected way
     123        MapModeUtils.dragFromTo(new LatLon(0, 0.00005), new LatLon(0.00005, 0.00005));
     124        assertEquals(3, this.dataSet.getWays().size());
     125        // now the selection is extended by other means, the next drag must use both ways
     126        this.dataSet.setSelected(w1, w2);
     127        MapModeUtils.dragFromTo(new LatLon(0, 0.00005), new LatLon(-0.00005, 0.00005));
     128        assertEquals(5, this.dataSet.getWays().size(), this.dataSet.getWays().toString());
     129    }
     130
     131    /**
    73132     * Unit test of {@link Mode} enum.
    74133     */
Note: See TracChangeset for help on using the changeset viewer.