source: josm/trunk/src/org/openstreetmap/josm/actions/mapmode/ParallelWays.java @ 12969

Last change on this file since 12969 was 12969, checked in by Don-vip, 14 months ago

see #15420 - should fix NPE in ParallelWays.copyNode (probably caused by an incomplete or empty way)

  • Property svn:eol-style set to native
File size: 8.1 KB
Line 
1// License: GPL. For details, see LICENSE file.
2package org.openstreetmap.josm.actions.mapmode;
3
4import java.util.ArrayList;
5import java.util.Collection;
6import java.util.Collections;
7import java.util.HashMap;
8import java.util.HashSet;
9import java.util.List;
10import java.util.Map;
11import java.util.Set;
12
13import org.openstreetmap.josm.Main;
14import org.openstreetmap.josm.command.AddCommand;
15import org.openstreetmap.josm.command.Command;
16import org.openstreetmap.josm.command.SequenceCommand;
17import org.openstreetmap.josm.data.coor.EastNorth;
18import org.openstreetmap.josm.data.osm.DataSet;
19import org.openstreetmap.josm.data.osm.Node;
20import org.openstreetmap.josm.data.osm.NodeGraph;
21import org.openstreetmap.josm.data.osm.Way;
22import org.openstreetmap.josm.gui.MainApplication;
23import org.openstreetmap.josm.tools.Geometry;
24
25/**
26 * Helper for {@link ParallelWayAction}.
27 *
28 * @author Ole Jørgen Brønner (olejorgenb)
29 */
30public class ParallelWays {
31    private final List<Way> ways;
32    private final List<Node> sortedNodes;
33
34    private final int nodeCount;
35
36    private final EastNorth[] pts;
37    private final EastNorth[] normals;
38
39    /**
40     * Constructs a new {@code ParallelWays}.
41     * @param sourceWays source ways
42     * @param copyTags whether tags should be copied
43     * @param refWayIndex Need a reference way to determine the direction of the offset when we manage multiple ways
44     */
45    public ParallelWays(Collection<Way> sourceWays, boolean copyTags, int refWayIndex) {
46        // Possible/sensible to use PrimitiveDeepCopy here?
47
48        // Make a deep copy of the ways, keeping the copied ways connected
49        // TODO: This assumes the first/last nodes of the ways are the only possible shared nodes.
50        Map<Node, Node> splitNodeMap = new HashMap<>(sourceWays.size());
51        for (Way w : sourceWays) {
52            copyNodeInMap(splitNodeMap, w.firstNode(), copyTags);
53            copyNodeInMap(splitNodeMap, w.lastNode(), copyTags);
54        }
55        ways = new ArrayList<>(sourceWays.size());
56        for (Way w : sourceWays) {
57            Way wCopy = new Way();
58            wCopy.addNode(splitNodeMap.get(w.firstNode()));
59            for (int i = 1; i < w.getNodesCount() - 1; i++) {
60                wCopy.addNode(copyNode(w.getNode(i), copyTags));
61            }
62            wCopy.addNode(splitNodeMap.get(w.lastNode()));
63            if (copyTags) {
64                wCopy.setKeys(w.getKeys());
65            }
66            ways.add(wCopy);
67        }
68
69        // Find a linear ordering of the nodes. Fail if there isn't one.
70        NodeGraph nodeGraph = NodeGraph.createUndirectedGraphFromNodeWays(ways);
71        List<Node> sortedNodesPath = nodeGraph.buildSpanningPath();
72        if (sortedNodesPath == null)
73            throw new IllegalArgumentException("Ways must have spanning path"); // Create a dedicated exception?
74
75        // Fix #8631 - Remove duplicated nodes from graph to be robust with self-intersecting ways
76        Set<Node> removedNodes = new HashSet<>();
77        sortedNodes = new ArrayList<>();
78        for (int i = 0; i < sortedNodesPath.size(); i++) {
79            Node n = sortedNodesPath.get(i);
80            if (i < sortedNodesPath.size()-1 && sortedNodesPath.get(i+1).getCoor().equals(n.getCoor())) {
81                removedNodes.add(n);
82                for (Way w : ways) {
83                    w.removeNode(n);
84                }
85                continue;
86            }
87            if (!removedNodes.contains(n)) {
88                sortedNodes.add(n);
89            }
90        }
91
92        // Ugly method of ensuring that the offset isn't inverted. I'm sure there is a better and more elegant way
93        Way refWay = ways.get(refWayIndex);
94        boolean refWayReversed = true;
95        for (int i = 0; i < sortedNodes.size() - 1; i++) {
96            if (sortedNodes.get(i) == refWay.firstNode() && sortedNodes.get(i + 1) == refWay.getNode(1)) {
97                refWayReversed = false;
98                break;
99            }
100        }
101        if (refWayReversed) {
102            Collections.reverse(sortedNodes); // need to keep the orientation of the reference way.
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    private static void copyNodeInMap(Map<Node, Node> splitNodeMap, Node node, boolean copyTags) {
124        if (!splitNodeMap.containsKey(node)) {
125            splitNodeMap.put(node, copyNode(node, copyTags));
126        }
127    }
128
129    /**
130     * Determines if the nodes graph form a closed path
131     * @return {@code true} if the nodes graph form a closed path
132     */
133    public boolean isClosedPath() {
134        return sortedNodes.get(0) == sortedNodes.get(sortedNodes.size() - 1);
135    }
136
137    /**
138     * Offsets the way(s) d units. Positive d means to the left (relative to the reference way)
139     * @param d offset
140     */
141    public void changeOffset(double d) {
142        // This is the core algorithm:
143        /* 1. Calculate a parallel line, offset by 'd', to each segment in the path
144         * 2. Find the intersection of lines belonging to neighboring segments. These become the new node positions
145         * 3. Do some special casing for closed paths
146         *
147         * Simple and probably not even close to optimal performance wise
148         */
149
150        EastNorth[] ppts = new EastNorth[nodeCount];
151
152        EastNorth prevA = pts[0].add(normals[0].scale(d));
153        EastNorth prevB = pts[1].add(normals[0].scale(d));
154        for (int i = 1; i < nodeCount - 1; i++) {
155            EastNorth a = pts[i].add(normals[i].scale(d));
156            EastNorth b = pts[i + 1].add(normals[i].scale(d));
157            if (Geometry.segmentsParallel(a, b, prevA, prevB)) {
158                ppts[i] = a;
159            } else {
160                ppts[i] = Geometry.getLineLineIntersection(a, b, prevA, prevB);
161            }
162            prevA = a;
163            prevB = b;
164        }
165        if (isClosedPath()) {
166            EastNorth a = pts[0].add(normals[0].scale(d));
167            EastNorth b = pts[1].add(normals[0].scale(d));
168            if (Geometry.segmentsParallel(a, b, prevA, prevB)) {
169                ppts[0] = a;
170            } else {
171                ppts[0] = Geometry.getLineLineIntersection(a, b, prevA, prevB);
172            }
173            ppts[nodeCount - 1] = ppts[0];
174        } else {
175            ppts[0] = pts[0].add(normals[0].scale(d));
176            ppts[nodeCount - 1] = pts[nodeCount - 1].add(normals[nodeCount - 2].scale(d));
177        }
178
179        for (int i = 0; i < nodeCount; i++) {
180            sortedNodes.get(i).setEastNorth(ppts[i]);
181        }
182    }
183
184    /**
185     * Performs the action by adding a new sequence command to the undo/redo queue.
186     */
187    public void commit() {
188        MainApplication.undoRedo.add(new SequenceCommand("Make parallel way(s)", makeAddWayAndNodesCommandList()));
189    }
190
191    private List<Command> makeAddWayAndNodesCommandList() {
192        DataSet ds = Main.main.getEditDataSet();
193        List<Command> commands = new ArrayList<>(sortedNodes.size() + ways.size());
194        for (int i = 0; i < sortedNodes.size() - (isClosedPath() ? 1 : 0); i++) {
195            commands.add(new AddCommand(ds, sortedNodes.get(i)));
196        }
197        for (Way w : ways) {
198            commands.add(new AddCommand(ds, w));
199        }
200        return commands;
201    }
202
203    private static Node copyNode(Node source, boolean copyTags) {
204        if (copyTags)
205            return new Node(source, true);
206        else {
207            Node n = new Node();
208            n.setCoor(source.getCoor());
209            return n;
210        }
211    }
212
213    /**
214     * Returns the resulting parallel ways.
215     * @return the resulting parallel ways
216     */
217    public final List<Way> getWays() {
218        return ways;
219    }
220}
Note: See TracBrowser for help on using the repository browser.