java - How to find a geographic point between two other points

Question

For my application I have to find the position of a point on Google map knowing only that it's located between 2 other points and the time (in ms) when the coordinates have been caught.

In my code, assumed A and B as the points given and X as the point to find, I:

1. calculate distance between A and B

2. basing on time I found out the speed (in micro degrees /ms) to travel from A to B

3. I found the distance from point A and point X (using time and speed)

4. using similar triangle's rule, I calculate latitude and longitude of point X from point A

This workflow bring out errors on the map, so, often the X marker is not on the line between A and B markers.

How can I make it works better? Is it a problem with the sphericity of the globe?

Thank you to all.

Here is the code:

    int ax = oldPoint.getLatitude();
    int ay = oldPoint.getLongitude();

    int bx = currentPoint.getLatitude();
    int by = currentPoint.getLongitude();

    long at = oldPoint.getDataRilevamento(); //get time first point
    long bt = currentPoint.getDataRilevamento(); // get time second point
    long xt = x.getDate(); // time of point to find

    int c1 = bx-ax;
    int c2 = by-ay;
    double hyp =  Math.sqrt(Math.pow(c1, 2) + Math.pow(c2, 2));

    double vel = hyp / (bt-at);

    double pos = vel*(xt - at);

    int posx = (int)((pos*c1)/hyp);
    int posy = (int)((pos*c2)/hyp);

    x.setLatitude(ax+posx); //set the latitude of X
    x.setLongitude(ay+posy); // set the longitude of X

Answer 1

Your problem can be solved by taking the following steps.

• Calculate the distance from points A and B. This calculation is called solving the "inverse geodesic problem", and this is discussed in C.F.F. Karney's article "Algorithms for geodesics, 2012. The code below uses the Haversine formula, which is not as accurate as the algorithms presented in Karney's article. To use the formula correctly, Android's microdegrees, which is what getLatitude and getLongitude return, must be converted to radians, using a formula like this:

    double radians = Math.toRadians((double)microdegrees/1000000);
  

• Calculate the bearing (direction) from points A and B (use the formula on the same page). This will be different from the Pythagorean formula because the earth is round, not flat.

• Then you can choose a new distance and calculate point X given point A and the bearing found in the previous step. This is called solving the "direct geodesic problem".

• Convert the radians from the generated point into microdegrees using this formula:

    int microdegrees = (int)(Math.toDegrees(radians)*1000000);
  

Putting it all together, we have the following function, which I place in the public domain:

    public static int[] getIntermediatePoint(
        int startLatMicroDeg,
        int startLonMicroDeg,
        int endLatMicroDeg,
        int endLonMicroDeg,
        double t // How much of the distance to use, from 0 through 1
    ){
        // Convert microdegrees to radians
        double alatRad=Math.toRadians((double)startLatMicroDeg/1000000);
        double alonRad=Math.toRadians((double)startLonMicroDeg/1000000);
        double blatRad=Math.toRadians((double)endLatMicroDeg/1000000);
        double blonRad=Math.toRadians((double)endLonMicroDeg/1000000);
        // Calculate distance in longitude
        double dlon=blonRad-alonRad;
        // Calculate common variables
        double alatRadSin=Math.sin(alatRad);
        double blatRadSin=Math.sin(blatRad);
        double alatRadCos=Math.cos(alatRad);
        double blatRadCos=Math.cos(blatRad);
        double dlonCos=Math.cos(dlon);
        // Find distance from A to B
        double distance=Math.acos(alatRadSin*blatRadSin +
                                  alatRadCos*blatRadCos *
                                  dlonCos);
        // Find bearing from A to B
        double bearing=Math.atan2(
            Math.sin(dlon) * blatRadCos,
            alatRadCos*blatRadSin -
            alatRadSin*blatRadCos*dlonCos);
        // Find new point
        double angularDistance=distance*t;
        double angDistSin=Math.sin(angularDistance);
        double angDistCos=Math.cos(angularDistance);
        double xlatRad = Math.asin( alatRadSin*angDistCos +
                                   alatRadCos*angDistSin*Math.cos(bearing) );
        double xlonRad = alonRad + Math.atan2(
            Math.sin(bearing)*angDistSin*alatRadCos,
            angDistCos-alatRadSin*Math.sin(xlatRad));
        // Convert radians to microdegrees
        int xlat=(int)Math.round(Math.toDegrees(xlatRad)*1000000);
        int xlon=(int)Math.round(Math.toDegrees(xlonRad)*1000000);
        if(xlat>90000000)xlat=90000000;
        if(xlat<-90000000)xlat=-90000000;
        while(xlon>180000000)xlon-=360000000;
        while(xlon<=-180000000)xlon+=360000000;
        return new int[]{xlat,xlon};
    }

And here's how it's used:

int ax = oldPoint.getLatitude();
int ay = oldPoint.getLongitude();

int bx = currentPoint.getLatitude();
int by = currentPoint.getLongitude();

long at = oldPoint.getDataRilevamento(); //get time first point
long bt = currentPoint.getDataRilevamento(); // get time second point
long xt = x.getDate(); // time of point to find

// Find relative time from point A to point B
double t=(bt==at) ? 0 : ((double)(xt-at))/((double)(bt-at));
// Find new point given the start and end points and the relative time
int[] xpos=getIntermediatePoint(ax,ay,bx,by,t);
x.setLatitude(xpos[0]); //set the latitude of X
x.setLongitude(xpos[1]); // set the longitude of X