001 // License: GPL. For details, see LICENSE file.
002 package org.openstreetmap.josm.tools;
003
004 import java.awt.Rectangle;
005 import java.awt.geom.Area;
006 import java.awt.geom.Line2D;
007 import java.awt.geom.Path2D;
008 import java.math.BigDecimal;
009 import java.math.MathContext;
010 import java.util.ArrayList;
011 import java.util.Comparator;
012 import java.util.LinkedHashSet;
013 import java.util.List;
014 import java.util.Set;
015
016 import org.openstreetmap.josm.Main;
017 import org.openstreetmap.josm.command.AddCommand;
018 import org.openstreetmap.josm.command.ChangeCommand;
019 import org.openstreetmap.josm.command.Command;
020 import org.openstreetmap.josm.data.coor.EastNorth;
021 import org.openstreetmap.josm.data.coor.LatLon;
022 import org.openstreetmap.josm.data.osm.BBox;
023 import org.openstreetmap.josm.data.osm.Node;
024 import org.openstreetmap.josm.data.osm.NodePositionComparator;
025 import org.openstreetmap.josm.data.osm.Way;
026
027 /**
028 * Some tools for geometry related tasks.
029 *
030 * @author viesturs
031 */
032 public class Geometry {
033 public enum PolygonIntersection {FIRST_INSIDE_SECOND, SECOND_INSIDE_FIRST, OUTSIDE, CROSSING}
034
035 /**
036 * Will find all intersection and add nodes there for list of given ways.
037 * Handles self-intersections too.
038 * And makes commands to add the intersection points to ways.
039 *
040 * Prerequisite: no two nodes have the same coordinates.
041 *
042 * @param ways a list of ways to test
043 * @param test if false, do not build list of Commands, just return nodes
044 * @param cmds list of commands, typically empty when handed to this method.
045 * Will be filled with commands that add intersection nodes to
046 * the ways.
047 * @return list of new nodes
048 */
049 public static Set<Node> addIntersections(List<Way> ways, boolean test, List<Command> cmds) {
050
051 //stupid java, cannot instantiate array of generic classes..
052 @SuppressWarnings("unchecked")
053 ArrayList<Node>[] newNodes = new ArrayList[ways.size()];
054 BBox[] wayBounds = new BBox[ways.size()];
055 boolean[] changedWays = new boolean[ways.size()];
056
057 Set<Node> intersectionNodes = new LinkedHashSet<Node>();
058
059 //copy node arrays for local usage.
060 for (int pos = 0; pos < ways.size(); pos ++) {
061 newNodes[pos] = new ArrayList<Node>(ways.get(pos).getNodes());
062 wayBounds[pos] = getNodesBounds(newNodes[pos]);
063 changedWays[pos] = false;
064 }
065
066 //iterate over all way pairs and introduce the intersections
067 Comparator<Node> coordsComparator = new NodePositionComparator();
068
069 WayLoop: for (int seg1Way = 0; seg1Way < ways.size(); seg1Way ++) {
070 for (int seg2Way = seg1Way; seg2Way < ways.size(); seg2Way ++) {
071
072 //do not waste time on bounds that do not intersect
073 if (!wayBounds[seg1Way].intersects(wayBounds[seg2Way])) {
074 continue;
075 }
076
077 ArrayList<Node> way1Nodes = newNodes[seg1Way];
078 ArrayList<Node> way2Nodes = newNodes[seg2Way];
079
080 //iterate over primary segmemt
081 for (int seg1Pos = 0; seg1Pos + 1 < way1Nodes.size(); seg1Pos ++) {
082
083 //iterate over secondary segment
084 int seg2Start = seg1Way != seg2Way ? 0: seg1Pos + 2;//skip the adjacent segment
085
086 for (int seg2Pos = seg2Start; seg2Pos + 1< way2Nodes.size(); seg2Pos ++) {
087
088 //need to get them again every time, because other segments may be changed
089 Node seg1Node1 = way1Nodes.get(seg1Pos);
090 Node seg1Node2 = way1Nodes.get(seg1Pos + 1);
091 Node seg2Node1 = way2Nodes.get(seg2Pos);
092 Node seg2Node2 = way2Nodes.get(seg2Pos + 1);
093
094 int commonCount = 0;
095 //test if we have common nodes to add.
096 if (seg1Node1 == seg2Node1 || seg1Node1 == seg2Node2) {
097 commonCount ++;
098
099 if (seg1Way == seg2Way &&
100 seg1Pos == 0 &&
101 seg2Pos == way2Nodes.size() -2) {
102 //do not add - this is first and last segment of the same way.
103 } else {
104 intersectionNodes.add(seg1Node1);
105 }
106 }
107
108 if (seg1Node2 == seg2Node1 || seg1Node2 == seg2Node2) {
109 commonCount ++;
110
111 intersectionNodes.add(seg1Node2);
112 }
113
114 //no common nodes - find intersection
115 if (commonCount == 0) {
116 EastNorth intersection = getSegmentSegmentIntersection(
117 seg1Node1.getEastNorth(), seg1Node2.getEastNorth(),
118 seg2Node1.getEastNorth(), seg2Node2.getEastNorth());
119
120 if (intersection != null) {
121 if (test) {
122 intersectionNodes.add(seg2Node1);
123 return intersectionNodes;
124 }
125
126 Node newNode = new Node(Main.getProjection().eastNorth2latlon(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 way1Nodes.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 way2Nodes.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 intersectionNodes;
178 }
179 }
180 }
181 }
182
183
184 for (int pos = 0; pos < ways.size(); pos ++) {
185 if (changedWays[pos] == false) {
186 continue;
187 }
188
189 Way way = ways.get(pos);
190 Way newWay = new Way(way);
191 newWay.setNodes(newNodes[pos]);
192
193 cmds.add(new ChangeCommand(way, newWay));
194 }
195
196 return intersectionNodes;
197 }
198
199 private static BBox getNodesBounds(ArrayList<Node> nodes) {
200
201 BBox bounds = new BBox(nodes.get(0));
202 for(Node n: nodes) {
203 bounds.add(n.getCoor());
204 }
205 return bounds;
206 }
207
208 /**
209 * Tests if given point is to the right side of path consisting of 3 points.
210 * @param lineP1 first point in path
211 * @param lineP2 second point in path
212 * @param lineP3 third point in path
213 * @param testPoint
214 * @return true if to the right side, false otherwise
215 */
216 public static boolean isToTheRightSideOfLine(Node lineP1, Node lineP2, Node lineP3, Node testPoint) {
217 boolean pathBendToRight = angleIsClockwise(lineP1, lineP2, lineP3);
218 boolean rightOfSeg1 = angleIsClockwise(lineP1, lineP2, testPoint);
219 boolean rightOfSeg2 = angleIsClockwise(lineP2, lineP3, testPoint);
220
221 if (pathBendToRight)
222 return rightOfSeg1 && rightOfSeg2;
223 else
224 return !(!rightOfSeg1 && !rightOfSeg2);
225 }
226
227 /**
228 * This method tests if secondNode is clockwise to first node.
229 * @param commonNode starting point for both vectors
230 * @param firstNode first vector end node
231 * @param secondNode second vector end node
232 * @return true if first vector is clockwise before second vector.
233 */
234 public static boolean angleIsClockwise(Node commonNode, Node firstNode, Node secondNode) {
235 return angleIsClockwise(commonNode.getEastNorth(), firstNode.getEastNorth(), secondNode.getEastNorth());
236 }
237
238 /**
239 * Finds the intersection of two line segments
240 * @return EastNorth null if no intersection was found, the EastNorth coordinates of the intersection otherwise
241 */
242 public static EastNorth getSegmentSegmentIntersection(
243 EastNorth p1, EastNorth p2,
244 EastNorth p3, EastNorth p4) {
245 double x1 = p1.getX();
246 double y1 = p1.getY();
247 double x2 = p2.getX();
248 double y2 = p2.getY();
249 double x3 = p3.getX();
250 double y3 = p3.getY();
251 double x4 = p4.getX();
252 double y4 = p4.getY();
253
254 //TODO: do this locally.
255 if (!Line2D.linesIntersect(x1, y1, x2, y2, x3, y3, x4, y4)) return null;
256
257 // Convert line from (point, point) form to ax+by=c
258 double a1 = y2 - y1;
259 double b1 = x1 - x2;
260 double c1 = x2*y1 - x1*y2;
261
262 double a2 = y4 - y3;
263 double b2 = x3 - x4;
264 double c2 = x4*y3 - x3*y4;
265
266 // Solve the equations
267 double det = a1*b2 - a2*b1;
268 if (det == 0) return null; // Lines are parallel
269
270 double x = (b1*c2 - b2*c1)/det;
271 double y = (a2*c1 -a1*c2)/det;
272
273 return new EastNorth(x, y);
274 }
275
276 /**
277 * Finds the intersection of two lines of infinite length.
278 * @return EastNorth null if no intersection was found, the coordinates of the intersection otherwise
279 */
280 public static EastNorth getLineLineIntersection(EastNorth p1, EastNorth p2, EastNorth p3, EastNorth p4) {
281
282 // Convert line from (point, point) form to ax+by=c
283 double a1 = p2.getY() - p1.getY();
284 double b1 = p1.getX() - p2.getX();
285 double c1 = p2.getX() * p1.getY() - p1.getX() * p2.getY();
286
287 double a2 = p4.getY() - p3.getY();
288 double b2 = p3.getX() - p4.getX();
289 double c2 = p4.getX() * p3.getY() - p3.getX() * p4.getY();
290
291 // Solve the equations
292 double det = a1 * b2 - a2 * b1;
293 if (det == 0)
294 return null; // Lines are parallel
295
296 return new EastNorth((b1 * c2 - b2 * c1) / det, (a2 * c1 - a1 * c2) / det);
297 }
298
299 public static boolean segmentsParallel(EastNorth p1, EastNorth p2, EastNorth p3, EastNorth p4) {
300 // Convert line from (point, point) form to ax+by=c
301 double a1 = p2.getY() - p1.getY();
302 double b1 = p1.getX() - p2.getX();
303
304 double a2 = p4.getY() - p3.getY();
305 double b2 = p3.getX() - p4.getX();
306
307 // Solve the equations
308 double det = a1 * b2 - a2 * b1;
309 // remove influence of of scaling factor
310 det /= Math.sqrt(a1*a1 + b1*b1) * Math.sqrt(a2*a2 + b2*b2);
311 return Math.abs(det) < 1e-3;
312 }
313
314 /**
315 * Calculates closest point to a line segment.
316 * @param segmentP1
317 * @param segmentP2
318 * @param point
319 * @return segmentP1 if it is the closest point, segmentP2 if it is the closest point,
320 * a new point if closest point is between segmentP1 and segmentP2.
321 */
322 public static EastNorth closestPointToSegment(EastNorth segmentP1, EastNorth segmentP2, EastNorth point) {
323
324 double ldx = segmentP2.getX() - segmentP1.getX();
325 double ldy = segmentP2.getY() - segmentP1.getY();
326
327 if (ldx == 0 && ldy == 0) //segment zero length
328 return segmentP1;
329
330 double pdx = point.getX() - segmentP1.getX();
331 double pdy = point.getY() - segmentP1.getY();
332
333 double offset = (pdx * ldx + pdy * ldy) / (ldx * ldx + ldy * ldy);
334
335 if (offset <= 0)
336 return segmentP1;
337 else if (offset >= 1)
338 return segmentP2;
339 else
340 return new EastNorth(segmentP1.getX() + ldx * offset, segmentP1.getY() + ldy * offset);
341 }
342
343 public static EastNorth closestPointToLine(EastNorth lineP1, EastNorth lineP2, EastNorth point) {
344 double ldx = lineP2.getX() - lineP1.getX();
345 double ldy = lineP2.getY() - lineP1.getY();
346
347 if (ldx == 0 && ldy == 0) //segment zero length
348 return lineP1;
349
350 double pdx = point.getX() - lineP1.getX();
351 double pdy = point.getY() - lineP1.getY();
352
353 double offset = (pdx * ldx + pdy * ldy) / (ldx * ldx + ldy * ldy);
354 return new EastNorth(lineP1.getX() + ldx * offset, lineP1.getY() + ldy * offset);
355 }
356
357 /**
358 * This method tests if secondNode is clockwise to first node.
359 * @param commonNode starting point for both vectors
360 * @param firstNode first vector end node
361 * @param secondNode second vector end node
362 * @return true if first vector is clockwise before second vector.
363 */
364 public static boolean angleIsClockwise(EastNorth commonNode, EastNorth firstNode, EastNorth secondNode) {
365 double dy1 = (firstNode.getY() - commonNode.getY());
366 double dy2 = (secondNode.getY() - commonNode.getY());
367 double dx1 = (firstNode.getX() - commonNode.getX());
368 double dx2 = (secondNode.getX() - commonNode.getX());
369
370 return dy1 * dx2 - dx1 * dy2 > 0;
371 }
372
373 private static Area getArea(List<Node> polygon) {
374 Path2D path = new Path2D.Double();
375
376 boolean begin = true;
377 for (Node n : polygon) {
378 if (begin) {
379 path.moveTo(n.getEastNorth().getX(), n.getEastNorth().getY());
380 begin = false;
381 } else {
382 path.lineTo(n.getEastNorth().getX(), n.getEastNorth().getY());
383 }
384 }
385 if (!begin) {
386 path.closePath();
387 }
388
389 return new Area(path);
390 }
391
392 /**
393 * Tests if two polygons intersect.
394 * @param first
395 * @param second
396 * @return intersection kind
397 */
398 public static PolygonIntersection polygonIntersection(List<Node> first, List<Node> second) {
399
400 Area a1 = getArea(first);
401 Area a2 = getArea(second);
402
403 Area inter = new Area(a1);
404 inter.intersect(a2);
405
406 Rectangle bounds = inter.getBounds();
407
408 if (inter.isEmpty() || bounds.getHeight()*bounds.getWidth() <= 1.0) {
409 return PolygonIntersection.OUTSIDE;
410 } else if (inter.equals(a1)) {
411 return PolygonIntersection.FIRST_INSIDE_SECOND;
412 } else if (inter.equals(a2)) {
413 return PolygonIntersection.SECOND_INSIDE_FIRST;
414 } else {
415 return PolygonIntersection.CROSSING;
416 }
417 }
418
419 /**
420 * Tests if point is inside a polygon. The polygon can be self-intersecting. In such case the contains function works in xor-like manner.
421 * @param polygonNodes list of nodes from polygon path.
422 * @param point the point to test
423 * @return true if the point is inside polygon.
424 */
425 public static boolean nodeInsidePolygon(Node point, List<Node> polygonNodes) {
426 if (polygonNodes.size() < 2)
427 return false;
428
429 boolean inside = false;
430 Node p1, p2;
431
432 //iterate each side of the polygon, start with the last segment
433 Node oldPoint = polygonNodes.get(polygonNodes.size() - 1);
434
435 for (Node newPoint : polygonNodes) {
436 //skip duplicate points
437 if (newPoint.equals(oldPoint)) {
438 continue;
439 }
440
441 //order points so p1.lat <= p2.lat;
442 if (newPoint.getEastNorth().getY() > oldPoint.getEastNorth().getY()) {
443 p1 = oldPoint;
444 p2 = newPoint;
445 } else {
446 p1 = newPoint;
447 p2 = oldPoint;
448 }
449
450 //test if the line is crossed and if so invert the inside flag.
451 if ((newPoint.getEastNorth().getY() < point.getEastNorth().getY()) == (point.getEastNorth().getY() <= oldPoint.getEastNorth().getY())
452 && (point.getEastNorth().getX() - p1.getEastNorth().getX()) * (p2.getEastNorth().getY() - p1.getEastNorth().getY())
453 < (p2.getEastNorth().getX() - p1.getEastNorth().getX()) * (point.getEastNorth().getY() - p1.getEastNorth().getY()))
454 {
455 inside = !inside;
456 }
457
458 oldPoint = newPoint;
459 }
460
461 return inside;
462 }
463
464 /**
465 * Returns area of a closed way in square meters.
466 * (approximate(?), but should be OK for small areas)
467 *
468 * Relies on the current projection: Works correctly, when
469 * one unit in projected coordinates corresponds to one meter.
470 * This is true for most projections, but not for WGS84 and
471 * Mercator (EPSG:3857).
472 *
473 * @param way Way to measure, should be closed (first node is the same as last node)
474 * @return area of the closed way.
475 */
476 public static double closedWayArea(Way way) {
477
478 //http://local.wasp.uwa.edu.au/~pbourke/geometry/polyarea/
479 double area = 0;
480 Node lastN = null;
481 for (Node n : way.getNodes()) {
482 if (lastN != null) {
483 n.getEastNorth().getX();
484
485 area += (calcX(n) * calcY(lastN)) - (calcY(n) * calcX(lastN));
486 }
487 lastN = n;
488 }
489 return Math.abs(area/2);
490 }
491
492 protected static double calcX(Node p1){
493 double lat1, lon1, lat2, lon2;
494 double dlon, dlat;
495
496 lat1 = p1.getCoor().lat() * Math.PI / 180.0;
497 lon1 = p1.getCoor().lon() * Math.PI / 180.0;
498 lat2 = lat1;
499 lon2 = 0;
500
501 dlon = lon2 - lon1;
502 dlat = lat2 - lat1;
503
504 double a = (Math.pow(Math.sin(dlat/2), 2) + Math.cos(lat1) * Math.cos(lat2) * Math.pow(Math.sin(dlon/2), 2));
505 double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a));
506 return 6367000 * c;
507 }
508
509 protected static double calcY(Node p1){
510 double lat1, lon1, lat2, lon2;
511 double dlon, dlat;
512
513 lat1 = p1.getCoor().lat() * Math.PI / 180.0;
514 lon1 = p1.getCoor().lon() * Math.PI / 180.0;
515 lat2 = 0;
516 lon2 = lon1;
517
518 dlon = lon2 - lon1;
519 dlat = lat2 - lat1;
520
521 double a = (Math.pow(Math.sin(dlat/2), 2) + Math.cos(lat1) * Math.cos(lat2) * Math.pow(Math.sin(dlon/2), 2));
522 double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a));
523 return 6367000 * c;
524 }
525
526 /**
527 * Determines whether a way is oriented clockwise.
528 *
529 * Internals: Assuming a closed non-looping way, compute twice the area
530 * of the polygon using the formula {@code 2 * area = sum (X[n] * Y[n+1] - X[n+1] * Y[n])}.
531 * If the area is negative the way is ordered in a clockwise direction.
532 *
533 * See http://paulbourke.net/geometry/polyarea/
534 *
535 * @param w the way to be checked.
536 * @return true if and only if way is oriented clockwise.
537 * @throws IllegalArgumentException if way is not closed (see {@link Way#isClosed}).
538 */
539 public static boolean isClockwise(Way w) {
540 if (!w.isClosed()) {
541 throw new IllegalArgumentException("Way must be closed to check orientation.");
542 }
543
544 double area2 = 0.;
545 int nodesCount = w.getNodesCount();
546
547 for (int node = 1; node <= /*sic! consider last-first as well*/ nodesCount; node++) {
548 LatLon coorPrev = w.getNode(node - 1).getCoor();
549 LatLon coorCurr = w.getNode(node % nodesCount).getCoor();
550 area2 += coorPrev.lon() * coorCurr.lat();
551 area2 -= coorCurr.lon() * coorPrev.lat();
552 }
553 return area2 < 0;
554 }
555
556 /**
557 * Returns angle of a segment defined with 2 point coordinates.
558 *
559 * @param p1
560 * @param p2
561 * @return Angle in radians (-pi, pi]
562 */
563 public static double getSegmentAngle(EastNorth p1, EastNorth p2) {
564 return Math.atan2(p2.north() - p1.north(), p2.east() - p1.east());
565 }
566
567 /**
568 * Returns angle of a corner defined with 3 point coordinates.
569 *
570 * @param p1
571 * @param p2 Common endpoint
572 * @param p3
573 * @return Angle in radians (-pi, pi]
574 */
575 public static double getCornerAngle(EastNorth p1, EastNorth p2, EastNorth p3) {
576 Double result = getSegmentAngle(p2, p1) - getSegmentAngle(p2, p3);
577 if (result <= -Math.PI) {
578 result += 2 * Math.PI;
579 }
580
581 if (result > Math.PI) {
582 result -= 2 * Math.PI;
583 }
584
585 return result;
586 }
587
588 public static EastNorth getCentroid(List<Node> nodes) {
589 // Compute the centroid of nodes
590
591 BigDecimal area = new BigDecimal(0);
592 BigDecimal north = new BigDecimal(0);
593 BigDecimal east = new BigDecimal(0);
594
595 // See http://en.wikipedia.org/w/index.php?title=Centroid&oldid=294224857#Centroid_of_polygon for the equation used here
596 for (int i = 0; i < nodes.size(); i++) {
597 EastNorth n0 = nodes.get(i).getEastNorth();
598 EastNorth n1 = nodes.get((i+1) % nodes.size()).getEastNorth();
599
600 BigDecimal x0 = new BigDecimal(n0.east());
601 BigDecimal y0 = new BigDecimal(n0.north());
602 BigDecimal x1 = new BigDecimal(n1.east());
603 BigDecimal y1 = new BigDecimal(n1.north());
604
605 BigDecimal k = x0.multiply(y1, MathContext.DECIMAL128).subtract(y0.multiply(x1, MathContext.DECIMAL128));
606
607 area = area.add(k, MathContext.DECIMAL128);
608 east = east.add(k.multiply(x0.add(x1, MathContext.DECIMAL128), MathContext.DECIMAL128));
609 north = north.add(k.multiply(y0.add(y1, MathContext.DECIMAL128), MathContext.DECIMAL128));
610 }
611
612 BigDecimal d = new BigDecimal(3, MathContext.DECIMAL128); // 1/2 * 6 = 3
613 area = area.multiply(d, MathContext.DECIMAL128);
614 if (area.compareTo(BigDecimal.ZERO) != 0) {
615 north = north.divide(area, MathContext.DECIMAL128);
616 east = east.divide(area, MathContext.DECIMAL128);
617 }
618
619 return new EastNorth(east.doubleValue(), north.doubleValue());
620 }
621
622 /**
623 * Returns the coordinate of intersection of segment sp1-sp2 and an altitude
624 * to it starting at point ap. If the line defined with sp1-sp2 intersects
625 * its altitude out of sp1-sp2, null is returned.
626 *
627 * @param sp1
628 * @param sp2
629 * @param ap
630 * @return Intersection coordinate or null
631 */
632 public static EastNorth getSegmentAltituteIntersection(EastNorth sp1,
633 EastNorth sp2, EastNorth ap) {
634 Double segmentLenght = sp1.distance(sp2);
635 Double altitudeAngle = getSegmentAngle(sp1, sp2) + Math.PI / 2;
636
637 // Taking a random point on the altitude line (angle is known).
638 EastNorth ap2 = new EastNorth(ap.east() + 1000
639 * Math.cos(altitudeAngle), ap.north() + 1000
640 * Math.sin(altitudeAngle));
641
642 // Finding the intersection of two lines
643 EastNorth resultCandidate = Geometry.getLineLineIntersection(sp1, sp2,
644 ap, ap2);
645
646 // Filtering result
647 if (resultCandidate != null
648 && resultCandidate.distance(sp1) * .999 < segmentLenght
649 && resultCandidate.distance(sp2) * .999 < segmentLenght) {
650 return resultCandidate;
651 } else {
652 return null;
653 }
654 }
655 }