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

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

removed dependencies to Main.ds, removed Main.ds
removed AddVisitor, NameVisitor, DeleteVisitor - unnecessary double dispatching for these simple cases
File size: 12.3 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.tools.DontShowAgainInfo;
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 */
36public final class OrthogonalizeAction extends JosmAction {
37
38 public OrthogonalizeAction() {
39 super(tr("Orthogonalize Shape"),
40 "ortho",
41 tr("Move nodes so all angles are 90 or 270 degree"),
42 Shortcut.registerShortcut("tools:orthogonalize", tr("Tool: {0}", tr("Orthogonalize Shape")),
43 KeyEvent.VK_Q,
44 Shortcut.GROUP_EDIT), true);
45 }
46
47 public void actionPerformed(ActionEvent e) {
48
49 Collection<OsmPrimitive> sel = getCurrentDataSet().getSelected();
50
51 ArrayList<Node> dirnodes = new ArrayList<Node>();
52
53 // Check the selection if it is suitible for the orthogonalization
54 for (OsmPrimitive osm : sel) {
55 // Check if not more than two nodes in the selection
56 if(osm instanceof Node) {
57 if(dirnodes.size() == 2) {
58 JOptionPane.showMessageDialog(Main.parent, tr("Only two nodes allowed"));
59 return;
60 }
61 dirnodes.add((Node) osm);
62 continue;
63 }
64 // Check if selection consists now only of ways
65 if (!(osm instanceof Way)) {
66 JOptionPane.showMessageDialog(Main.parent, tr("Selection must consist only of ways."));
67 return;
68 }
69
70 // Check if every way is made of at least four segments and closed
71 Way way = (Way)osm;
72 if ((way.nodes.size() < 5) || (!way.nodes.get(0).equals(way.nodes.get(way.nodes.size() - 1)))) {
73 JOptionPane.showMessageDialog(Main.parent, tr("Please select one or more closed ways of at least four nodes."));
74 return;
75 }
76
77 // Check if every edge in the way is a definite edge of at least 45 degrees of direction change
78 // Otherwise, two segments could be turned into same direction and intersection would fail.
79 // Or changes of shape would be too serious.
80 for (int i1=0; i1 < way.nodes.size()-1; i1++) {
81 int i2 = (i1+1) % (way.nodes.size()-1);
82 int i3 = (i1+2) % (way.nodes.size()-1);
83 double angle1 =Math.abs(way.nodes.get(i1).getEastNorth().heading(way.nodes.get(i2).getEastNorth()));
84 double angle2 = Math.abs(way.nodes.get(i2).getEastNorth().heading(way.nodes.get(i3).getEastNorth()));
85 double delta = Math.abs(angle2 - angle1);
86 while(delta > Math.PI) {
87 delta -= Math.PI;
88 }
89 if(delta < Math.PI/4) {
90 JOptionPane.showMessageDialog(Main.parent, tr("Please select ways with almost right angles to orthogonalize."));
91 return;
92 }
93 }
94 }
95
96 if ("EPSG:4326".equals(Main.proj.toString())) {
97 String msg = tr("<html>You are using the EPSG:4326 projection which might lead<br>" +
98 "to undesirable results when doing rectangular alignments.<br>" +
99 "Change your projection to get rid of this warning.<br>" +
100 "Do you want to continue?");
101
102 if (!DontShowAgainInfo.show("align_rectangular_4326", msg, false))
103 return;
104 }
105 // Check, if selection held neither none nor two nodes
106 if(dirnodes.size() == 1) {
107 JOptionPane.showMessageDialog(Main.parent, tr("Only one node selected"));
108 return;
109 }
110
111 // Now all checks are done and we can now do the neccessary computations
112 // From here it is assumed that the above checks hold
113 Collection<Command> cmds = new LinkedList<Command>();
114 double align_to_heading = 0.0;
115 boolean use_dirnodes = false;
116
117 if (dirnodes.size() == 2) {
118 // When selection contains two nodes, use the nodes to compute a direction
119 // to align all ways to
120 align_to_heading = normalize_angle(dirnodes.get(0).getEastNorth().heading(dirnodes.get(1).getEastNorth()));
121 use_dirnodes = true;
122 }
123
124 for (OsmPrimitive osm : sel) {
125 if(!(osm instanceof Way)) {
126 continue;
127 }
128
129 Way way = (Way)osm;
130 int nodes = way.nodes.size();
131 int sides = nodes - 1;
132 // Copy necessary data into a more suitable data structure
133 EastNorth en[] = new EastNorth[sides];
134 for (int i=0; i < sides; i++) {
135 en[i] = new EastNorth(way.nodes.get(i).getEastNorth().east(), way.nodes.get(i).getEastNorth().north());
136 }
137
138 if (! use_dirnodes) {
139 // To find orientation of all segments, compute weighted average of all segment's headings
140 // all headings are mapped into [-PI/4, PI/4] by PI/2 rotations so both main orientations are mapped into one
141 // the headings are weighted by the length of the segment establishing it, so a longer segment, that is more
142 // likely to have the correct orientation, has more influence in the computing than a short segment, that is easier to misalign.
143 double headings[] = new double[sides];
144 double weights[] = new double[sides];
145 for (int i=0; i < sides; i++) {
146 headings[i] = normalize_angle(way.nodes.get(i).getEastNorth().heading(way.nodes.get(i+1).getEastNorth()));
147 weights[i] = way.nodes.get(i).getEastNorth().distance(way.nodes.get(i+1).getEastNorth());
148 }
149
150 // CAVEAT: for orientations near -PI/4 or PI/4 the mapping into ONE orientation fails
151 // resulting in a heading-difference between adjacent sides of almost PI/2
152 // and a totally wrong average
153 // check for this (use PI/3 as arbitray limit) and rotate into ONE orientation
154 double angle_diff_max = 0.0;
155 for (int i=0; i < sides; i++) {
156 double diff = 0.0;
157 if (i == 0) {
158 diff = heading_diff(headings[i], headings[sides - 1]);
159 } else {
160 diff = heading_diff(headings[i], headings[i - 1]);
161 }
162 if (diff > angle_diff_max) {
163 angle_diff_max = diff;
164 }
165 }
166
167 if (angle_diff_max > Math.PI/3) {
168 // rearrange headings: everything < 0 gets PI/2-rotated
169 for (int i=0; i < sides; i++) {
170 if (headings[i] < 0) {
171 headings[i] += Math.PI/2;
172 }
173 }
174 }
175
176 // TODO:
177 // use angle_diff_max as an indicator that the way is already orthogonal
178 // e.g. if angle_diff_max is less then Math.toRadians(0.5)
179 // and do nothing in that case (?)
180
181 // Compute the weighted average of the headings of all segments
182 double sum_weighted_headings = 0.0;
183 double sum_weights = 0.0;
184 for (int i=0; i < sides; i++) {
185 sum_weighted_headings += headings[i] * weights[i];
186 sum_weights += weights[i];
187 }
188 align_to_heading = normalize_angle(sum_weighted_headings/sum_weights);
189 }
190
191
192 for (int i=0; i < sides; i++) {
193 // Compute handy indices of three nodes to be used in one loop iteration.
194 // We use segments (i1,i2) and (i2,i3), align them and compute the new
195 // position of the i2-node as the intersection of the realigned (i1,i2), (i2,i3) segments
196 // Not the most efficient algorithm, but we don't handle millions of nodes...
197 int i1 = i;
198 int i2 = (i+1)%sides;
199 int i3 = (i+2)%sides;
200 double heading1, heading2;
201 double delta1, delta2;
202 // Compute neccessary rotation of first segment to align it with main orientation
203 heading1 = normalize_angle(en[i1].heading(en[i2]), align_to_heading);
204 delta1 = align_to_heading - heading1;
205 // Compute neccessary rotation of second segment to align it with main orientation
206 heading2 = normalize_angle(en[i2].heading(en[i3]), align_to_heading);
207 delta2 = align_to_heading - heading2;
208 // To align a segment, rotate around its center
209 EastNorth pivot1 = new EastNorth((en[i1].east()+en[i2].east())/2, (en[i1].north()+en[i2].north())/2);
210 EastNorth A=en[i1].rotate(pivot1, delta1);
211 EastNorth B=en[i2].rotate(pivot1, delta1);
212 EastNorth pivot2 = new EastNorth((en[i2].east()+en[i3].east())/2, (en[i2].north()+en[i3].north())/2);
213 EastNorth C=en[i2].rotate(pivot2, delta2);
214 EastNorth D=en[i3].rotate(pivot2, delta2);
215
216 // compute intersection of segments
217 double u=det(B.east() - A.east(), B.north() - A.north(),
218 C.east() - D.east(), C.north() - D.north());
219
220 // Check for parallel segments and do nothing if they are
221 // In practice this will probably only happen when a way has
222 // been duplicated
223
224 if (u == 0) {
225 continue;
226 }
227
228 // q is a number between 0 and 1
229 // It is the point in the segment where the intersection occurs
230 // if the segment is scaled to length 1
231
232 double q = det(B.north() - C.north(), B.east() - C.east(),
233 D.north() - C.north(), D.east() - C.east()) / u;
234 EastNorth intersection = new EastNorth(
235 B.east() + q * (A.east() - B.east()),
236 B.north() + q * (A.north() - B.north()));
237
238 Node n = way.nodes.get(i2);
239
240 LatLon ill = Main.proj.eastNorth2latlon(intersection);
241 if (!ill.equalsEpsilon(n.getCoor())) {
242 double dx = intersection.east()-n.getEastNorth().east();
243 double dy = intersection.north()-n.getEastNorth().north();
244 cmds.add(new MoveCommand(n, dx, dy));
245 }
246 }
247 }
248
249 if (cmds.size() > 0) {
250 Main.main.undoRedo.add(new SequenceCommand(tr("Orthogonalize"), cmds));
251 Main.map.repaint();
252 }
253 }
254
255 static double det(double a, double b, double c, double d)
256 {
257 return a * d - b * c;
258 }
259
260 static double normalize_angle(double h) {
261 return normalize_angle(h, 0.0);
262 }
263 static double normalize_angle(double h, double align_to) {
264 double llimit = -Math.PI/4;
265 double ulimit = Math.PI/4;
266 while (h - align_to > ulimit) {
267 h -= Math.PI/2;
268 }
269 while (h - align_to < llimit) {
270 h += Math.PI/2;
271 }
272
273 return h;
274 }
275
276 static double heading_diff(double h1, double h2) {
277 double heading_delta = h1 > h2 ? h1 - h2 : h2 - h1;
278 return heading_delta;
279 }
280}
Note: See TracBrowser for help on using the repository browser.