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