source: josm/trunk/src/org/openstreetmap/josm/tools/Geometry.java@ 3636

Last change on this file since 3636 was 3636, checked in by bastiK, 14 years ago

see #5577 (patch by extropy) - Move some methods and make them public static
  • Property svn:eol-style set to native
File size: 11.5 KB
Line 
1// License: GPL. For details, see LICENSE file.
2package org.openstreetmap.josm.tools;
3
4import java.awt.geom.Line2D;
5import java.util.ArrayList;
6import java.util.Comparator;
7import java.util.LinkedHashSet;
8import java.util.List;
9import java.util.Set;
10import org.openstreetmap.josm.Main;
11import org.openstreetmap.josm.command.AddCommand;
12import org.openstreetmap.josm.command.ChangeCommand;
13import org.openstreetmap.josm.command.Command;
14import org.openstreetmap.josm.data.coor.EastNorth;
15import org.openstreetmap.josm.data.coor.LatLon;
16import org.openstreetmap.josm.data.osm.Node;
17import org.openstreetmap.josm.data.osm.NodePositionComparator;
18import org.openstreetmap.josm.data.osm.Way;
19
20/**
21 * Some tools for geometry related tasks.
22 *
23 * @author viesturs
24 */
25public class Geometry {
26 /**
27 * Will find all intersection and add nodes there for list of given ways. Handles self-intersections too.
28 * And make commands to add the intersection points to ways.
29 * @param List<Way> - a list of ways to test
30 * @return ArrayList<Node> List of new nodes
31 * Prerequisite: no two nodes have the same coordinates.
32 */
33 public static ArrayList<Node> addIntersections(List<Way> ways, boolean test, List<Command> cmds) {
34 //TODO: this is a bit slow - O( (number of nodes)^2 + numberOfIntersections * numberOfNodes )
35
36 //stupid java, cannot instantiate array of generic classes..
37 @SuppressWarnings("unchecked")
38 ArrayList<Node>[] newNodes = new ArrayList[ways.size()];
39 boolean[] changedWays = new boolean[ways.size()];
40
41 Set<Node> intersectionNodes = new LinkedHashSet<Node>();
42
43 for (int pos = 0; pos < ways.size(); pos ++) {
44 newNodes[pos] = new ArrayList<Node>(ways.get(pos).getNodes());
45 changedWays[pos] = false;
46 }
47
48 //iterate over all segment pairs and introduce the intersections
49
50 Comparator<Node> coordsComparator = new NodePositionComparator();
51
52 int seg1Way = 0;
53 int seg1Pos = -1;
54
55 while (true) {
56 //advance to next segment
57 seg1Pos++;
58 if (seg1Pos > newNodes[seg1Way].size() - 2) {
59 seg1Way++;
60 seg1Pos = 0;
61
62 if (seg1Way == ways.size()) { //finished
63 break;
64 }
65 }
66
67
68 //iterate over secondary segment
69
70 int seg2Way = seg1Way;
71 int seg2Pos = seg1Pos + 1;//skip the adjacent segment
72
73 while (true) {
74
75 //advance to next segment
76 seg2Pos++;
77 if (seg2Pos > newNodes[seg2Way].size() - 2) {
78 seg2Way++;
79 seg2Pos = 0;
80
81 if (seg2Way == ways.size()) { //finished
82 break;
83 }
84 }
85
86 //need to get them again every time, because other segments may be changed
87 Node seg1Node1 = newNodes[seg1Way].get(seg1Pos);
88 Node seg1Node2 = newNodes[seg1Way].get(seg1Pos + 1);
89 Node seg2Node1 = newNodes[seg2Way].get(seg2Pos);
90 Node seg2Node2 = newNodes[seg2Way].get(seg2Pos + 1);
91
92 int commonCount = 0;
93 //test if we have common nodes to add.
94 if (seg1Node1 == seg2Node1 || seg1Node1 == seg2Node2) {
95 commonCount ++;
96
97 if (seg1Way == seg2Way &&
98 seg1Pos == 0 &&
99 seg2Pos == newNodes[seg2Way].size() -2) {
100 //do not add - this is first and last segment of the same way.
101 } else {
102 intersectionNodes.add(seg1Node1);
103 }
104 }
105
106 if (seg1Node2 == seg2Node1 || seg1Node2 == seg2Node2) {
107 commonCount ++;
108
109 intersectionNodes.add(seg1Node2);
110 }
111
112 //no common nodes - find intersection
113 if (commonCount == 0) {
114 LatLon intersection = getLineLineIntersection(
115 seg1Node1.getEastNorth().east(), seg1Node1.getEastNorth().north(),
116 seg1Node2.getEastNorth().east(), seg1Node2.getEastNorth().north(),
117 seg2Node1.getEastNorth().east(), seg2Node1.getEastNorth().north(),
118 seg2Node2.getEastNorth().east(), seg2Node2.getEastNorth().north());
119
120 if (intersection != null) {
121 if (test) {
122 intersectionNodes.add(seg2Node1);
123 return new ArrayList<Node>(intersectionNodes);
124 }
125
126 Node newNode = new Node(intersection);
127 Node intNode = newNode;
128 boolean insertInSeg1 = false;
129 boolean insertInSeg2 = false;
130
131 //find if the intersection point is at end point of one of the segments, if so use that point
132
133 //segment 1
134 if (coordsComparator.compare(newNode, seg1Node1) == 0) {
135 intNode = seg1Node1;
136 } else if (coordsComparator.compare(newNode, seg1Node2) == 0) {
137 intNode = seg1Node2;
138 } else {
139 insertInSeg1 = true;
140 }
141
142 //segment 2
143 if (coordsComparator.compare(newNode, seg2Node1) == 0) {
144 intNode = seg2Node1;
145 } else if (coordsComparator.compare(newNode, seg2Node2) == 0) {
146 intNode = seg2Node2;
147 } else {
148 insertInSeg2 = true;
149 }
150
151 if (insertInSeg1) {
152 newNodes[seg1Way].add(seg1Pos +1, intNode);
153 changedWays[seg1Way] = true;
154
155 //fix seg2 position, as indexes have changed, seg2Pos is always bigger than seg1Pos on the same segment.
156 if (seg2Way == seg1Way) {
157 seg2Pos ++;
158 }
159 }
160
161 if (insertInSeg2) {
162 newNodes[seg2Way].add(seg2Pos +1, intNode);
163 changedWays[seg2Way] = true;
164
165 //Do not need to compare again to already split segment
166 seg2Pos ++;
167 }
168
169 intersectionNodes.add(intNode);
170
171 if (intNode == newNode) {
172 cmds.add(new AddCommand(intNode));
173 }
174 }
175 }
176 else if (test && intersectionNodes.size() > 0)
177 return new ArrayList<Node>(intersectionNodes);
178 }
179 }
180
181 for (int pos = 0; pos < ways.size(); pos ++) {
182 if (changedWays[pos] == false) {
183 continue;
184 }
185
186 Way way = ways.get(pos);
187 Way newWay = new Way(way);
188 newWay.setNodes(newNodes[pos]);
189
190 cmds.add(new ChangeCommand(way, newWay));
191 }
192
193 return new ArrayList<Node>(intersectionNodes);
194 }
195
196 /**
197 * Finds the intersection of two lines
198 * @return LatLon null if no intersection was found, the LatLon coordinates of the intersection otherwise
199 */
200 static private LatLon getLineLineIntersection(
201 double x1, double y1, double x2, double y2,
202 double x3, double y3, double x4, double y4) {
203
204 if (!Line2D.linesIntersect(x1, y1, x2, y2, x3, y3, x4, y4)) return null;
205
206 // Convert line from (point, point) form to ax+by=c
207 double a1 = y2 - y1;
208 double b1 = x1 - x2;
209 double c1 = x2*y1 - x1*y2;
210
211 double a2 = y4 - y3;
212 double b2 = x3 - x4;
213 double c2 = x4*y3 - x3*y4;
214
215 // Solve the equations
216 double det = a1*b2 - a2*b1;
217 if (det == 0) return null; // Lines are parallel
218
219 return Main.proj.eastNorth2latlon(new EastNorth(
220 (b1*c2 - b2*c1)/det,
221 (a2*c1 -a1*c2)/det
222 ));
223 }
224
225 /**
226 * Tests if given point is to the right side of path consisting of 3 points.
227 * @param lineP1 first point in path
228 * @param lineP2 second point in path
229 * @param lineP3 third point in path
230 * @param testPoint
231 * @return true if to the right side, false otherwise
232 */
233 public static boolean isToTheRightSideOfLine(Node lineP1, Node lineP2, Node lineP3, Node testPoint) {
234 boolean pathBendToRight = angleIsClockwise(lineP1, lineP2, lineP3);
235 boolean rightOfSeg1 = angleIsClockwise(lineP1, lineP2, testPoint);
236 boolean rightOfSeg2 = angleIsClockwise(lineP2, lineP3, testPoint);
237
238 if (pathBendToRight)
239 return rightOfSeg1 && rightOfSeg2;
240 else
241 return !(!rightOfSeg1 && !rightOfSeg2);
242 }
243
244 /**
245 * This method tests if secondNode is clockwise to first node.
246 * @param commonNode starting point for both vectors
247 * @param firstNode first vector end node
248 * @param secondNode second vector end node
249 * @return true if first vector is clockwise before second vector.
250 */
251 public static boolean angleIsClockwise(Node commonNode, Node firstNode, Node secondNode) {
252 double dy1 = (firstNode.getEastNorth().getY() - commonNode.getEastNorth().getY());
253 double dy2 = (secondNode.getEastNorth().getY() - commonNode.getEastNorth().getY());
254 double dx1 = (firstNode.getEastNorth().getX() - commonNode.getEastNorth().getX());
255 double dx2 = (secondNode.getEastNorth().getX() - commonNode.getEastNorth().getX());
256
257 return dy1 * dx2 - dx1 * dy2 > 0;
258 }
259
260 /**
261 * Tests if point is inside a polygon. The polygon can be self-intersecting. In such case the contains function works in xor-like manner.
262 * @param polygonNodes list of nodes from polygon path.
263 * @param point the point to test
264 * @return true if the point is inside polygon.
265 */
266 public static boolean nodeInsidePolygon(Node point, List<Node> polygonNodes) {
267 if (polygonNodes.size() < 3)
268 return false;
269
270 boolean inside = false;
271 Node p1, p2;
272
273 //iterate each side of the polygon, start with the last segment
274 Node oldPoint = polygonNodes.get(polygonNodes.size() - 1);
275
276 for (Node newPoint : polygonNodes) {
277 //skip duplicate points
278 if (newPoint.equals(oldPoint)) {
279 continue;
280 }
281
282 //order points so p1.lat <= p2.lat;
283 if (newPoint.getEastNorth().getY() > oldPoint.getEastNorth().getY()) {
284 p1 = oldPoint;
285 p2 = newPoint;
286 } else {
287 p1 = newPoint;
288 p2 = oldPoint;
289 }
290
291 //test if the line is crossed and if so invert the inside flag.
292 if ((newPoint.getEastNorth().getY() < point.getEastNorth().getY()) == (point.getEastNorth().getY() <= oldPoint.getEastNorth().getY())
293 && (point.getEastNorth().getX() - p1.getEastNorth().getX()) * (p2.getEastNorth().getY() - p1.getEastNorth().getY())
294 < (p2.getEastNorth().getX() - p1.getEastNorth().getX()) * (point.getEastNorth().getY() - p1.getEastNorth().getY()))
295 {
296 inside = !inside;
297 }
298
299 oldPoint = newPoint;
300 }
301
302 return inside;
303 }
304}
Note: See TracBrowser for help on using the repository browser.