1 | // License: GPL. For details, see LICENSE file.
|
---|
2 | package org.openstreetmap.josm.actions.mapmode;
|
---|
3 |
|
---|
4 | import java.util.ArrayList;
|
---|
5 | import java.util.Collection;
|
---|
6 | import java.util.Collections;
|
---|
7 | import java.util.HashMap;
|
---|
8 | import java.util.HashSet;
|
---|
9 | import java.util.List;
|
---|
10 | import java.util.Map;
|
---|
11 | import java.util.Set;
|
---|
12 | import java.util.stream.IntStream;
|
---|
13 |
|
---|
14 | import org.openstreetmap.josm.command.AddCommand;
|
---|
15 | import org.openstreetmap.josm.command.Command;
|
---|
16 | import org.openstreetmap.josm.command.SequenceCommand;
|
---|
17 | import org.openstreetmap.josm.data.UndoRedoHandler;
|
---|
18 | import org.openstreetmap.josm.data.coor.EastNorth;
|
---|
19 | import org.openstreetmap.josm.data.osm.DataSet;
|
---|
20 | import org.openstreetmap.josm.data.osm.Node;
|
---|
21 | import org.openstreetmap.josm.data.osm.NodeGraph;
|
---|
22 | import org.openstreetmap.josm.data.osm.OsmDataManager;
|
---|
23 | import org.openstreetmap.josm.data.osm.Way;
|
---|
24 | import org.openstreetmap.josm.tools.Geometry;
|
---|
25 | import org.openstreetmap.josm.tools.Utils;
|
---|
26 |
|
---|
27 | /**
|
---|
28 | * Helper for {@link ParallelWayAction}.
|
---|
29 | *
|
---|
30 | * @author Ole Jørgen Brønner (olejorgenb)
|
---|
31 | */
|
---|
32 | public class ParallelWays {
|
---|
33 | private final List<Way> ways;
|
---|
34 | private final List<Node> sortedNodes;
|
---|
35 |
|
---|
36 | private final int nodeCount;
|
---|
37 |
|
---|
38 | private final EastNorth[] pts;
|
---|
39 | private final EastNorth[] normals;
|
---|
40 |
|
---|
41 | /**
|
---|
42 | * Constructs a new {@code ParallelWays}.
|
---|
43 | * @param sourceWays source ways
|
---|
44 | * @param copyTags whether tags should be copied
|
---|
45 | * @param refWayIndex Need a reference way to determine the direction of the offset when we manage multiple ways
|
---|
46 | */
|
---|
47 | public ParallelWays(Collection<Way> sourceWays, boolean copyTags, int refWayIndex) {
|
---|
48 | // Possible/sensible to use PrimitiveDeepCopy here?
|
---|
49 |
|
---|
50 | // Make a deep copy of the ways, keeping the copied ways connected
|
---|
51 | // TODO: This assumes the first/last nodes of the ways are the only possible shared nodes.
|
---|
52 | Map<Node, Node> splitNodeMap = new HashMap<>(Utils.hashMapInitialCapacity(sourceWays.size()));
|
---|
53 | for (Way w : sourceWays) {
|
---|
54 | copyNodeInMap(splitNodeMap, w.firstNode(), copyTags);
|
---|
55 | copyNodeInMap(splitNodeMap, w.lastNode(), copyTags);
|
---|
56 | }
|
---|
57 | ways = new ArrayList<>(sourceWays.size());
|
---|
58 | for (Way w : sourceWays) {
|
---|
59 | Way wCopy = new Way();
|
---|
60 | wCopy.addNode(splitNodeMap.get(w.firstNode()));
|
---|
61 | for (int i = 1; i < w.getNodesCount() - 1; i++) {
|
---|
62 | wCopy.addNode(copyNode(w.getNode(i), copyTags));
|
---|
63 | }
|
---|
64 | wCopy.addNode(splitNodeMap.get(w.lastNode()));
|
---|
65 | if (copyTags) {
|
---|
66 | wCopy.setKeys(w.getKeys());
|
---|
67 | }
|
---|
68 | ways.add(wCopy);
|
---|
69 | }
|
---|
70 |
|
---|
71 | // Find a linear ordering of the nodes. Fail if there isn't one.
|
---|
72 | NodeGraph nodeGraph = NodeGraph.createUndirectedGraphFromNodeWays(ways);
|
---|
73 | List<Node> sortedNodesPath = nodeGraph.buildSpanningPath();
|
---|
74 | if (sortedNodesPath == null)
|
---|
75 | throw new IllegalArgumentException("Ways must have spanning path"); // Create a dedicated exception?
|
---|
76 |
|
---|
77 | // Fix #8631 - Remove duplicated nodes from graph to be robust with self-intersecting ways
|
---|
78 | Set<Node> removedNodes = new HashSet<>();
|
---|
79 | sortedNodes = new ArrayList<>();
|
---|
80 | for (int i = 0; i < sortedNodesPath.size(); i++) {
|
---|
81 | Node n = sortedNodesPath.get(i);
|
---|
82 | if (i < sortedNodesPath.size()-1 && sortedNodesPath.get(i+1).getCoor().equals(n.getCoor())) {
|
---|
83 | removedNodes.add(n);
|
---|
84 | for (Way w : ways) {
|
---|
85 | w.removeNode(n);
|
---|
86 | }
|
---|
87 | continue;
|
---|
88 | }
|
---|
89 | if (!removedNodes.contains(n)) {
|
---|
90 | sortedNodes.add(n);
|
---|
91 | }
|
---|
92 | }
|
---|
93 |
|
---|
94 | // Ugly method of ensuring that the offset isn't inverted. I'm sure there is a better and more elegant way
|
---|
95 | Way refWay = ways.get(refWayIndex);
|
---|
96 | boolean refWayReversed = IntStream.range(0, sortedNodes.size() - 1)
|
---|
97 | .noneMatch(i -> sortedNodes.get(i) == refWay.firstNode() && sortedNodes.get(i + 1) == refWay.getNode(1));
|
---|
98 | if (refWayReversed) {
|
---|
99 | 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 | }
|
---|