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

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

replaced JOptionDialog.show... by OptionPaneUtil.show....
improved relation editor
File size: 13.7 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;
14import javax.swing.text.html.Option;
15
16import org.openstreetmap.josm.Main;
17import org.openstreetmap.josm.command.Command;
18import org.openstreetmap.josm.command.MoveCommand;
19import org.openstreetmap.josm.command.SequenceCommand;
20import org.openstreetmap.josm.data.coor.EastNorth;
21import org.openstreetmap.josm.data.coor.LatLon;
22import org.openstreetmap.josm.data.osm.Node;
23import org.openstreetmap.josm.data.osm.OsmPrimitive;
24import org.openstreetmap.josm.data.osm.Way;
25import org.openstreetmap.josm.gui.ConditionalOptionPaneUtil;
26import org.openstreetmap.josm.gui.OptionPaneUtil;
27import org.openstreetmap.josm.tools.Shortcut;
28
29/**
30 * Align edges of a way so all angles are right angles.
31 *
32 * 1. Find orientation of all edges
33 * 2. Compute main orientation, weighted by length of edge, normalized to angles between 0 and pi/2
34 * 3. Rotate every edge around its center to align with main orientation or perpendicular to it
35 * 4. Compute new intersection points of two adjascent edges
36 * 5. Move nodes to these points
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
56 // Check the selection if it is suitible for the orthogonalization
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 OptionPaneUtil.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 OptionPaneUtil.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.nodes.size() < 5) || (!way.nodes.get(0).equals(way.nodes.get(way.nodes.size() - 1)))) {
86 OptionPaneUtil.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.nodes.size()-1; i1++) {
99 int i2 = (i1+1) % (way.nodes.size()-1);
100 int i3 = (i1+2) % (way.nodes.size()-1);
101 double angle1 =Math.abs(way.nodes.get(i1).getEastNorth().heading(way.nodes.get(i2).getEastNorth()));
102 double angle2 = Math.abs(way.nodes.get(i2).getEastNorth().heading(way.nodes.get(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 OptionPaneUtil.showMessageDialog(
109 Main.parent,
110 tr("Please select ways with almost right angles to orthogonalize."),
111 tr("Information"),
112 JOptionPane.INFORMATION_MESSAGE
113 );
114 return;
115 }
116 }
117 }
118
119 if ("EPSG:4326".equals(Main.proj.toString())) {
120 String msg = tr("<html>You are using the EPSG:4326 projection which might lead<br>" +
121 "to undesirable results when doing rectangular alignments.<br>" +
122 "Change your projection to get rid of this warning.<br>" +
123 "Do you want to continue?</html>");
124 if (!ConditionalOptionPaneUtil.showConfirmationDialog(
125 "align_rectangular_4326",
126 Main.parent,
127 msg,
128 tr("Warning"),
129 JOptionPane.YES_NO_OPTION,
130 JOptionPane.QUESTION_MESSAGE,
131 JOptionPane.YES_OPTION))
132 return;
133 }
134 // Check, if selection held neither none nor two nodes
135 if(dirnodes.size() == 1) {
136 OptionPaneUtil.showMessageDialog(
137 Main.parent,
138 tr("Only one node selected"),
139 tr("Warning"),
140 JOptionPane.WARNING_MESSAGE
141 );
142 return;
143 }
144
145 // Now all checks are done and we can now do the neccessary computations
146 // From here it is assumed that the above checks hold
147 Collection<Command> cmds = new LinkedList<Command>();
148 double align_to_heading = 0.0;
149 boolean use_dirnodes = false;
150
151 if (dirnodes.size() == 2) {
152 // When selection contains two nodes, use the nodes to compute a direction
153 // to align all ways to
154 align_to_heading = normalize_angle(dirnodes.get(0).getEastNorth().heading(dirnodes.get(1).getEastNorth()));
155 use_dirnodes = true;
156 }
157
158 for (OsmPrimitive osm : sel) {
159 if(!(osm instanceof Way)) {
160 continue;
161 }
162
163 Way way = (Way)osm;
164 int nodes = way.nodes.size();
165 int sides = nodes - 1;
166 // Copy necessary data into a more suitable data structure
167 EastNorth en[] = new EastNorth[sides];
168 for (int i=0; i < sides; i++) {
169 en[i] = new EastNorth(way.nodes.get(i).getEastNorth().east(), way.nodes.get(i).getEastNorth().north());
170 }
171
172 if (! use_dirnodes) {
173 // To find orientation of all segments, compute weighted average of all segment's headings
174 // all headings are mapped into [-PI/4, PI/4] by PI/2 rotations so both main orientations are mapped into one
175 // the headings are weighted by the length of the segment establishing it, so a longer segment, that is more
176 // likely to have the correct orientation, has more influence in the computing than a short segment, that is easier to misalign.
177 double headings[] = new double[sides];
178 double weights[] = new double[sides];
179 for (int i=0; i < sides; i++) {
180 headings[i] = normalize_angle(way.nodes.get(i).getEastNorth().heading(way.nodes.get(i+1).getEastNorth()));
181 weights[i] = way.nodes.get(i).getEastNorth().distance(way.nodes.get(i+1).getEastNorth());
182 }
183
184 // CAVEAT: for orientations near -PI/4 or PI/4 the mapping into ONE orientation fails
185 // resulting in a heading-difference between adjacent sides of almost PI/2
186 // and a totally wrong average
187 // check for this (use PI/3 as arbitray limit) and rotate into ONE orientation
188 double angle_diff_max = 0.0;
189 for (int i=0; i < sides; i++) {
190 double diff = 0.0;
191 if (i == 0) {
192 diff = heading_diff(headings[i], headings[sides - 1]);
193 } else {
194 diff = heading_diff(headings[i], headings[i - 1]);
195 }
196 if (diff > angle_diff_max) {
197 angle_diff_max = diff;
198 }
199 }
200
201 if (angle_diff_max > Math.PI/3) {
202 // rearrange headings: everything < 0 gets PI/2-rotated
203 for (int i=0; i < sides; i++) {
204 if (headings[i] < 0) {
205 headings[i] += Math.PI/2;
206 }
207 }
208 }
209
210 // TODO:
211 // use angle_diff_max as an indicator that the way is already orthogonal
212 // e.g. if angle_diff_max is less then Math.toRadians(0.5)
213 // and do nothing in that case (?)
214
215 // Compute the weighted average of the headings of all segments
216 double sum_weighted_headings = 0.0;
217 double sum_weights = 0.0;
218 for (int i=0; i < sides; i++) {
219 sum_weighted_headings += headings[i] * weights[i];
220 sum_weights += weights[i];
221 }
222 align_to_heading = normalize_angle(sum_weighted_headings/sum_weights);
223 }
224
225
226 for (int i=0; i < sides; i++) {
227 // Compute handy indices of three nodes to be used in one loop iteration.
228 // We use segments (i1,i2) and (i2,i3), align them and compute the new
229 // position of the i2-node as the intersection of the realigned (i1,i2), (i2,i3) segments
230 // Not the most efficient algorithm, but we don't handle millions of nodes...
231 int i1 = i;
232 int i2 = (i+1)%sides;
233 int i3 = (i+2)%sides;
234 double heading1, heading2;
235 double delta1, delta2;
236 // Compute neccessary rotation of first segment to align it with main orientation
237 heading1 = normalize_angle(en[i1].heading(en[i2]), align_to_heading);
238 delta1 = align_to_heading - heading1;
239 // Compute neccessary rotation of second segment to align it with main orientation
240 heading2 = normalize_angle(en[i2].heading(en[i3]), align_to_heading);
241 delta2 = align_to_heading - heading2;
242 // To align a segment, rotate around its center
243 EastNorth pivot1 = new EastNorth((en[i1].east()+en[i2].east())/2, (en[i1].north()+en[i2].north())/2);
244 EastNorth A=en[i1].rotate(pivot1, delta1);
245 EastNorth B=en[i2].rotate(pivot1, delta1);
246 EastNorth pivot2 = new EastNorth((en[i2].east()+en[i3].east())/2, (en[i2].north()+en[i3].north())/2);
247 EastNorth C=en[i2].rotate(pivot2, delta2);
248 EastNorth D=en[i3].rotate(pivot2, delta2);
249
250 // compute intersection of segments
251 double u=det(B.east() - A.east(), B.north() - A.north(),
252 C.east() - D.east(), C.north() - D.north());
253
254 // Check for parallel segments and do nothing if they are
255 // In practice this will probably only happen when a way has
256 // been duplicated
257
258 if (u == 0) {
259 continue;
260 }
261
262 // q is a number between 0 and 1
263 // It is the point in the segment where the intersection occurs
264 // if the segment is scaled to length 1
265
266 double q = det(B.north() - C.north(), B.east() - C.east(),
267 D.north() - C.north(), D.east() - C.east()) / u;
268 EastNorth intersection = new EastNorth(
269 B.east() + q * (A.east() - B.east()),
270 B.north() + q * (A.north() - B.north()));
271
272 Node n = way.nodes.get(i2);
273
274 LatLon ill = Main.proj.eastNorth2latlon(intersection);
275 if (!ill.equalsEpsilon(n.getCoor())) {
276 double dx = intersection.east()-n.getEastNorth().east();
277 double dy = intersection.north()-n.getEastNorth().north();
278 cmds.add(new MoveCommand(n, dx, dy));
279 }
280 }
281 }
282
283 if (cmds.size() > 0) {
284 Main.main.undoRedo.add(new SequenceCommand(tr("Orthogonalize"), cmds));
285 Main.map.repaint();
286 }
287 }
288
289 static double det(double a, double b, double c, double d)
290 {
291 return a * d - b * c;
292 }
293
294 static double normalize_angle(double h) {
295 return normalize_angle(h, 0.0);
296 }
297 static double normalize_angle(double h, double align_to) {
298 double llimit = -Math.PI/4;
299 double ulimit = Math.PI/4;
300 while (h - align_to > ulimit) {
301 h -= Math.PI/2;
302 }
303 while (h - align_to < llimit) {
304 h += Math.PI/2;
305 }
306
307 return h;
308 }
309
310 static double heading_diff(double h1, double h2) {
311 double heading_delta = h1 > h2 ? h1 - h2 : h2 - h1;
312 return heading_delta;
313 }
314
315 @Override
316 protected void updateEnabledState() {
317 setEnabled(getCurrentDataSet() != null && ! getCurrentDataSet().getSelected().isEmpty());
318 }
319}
Note: See TracBrowser for help on using the repository browser.