Search code examples
androidlatitude-longitudepolyline

How to calculate x number of points on a line?


I am working with drawing polylines on google maps. Given an origin and destination (latitude,longitude) coordinates how can I get 'x' number of points on that line?

I have tried applying mathematical concepts such as the equation of a line y = mx + c or even (x-x1)/(x1-x2) = (y-y1)/(y1-y2) but these methodologies do not work. The world is not flat. What is the formula for finding all points in a linear line for latitude/longitude values? Does anyone have any ideas for this? I believe I have to apply this equation: https://en.wikipedia.org/wiki/Mercator_projection

EDIT: Someone suggested trying to convert the lat/lng to points and then doing the math and then converting back to lat/lng. There seems to be a large margin or error when doing this. Latitude is accurate, but Longitude is completely off. The TILE_SIZE = 256, the size of tiles that Google returns for Google Maps

public GoogleMapsProjection2() {
    this._pixelOrigin = new PointF(TILE_SIZE / 2.0, TILE_SIZE / 2.0);
    this._pixelsPerLonDegree = TILE_SIZE / 360.0;
    this._pixelsPerLonRadian = TILE_SIZE / (2 * Math.PI);
}

public PointF fromLatLngToPoint(double lat, double lng, int zoom) {
    PointF point = new PointF(0, 0);

    point.x = _pixelOrigin.x + lng * _pixelsPerLonDegree;

    // Truncating to 0.9999 effectively limits latitude to 89.189. This is
    // about a third of a tile past the edge of the world tile.
    double siny = bound(Math.sin(degreesToRadians(lat)), -0.9999, 0.9999);
    point.y = _pixelOrigin.y + 0.5 * Math.log((1 + siny) / (1 - siny)) * -_pixelsPerLonRadian;

    int numTiles = 1 << zoom;
    point.x = point.x * numTiles;
    point.y = point.y * numTiles;
    return point;
}

public PointF fromPointToLatLng(PointF point, int zoom) {
    int numTiles = 1 << zoom;
    point.x = point.x / numTiles;
    point.y = point.y / numTiles;

    double lng = (point.x - _pixelOrigin.x) / _pixelsPerLonDegree;
    double latRadians = (point.y - _pixelOrigin.y) / -_pixelsPerLonRadian;
    double lat = radiansToDegrees(2 * Math.atan(Math.exp(latRadians)) - Math.PI / 2);
    return new PointF(lat, lng);
}

public final class PointF {
    public double x;
    public double y;

    public PointF(double x, double y) {
        this.x = x;
        this.y = y;
    }
}

Solution

  • A line segment in a Google Maps polyline is a geodesic line. In a spherical earth approximation, this is a great circle. The polyline with a single segment (your origin and destination in lat/long coordinates) is rendered onto a 2D map using a projection, but it's still a geodesic line (great circle).

    GIS stack exchange has this question of interpolating two (latitude, longitude) coordinates to compute waypoints. The answer suggests using GeographicLib, which has a java library, and provides a JavaScript example. The resulting waypoints in latitude/longitude coordinates are your inputs to the polyline.

    It's best to perform the interpolation in the latitude/longitude coordinate system to avoid magnifying errors with projection or discretization.