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

Last change on this file since 4067 was 3939, checked in by stoecker, 13 years ago

hopefully fix #5427
  • Property svn:eol-style set to native
File size: 17.4 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.HashSet;
8import java.util.LinkedHashSet;
9import java.util.List;
10import java.util.Set;
11
12import org.openstreetmap.josm.Main;
13import org.openstreetmap.josm.command.AddCommand;
14import org.openstreetmap.josm.command.ChangeCommand;
15import org.openstreetmap.josm.command.Command;
16import org.openstreetmap.josm.data.coor.EastNorth;
17import org.openstreetmap.josm.data.osm.BBox;
18import org.openstreetmap.josm.data.osm.Node;
19import org.openstreetmap.josm.data.osm.NodePositionComparator;
20import org.openstreetmap.josm.data.osm.Way;
21
22/**
23 * Some tools for geometry related tasks.
24 *
25 * @author viesturs
26 */
27public class Geometry {
28 public enum PolygonIntersection {FIRST_INSIDE_SECOND, SECOND_INSIDE_FIRST, OUTSIDE, CROSSING}
29
30 /**
31 * Will find all intersection and add nodes there for list of given ways. Handles self-intersections too.
32 * And make commands to add the intersection points to ways.
33 * @param List<Way> - a list of ways to test
34 * @return ArrayList<Node> List of new nodes
35 * Prerequisite: no two nodes have the same coordinates.
36 */
37 public static Set<Node> addIntersections(List<Way> ways, boolean test, List<Command> cmds) {
38
39 //stupid java, cannot instantiate array of generic classes..
40 @SuppressWarnings("unchecked")
41 ArrayList<Node>[] newNodes = new ArrayList[ways.size()];
42 BBox[] wayBounds = new BBox[ways.size()];
43 boolean[] changedWays = new boolean[ways.size()];
44
45 Set<Node> intersectionNodes = new LinkedHashSet<Node>();
46
47 //copy node arrays for local usage.
48 for (int pos = 0; pos < ways.size(); pos ++) {
49 newNodes[pos] = new ArrayList<Node>(ways.get(pos).getNodes());
50 wayBounds[pos] = getNodesBounds(newNodes[pos]);
51 changedWays[pos] = false;
52 }
53
54 //iterate over all way pairs and introduce the intersections
55 Comparator<Node> coordsComparator = new NodePositionComparator();
56
57 WayLoop: for (int seg1Way = 0; seg1Way < ways.size(); seg1Way ++) {
58 for (int seg2Way = seg1Way; seg2Way < ways.size(); seg2Way ++) {
59
60 //do not waste time on bounds that do not intersect
61 if (!wayBounds[seg1Way].intersects(wayBounds[seg2Way])) {
62 continue;
63 }
64
65 ArrayList<Node> way1Nodes = newNodes[seg1Way];
66 ArrayList<Node> way2Nodes = newNodes[seg2Way];
67
68 //iterate over primary segmemt
69 for (int seg1Pos = 0; seg1Pos + 1 < way1Nodes.size(); seg1Pos ++) {
70
71 //iterate over secondary segment
72 int seg2Start = seg1Way != seg2Way ? 0: seg1Pos + 2;//skip the adjacent segment
73
74 for (int seg2Pos = seg2Start; seg2Pos + 1< way2Nodes.size(); seg2Pos ++) {
75
76 //need to get them again every time, because other segments may be changed
77 Node seg1Node1 = way1Nodes.get(seg1Pos);
78 Node seg1Node2 = way1Nodes.get(seg1Pos + 1);
79 Node seg2Node1 = way2Nodes.get(seg2Pos);
80 Node seg2Node2 = way2Nodes.get(seg2Pos + 1);
81
82 int commonCount = 0;
83 //test if we have common nodes to add.
84 if (seg1Node1 == seg2Node1 || seg1Node1 == seg2Node2) {
85 commonCount ++;
86
87 if (seg1Way == seg2Way &&
88 seg1Pos == 0 &&
89 seg2Pos == way2Nodes.size() -2) {
90 //do not add - this is first and last segment of the same way.
91 } else {
92 intersectionNodes.add(seg1Node1);
93 }
94 }
95
96 if (seg1Node2 == seg2Node1 || seg1Node2 == seg2Node2) {
97 commonCount ++;
98
99 intersectionNodes.add(seg1Node2);
100 }
101
102 //no common nodes - find intersection
103 if (commonCount == 0) {
104 EastNorth intersection = getSegmentSegmentIntersection(
105 seg1Node1.getEastNorth(), seg1Node2.getEastNorth(),
106 seg2Node1.getEastNorth(), seg2Node2.getEastNorth());
107
108 if (intersection != null) {
109 if (test) {
110 intersectionNodes.add(seg2Node1);
111 return intersectionNodes;
112 }
113
114 Node newNode = new Node(Main.proj.eastNorth2latlon(intersection));
115 Node intNode = newNode;
116 boolean insertInSeg1 = false;
117 boolean insertInSeg2 = false;
118
119 //find if the intersection point is at end point of one of the segments, if so use that point
120
121 //segment 1
122 if (coordsComparator.compare(newNode, seg1Node1) == 0) {
123 intNode = seg1Node1;
124 } else if (coordsComparator.compare(newNode, seg1Node2) == 0) {
125 intNode = seg1Node2;
126 } else {
127 insertInSeg1 = true;
128 }
129
130 //segment 2
131 if (coordsComparator.compare(newNode, seg2Node1) == 0) {
132 intNode = seg2Node1;
133 } else if (coordsComparator.compare(newNode, seg2Node2) == 0) {
134 intNode = seg2Node2;
135 } else {
136 insertInSeg2 = true;
137 }
138
139 if (insertInSeg1) {
140 way1Nodes.add(seg1Pos +1, intNode);
141 changedWays[seg1Way] = true;
142
143 //fix seg2 position, as indexes have changed, seg2Pos is always bigger than seg1Pos on the same segment.
144 if (seg2Way == seg1Way) {
145 seg2Pos ++;
146 }
147 }
148
149 if (insertInSeg2) {
150 way2Nodes.add(seg2Pos +1, intNode);
151 changedWays[seg2Way] = true;
152
153 //Do not need to compare again to already split segment
154 seg2Pos ++;
155 }
156
157 intersectionNodes.add(intNode);
158
159 if (intNode == newNode) {
160 cmds.add(new AddCommand(intNode));
161 }
162 }
163 }
164 else if (test && intersectionNodes.size() > 0)
165 return intersectionNodes;
166 }
167 }
168 }
169 }
170
171
172 for (int pos = 0; pos < ways.size(); pos ++) {
173 if (changedWays[pos] == false) {
174 continue;
175 }
176
177 Way way = ways.get(pos);
178 Way newWay = new Way(way);
179 newWay.setNodes(newNodes[pos]);
180
181 cmds.add(new ChangeCommand(way, newWay));
182 }
183
184 return intersectionNodes;
185 }
186
187 private static BBox getNodesBounds(ArrayList<Node> nodes) {
188
189 BBox bounds = new BBox(nodes.get(0));
190 for(Node n: nodes) {
191 bounds.add(n.getCoor());
192 }
193 return bounds;
194 }
195
196 /**
197 * Tests if given point is to the right side of path consisting of 3 points.
198 * @param lineP1 first point in path
199 * @param lineP2 second point in path
200 * @param lineP3 third point in path
201 * @param testPoint
202 * @return true if to the right side, false otherwise
203 */
204 public static boolean isToTheRightSideOfLine(Node lineP1, Node lineP2, Node lineP3, Node testPoint) {
205 boolean pathBendToRight = angleIsClockwise(lineP1, lineP2, lineP3);
206 boolean rightOfSeg1 = angleIsClockwise(lineP1, lineP2, testPoint);
207 boolean rightOfSeg2 = angleIsClockwise(lineP2, lineP3, testPoint);
208
209 if (pathBendToRight)
210 return rightOfSeg1 && rightOfSeg2;
211 else
212 return !(!rightOfSeg1 && !rightOfSeg2);
213 }
214
215 /**
216 * This method tests if secondNode is clockwise to first node.
217 * @param commonNode starting point for both vectors
218 * @param firstNode first vector end node
219 * @param secondNode second vector end node
220 * @return true if first vector is clockwise before second vector.
221 */
222 public static boolean angleIsClockwise(Node commonNode, Node firstNode, Node secondNode) {
223 double dy1 = (firstNode.getEastNorth().getY() - commonNode.getEastNorth().getY());
224 double dy2 = (secondNode.getEastNorth().getY() - commonNode.getEastNorth().getY());
225 double dx1 = (firstNode.getEastNorth().getX() - commonNode.getEastNorth().getX());
226 double dx2 = (secondNode.getEastNorth().getX() - commonNode.getEastNorth().getX());
227
228 return dy1 * dx2 - dx1 * dy2 > 0;
229 }
230
231 /**
232 * Finds the intersection of two line segments
233 * @return EastNorth null if no intersection was found, the EastNorth coordinates of the intersection otherwise
234 */
235 public static EastNorth getSegmentSegmentIntersection(
236 EastNorth p1, EastNorth p2,
237 EastNorth p3, EastNorth p4) {
238 double x1 = p1.getX();
239 double y1 = p1.getY();
240 double x2 = p2.getX();
241 double y2 = p2.getY();
242 double x3 = p3.getX();
243 double y3 = p3.getY();
244 double x4 = p4.getX();
245 double y4 = p4.getY();
246
247 //TODO: do this locally.
248 if (!Line2D.linesIntersect(x1, y1, x2, y2, x3, y3, x4, y4)) return null;
249
250 // Convert line from (point, point) form to ax+by=c
251 double a1 = y2 - y1;
252 double b1 = x1 - x2;
253 double c1 = x2*y1 - x1*y2;
254
255 double a2 = y4 - y3;
256 double b2 = x3 - x4;
257 double c2 = x4*y3 - x3*y4;
258
259 // Solve the equations
260 double det = a1*b2 - a2*b1;
261 if (det == 0) return null; // Lines are parallel
262
263 double x = (b1*c2 - b2*c1)/det;
264 double y = (a2*c1 -a1*c2)/det;
265
266 return new EastNorth(x, y);
267 }
268
269 /**
270 * Finds the intersection of two lines of infinite length.
271 * @return EastNorth null if no intersection was found, the coordinates of the intersection otherwise
272 */
273 public static EastNorth getLineLineIntersection(EastNorth p1, EastNorth p2, EastNorth p3, EastNorth p4) {
274
275 // Convert line from (point, point) form to ax+by=c
276 double a1 = p2.getY() - p1.getY();
277 double b1 = p1.getX() - p2.getX();
278 double c1 = p2.getX() * p1.getY() - p1.getX() * p2.getY();
279
280 double a2 = p4.getY() - p3.getY();
281 double b2 = p3.getX() - p4.getX();
282 double c2 = p4.getX() * p3.getY() - p3.getX() * p4.getY();
283
284 // Solve the equations
285 double det = a1 * b2 - a2 * b1;
286 if (det == 0)
287 return null; // Lines are parallel
288
289 return new EastNorth((b1 * c2 - b2 * c1) / det, (a2 * c1 - a1 * c2) / det);
290 }
291
292 public static boolean segmentsParallel(EastNorth p1, EastNorth p2, EastNorth p3, EastNorth p4) {
293 // Convert line from (point, point) form to ax+by=c
294 double a1 = p2.getY() - p1.getY();
295 double b1 = p1.getX() - p2.getX();
296
297 double a2 = p4.getY() - p3.getY();
298 double b2 = p3.getX() - p4.getX();
299
300 // Solve the equations
301 double det = a1 * b2 - a2 * b1;
302 // remove influence of of scaling factor
303 det /= Math.sqrt(a1*a1 + b1*b1) * Math.sqrt(a2*a2 + b2*b2);
304 return Math.abs(det) < 1e-3;
305 }
306
307 /**
308 * Calculates closest point to a line segment.
309 * @param segmentP1
310 * @param segmentP2
311 * @param point
312 * @return segmentP1 if it is the closest point, segmentP2 if it is the closest point,
313 * a new point if closest point is between segmentP1 and segmentP2.
314 */
315 public static EastNorth closestPointToSegment(EastNorth segmentP1, EastNorth segmentP2, EastNorth point) {
316
317 double ldx = segmentP2.getX() - segmentP1.getX();
318 double ldy = segmentP2.getY() - segmentP1.getY();
319
320 if (ldx == 0 && ldy == 0) //segment zero length
321 return segmentP1;
322
323 double pdx = point.getX() - segmentP1.getX();
324 double pdy = point.getY() - segmentP1.getY();
325
326 double offset = (pdx * ldx + pdy * ldy) / (ldx * ldx + ldy * ldy);
327
328 if (offset <= 0)
329 return segmentP1;
330 else if (offset >= 1)
331 return segmentP2;
332 else
333 return new EastNorth(segmentP1.getX() + ldx * offset, segmentP1.getY() + ldy * offset);
334 }
335
336 /**
337 * This method tests if secondNode is clockwise to first node.
338 * @param commonNode starting point for both vectors
339 * @param firstNode first vector end node
340 * @param secondNode second vector end node
341 * @return true if first vector is clockwise before second vector.
342 */
343 public static boolean angleIsClockwise(EastNorth commonNode, EastNorth firstNode, EastNorth secondNode) {
344 double dy1 = (firstNode.getY() - commonNode.getY());
345 double dy2 = (secondNode.getY() - commonNode.getY());
346 double dx1 = (firstNode.getX() - commonNode.getX());
347 double dx2 = (secondNode.getX() - commonNode.getX());
348
349 return dy1 * dx2 - dx1 * dy2 > 0;
350 }
351
352 /**
353 * Tests if two polygons intersect.
354 * @param first
355 * @param second
356 * @return intersection kind
357 * TODO: test segments, not only points
358 * TODO: is O(N*M), should use sweep for better performance.
359 */
360 public static PolygonIntersection polygonIntersection(List<Node> first, List<Node> second) {
361 Set<Node> firstSet = new HashSet<Node>(first);
362 Set<Node> secondSet = new HashSet<Node>(second);
363
364 int nodesInsideSecond = 0;
365 int nodesOutsideSecond = 0;
366 int nodesInsideFirst = 0;
367 int nodesOutsideFirst = 0;
368
369 for (Node insideNode : first) {
370 if (secondSet.contains(insideNode)) {
371 continue;
372 //ignore touching nodes.
373 }
374
375 if (nodeInsidePolygon(insideNode, second)) {
376 nodesInsideSecond ++;
377 }
378 else {
379 nodesOutsideSecond ++;
380 }
381 }
382
383 for (Node insideNode : second) {
384 if (firstSet.contains(insideNode)) {
385 continue;
386 //ignore touching nodes.
387 }
388
389 if (nodeInsidePolygon(insideNode, first)) {
390 nodesInsideFirst ++;
391 }
392 else {
393 nodesOutsideFirst ++;
394 }
395 }
396
397 if (nodesInsideFirst == 0) {
398 if (nodesInsideSecond == 0){
399 if (nodesOutsideFirst + nodesInsideSecond > 0)
400 return PolygonIntersection.OUTSIDE;
401 else
402 //all nodes common
403 return PolygonIntersection.CROSSING;
404 } else
405 return PolygonIntersection.FIRST_INSIDE_SECOND;
406 }
407 else
408 {
409 if (nodesInsideSecond == 0)
410 return PolygonIntersection.SECOND_INSIDE_FIRST;
411 else
412 return PolygonIntersection.CROSSING;
413 }
414 }
415
416 /**
417 * Tests if point is inside a polygon. The polygon can be self-intersecting. In such case the contains function works in xor-like manner.
418 * @param polygonNodes list of nodes from polygon path.
419 * @param point the point to test
420 * @return true if the point is inside polygon.
421 */
422 public static boolean nodeInsidePolygon(Node point, List<Node> polygonNodes) {
423 if (polygonNodes.size() < 2)
424 return false;
425
426 boolean inside = false;
427 Node p1, p2;
428
429 //iterate each side of the polygon, start with the last segment
430 Node oldPoint = polygonNodes.get(polygonNodes.size() - 1);
431
432 for (Node newPoint : polygonNodes) {
433 //skip duplicate points
434 if (newPoint.equals(oldPoint)) {
435 continue;
436 }
437
438 //order points so p1.lat <= p2.lat;
439 if (newPoint.getEastNorth().getY() > oldPoint.getEastNorth().getY()) {
440 p1 = oldPoint;
441 p2 = newPoint;
442 } else {
443 p1 = newPoint;
444 p2 = oldPoint;
445 }
446
447 //test if the line is crossed and if so invert the inside flag.
448 if ((newPoint.getEastNorth().getY() < point.getEastNorth().getY()) == (point.getEastNorth().getY() <= oldPoint.getEastNorth().getY())
449 && (point.getEastNorth().getX() - p1.getEastNorth().getX()) * (p2.getEastNorth().getY() - p1.getEastNorth().getY())
450 < (p2.getEastNorth().getX() - p1.getEastNorth().getX()) * (point.getEastNorth().getY() - p1.getEastNorth().getY()))
451 {
452 inside = !inside;
453 }
454
455 oldPoint = newPoint;
456 }
457
458 return inside;
459 }
460}
Note: See TracBrowser for help on using the repository browser.