source: josm/trunk/src/org/openstreetmap/josm/actions/OrthogonalizeAction.java@ 2014

Last change on this file since 2014 was 2014, checked in by stoecker, 15 years ago

fixed #3205 - patch by dmuecke - arrange orthogonal not working
File size: 16.8 KB
Line 
1// License: GPL. See LICENSE file for details.
2//
3package org.openstreetmap.josm.actions;
4
5import static org.openstreetmap.josm.tools.I18n.tr;
6
7import java.awt.event.ActionEvent;
8import java.awt.event.KeyEvent;
9import java.util.ArrayList;
10import java.util.Collection;
11import java.util.LinkedList;
12
13import javax.swing.JOptionPane;
14
15import org.openstreetmap.josm.Main;
16import org.openstreetmap.josm.command.Command;
17import org.openstreetmap.josm.command.MoveCommand;
18import org.openstreetmap.josm.command.SequenceCommand;
19import org.openstreetmap.josm.data.coor.EastNorth;
20import org.openstreetmap.josm.data.coor.LatLon;
21import org.openstreetmap.josm.data.osm.Node;
22import org.openstreetmap.josm.data.osm.OsmPrimitive;
23import org.openstreetmap.josm.data.osm.Way;
24import org.openstreetmap.josm.gui.ConditionalOptionPaneUtil;
25import org.openstreetmap.josm.gui.OptionPaneUtil;
26import org.openstreetmap.josm.tools.Shortcut;
27
28/**
29 * Align edges of a way so all angles are right angles.
30 *
31 * 1. Find orientation of all edges
32 * 2. Compute main orientation, weighted by length of edge, normalized to angles between 0 and pi/2
33 * 3. Rotate every edge around its center to align with main orientation or perpendicular to it
34 * 4. Compute new intersection points of two adjascent edges
35 * 5. Move nodes to these points
36 * 6. if there are nodes between edges then align the nodes
37 */
38public final class OrthogonalizeAction extends JosmAction {
39
40 public OrthogonalizeAction() {
41 super(tr("Orthogonalize Shape"),
42 "ortho",
43 tr("Move nodes so all angles are 90 or 270 degree"),
44 Shortcut.registerShortcut("tools:orthogonalize", tr("Tool: {0}", tr("Orthogonalize Shape")),
45 KeyEvent.VK_Q,
46 Shortcut.GROUP_EDIT), true);
47 }
48
49 public void actionPerformed(ActionEvent e) {
50 if (!isEnabled())
51 return;
52 Collection<OsmPrimitive> sel = getCurrentDataSet().getSelected();
53
54 ArrayList<Node> dirnodes = new ArrayList<Node>();
55 ArrayList<Node> alignNodes = new ArrayList<Node>();
56
57 // Check the selection if it is suitable for the orthogonalisation
58 for (OsmPrimitive osm : sel) {
59 // Check if not more than two nodes in the selection
60 if(osm instanceof Node) {
61 if(dirnodes.size() == 2) {
62 OptionPaneUtil.showMessageDialog(
63 Main.parent,
64 tr("Only two nodes allowed"),
65 tr("Information"),
66 JOptionPane.INFORMATION_MESSAGE
67 );
68 return;
69 }
70 dirnodes.add((Node) osm);
71 continue;
72 }
73 // Check if selection consists now only of ways
74 if (!(osm instanceof Way)) {
75 OptionPaneUtil.showMessageDialog(
76 Main.parent,
77 tr("Selection must consist only of ways."),
78 tr("Information"),
79 JOptionPane.INFORMATION_MESSAGE
80 );
81 return;
82 }
83
84 // Check if every way is made of at least four segments and closed
85 Way way = (Way)osm;
86 if ((way.getNodesCount() < 5) || !way.isClosed()) {
87 OptionPaneUtil.showMessageDialog(
88 Main.parent,
89 tr("Please select one or more closed ways of at least four nodes."),
90 tr("Information"),
91 JOptionPane.INFORMATION_MESSAGE
92 );
93 return;
94 }
95
96 // Check if every edge in the way is a definite edge of at least 45 degrees of direction change
97 // Otherwise, two segments could be turned into same direction and intersection would fail.
98 // Or changes of shape would be too serious.
99 for (int i1=0; i1 < way.getNodesCount()-1; i1++) {
100 int i2 = (i1+1) % (way.getNodesCount()-1);
101 int i3 = (i1+2) % (way.getNodesCount()-1);
102 double angle1 =Math.abs(way.getNode(i1).getEastNorth().heading(way.getNode(i2).getEastNorth()));
103 double angle2 = Math.abs(way.getNode(i2).getEastNorth().heading(way.getNode(i3).getEastNorth()));
104 double delta = Math.abs(angle2 - angle1);
105 while(delta > Math.PI) {
106 delta -= Math.PI;
107 }
108 if(delta < Math.PI/4) {
109 // not an edge
110 alignNodes.add(way.getNode(i2));
111 }
112 }
113
114 // first node has to be an edge so we move the node to the end of the way
115 while (alignNodes.contains(way.firstNode())) {
116 Node n = way.firstNode();
117 way.removeNode(n);
118 way.addNode(way.getNodesCount() - 2, n); // ! -2 because first node == last node in closed way
119 }
120 }
121
122 if ("EPSG:4326".equals(Main.proj.toString())) {
123 String msg = tr("<html>You are using the EPSG:4326 projection which might lead<br>" +
124 "to undesirable results when doing rectangular alignments.<br>" +
125 "Change your projection to get rid of this warning.<br>" +
126 "Do you want to continue?</html>");
127 if (!ConditionalOptionPaneUtil.showConfirmationDialog(
128 "align_rectangular_4326",
129 Main.parent,
130 msg,
131 tr("Warning"),
132 JOptionPane.YES_NO_OPTION,
133 JOptionPane.QUESTION_MESSAGE,
134 JOptionPane.YES_OPTION))
135 return;
136 }
137 // Check, if selection held neither none nor two nodes
138 if(dirnodes.size() == 1) {
139 OptionPaneUtil.showMessageDialog(
140 Main.parent,
141 tr("Only one node selected"),
142 tr("Warning"),
143 JOptionPane.WARNING_MESSAGE
144 );
145 return;
146 }
147
148 // Now all checks are done and we can now do the neccessary computations
149 // From here it is assumed that the above checks hold
150 Collection<Command> cmds = new LinkedList<Command>();
151 double align_to_heading = 0.0;
152 boolean use_dirnodes = false;
153
154 if (dirnodes.size() == 2) {
155 // When selection contains two nodes, use the nodes to compute a direction
156 // to align all ways to
157 align_to_heading = normalize_angle(dirnodes.get(0).getEastNorth().heading(dirnodes.get(1).getEastNorth()));
158 use_dirnodes = true;
159 }
160
161 for (OsmPrimitive osm : sel) {
162 if(!(osm instanceof Way)) {
163 continue;
164 }
165
166 Way oldWay = (Way) osm;
167 Way way = new Way();
168 // copy only edges into way
169 for (Node origNode : oldWay.getNodes()) {
170 if (alignNodes.contains(origNode)) {
171 continue;
172 }
173 way.addNode(origNode);
174 }
175 int nodes = way.getNodesCount();
176 int sides = nodes - 1;
177 // Copy necessary data into a more suitable data structure
178 EastNorth en[] = new EastNorth[sides];
179 for (int i = 0; i < sides; i++) {
180 en[i] = new EastNorth(way.getNode(i).getEastNorth().east(), way.getNode(i).getEastNorth().north());
181 }
182
183 if (! use_dirnodes) {
184 // To find orientation of all segments, compute weighted average of all segment's headings
185 // all headings are mapped into [-PI/4, PI/4] by PI/2 rotations so both main orientations are mapped into one
186 // the headings are weighted by the length of the segment establishing it, so a longer segment, that is more
187 // likely to have the correct orientation, has more influence in the computing than a short segment, that is easier to misalign.
188 double headings[] = new double[sides];
189 double weights[] = new double[sides];
190 for (int i=0; i < sides; i++) {
191 headings[i] = normalize_angle(way.getNode(i).getEastNorth().heading(way.getNode(i+1).getEastNorth()));
192 weights[i] = way.getNode(i).getEastNorth().distance(way.getNode(i+1).getEastNorth());
193 }
194
195 // CAVEAT: for orientations near -PI/4 or PI/4 the mapping into ONE orientation fails
196 // resulting in a heading-difference between adjacent sides of almost PI/2
197 // and a totally wrong average
198 // check for this (use PI/3 as arbitray limit) and rotate into ONE orientation
199 double angle_diff_max = 0.0;
200 for (int i=0; i < sides; i++) {
201 double diff = 0.0;
202 if (i == 0) {
203 diff = heading_diff(headings[i], headings[sides - 1]);
204 } else {
205 diff = heading_diff(headings[i], headings[i - 1]);
206 }
207 if (diff > angle_diff_max) {
208 angle_diff_max = diff;
209 }
210 }
211
212 if (angle_diff_max > Math.PI/3) {
213 // rearrange headings: everything < 0 gets PI/2-rotated
214 for (int i=0; i < sides; i++) {
215 if (headings[i] < 0) {
216 headings[i] += Math.PI/2;
217 }
218 }
219 }
220
221 // TODO:
222 // use angle_diff_max as an indicator that the way is already orthogonal
223 // e.g. if angle_diff_max is less then Math.toRadians(0.5)
224 // and do nothing in that case (?)
225
226 // Compute the weighted average of the headings of all segments
227 double sum_weighted_headings = 0.0;
228 double sum_weights = 0.0;
229 for (int i=0; i < sides; i++) {
230 sum_weighted_headings += headings[i] * weights[i];
231 sum_weights += weights[i];
232 }
233 align_to_heading = normalize_angle(sum_weighted_headings/sum_weights);
234 }
235
236 EastNorth aligna = null;
237 EastNorth alignb = null;
238 EastNorth align0 = null;
239 Node nodea = null;
240 Node nodeb = null;
241 Node node0 = null;
242
243 for (int i=0; i < sides; i++) {
244 // Compute handy indices of three nodes to be used in one loop iteration.
245 // We use segments (i1,i2) and (i2,i3), align them and compute the new
246 // position of the i2-node as the intersection of the realigned (i1,i2), (i2,i3) segments
247 // Not the most efficient algorithm, but we don't handle millions of nodes...
248 int i1 = i;
249 int i2 = (i+1)%sides;
250 int i3 = (i+2)%sides;
251 double heading1, heading2;
252 double delta1, delta2;
253 // Compute neccessary rotation of first segment to align it with main orientation
254 heading1 = normalize_angle(en[i1].heading(en[i2]), align_to_heading);
255 delta1 = align_to_heading - heading1;
256 // Compute neccessary rotation of second segment to align it with main orientation
257 heading2 = normalize_angle(en[i2].heading(en[i3]), align_to_heading);
258 delta2 = align_to_heading - heading2;
259 // To align a segment, rotate around its center
260 EastNorth pivot1 = new EastNorth((en[i1].east()+en[i2].east())/2, (en[i1].north()+en[i2].north())/2);
261 EastNorth A=en[i1].rotate(pivot1, delta1);
262 EastNorth B=en[i2].rotate(pivot1, delta1);
263 EastNorth pivot2 = new EastNorth((en[i2].east()+en[i3].east())/2, (en[i2].north()+en[i3].north())/2);
264 EastNorth C=en[i2].rotate(pivot2, delta2);
265 EastNorth D=en[i3].rotate(pivot2, delta2);
266
267 // compute intersection of segments
268 double u=det(B.east() - A.east(), B.north() - A.north(),
269 C.east() - D.east(), C.north() - D.north());
270
271 // Check for parallel segments and do nothing if they are
272 // In practice this will probably only happen when a way has
273 // been duplicated
274
275 if (u == 0) {
276 continue;
277 }
278
279 // q is a number between 0 and 1
280 // It is the point in the segment where the intersection occurs
281 // if the segment is scaled to length 1
282
283 double q = det(B.north() - C.north(), B.east() - C.east(),
284 D.north() - C.north(), D.east() - C.east()) / u;
285 EastNorth intersection = new EastNorth(
286 B.east() + q * (A.east() - B.east()),
287 B.north() + q * (A.north() - B.north()));
288
289 Node n = way.getNode(i2);
290
291 LatLon ill = Main.proj.eastNorth2latlon(intersection);
292 if (!ill.equalsEpsilon(n.getCoor())) {
293 double dx = intersection.east()-n.getEastNorth().east();
294 double dy = intersection.north()-n.getEastNorth().north();
295 cmds.add(new MoveCommand(n, dx, dy));
296 }
297
298 // align all nodes between two edges
299 aligna = alignb;
300 alignb = intersection;
301 nodea = nodeb;
302 nodeb = n;
303 if (aligna != null) {
304
305 MoveCommand cmd = alignSide(findNodesToAlign(oldWay, nodea, nodeb), aligna, alignb);
306 if (cmd != null) {
307 cmds.add(cmd);
308 }
309
310 } else {
311 align0 = alignb;
312 node0 = nodeb;
313 }
314 }
315 MoveCommand cmd = alignSide(findNodesToAlign(oldWay, nodeb, node0), alignb, align0);
316 if (cmd != null) {
317 cmds.add(cmd);
318 }
319 }
320
321 if (cmds.size() > 0) {
322 Main.main.undoRedo.add(new SequenceCommand(tr("Orthogonalize"), cmds));
323 Main.map.repaint();
324 }
325 }
326
327 private MoveCommand alignSide(ArrayList<Node> aNodes, EastNorth aligna, EastNorth alignb) {
328
329 // Find out co-ords of A and B
330 double ax = aligna.east();
331 double ay = aligna.north();
332 double bx = alignb.east();
333 double by = alignb.north();
334
335 // OK, for each node to move, work out where to move it!
336 for (Node n1 : aNodes) {
337 // Get existing co-ords of node to move
338 double nx = n1.getEastNorth().east();
339 double ny = n1.getEastNorth().north();
340
341 if (ax == bx) {
342 // Special case if AB is vertical...
343 nx = ax;
344 } else if (ay == by) {
345 // ...or horizontal
346 ny = ay;
347 } else {
348 // Otherwise calculate position by solving y=mx+c
349 double m1 = (by - ay) / (bx - ax);
350 double c1 = ay - (ax * m1);
351 double m2 = (-1) / m1;
352 double c2 = n1.getEastNorth().north() - (n1.getEastNorth().east() * m2);
353
354 nx = (c2 - c1) / (m1 - m2);
355 ny = (m1 * nx) + c1;
356 }
357
358 // Return the command to move the node to its new position.
359 return new MoveCommand(n1, nx - n1.getEastNorth().east(), ny - n1.getEastNorth().north());
360 }
361 return null;
362 }
363
364 private ArrayList<Node> findNodesToAlign(Way w, Node from, Node to) {
365 ArrayList<Node> l = new ArrayList<Node>();
366 boolean start = false;
367 for (int i = 0; i < w.getNodesCount(); i++) {
368 Node n = w.getNode(i % w.getNodesCount());
369 if (n.equals(to)) {
370 break;
371 }
372 if (start) {
373 l.add(n);
374 }
375 if (n.equals(from)) {
376 start = true;
377 }
378
379 }
380 return l;
381 }
382
383 static double det(double a, double b, double c, double d)
384 {
385 return a * d - b * c;
386 }
387
388 static double normalize_angle(double h) {
389 return normalize_angle(h, 0.0);
390 }
391 static double normalize_angle(double h, double align_to) {
392 double llimit = -Math.PI/4;
393 double ulimit = Math.PI/4;
394 while (h - align_to > ulimit) {
395 h -= Math.PI/2;
396 }
397 while (h - align_to < llimit) {
398 h += Math.PI/2;
399 }
400
401 return h;
402 }
403
404 static double heading_diff(double h1, double h2) {
405 double heading_delta = h1 > h2 ? h1 - h2 : h2 - h1;
406 return heading_delta;
407 }
408
409 @Override
410 protected void updateEnabledState() {
411 setEnabled(getCurrentDataSet() != null && ! getCurrentDataSet().getSelected().isEmpty());
412 }
413}
Note: See TracBrowser for help on using the repository browser.