@Test public void testDistanceWithinPolygon() { final double[] lons = { 2.333523, 2.333432, 2.333833, 2.333983, 2.334815, 2.334766 }; final double[] lats = { 48.823778, 48.824091, 48.82389, 48.824165, 48.824232, 48.82384 }; OsmNogoPolygon polygon = new OsmNogoPolygon(true); for (int i = 0; i < lons.length; i++) { polygon.addVertex(toOsmLon(lons[i], 0), toOsmLat(lats[i], 0)); } OsmNogoPolygon polyline = new OsmNogoPolygon(false); for (int i = 0; i < lons.length; i++) { polyline.addVertex(toOsmLon(lons[i], 0), toOsmLat(lats[i], 0)); } int lon1 = toOsmLon(2.33308732509613, 0); int lat1 = toOsmLat(48.8238790443901, 0); int lon2 = toOsmLon(2.33378201723099, 0); int lat2 = toOsmLat(48.8239585098974, 0); assertEquals( "Should give the correct length for a segment with a single intersection", 17.5, polygon.distanceWithinPolygon(lon1, lat1, lon2, lat2), 0.05 * 17.5 ); lon2 = toOsmLon(2.33488172292709, 0); lat2 = toOsmLat(48.8240891862353, 0); assertEquals( "Should give the correct length for a segment with multiple intersections", 85, polygon.distanceWithinPolygon(lon1, lat1, lon2, lat2), 0.05 * 85 ); lon2 = toOsmLon(2.33433187007904, 0); lat2 = toOsmLat(48.8240238480664, 0); assertEquals( "Should give the correct length when last point is within the polygon", 50, polygon.distanceWithinPolygon(lon1, lat1, lon2, lat2), 0.05 * 50 ); lon1 = toOsmLon(2.33433187007904, 0); lat1 = toOsmLat(48.8240238480664, 0); lon2 = toOsmLon(2.33488172292709, 0); lat2 = toOsmLat(48.8240891862353, 0); assertEquals( "Should give the correct length when first point is within the polygon", 35, polygon.distanceWithinPolygon(lon1, lat1, lon2, lat2), 0.05 * 35 ); lon1 = toOsmLon(2.333523, 0); lat1 = toOsmLat(48.823778, 0); lon2 = toOsmLon(2.333432, 0); lat2 = toOsmLat(48.824091, 0); assertEquals( "Should give the correct length if the segment overlaps with an edge of the polygon", CheapRuler.distance(lon1, lat1, lon2, lat2), polygon.distanceWithinPolygon(lon1, lat1, lon2, lat2), 0.05 * CheapRuler.distance(lon1, lat1, lon2, lat2) ); lon1 = toOsmLon(2.333523, 0); lat1 = toOsmLat(48.823778, 0); lon2 = toOsmLon(2.3334775, 0); lat2 = toOsmLat(48.8239345, 0); assertEquals( "Should give the correct length if the segment overlaps with a polyline", CheapRuler.distance(lon1, lat1, lon2, lat2), polyline.distanceWithinPolygon(lon1, lat1, lon2, lat2), 0.05 * CheapRuler.distance(lon1, lat1, lon2, lat2) ); }
public double distanceWithinPolygon(int lon1, int lat1, int lon2, int lat2) { double distance = 0.; final Point p1 = new Point (lon1, lat1); final Point p2 = new Point (lon2, lat2); Point previousIntersectionOnSegment = null; if (isWithin(lon1, lat1)) { previousIntersectionOnSegment = p1; } int i_last = points.size() - 1; for (int i = (isClosed ? 0 : 1), j = (isClosed ? i_last : 0); i <= i_last; j = i++) { Point edgePoint1 = points.get(j); Point edgePoint2 = points.get(i); int intersectsEdge = intersect2D_2Segments(p1, p2, edgePoint1, edgePoint2); if (isClosed && intersectsEdge == 1) { int xdiffSegment = lon1 - lon2; int xdiffEdge = edgePoint1.x - edgePoint2.x; int ydiffSegment = lat1 - lat2; int ydiffEdge = edgePoint1.y - edgePoint2.y; int div = xdiffSegment * ydiffEdge - xdiffEdge * ydiffSegment; long dSegment = (long) lon1 * (long) lat2 - (long) lon2 * (long) lat1; long dEdge = (long) edgePoint1.x * (long) edgePoint2.y - (long) edgePoint2.x * (long) edgePoint1.y; Point intersection = new Point( (int) ((dSegment * xdiffEdge - dEdge * xdiffSegment) / div), (int) ((dSegment * ydiffEdge - dEdge * ydiffSegment) / div) ); if ( previousIntersectionOnSegment != null && isWithin( (intersection.x + previousIntersectionOnSegment.x) >> 1, (intersection.y + previousIntersectionOnSegment.y) >> 1 ) ) { distance += CheapRuler.distance( previousIntersectionOnSegment.x, previousIntersectionOnSegment.y, intersection.x, intersection.y ); } previousIntersectionOnSegment = intersection; } else if (intersectsEdge == 2) { distance += Math.min( CheapRuler.distance(p1.x, p1.y, p2.x, p2.y), Math.min( CheapRuler.distance(edgePoint1.x, edgePoint1.y, edgePoint2.x, edgePoint2.y), Math.min( CheapRuler.distance(p1.x, p1.y, edgePoint2.x, edgePoint2.y), CheapRuler.distance(edgePoint1.x, edgePoint1.y, p2.x, p2.y) ) ) ); previousIntersectionOnSegment = null; } } if ( previousIntersectionOnSegment != null && isWithin(lon2, lat2) ) { distance += CheapRuler.distance( previousIntersectionOnSegment.x, previousIntersectionOnSegment.y, lon2, lat2 ); } return distance; }
OsmNogoPolygon extends OsmNodeNamed { public double distanceWithinPolygon(int lon1, int lat1, int lon2, int lat2) { double distance = 0.; final Point p1 = new Point (lon1, lat1); final Point p2 = new Point (lon2, lat2); Point previousIntersectionOnSegment = null; if (isWithin(lon1, lat1)) { previousIntersectionOnSegment = p1; } int i_last = points.size() - 1; for (int i = (isClosed ? 0 : 1), j = (isClosed ? i_last : 0); i <= i_last; j = i++) { Point edgePoint1 = points.get(j); Point edgePoint2 = points.get(i); int intersectsEdge = intersect2D_2Segments(p1, p2, edgePoint1, edgePoint2); if (isClosed && intersectsEdge == 1) { int xdiffSegment = lon1 - lon2; int xdiffEdge = edgePoint1.x - edgePoint2.x; int ydiffSegment = lat1 - lat2; int ydiffEdge = edgePoint1.y - edgePoint2.y; int div = xdiffSegment * ydiffEdge - xdiffEdge * ydiffSegment; long dSegment = (long) lon1 * (long) lat2 - (long) lon2 * (long) lat1; long dEdge = (long) edgePoint1.x * (long) edgePoint2.y - (long) edgePoint2.x * (long) edgePoint1.y; Point intersection = new Point( (int) ((dSegment * xdiffEdge - dEdge * xdiffSegment) / div), (int) ((dSegment * ydiffEdge - dEdge * ydiffSegment) / div) ); if ( previousIntersectionOnSegment != null && isWithin( (intersection.x + previousIntersectionOnSegment.x) >> 1, (intersection.y + previousIntersectionOnSegment.y) >> 1 ) ) { distance += CheapRuler.distance( previousIntersectionOnSegment.x, previousIntersectionOnSegment.y, intersection.x, intersection.y ); } previousIntersectionOnSegment = intersection; } else if (intersectsEdge == 2) { distance += Math.min( CheapRuler.distance(p1.x, p1.y, p2.x, p2.y), Math.min( CheapRuler.distance(edgePoint1.x, edgePoint1.y, edgePoint2.x, edgePoint2.y), Math.min( CheapRuler.distance(p1.x, p1.y, edgePoint2.x, edgePoint2.y), CheapRuler.distance(edgePoint1.x, edgePoint1.y, p2.x, p2.y) ) ) ); previousIntersectionOnSegment = null; } } if ( previousIntersectionOnSegment != null && isWithin(lon2, lat2) ) { distance += CheapRuler.distance( previousIntersectionOnSegment.x, previousIntersectionOnSegment.y, lon2, lat2 ); } return distance; } }
OsmNogoPolygon extends OsmNodeNamed { public double distanceWithinPolygon(int lon1, int lat1, int lon2, int lat2) { double distance = 0.; final Point p1 = new Point (lon1, lat1); final Point p2 = new Point (lon2, lat2); Point previousIntersectionOnSegment = null; if (isWithin(lon1, lat1)) { previousIntersectionOnSegment = p1; } int i_last = points.size() - 1; for (int i = (isClosed ? 0 : 1), j = (isClosed ? i_last : 0); i <= i_last; j = i++) { Point edgePoint1 = points.get(j); Point edgePoint2 = points.get(i); int intersectsEdge = intersect2D_2Segments(p1, p2, edgePoint1, edgePoint2); if (isClosed && intersectsEdge == 1) { int xdiffSegment = lon1 - lon2; int xdiffEdge = edgePoint1.x - edgePoint2.x; int ydiffSegment = lat1 - lat2; int ydiffEdge = edgePoint1.y - edgePoint2.y; int div = xdiffSegment * ydiffEdge - xdiffEdge * ydiffSegment; long dSegment = (long) lon1 * (long) lat2 - (long) lon2 * (long) lat1; long dEdge = (long) edgePoint1.x * (long) edgePoint2.y - (long) edgePoint2.x * (long) edgePoint1.y; Point intersection = new Point( (int) ((dSegment * xdiffEdge - dEdge * xdiffSegment) / div), (int) ((dSegment * ydiffEdge - dEdge * ydiffSegment) / div) ); if ( previousIntersectionOnSegment != null && isWithin( (intersection.x + previousIntersectionOnSegment.x) >> 1, (intersection.y + previousIntersectionOnSegment.y) >> 1 ) ) { distance += CheapRuler.distance( previousIntersectionOnSegment.x, previousIntersectionOnSegment.y, intersection.x, intersection.y ); } previousIntersectionOnSegment = intersection; } else if (intersectsEdge == 2) { distance += Math.min( CheapRuler.distance(p1.x, p1.y, p2.x, p2.y), Math.min( CheapRuler.distance(edgePoint1.x, edgePoint1.y, edgePoint2.x, edgePoint2.y), Math.min( CheapRuler.distance(p1.x, p1.y, edgePoint2.x, edgePoint2.y), CheapRuler.distance(edgePoint1.x, edgePoint1.y, p2.x, p2.y) ) ) ); previousIntersectionOnSegment = null; } } if ( previousIntersectionOnSegment != null && isWithin(lon2, lat2) ) { distance += CheapRuler.distance( previousIntersectionOnSegment.x, previousIntersectionOnSegment.y, lon2, lat2 ); } return distance; } OsmNogoPolygon(boolean closed); }
OsmNogoPolygon extends OsmNodeNamed { public double distanceWithinPolygon(int lon1, int lat1, int lon2, int lat2) { double distance = 0.; final Point p1 = new Point (lon1, lat1); final Point p2 = new Point (lon2, lat2); Point previousIntersectionOnSegment = null; if (isWithin(lon1, lat1)) { previousIntersectionOnSegment = p1; } int i_last = points.size() - 1; for (int i = (isClosed ? 0 : 1), j = (isClosed ? i_last : 0); i <= i_last; j = i++) { Point edgePoint1 = points.get(j); Point edgePoint2 = points.get(i); int intersectsEdge = intersect2D_2Segments(p1, p2, edgePoint1, edgePoint2); if (isClosed && intersectsEdge == 1) { int xdiffSegment = lon1 - lon2; int xdiffEdge = edgePoint1.x - edgePoint2.x; int ydiffSegment = lat1 - lat2; int ydiffEdge = edgePoint1.y - edgePoint2.y; int div = xdiffSegment * ydiffEdge - xdiffEdge * ydiffSegment; long dSegment = (long) lon1 * (long) lat2 - (long) lon2 * (long) lat1; long dEdge = (long) edgePoint1.x * (long) edgePoint2.y - (long) edgePoint2.x * (long) edgePoint1.y; Point intersection = new Point( (int) ((dSegment * xdiffEdge - dEdge * xdiffSegment) / div), (int) ((dSegment * ydiffEdge - dEdge * ydiffSegment) / div) ); if ( previousIntersectionOnSegment != null && isWithin( (intersection.x + previousIntersectionOnSegment.x) >> 1, (intersection.y + previousIntersectionOnSegment.y) >> 1 ) ) { distance += CheapRuler.distance( previousIntersectionOnSegment.x, previousIntersectionOnSegment.y, intersection.x, intersection.y ); } previousIntersectionOnSegment = intersection; } else if (intersectsEdge == 2) { distance += Math.min( CheapRuler.distance(p1.x, p1.y, p2.x, p2.y), Math.min( CheapRuler.distance(edgePoint1.x, edgePoint1.y, edgePoint2.x, edgePoint2.y), Math.min( CheapRuler.distance(p1.x, p1.y, edgePoint2.x, edgePoint2.y), CheapRuler.distance(edgePoint1.x, edgePoint1.y, p2.x, p2.y) ) ) ); previousIntersectionOnSegment = null; } } if ( previousIntersectionOnSegment != null && isWithin(lon2, lat2) ) { distance += CheapRuler.distance( previousIntersectionOnSegment.x, previousIntersectionOnSegment.y, lon2, lat2 ); } return distance; } OsmNogoPolygon(boolean closed); final void addVertex(int lon, int lat); void calcBoundingCircle(); boolean intersects(int lon0, int lat0, int lon1, int lat1); boolean isOnPolyline( long px, long py ); static boolean isOnLine( long px, long py, long p0x, long p0y, long p1x, long p1y ); boolean isWithin(final long px, final long py); double distanceWithinPolygon(int lon1, int lat1, int lon2, int lat2); }
OsmNogoPolygon extends OsmNodeNamed { public double distanceWithinPolygon(int lon1, int lat1, int lon2, int lat2) { double distance = 0.; final Point p1 = new Point (lon1, lat1); final Point p2 = new Point (lon2, lat2); Point previousIntersectionOnSegment = null; if (isWithin(lon1, lat1)) { previousIntersectionOnSegment = p1; } int i_last = points.size() - 1; for (int i = (isClosed ? 0 : 1), j = (isClosed ? i_last : 0); i <= i_last; j = i++) { Point edgePoint1 = points.get(j); Point edgePoint2 = points.get(i); int intersectsEdge = intersect2D_2Segments(p1, p2, edgePoint1, edgePoint2); if (isClosed && intersectsEdge == 1) { int xdiffSegment = lon1 - lon2; int xdiffEdge = edgePoint1.x - edgePoint2.x; int ydiffSegment = lat1 - lat2; int ydiffEdge = edgePoint1.y - edgePoint2.y; int div = xdiffSegment * ydiffEdge - xdiffEdge * ydiffSegment; long dSegment = (long) lon1 * (long) lat2 - (long) lon2 * (long) lat1; long dEdge = (long) edgePoint1.x * (long) edgePoint2.y - (long) edgePoint2.x * (long) edgePoint1.y; Point intersection = new Point( (int) ((dSegment * xdiffEdge - dEdge * xdiffSegment) / div), (int) ((dSegment * ydiffEdge - dEdge * ydiffSegment) / div) ); if ( previousIntersectionOnSegment != null && isWithin( (intersection.x + previousIntersectionOnSegment.x) >> 1, (intersection.y + previousIntersectionOnSegment.y) >> 1 ) ) { distance += CheapRuler.distance( previousIntersectionOnSegment.x, previousIntersectionOnSegment.y, intersection.x, intersection.y ); } previousIntersectionOnSegment = intersection; } else if (intersectsEdge == 2) { distance += Math.min( CheapRuler.distance(p1.x, p1.y, p2.x, p2.y), Math.min( CheapRuler.distance(edgePoint1.x, edgePoint1.y, edgePoint2.x, edgePoint2.y), Math.min( CheapRuler.distance(p1.x, p1.y, edgePoint2.x, edgePoint2.y), CheapRuler.distance(edgePoint1.x, edgePoint1.y, p2.x, p2.y) ) ) ); previousIntersectionOnSegment = null; } } if ( previousIntersectionOnSegment != null && isWithin(lon2, lat2) ) { distance += CheapRuler.distance( previousIntersectionOnSegment.x, previousIntersectionOnSegment.y, lon2, lat2 ); } return distance; } OsmNogoPolygon(boolean closed); final void addVertex(int lon, int lat); void calcBoundingCircle(); boolean intersects(int lon0, int lat0, int lon1, int lat1); boolean isOnPolyline( long px, long py ); static boolean isOnLine( long px, long py, long p0x, long p0y, long p1x, long p1y ); boolean isWithin(final long px, final long py); double distanceWithinPolygon(int lon1, int lat1, int lon2, int lat2); final List<Point> points; final boolean isClosed; }