OSM Tiles werden falsch berechnet (Problem behoben)

Gibson · April 8, 2010, 8:25pm

Hallo liebe OSM-Community,

ich arbeite an meiner Bachelorarbeit und muss dafür eine Karte auf mobilen javafähigen Geräten -J2ME- (Handy & Co) mithilfe der OpenStreetmap Rohdaten erstellen. Ich bin soweit, das ich mittels Mercator-Projektion eine Vektorkarte um einen GPS-Punkt (lat/lon) zeichnen lassen kann. Gleichzeitig unterstützt mein Renderer jedoch auch das darstellen vorgerenderter Tiles im PNG-Format. Um nun meine echte Position auch auf dem Bildschirm darstellen zu können, muss ich die Bounding Box der Tiles berechnen. Nutzen tuhe ich dafür die Java-Funktionen auf http://wiki.openstreetmap.org/wiki/Slippy_map_tilenames.

Die Tilenummern werden richtig berechnet, jedoch nicht die Bounding Box.

So sieht das ganze bei mir aus:

public int getTileNumber(final double lat, final double lon, final int zoom) {
int tile = new int[2];
tile[0] = (int)Math.floor( (lon + 180) / 360 * (1<<zoom) ) ;
tile[1] = (int)Math.floor( (1 - log(Math.tan(Math.toRadians(lat)) + 1 / Math.cos(Math.toRadians(lat))) / Math.PI) / 2 * (1<<zoom) ) ;
return tile;
}
public double[] tile2boundingBox(final int x, final int y, final int zoom) {
		double[] coord = new double[4];
		coord[0] = tile2lat(y, zoom);
		coord[1] = tile2lat(y +1 , zoom);
		coord[2] = tile2lon(x, zoom);
		coord[3] = tile2lon(x + 1, zoom);
	    return coord;
	  }

static double tile2lon(int x, int z) {
     return (x / pow(2, z) * 360 - 180);
  }
public static double tile2lat(int y, int zoom) {
final double n = Math.PI - ((2.0 * Math.PI * y) / (1 << zoom));
return 180.0 / Math.PI * atan(0.5 * (exp(n) - exp(-n)));
}

Zum verifizieren der Ergebnisse nutze ich den Rechner auf: http://oms.wff.ch/calc.php

Gebe ich nun zum Testen Beispielsweise lat=46 und lon=6 ein, bekomm eich als Ergebnis die Tilenummer tileX=33860 und tileY=23315 was laut Online-Rechner auch Korrekt ist. Versuche ich jetzt die Bounding Box zu berechnen, bekomme ich heraus:

… laut http://oms.wff.ch/calc.php müsste aber richtig sein:

Weiss jemand wo der Fehler liegt? Ich sitz schon viele Stunden an diesem Problem und finde den Fehler nicht. Ohne diese korrekte Berechnung kann ich keine Navigation auf der Karte und auf dem Handy ermöglichen.

Gibson · April 9, 2010, 3:35am

J2ME ist echt nen Graus… es scheint an meiner geklauten und selbstgefummelten atan() Funktion zu liegen… sie scheint nicht das exakte Ergebnis zu liefern:

// ATAN Funktion
public static double atan(double a) {

	if (Math.abs(a) <= 1.0f) {
	    return (a /(1 + 0.28f*(a*a)));
	} else {
	    double retval = (((double)Math.PI)/2) - (a/((a*a) + 0.28)); 
	    if (a < (-1.0f)){
		return (retval - (double)Math.PI);
	    } else {
		//if a > 1.0f
		return retval;
	    }
	}
    }

Hat jemand eine Alternative?

PA94 · April 9, 2010, 11:02am

Hallo,

versuch es mal mit

http://www.forum.nokia.com/forum/showthread.php?t=72840

oder

http://real-java.sourceforge.net/Real.html

Beide habe ich nicht getestet.

Schöne Grüße

PA94

PA94 · April 9, 2010, 1:32pm

Hallo,

der “atan”-Ersatz von
http://www.forum.nokia.com/forum/showthread.php?t=72840
ist anscheinend ziemlich gut…

Hab mir mal schnell einen Vergleich quick’n dirty in C zusammengehackt:


#include <stdio.h>
#include <math.h>


// taken from
//
// http://svn.bbtracker.org/bbtracker_common/trunk/src/org/bbtracker/MMath.java
//
// resp.
//
// http://www.forum.nokia.com/forum/showthread.php?t=72840 


double sq2p1 = 2.414213562373095048802e0;
double sq2m1  = .414213562373095048802e0;
double p4  = .161536412982230228262e2;
double p3  = .26842548195503973794141e3;
double p2  = .11530293515404850115428136e4;
double p1  = .178040631643319697105464587e4;
double p0  = .89678597403663861959987488e3;
double q4  = .5895697050844462222791e2;
double q3  = .536265374031215315104235e3;
double q2  = .16667838148816337184521798e4;
double q1  = .207933497444540981287275926e4;
double q0  = .89678597403663861962481162e3;
double PIO2 = 1.5707963267948966135E0;
//double nan = (0.0/0.0);


