001// License: GPL. See LICENSE file for details.
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.Set;
011
012import org.openstreetmap.josm.Main;
013import org.openstreetmap.josm.actions.CombineWayAction;
014import org.openstreetmap.josm.command.AddCommand;
015import org.openstreetmap.josm.command.Command;
016import org.openstreetmap.josm.command.SequenceCommand;
017import org.openstreetmap.josm.data.coor.EastNorth;
018import org.openstreetmap.josm.data.osm.Node;
019import org.openstreetmap.josm.data.osm.Way;
020import org.openstreetmap.josm.tools.Geometry;
021
022/**
023 * Helper for ParallelWayAction
024 *
025 * @author Ole Jørgen Brønner (olejorgenb)
026 */
027public class ParallelWays {
028    final List<Way> ways;
029    private final List<Node> sortedNodes;
030
031    private final int nodeCount;
032
033    private final EastNorth[] pts;
034    private final EastNorth[] normals;
035
036    // Need a reference way to determine the direction of the offset when we manage multiple ways
037    public ParallelWays(Collection<Way> sourceWays, boolean copyTags, int refWayIndex) {
038        // Possible/sensible to use PrimetiveDeepCopy here?
039
040        // Make a deep copy of the ways, keeping the copied ways connected
041        // TODO: This assumes the first/last nodes of the ways are the only possible shared nodes.
042        HashMap<Node, Node> splitNodeMap = new HashMap<Node, Node>(sourceWays.size());
043        for (Way w : sourceWays) {
044            if (!splitNodeMap.containsKey(w.firstNode())) {
045                splitNodeMap.put(w.firstNode(), copyNode(w.firstNode(), copyTags));
046            }
047            if (!splitNodeMap.containsKey(w.lastNode())) {
048                splitNodeMap.put(w.lastNode(), copyNode(w.lastNode(), copyTags));
049            }
050        }
051        ways = new ArrayList<Way>(sourceWays.size());
052        for (Way w : sourceWays) {
053            Way wCopy = new Way();
054            wCopy.addNode(splitNodeMap.get(w.firstNode()));
055            for (int i = 1; i < w.getNodesCount() - 1; i++) {
056                wCopy.addNode(copyNode(w.getNode(i), copyTags));
057            }
058            wCopy.addNode(splitNodeMap.get(w.lastNode()));
059            if (copyTags) {
060                wCopy.setKeys(w.getKeys());
061            }
062            ways.add(wCopy);
063        }
064        sourceWays = null; // Ensure that we only use the copies from now
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<Node>();
074        sortedNodes = new ArrayList<Node>();
075        for (int i = 0; i < sortedNodesPath.size(); i++) {
076            Node n = sortedNodesPath.get(i);
077            if (i < sortedNodesPath.size()-1) {
078                if (sortedNodesPath.get(i+1).getCoor().equals(n.getCoor())) {
079                    removedNodes.add(n);
080                    for (Way w : ways)
081                        w.removeNode(n);
082                    continue;
083                }
084            }
085            if (!removedNodes.contains(n)) {
086                sortedNodes.add(n);
087            }
088        }
089
090        // Ugly method of ensuring that the offset isn't inverted. I'm sure there is a better and more elegant way, but I'm starting to get sleepy, so I do this for now.
091        {
092            Way refWay = ways.get(refWayIndex);
093            boolean refWayReversed = true;
094            for (int i = 0; i < sortedNodes.size() - 1; i++) {
095                if (sortedNodes.get(i) == refWay.firstNode() && sortedNodes.get(i + 1) == refWay.getNode(1)) {
096                    refWayReversed = false;
097                    break;
098                }
099            }
100            if (refWayReversed) {
101                Collections.reverse(sortedNodes); // need to keep the orientation of the reference way.
102            }
103        }
104
105        // Initialize the required parameters. (segment normals, etc.)
106        nodeCount = sortedNodes.size();
107        pts = new EastNorth[nodeCount];
108        normals = new EastNorth[nodeCount - 1];
109        int i = 0;
110        for (Node n : sortedNodes) {
111            EastNorth t = n.getEastNorth();
112            pts[i] = t;
113            i++;
114        }
115        for (i = 0; i < nodeCount - 1; i++) {
116            double dx = pts[i + 1].getX() - pts[i].getX();
117            double dy = pts[i + 1].getY() - pts[i].getY();
118            double len = Math.sqrt(dx * dx + dy * dy);
119            normals[i] = new EastNorth(-dy / len, dx / len);
120        }
121    }
122
123    public boolean isClosedPath() {
124        return sortedNodes.get(0) == sortedNodes.get(sortedNodes.size() - 1);
125    }
126
127    /**
128     * Offsets the way(s) d units. Positive d means to the left (relative to the reference way)
129     * @param d
130     */
131    public void changeOffset(double d) {
132        // This is the core algorithm:
133        /* 1. Calculate a parallel line, offset by 'd', to each segment in the path
134         * 2. Find the intersection of lines belonging to neighboring segments. These become the new node positions
135         * 3. Do some special casing for closed paths
136         *
137         * Simple and probably not even close to optimal performance wise
138         */
139
140        EastNorth[] ppts = new EastNorth[nodeCount];
141
142        EastNorth prevA = pts[0].add(normals[0].scale(d));
143        EastNorth prevB = pts[1].add(normals[0].scale(d));
144        for (int i = 1; i < nodeCount - 1; i++) {
145            EastNorth A = pts[i].add(normals[i].scale(d));
146            EastNorth B = pts[i + 1].add(normals[i].scale(d));
147            if (Geometry.segmentsParallel(A, B, prevA, prevB)) {
148                ppts[i] = A;
149            } else {
150                ppts[i] = Geometry.getLineLineIntersection(A, B, prevA, prevB);
151            }
152            prevA = A;
153            prevB = B;
154        }
155        if (isClosedPath()) {
156            EastNorth A = pts[0].add(normals[0].scale(d));
157            EastNorth B = pts[1].add(normals[0].scale(d));
158            if (Geometry.segmentsParallel(A, B, prevA, prevB)) {
159                ppts[0] = A;
160            } else {
161                ppts[0] = Geometry.getLineLineIntersection(A, B, prevA, prevB);
162            }
163            ppts[nodeCount - 1] = ppts[0];
164        } else {
165            ppts[0] = pts[0].add(normals[0].scale(d));
166            ppts[nodeCount - 1] = pts[nodeCount - 1].add(normals[nodeCount - 2].scale(d));
167        }
168
169        for (int i = 0; i < nodeCount; i++) {
170            sortedNodes.get(i).setEastNorth(ppts[i]);
171        }
172    }
173
174    public void commit() {
175        SequenceCommand undoCommand = new SequenceCommand("Make parallel way(s)", makeAddWayAndNodesCommandList());
176        Main.main.undoRedo.add(undoCommand);
177    }
178
179    private List<Command> makeAddWayAndNodesCommandList() {
180        List<Command> commands = new ArrayList<Command>(sortedNodes.size() + ways.size());
181        for (int i = 0; i < sortedNodes.size() - (isClosedPath() ? 1 : 0); i++) {
182            commands.add(new AddCommand(sortedNodes.get(i)));
183        }
184        for (Way w : ways) {
185            commands.add(new AddCommand(w));
186        }
187        return commands;
188    }
189
190    static private Node copyNode(Node source, boolean copyTags) {
191        if (copyTags)
192            return new Node(source, true);
193        else {
194            Node n = new Node();
195            n.setCoor(source.getCoor());
196            return n;
197        }
198    }
199}