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 }