double mxatan(double arg)
{
    double argsq, value;

    argsq = arg*arg;
    value = ((((p4*argsq + p3)*argsq + p2)*argsq + p1)*argsq + p0);
    value = value/(((((argsq + q4)*argsq + q3)*argsq + q2)*argsq + q1)*argsq + q0);
    return value*arg;
}

double msatan(double arg)
{
    if(arg < sq2m1)
        return mxatan(arg);
    if(arg > sq2p1)
        return PIO2 - mxatan(1/arg);
        return PIO2/2 + mxatan((arg-1)/(arg+1));
}

double atan_approx(double arg)
{
    if(arg > 0)
        return msatan(arg);
    return -msatan(-arg);
}



double PI= 3.14159265358979323846;

double tile2lat_approx(int y, int zoom)
{
    double n = PI - ((2.0 * PI * y) / (1 << zoom));
    return 180.0 / PI * atan_approx(0.5 * (exp(n) - exp(-n)));
}

double tile2lat(int y, int zoom)
{
    double n = PI - ((2.0 * PI * y) / (1 << zoom));
    return 180.0 / PI * atan(0.5 * (exp(n) - exp(-n)));
}

// gcc -c -Wall atan_tst.c
// 
// gcc -o atan_tst atan_tst.o -lm


int main(void)
{
    int i;
    double delta, min= 1, max= -1;
    
    
    for(i=23314; i<=23316; i++)
        printf("tile2lat(%5d)=%22.18lf  %22.18lf  %.18lf\n", i, tile2lat(i, 16) , tile2lat_approx(i, 16), tile2lat(i, 16)-tile2lat_approx(i, 16));
    printf("\n");
    
    for(i=0; i<=2; i++)
        printf("tile2lat(%5d)=%22.18lf  %22.18lf  %.18lf\n", i, tile2lat(i, 16) , tile2lat_approx(i, 16), tile2lat(i, 16)-tile2lat_approx(i, 16));
    for(i=16383; i<=16385; i++)
        printf("tile2lat(%5d)=%22.18lf  %22.18lf  %.18lf\n", i, tile2lat(i, 16) , tile2lat_approx(i, 16), tile2lat(i, 16)-tile2lat_approx(i, 16));
    for(i=32767; i<=32769; i++)
        printf("tile2lat(%5d)=%22.18lf  %22.18lf  %.18lf\n", i, tile2lat(i, 16) , tile2lat_approx(i, 16), tile2lat(i, 16)-tile2lat_approx(i, 16));
    for(i=65534; i<=65536; i++)
        printf("tile2lat(%5d)=%22.18lf  %22.18lf  %.18lf\n", i, tile2lat(i, 16) , tile2lat_approx(i, 16), tile2lat(i, 16)-tile2lat_approx(i, 16));
    for(i=0; i<=65536; i++)
    {
        delta= tile2lat(i, 16)-tile2lat_approx(i, 16);
        if (delta < min) min= delta;
        if (delta > max) max= delta;
    }
    printf("\nmin=%.18lf  max=%.18lf\n", min, max);

    return 0;
}

Es liefert:


tile2lat(23314)= 46.004593255744815000   46.004593255744815000  -0.000000000000000836
tile2lat(23315)= 46.000777568556607000   46.000777568556600000  0.000000000000005742
tile2lat(23316)= 45.996961618203812000   45.996961618203805000  0.000000000000004382

tile2lat(    0)= 85.051128779806604000   85.051128779806589000  0.000000000000011907
tile2lat(    1)= 85.050654879827547000   85.050654879827547000  0.000000000000002193
tile2lat(    2)= 85.050180934581164000   85.050180934581149000  0.000000000000012206
tile2lat(16383)= 66.515449574975378000   66.515449574975378000  0.000000000000006689
tile2lat(16384)= 66.513260443111861000   66.513260443111861000  0.000000000000002227
tile2lat(16385)= 66.511071118747594000   66.511071118747594000  0.000000000000004975
tile2lat(32767)=  0.005493164054085968    0.005493164054085968  0.000000000000000001
tile2lat(32768)=  0.000000000000000000    0.000000000000000000  0.000000000000000000
tile2lat(32769)= -0.005493164054084375   -0.005493164054084374  -0.000000000000000001
tile2lat(65534)=-85.050180934581164000  -85.050180934581149000  -0.000000000000012206
tile2lat(65535)=-85.050654879827547000  -85.050654879827547000  -0.000000000000002193
tile2lat(65536)=-85.051128779806604000  -85.051128779806589000  -0.000000000000012691

