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

Last change on this file since 2136 was 2017, checked in by Gubaer, 15 years ago

removed OptionPaneUtil
cleanup of deprecated Layer API
cleanup of deprecated APIs in OsmPrimitive and Way
cleanup of imports

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