001// License: GPL. For details, see LICENSE file.
002package org.openstreetmap.josm.actions.mapmode;
003
004import java.util.ArrayList;
005import java.util.Collection;
006import java.util.Collections;
007import java.util.HashMap;
008import java.util.HashSet;
009import java.util.List;
010import java.util.Map;
011import java.util.Set;
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;
024import org.openstreetmap.josm.tools.Geometry;
025import org.openstreetmap.josm.tools.Utils;
026
027/**
028 * Helper for {@link ParallelWayAction}.
029 *
030 * @author Ole Jørgen Brønner (olejorgenb)
031 */
032public class ParallelWays {
033    private final List<Way> ways;
034    private final List<Node> sortedNodes;
035
036    private final int nodeCount;
037
038    private final EastNorth[] pts;
039    private final EastNorth[] normals;
040
041    /**
042     * Constructs a new {@code ParallelWays}.
043     * @param sourceWays source ways
044     * @param copyTags whether tags should be copied
045     * @param refWayIndex Need a reference way to determine the direction of the offset when we manage multiple ways
046     */
047    public ParallelWays(Collection<Way> sourceWays, boolean copyTags, int refWayIndex) {
048        // Possible/sensible to use PrimitiveDeepCopy here?
049
050        // Make a deep copy of the ways, keeping the copied ways connected
051        // TODO: This assumes the first/last nodes of the ways are the only possible shared nodes.
052        Map<Node, Node> splitNodeMap = new HashMap<>(Utils.hashMapInitialCapacity(sourceWays.size()));
053        for (Way w : sourceWays) {
054            copyNodeInMap(splitNodeMap, w.firstNode(), copyTags);
055            copyNodeInMap(splitNodeMap, w.lastNode(), copyTags);
056        }
057        ways = new ArrayList<>(sourceWays.size());
058        for (Way w : sourceWays) {
059            Way wCopy = new Way();
060            wCopy.addNode(splitNodeMap.get(w.firstNode()));
061            for (int i = 1; i < w.getNodesCount() - 1; i++) {
062                wCopy.addNode(copyNode(w.getNode(i), copyTags));
063            }
064            wCopy.addNode(splitNodeMap.get(w.lastNode()));
065            if (copyTags) {
066                wCopy.setKeys(w.getKeys());
067            }
068            ways.add(wCopy);
069        }
070
071        // Find a linear ordering of the nodes. Fail if there isn't one.
072        NodeGraph nodeGraph = NodeGraph.createUndirectedGraphFromNodeWays(ways);
073        List<Node> sortedNodesPath = nodeGraph.buildSpanningPath();
074        if (sortedNodesPath == null)
075            throw new IllegalArgumentException("Ways must have spanning path"); // Create a dedicated exception?
076
077        // Fix #8631 - Remove duplicated nodes from graph to be robust with self-intersecting ways
078        Set<Node> removedNodes = new HashSet<>();
079        sortedNodes = new ArrayList<>();
080        for (int i = 0; i < sortedNodesPath.size(); i++) {
081            Node n = sortedNodesPath.get(i);
082            if (i < sortedNodesPath.size()-1 && sortedNodesPath.get(i+1).getCoor().equals(n.getCoor())) {
083                removedNodes.add(n);
084                for (Way w : ways) {
085                    w.removeNode(n);
086                }
087                continue;
088            }
089            if (!removedNodes.contains(n)) {
090                sortedNodes.add(n);
091            }
092        }
093
094        // Ugly method of ensuring that the offset isn't inverted. I'm sure there is a better and more elegant way
095        Way refWay = ways.get(refWayIndex);
096        boolean refWayReversed = IntStream.range(0, sortedNodes.size() - 1)
097                .noneMatch(i -> sortedNodes.get(i) == refWay.firstNode() && sortedNodes.get(i + 1) == refWay.getNode(1));
098        if (refWayReversed) {
099            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        }
124    }
125
126    /**
127     * Determines if the nodes graph form a closed path
128     * @return {@code true} if the nodes graph form a closed path
129     */
130    public boolean isClosedPath() {
131        return sortedNodes.get(0) == sortedNodes.get(sortedNodes.size() - 1);
132    }
133
134    /**
135     * Offsets the way(s) d units. Positive d means to the left (relative to the reference way)
136     * @param d offset
137     */
138    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;
156            } 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;
167            } 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.
183     */
184    public void commit() {
185        UndoRedoHandler.getInstance().add(new SequenceCommand("Make parallel way(s)", makeAddWayAndNodesCommandList()));
186    }
187
188    private List<Command> makeAddWayAndNodesCommandList() {
189        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) {
201            commands.add(new AddCommand(ds, w));
202        }
203        return commands;
204    }
205
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
219     */
220    public final List<Way> getWays() {
221        return ways;
222    }
223}