min=-0.000000000000018617  max=0.000000000000018020

Schöne Grüße

PA94

Gibson · April 10, 2010, 6:30am

Vielen Dank für die Antworten. Die atan Funktion auf http://www.forum.nokia.com/forum/showthread.php?t=72840 funktioniert prima. Falls jemand ein ähnliches Problem hat… http://www.forum.nokia.com/forum/showthread.php?t=72840 !!! ;). Ist aber auch nen fieser Fehler gewesen. Ein atan(10) hat bei meiner Funktion das richtige Ergebnis geliefert. Solche Problemchen im Programm wünsch ich niemanden… bei vielen Funktionen wirklich schwer zu finden. Vielen Dank

Falls es jemanden interessieren sollte… Hier ein paar Bilder einer frühen Version. Mein Renderer kann zwischen meiner eigenen Vektorkarte und den vorgerenderten Tiles (in diesem Fall der Osmarenderer) im Echtzeitbetrieb hin und herwechseln. Die Vektorkarte wird dabei direkt aus den OSM-Rohdaten in Echtzeit generiert und in 9 Bilden dargestellt. In einem Vektorbild können maximal 100 Ways (Zoomfaktor 16 zum navigieren) dargestellt werden, da ich sonst den Speicher (beim Parsen) einiger Geräte überschreite. Die Zeit zum generieren der Karenausschnitte, die möglichst konform der vorgerenderten Tiles ist (Mercator Projektion), dauert momentan im Schnitt auf einem Samsung Jet 5 Sekunden pro Bild auch bei recht vielen Ways, was zu verkraften ist. Die OSM Daten werden dabei vom mobilen Gerät in ein Tiny-SVG Format umgewandelt und dargestellt. (Das rote Viereck symbolisiert im Augenblick die Position… Der Kartenauschnitt ist frei gewählt (lat 46, lon 6 als Koordinate für das zu zeichnende “Tile”)… Es ist noch eine sehr frühe Version ;).

Im eigenen Vektormodus (ist noch um 90 Grad verdreht…)
FluxBB bbcode test
Im Bildmodus (auch hier wird die Position Pixelgenau berechnet bei der vorgegebenen Bildgrösse von 256x256 Pixeln

Die Vektorkarte beim laden…

PA94 · April 10, 2010, 11:30am

Hallo Gibson,

Ist ja auch kein Wunder, denn die atan-Funktion konvergiert für x->unendlich gegen pi/2 (siehe auch http://de.wikipedia.org/wiki/Arcustangens).
Der “interessante” Bereich liegt also ca. zwischen -2 und 2.
In dem Wikipedia-Artikel ist auch noch im Abschnitt “Näherungsweise Berechnung” http://de.wikipedia.org/wiki/Arcustangens#N.C3.A4herungsweise_Berechnung ein Link auf http://www.lightsoft.co.uk/PD/stu/stuchat37.html, in dem auch auf “Deine” Näherung eingegangen wird, aber wie schon gesagt: Die Näherung von http://www.forum.nokia.com/forum/showthread.php?t=72840 ist wirklich gut!

Schöne Grüße

PA94

Gibson · April 10, 2010, 3:23pm

Ja jetzt bin ich auch schlauer… hab bei der Suche nach dem Fehler nur überhaupt nicht an die atan Funktion gedacht.

chris66 · April 10, 2010, 5:09pm

Hi, ist zwar reichlich offtopic, aber hat das “normale” java denn eine atan Funktion? Kann kaum glauben,
dass J2ME kein atan eingebaut hat.

Chris

PA94 · April 11, 2010, 12:18pm

Hallo,

Sorry, auch wenn sich das für Dich wahrscheinlich arrogant anhört: Das wäre mein erster Tipp gewesen, da Du ja die atan-Funktion selbst eingbaut hast…

Doch, genau so ist es:

J2SE atan: http://java.sun.com/javase/6/docs/api/java/lang/Math.html
J2ME hat kein atan!

Schöne Grüße

PA94

Gibson · April 12, 2010, 9:27am

Klingt nicht arrogant… bedenke jedoch bitte, das ich nicht nur eine atan Funktion brauche und schon recht viele Funktionen (log, ln, exp, pow, atan2…) selbst implementieren musste. Da mir der Fehler erst so richtig aufgefallen ist, als ich die Tiles berechnen wollte, musste ich erstmal gründlich suchen… und da der Fehler auch nur bei Floating Point Operationen zustande kam, hats bei mir etwas länger gedauert. Aber vielen Dank nochmal für die Hilfe und die ausführlichen Erläuterungen. Jetzt funktioniert es sauber.

J2ME ist in einigen Bereichen leider sehr beschnitten.