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;
012
013import org.openstreetmap.josm.Main;
014import org.openstreetmap.josm.actions.CombineWayAction;
015import org.openstreetmap.josm.command.AddCommand;
016import org.openstreetmap.josm.command.Command;
017import org.openstreetmap.josm.command.SequenceCommand;
018import org.openstreetmap.josm.data.coor.EastNorth;
019import org.openstreetmap.josm.data.osm.Node;
020import org.openstreetmap.josm.data.osm.Way;
021import org.openstreetmap.josm.tools.Geometry;
022
023/**
024 * Helper for ParallelWayAction
025 *
026 * @author Ole Jørgen Brønner (olejorgenb)
027 */
028public class ParallelWays {
029    private final List<Way> ways;
030    private final List<Node> sortedNodes;
031
032    private final int nodeCount;
033
034    private final EastNorth[] pts;
035    private final EastNorth[] normals;
036
037    // Need a reference way to determine the direction of the offset when we manage multiple ways
038    public ParallelWays(Collection<Way> sourceWays, boolean copyTags, int refWayIndex) {
039        // Possible/sensible to use PrimetiveDeepCopy here?
040
041        // Make a deep copy of the ways, keeping the copied ways connected
042        // TODO: This assumes the first/last nodes of the ways are the only possible shared nodes.
043        Map<Node, Node> splitNodeMap = new HashMap<>(sourceWays.size());
044        for (Way w : sourceWays) {
045            if (!splitNodeMap.containsKey(w.firstNode())) {
046                splitNodeMap.put(w.firstNode(), copyNode(w.firstNode(), copyTags));
047            }
048            if (!splitNodeMap.containsKey(w.lastNode())) {
049                splitNodeMap.put(w.lastNode(), copyNode(w.lastNode(), copyTags));
050            }
051        }
052        ways = new ArrayList<>(sourceWays.size());
053        for (Way w : sourceWays) {
054            Way wCopy = new Way();
055            wCopy.addNode(splitNodeMap.get(w.firstNode()));
056            for (int i = 1; i < w.getNodesCount() - 1; i++) {
057                wCopy.addNode(copyNode(w.getNode(i), copyTags));
058            }
059            wCopy.addNode(splitNodeMap.get(w.lastNode()));
060            if (copyTags) {
061                wCopy.setKeys(w.getKeys());
062            }
063            ways.add(wCopy);
064        }
065
066        // Find a linear ordering of the nodes. Fail if there isn't one.
067        CombineWayAction.NodeGraph nodeGraph = CombineWayAction.NodeGraph.createUndirectedGraphFromNodeWays(ways);
068        List<Node> sortedNodesPath = nodeGraph.buildSpanningPath();
069        if (sortedNodesPath == null)
070            throw new IllegalArgumentException("Ways must have spanning path"); // Create a dedicated exception?
071
072        // Fix #8631 - Remove duplicated nodes from graph to be robust with self-intersecting ways
073        Set<Node> removedNodes = new HashSet<>();
074        sortedNodes = new ArrayList<>();
075        for (int i = 0; i < sortedNodesPath.size(); i++) {
076            Node n = sortedNodesPath.get(i);
077            if (i < sortedNodesPath.size()-1 && sortedNodesPath.get(i+1).getCoor().equals(n.getCoor())) {
078                removedNodes.add(n);
079                for (Way w : ways) {
080                    w.removeNode(n);
081                }
082                continue;
083            }
084            if (!removedNodes.contains(n)) {
085                sortedNodes.add(n);
086            }
087        }
088
089        // Ugly method of ensuring that the offset isn't inverted. I'm sure there is a better and more elegant way
090        Way refWay = ways.get(refWayIndex);
091        boolean refWayReversed = true;
092        for (int i = 0; i < sortedNodes.size() - 1; i++) {
093            if (sortedNodes.get(i) == refWay.firstNode() && sortedNodes.get(i + 1) == refWay.getNode(1)) {
094                refWayReversed = false;
095                break;
096            }
097        }
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    public boolean isClosedPath() {
121        return sortedNodes.get(0) == sortedNodes.get(sortedNodes.size() - 1);
122    }
123
124    /**
125     * Offsets the way(s) d units. Positive d means to the left (relative to the reference way)
126     * @param d offset
127     */
128    public void changeOffset(double d) {
129        // This is the core algorithm:
130        /* 1. Calculate a parallel line, offset by 'd', to each segment in the path
131         * 2. Find the intersection of lines belonging to neighboring segments. These become the new node positions
132         * 3. Do some special casing for closed paths
133         *
134         * Simple and probably not even close to optimal performance wise
135         */
136
137        EastNorth[] ppts = new EastNorth[nodeCount];
138
139        EastNorth prevA = pts[0].add(normals[0].scale(d));
140        EastNorth prevB = pts[1].add(normals[0].scale(d));
141        for (int i = 1; i < nodeCount - 1; i++) {
142            EastNorth a = pts[i].add(normals[i].scale(d));
143            EastNorth b = pts[i + 1].add(normals[i].scale(d));
144            if (Geometry.segmentsParallel(a, b, prevA, prevB)) {
145                ppts[i] = a;
146            } else {
147                ppts[i] = Geometry.getLineLineIntersection(a, b, prevA, prevB);
148            }
149            prevA = a;
150            prevB = b;
151        }
152        if (isClosedPath()) {
153            EastNorth a = pts[0].add(normals[0].scale(d));
154            EastNorth b = pts[1].add(normals[0].scale(d));
155            if (Geometry.segmentsParallel(a, b, prevA, prevB)) {
156                ppts[0] = a;
157            } else {
158                ppts[0] = Geometry.getLineLineIntersection(a, b, prevA, prevB);
159            }
160            ppts[nodeCount - 1] = ppts[0];
161        } else {
162            ppts[0] = pts[0].add(normals[0].scale(d));
163            ppts[nodeCount - 1] = pts[nodeCount - 1].add(normals[nodeCount - 2].scale(d));
164        }
165
166        for (int i = 0; i < nodeCount; i++) {
167            sortedNodes.get(i).setEastNorth(ppts[i]);
168        }
169    }
170
171    public void commit() {
172        SequenceCommand undoCommand = new SequenceCommand("Make parallel way(s)", makeAddWayAndNodesCommandList());
173        Main.main.undoRedo.add(undoCommand);
174    }
175
176    private List<Command> makeAddWayAndNodesCommandList() {
177        List<Command> commands = new ArrayList<>(sortedNodes.size() + ways.size());
178        for (int i = 0; i < sortedNodes.size() - (isClosedPath() ? 1 : 0); i++) {
179            commands.add(new AddCommand(sortedNodes.get(i)));
180        }
181        for (Way w : ways) {
182            commands.add(new AddCommand(w));
183        }
184        return commands;
185    }
186
187    private static Node copyNode(Node source, boolean copyTags) {
188        if (copyTags)
189            return new Node(source, true);
190        else {
191            Node n = new Node();
192            n.setCoor(source.getCoor());
193            return n;
194        }
195    }
196
197    public final List<Way> getWays() {
198        return ways;
199    }
200}