r123454321
r123454321

Reputation: 3403

Distance between a Lat/Long & the closest edge of a polygon which is made up of Lat/Longs?

I have a list of Lat/Long coordinates that represents a polygon and a single separate Lat/Long which I know is contained within the polygon.

How do I determine the distance from the single Lat/Long to the closest edge of the polygon? Is there a known Java library for this?

Upvotes: 4

Views: 1602

Answers (3)

esel
esel

Reputation: 983

I suggest following solution, which also works in case of a polygon that is around the north pole, where a calculation of the longitude and latitude difference doesn't make sense.

The solution transforms the longitude and latitude of points on the earth into three-dimensional coordinates by using the World Geodetic System 84. With those three-dimensional points, you can calculate the projection of one point on the line defined by two other points in three-dimensional space.

Here is the code doing the calculations. It uses the class javafx.geometry.Point3D, available in Java 8.

/** Semi-major axis of earth in meter */
public static final double WGS84_A = 6378137.0;

/** Semi-minor axis of earth in meter */
public static final double WGS84_B = 6356752.314245;

/** Eccentricity of earth */
public static final double WGS84_E =  
        Math.sqrt( (WGS84_A * WGS84_A) / (WGS84_B * WGS84_B) - 1);

public static final double DEGREES_TO_RADIANS = Math.PI / 180;

/**
 * Calculates a three-dimensional point in the 
 * World Geodetic System (WGS84) from latitude and longitude.
 */
public static Point3D latLonToPoint3D(double lat, double lon) {
    double clat = Math.cos(lat * DEGREES_TO_RADIANS);
    double slat = Math.sin(lat * DEGREES_TO_RADIANS);
    double clon = Math.cos(lon * DEGREES_TO_RADIANS);
    double slon = Math.sin(lon * DEGREES_TO_RADIANS);

    double N = WGS84_A / Math.sqrt(1.0 - WGS84_E * WGS84_E * slat * slat);

    double x = N  * clat * clon;
    double y = N  * clat * slon;
    double z = N * (1.0 - WGS84_E * WGS84_E) * slat;
    return new Point3D(x, y, z);
}

/**
 * Calculates distance of projection p of vector a on vector b.
 *
 * Use formula for projection, with p being the projection point:
 * <p>
 * p = a X b / |b|^2 * b
 * </p>
 * X being the dot product, * being multiplication of vector and constant
 */
public static Point3D calculateProjection(Point3D a, Point3D b) {
    return b.multiply(a.dotProduct(b) / (b.dotProduct(b)));
}

/**
 * Calculates shortest distance of vector x and the line defined by 
 * the vectors a and b.
 */
public static double calculateDistanceToLine(Point3D x, Point3D a, Point3D b) {
    Point3D projectionOntoLine = 
            calculateProjection(x.subtract(a), b.subtract(a)).add(a);
    return projectionOntoLine.distance(x);
}

By calling calculateDistanceToLine with the point and the polygon segments' points, you are able to find the nearest line defined by the edge points and extended to infinity. In the case of a concave polygon, this may not be what you want, as you see in the picture.

A concave polygon where the next edge (orange) is not the line with the nearest projection point.

Taking into account that the distance to the polygon edge must be at least as long as the distance to the nearest edge point, you can get the distance to the edge as:

Math.max(calculateDistanceToLine(x, edgePoint1, edgePoint2), 
    Math.min(x.distance(edgePoint1), x.distance(edgePoint2)));

Note that this calculation yields also not the distance on the surface of the earth, but the direct distance cutting through the earth. Anyway, it should suffice for choosing the shortest distance.

The function latLonToPoint3Dis a modified version of the function that I found here.

Upvotes: 2

Ichor de Dionysos
Ichor de Dionysos

Reputation: 1137

you can just loop through all your edges and calculate the distance between the two points like this:

function double calculateDistance(
    double edgeLat1, double edgeLng1, 
    double edgeLat2, double edgeLng2, 
    double pointLat, double pointLng) {

  //calculate straight/edge
  double mS = (edgeLng2 - edgeLng1)/(edgeLat2- edgeLat2);
  double tS = edgeLng1 - edgeLng1 * mS;

  //calculate helper straight
  double mH = -mS;
  double tH = pointLng - mH * pointLat;

  //calcuate straight intersection
  xI = (tH - tS)/(mS - mH);
  yI = mH * xI - tH;

  //calculate distance
  /* in degree
  double dInDegree = Math.sqrt((pointLat - xI) * (pointLat - xI) 
                           + (pointLng - yI) * (pointLng - yI));

  return dInDegree;
  */
  //in meter
  double R = 6371000; // m
  double dLat = (pointLat-xI).toRad();
  double dLon = (pointLng-yI).toRad(); 
  double a = Math.sin(dLat/2) * Math.sin(dLat/2) +
    Math.cos(x1.toRad()) * Math.cos(pointLat.toRad()) * 
    Math.sin(dLon/2) * Math.sin(dLon/2); 
  double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a)); 
  double distanceInMeter = R * c;
  return distanceInMeter;
}

I hope this works for you, this is "simple" vector maths.

Upvotes: 1

Lencalot
Lencalot

Reputation: 395

Check the Single Separate Lat/Long, for the closest coordinate that exists in your list.

Then Gather the two points that are connected to that Coordinate(the one that is closest to your single point) So now you have 4 points.

singlePoint, closestPointToSinglePoint, neighbor1, neighbor2. I'm assuming you have some basic trig experience at this point(no pun intended). What you should do from here is visualize 2 triangles. (singlePoint, closestPointToSinglePoint, neighbor1) and (singlePoint, closestPointToSinglePoint, neighbor2).

At this point, calculate the height of the triangles from the SinglePoint as a reference. You now have 2 distances to the 2 closest edges. Compare, and enjoy your results.

Upvotes: 0

Related Questions