Java Rotation eines Punktes (Google Maps Coordinaten)

[anonymous1234]

Ich habe momentan ein kleines Problem und komme nicht weiter.
(Ich habe diese Frage auch schon auf [http://stackoverflow.com/questions/...round-an-other-using-google-maps-corodinates] stack overflow [/URL] gestellt, aber keine passende Antwort bekommen. Hoffe das ist daher ok sie nochmal hier zu stellen).


Und zwar habe ich von Google Maps ein Ground Overlay mit folgenden Werten abgefragt:

   <LatLonBox>
        <north>53.10685</north>
        <south>53.10637222222223</south>
        <east>8.853144444444444</east>
        <west>8.851858333333333</west>
        <rotation>-26.3448</rotation>
    </LatLonBox>

Nun will ich testen, ob bestimmte Punkte innerhalb dieses rotierten Rechteckes liegen.
Meine Grundidee hierfür war: Ich rotiere den Punkt, für den ich testen möchte, ob er innerhalb des Rechteckes liegt zurück und muss dann das überschneiden nur noch für ein regulares (nicht rotiertes) Rechteck testen.

public static MyGeoPoint rotatePoint(MyGeoPoint point, MyGeoPoint origion, double degree)
{
	double x =  origion.getLongitude()	+ (Math.cos(Math.toRadians(degree)) * (point.getLongitude() - origion.getLongitude()) - Math.sin(Math.toRadians(degree))	* (point.getLatitude() - origion.getLatitude()));
	double y = origion.getLatitude() + (Math.sin(Math.toRadians(degree)) * (point.getLongitude() - origion.getLongitude()) + Math.cos(Math.toRadians(degree))	* (point.getLatitude() - origion.getLatitude()));
	return new MyGeoPoint(x, y);

}

public boolean intersect(MyGeoPoint geoPoint)
{   
    geoPoint = MyGeoPoint.rotatePoint(geoPoint, this.getCenter(), - this.getRotation());

    return (geoPoint.getLatitude() < getTopLeftLatitude()
            && geoPoint.getLatitude() > getBottomRightLatitude()
                && geoPoint.getLongitude() > getTopLeftLongitude()
                    && geoPoint.getLongitude() < getBottomRightLongitude());
}

Allerdings scheine ich noch irgendwelche Fehler zu machen, vll auch grundlegende Denkfehler.

 LatLonBox box = new LatLonBox(53.10685, 8.851858333333333, 53.10637222222223, 8.853144444444444, -26.3448);

    MyGeoPoint point1 = new MyGeoPoint(8.852311, 53.106872);
    MyGeoPoint point2 = new MyGeoPoint(8.852967186822669, 53.10670378322918);	
    MyGeoPoint point3 = new MyGeoPoint(8.851994565566875, 53.10652664993972);
    MyGeoPoint point4 = new MyGeoPoint(8.85270995172055, 53.10631650700605);

    System.out.println(box.intersect(point1));
    System.out.println(box.intersect(point2));
    System.out.println(box.intersect(point3));
    System.out.println(box.intersect(point4));

Das Ergebnis von diesem Test ist false, true, true, false obwohl es 4x true sein müsste.
Eigentlich kann der Fehler nur bei der Rotation liegen, denn bei rotation = 0 scheint alles zu klappen wie es soll.

Ich hoffe jemand hat eine Idee, denn ich hänge an der Stelle schon über eine Woche.
Schon mal Danke für jede Hilfe im voraus.

 

[1668mib]

Ist denn die rotatePoint durchgetestet und liefert korrekte Ergebnisse?

 

[anonymous1234]

Ich glaube das *-1 ist (war) falsch und habe das jetzt gelöscht.
Zumindest für einfache Werte, wo ich die rotation im Kopf nachvollziehen kann scheint es dann zu stimmen.

Jetzt ist das Ergebnis: false, true, true, false.

Daher muss irgendwas trotzdem noch falsch sein.

 

[Tumbleweed]

Also ich sehe den Fehler gerade auf Anhieb nicht und es strengt auch immer an, sich in ein fremdes Problem reinzudenken, daher verzeih mir, dass ich dir dein Problem nicht direkt lösen kann. Aber...

nimm dir den Hinweis von 1668mib mal zu Herzen, vor allem, wenn du schon so lange an der gleichen Stelle hängst. Mach mal lieber einen Schritt zurück und zieh das anders auf.

Entwickle die rotatePoint- und die intersect-Methode mit einfachen Werten, nicht direkt mit doubles, bei denen die Augen vor Nachkommastellen brennen. Schon wegen dem Überblick. Dann nimmst du also ganz klare und einfache Testwerte und entwickelst test-first und schaust, ob die Berechnungen stimmen. Wenn du so weiter machst wie bisher, kannst du natürlich auch irgendwann zum Ziel gelangen, aber es kostet zu viel Zeit und Hirnschmalz und man will seine Freizeit ja nicht mit Debuggen verschwenden.

 

[anonymous1234]

Grundsätzlich sollte die Rotations Funktion so richtig sein.
Zumindest kommt mit AffineTrasnformation das gleiche raus.

AffineTransform t = new AffineTransform();	
t.setToRotation(Math.toRadians(rotation), center.getX(), center.getY());	
Point2D rotated = t.transform(point, null);

Daher bleibt die Frage, woher der Fehler kommt.

Habe eben extra auch nochmal die Koordinaten überprüft. Es müsste definitiv 4x true rauskommen.

Bin echt ratlos woran es sonst noch liegen kann....

(Liegt es vll. an dem benutzten Koordinatensystem? Damit meine ich dass die Latitude Werte nach oben größer werden? )


EDIT:
Ich hänge nochmal den kompletten Code an. Vll. hilft es ja.

public class Main 
{
	public static void main(String[] args)
	{	
		LatLonBox box = new LatLonBox(53.10685, 8.851858333333333, 53.10637222222223, 8.853144444444444, -26.3448);		
		
		MyGeoPoint point1 = new MyGeoPoint(8.852311, 53.106872);
		MyGeoPoint point2 = new MyGeoPoint(8.852967186822669, 53.10670378322918);	
		MyGeoPoint point3 = new MyGeoPoint(8.851994565566875, 53.10652664993972);
		MyGeoPoint point4 = new MyGeoPoint(8.85270995172055, 53.10631650700605);
		
		System.out.println(box.intersect(point1));
		System.out.println(box.intersect(point2));
		System.out.println(box.intersect(point3));
		System.out.println(box.intersect(point4));
	}
}

import java.text.DecimalFormat;
import java.text.DecimalFormatSymbols;

public class MyGeoPoint {
	
double latitude;
double longitude;

public MyGeoPoint(double longitude, double latitude)
{
	this.latitude = latitude;
	this.longitude = longitude;
}

@Override
public String toString()
{
	DecimalFormatSymbols dfs = DecimalFormatSymbols.getInstance();
	dfs.setDecimalSeparator('.');
	DecimalFormat f = new DecimalFormat("#.##########", dfs); 

	return "long: "+f.format(longitude)+" lat: "+f.format(latitude);
}

public static MyGeoPoint rotatePoint(MyGeoPoint point, MyGeoPoint origion, double degree)
{
	double x =  origion.longitude	+ (Math.cos(Math.toRadians(degree)) * (point.longitude - origion.longitude) - Math.sin(Math.toRadians(degree))	* (point.latitude - origion.latitude));
	double y = origion.latitude + (Math.sin(Math.toRadians(degree)) * (point.longitude - origion.longitude) + Math.cos(Math.toRadians(degree))	* (point.latitude - origion.latitude));
	return new MyGeoPoint(x, y);
}

}

public class LatLonBox
{
	 MyGeoPoint topLeft;
	 MyGeoPoint bottomRight;
	 double rotation; 
	
	public LatLonBox(MyGeoPoint topLeft, MyGeoPoint bottomRight)
	{
		this.topLeft = topLeft;
		this.bottomRight = bottomRight;
		this.rotation = 0;
	}
		
	public LatLonBox(MyGeoPoint topLeft, MyGeoPoint bottomRight, double rotation)
	{
		this.topLeft = topLeft;
		this.bottomRight = bottomRight;
		this.rotation = rotation;
	}
	
	public LatLonBox(double topLeftLat, double topLeftLong,  double bottomRightLat, double bottomRightLong, double rotation)
	{
		this.topLeft = new MyGeoPoint(topLeftLong, topLeftLat);
		this.bottomRight = new MyGeoPoint(bottomRightLong, bottomRightLat);
		this.rotation = rotation;
	}

	public MyGeoPoint getCenter()
	{
		double centerLat = ( topLeft.latitude + bottomRight.latitude) / 2;
		double centerLong = (topLeft.longitude + bottomRight.longitude) / 2;
		return new MyGeoPoint(centerLong, centerLat);		
	}
		
	public boolean intersect(MyGeoPoint geoPoint)
	{	
		geoPoint = MyGeoPoint.rotatePoint(geoPoint, this.getCenter(),  -rotation);	
		return (geoPoint.latitude < topLeft.latitude
				&& geoPoint.latitude > bottomRight.latitude
					&& geoPoint.longitude > topLeft.longitude
						&& geoPoint.longitude < bottomRight.longitude);
	}			
}

Ergänzung (8. Oktober 2012)

Also ich bin mir mittlerweile echt ziemlich sicher, dass meine Grundidee und meine Formel dazu zumindest grundsätzlich richtig sind.

Habe durch googeln mittlerweile auch ähnliche Lösungen gefunden und verglichen und keinen Unterschied feststellen können. Z.B.: http://developer.coronalabs.com/code/checking-if-point-inside-rotated-rectangle

Daher bleibt meiner Meinung nach eigentlich nur, die Art und Weise wie das Rechteck gespeichert wird als Fehlerquelle übrig. Damit meine ich, dass benutzte Koordinatensystem. (Kartesisches) (Also dass die Latitude Werte nach oben hin größer werden und nicht nach unten).

Hat jemand eine Idee wie die Rotation daraufhin abgeändert werden muss? Habe leider von Mathe zu wenig Ahnung um die Formel umzustellen und durch googeln habe ich auch nichts weiter gefunden.

 

[Hancock]

Änder einfach ein Vorzeichen bis es passt .
Eigentlich müsste die "Richtung" des Koordinatensystems egal sein. Entscheidender ist wahrscheinlich eher die Drehrichtung, die durch die Spiegelung "verkehrtherum" abläuft.
Teste doch mal, was passiert, wenn du den Winkel im Vorzeichen änderst.

 

[1668mib]

@Hancock: Stellt sich nur die Frage, inwieweit Längen- und Breitengrad-Angaben einem karthesischen Koordinatensystem entsprechen ...

 

[anonymous1234]

Teste doch mal, was passiert, wenn du den Winkel im Vorzeichen änderst.

Das ist immer das erste was ich getestet habe, wenn ich was geändert hatte.
Hat aber leider nie zu dem gewünschten Ergebnis geführt.

Erstaunlich ist allerdings daran, dass wenn ich das Vorzeichen ändere genau bei den zwei anderen Punkten der Test fehlschlägt. Allerdings würde mir kein sinnvolle Regel bzw. ein sinnvoller Grund einfallen warum man einmal im Uhrzeiger sinn und einmal gegen den Uhrzeigersinn rotieren muss.
Die 4 Beispielpunkte sind übrigens ungefähr die 4 Ecken des Rechtecks.

@Hancock: Stellt sich nur die Frage, inwieweit Längen- und Breitengrad-Angaben einem karthesischen Koordinatensystem entsprechen ...

Naja, damit ist halt gemeint, dass der Koordinatenursprung im Mittelpunkt ist und nicht links oben wie man es vll. von einem Canvas gewöhnt ist.
Siehe hier: http://itouchmap.com/latlong.html
(Das die Erde eig. rund ist kann vernachlässigt werden, da ich keine Rechtecke über die Grenzen hinweg habe.)

Und wenn das auch nicht der Grund ist, bin ich einfach ratlos wie ich noch weiter kommen soll.

 

[Hancock]

OK, wenns die Ecken sind, ist dir sicherlich klar, dass double nicht stabil ist, also bei mehreren Berechnungen dann "wegdriftet".
Was kommt denn für die Koordinaten raus, wenn du sie zurückgedreht hast? Ganz knapp neben dran?
Ich hab so was gerne visualisiert...

Dass die Erde rund ist, kannst du nur solange vernachlässigen, solange du:
1. nicht Nordpol und Südpol im Rechteck hast
2. sehr kleine Rechtecke hast (<1° Länge)

 

[anonymous1234]

Was kommt denn für die Koordinaten raus, wenn du sie zurückgedreht hast? Ganz knapp neben dran?

Jop min. die ersten 10 Stellen nach dem Komma sind gleich, was an Genauigkeit reichen würde.

Dass die Erde rund ist, kannst du nur solange vernachlässigen, solange du:
1. nicht Nordpol und Südpol im Rechteck hast
2. sehr kleine Rechtecke hast (<1° Länge)

Beide Punkte sollten erfüllt sein. Die maximale Größe ist ungefähr: große Gebäude.

 

[kuddlmuddl]

Ich find Tumbleweed hat in #4 alles gesagt was du beachten solltest.
Immer erstmal aufm Blatt Papier einfache naheliegende Fälle simulieren und dann prüfen ob die Software das auch korrekt nachbildet.. dann sieht man den Fehler sicher sofort.

 

[anonymous1234]

Ich find Tumbleweed hat in #4 alles gesagt was du beachten solltest.
Immer erstmal aufm Blatt Papier einfache naheliegende Fälle simulieren und dann prüfen ob die Software das auch korrekt nachbildet.. dann sieht man den Fehler sicher sofort.

Glaubst du nicht, das ist das erste, was ich versucht habe? Immerhin hänge ich da schon über eine Woche lang.

Und wie ich auch schon gesagt habe, funktionieren beide Funktionen bei Beispielwerten:

System.out.println(MyGeoPoint.rotatePoint(new MyGeoPoint(5, 5), new MyGeoPoint(0, 0),90));
System.out.println(MyGeoPoint.rotatePoint(new MyGeoPoint(5, 5), new MyGeoPoint(0, 0),-90));
System.out.println(MyGeoPoint.rotatePoint(new MyGeoPoint(-3, 2), new MyGeoPoint(1, -1), -60));
System.out.println(MyGeoPoint.rotatePoint(new MyGeoPoint(5, -2), new MyGeoPoint(3, -4), 135));


long: -5 lat: 5
long: 5 lat: -5
long: 1.5980762114 lat: 3.9641016151
long: 0.1715728753 lat: -4

Die Ergebnisse sind alle richtig. Alle auf dem Blatt nachgerechnet. (Die rotate Funktion rotiert mom. gegen den Uhrzeigersinn)

Und die intersect Methode ist definitiev richtig. Weiß auch nicht was es mir jetzt helfen sollte das nochmal auf int zurückzusetzen, wo ich das am Anfang auch schonmal probiert hatte aber nichts genützt hat.

 

[R3ddy]

Wie hast du den geprüft, dass 4-mal true herrauskommen muss? Ich habe es grade mal mit einem völlig anderen Rechenweg (ohne Drehmatrix) nachgerechtet und erhalte false, true, true und false also genau das, was auch dein Programm sagt!

 

[anonymous1234]

Wie hast du den geprüft, dass 4-mal true herrauskommen muss? Ich habe es grade mal mit einem völlig anderen Rechenweg (ohne Drehmatrix) nachgerechtet und erhalte false, true, true und false also genau das, was auch dein Programm sagt!

Die Werte habe ich von Google Earth. Dort werden die 4 Punkte so angezeigt, dass diese innerhalb des GroundOverlays liegen (sogar mit einer kleiner Pufferzone).
Und in einem weiteren unabhängigen Programm wird es auch so angezeigt.


Ansonsten sind vll. die Achsen nicht proportional zu einander? Kann dazu aber auch nichts hilfreiches finden.

 

[R3ddy]

Jetzt wo du es sagst, leuchtet es mir ein.

Dein Problem ist, dass du ein krummliniges Koordinatensystem hast, wenn du dies als "normales" Koordinatensystem annimmst tritt das Problem auf, dass deine Achsen nur auf dem Äquator normiert sind (guck im Atlas: nur am Äquator sind es näherungsweise Quadrate - in unseren Breiten eher Rechtecke) deshalb kannst du eine Drehung nicht auf einfache Weise realisieren. Ich überlege mir mal was.

 

[anonymous1234]

Jetzt wo du es sagst, leuchtet es mir ein.

Dein Problem ist, dass du ein krummliniges Koordinatensystem hast, wenn du dies als "normales" Koordinatensystem annimmst tritt das Problem auf, dass deine Achsen nur auf dem Äquator normiert sind (guck im Atlas: nur am Äquator sind es näherungsweise Quadrate - in unseren Breiten eher Rechtecke) deshalb kannst du eine Drehung nicht auf einfache Weise realisieren. Ich überlege mir mal was.

Google Earth benutzt angeblich die Mercator Projektion, welche laut wiki winkelgetreu ist (in kleinen Gebieten). Daher dachte ich, dass das schon irgendwie klappt mit der Rotation.
Aber je länger ich darüber nachdenke, ist damit wohl nur die Darstellung gemeint, aber nicht die eigentlichen Koordinaten. Frage ist jetzt also, wie man die nicht proportionalen Achsen berücksichtigt.

Wäre auf jeden Fall großartig, wenn dir noch was einfällt.

 

[R3ddy]

Versuch es mal so (wenn es nicht klappt änder mal das Vorzeichen des Winkels):

public static MyGeoPoint rotatePoint(MyGeoPoint point, MyGeoPoint origion, double degree)
{
	double x =  origion.longitude	+ (Math.cos(Math.toRadians(degree)) * (point.longitude - origion.longitude) - Math.sin(Math.toRadians(degree))	* (point.latitude - origion.latitude) / Math.abs(Math.cos(Math.toRadians(origion.latitude)));
	double y = origion.latitude + (Math.sin(Math.toRadians(degree)) * (point.longitude - origion.longitude) * Math.abs(Math.cos(Math.toRadians(origion.latitude))) + Math.cos(Math.toRadians(degree))	* (point.latitude - origion.latitude));
	return new MyGeoPoint(x, y);
}

Hab den Code nicht in Java getestet. Falls ne Klammer zu oder ähnliches fehlt musst du die ergänzen.

 

[anonymous1234]

Versuch es mal so

Es scheint jetzt zu klappen.
Auch bei Punkten knapp außerhalb des Rechtecks scheint das richtige Ergebnis (false) rauszukommen.

Könntest du mir auch erklären, wie das jetzt funktioniert, bzw. was du warum geändert hast?

Auf jeden Fall vielen Dank.

 

[R3ddy]

Ich versuch es mal (hoffe man kann es nachvollziehen)

Wie bereits in einem vorherigen Posting geschrieben handelt es sich bei der Angabe von Breiten- und Längengraden um ein krummliniges Koordinatensystem. Dies hat zur Folge, das 1 Längengrad am Äquator 111 km, beim 60. Breitengrad nur noch 55,5 km und an den Polen 0 km entspricht.

Der Stauchungsfaktor berechnet sich dabei aus den Cosinus des Breitengrades.

Um nun eine Drehung (näherungsweise) durchzuführen muss diese Stauchung rückgängig gemacht werden. Dies gelingt durch Multiplikation (<-nicht Division, da des KO-System gestaucht ist) des Längengrades mit dem Stauchungsfaktor.

Für den Längengrad muss die Stauchung des KO-Systems dann natürlich wieder vollzogen werden, indem mit dem Kehrwert des Stauchungsfaktors multipliziert wird. Wenn man dann noch schön kürzt führt das zu den gemachten Änderungen (die du selber leicht durch vergleich finden kannst).