Sphärische Trigonometrie: Tangenten- und Sekanten-n-Ecke in/an Kreisen

30/12/2007 - 19:10 von Sebastian Suchanek | Report spam
Hallo NG!

Die eigentliche Vorgeschichte zu diesem Problem ist etwas lànger und
kann bei Interesse teilweise in <fkuk84$3po$1@suchanek.de> ff. nachgelesen.
Die Kurzfassung davon ist wie folgt: In einer Datenbank möchte in
Geo-Koordinaten in Form von zwei Winkelangaben für Làngen- und
Breitengrad speichern. Das wird aller Voraussicht nach in der Form von
zwei Fließkommazahlen geschehen, weil ich mit aktuell Zweifel daran
habe, daß die GIS-Erweiterungen der mir zur Verfügung stehenden
Datenbank tatsàchlich das leistet, was ich möchte.
Zumal sich die Nutzung der Koordinaten in 99% der Fàlle auf reines
Anzeigen beschrànken wird und ich mir derzeit nur einen einzigen Fall
einer "richtigen" Auswertung dieser Angaben vorstellen kann.

Diese Auswertung ist dafür umso aufwendiger: Ich könnte mir eine
Datenbankabfrage der Art "Gib mir alle Eintràge, die innerhalb eines
Kreises mit dem Radius r um den Punkt X(Lat/Lon) liegen" vorstellen.
OK, prinzipiell làßt sich die Großkreis-Entfernung d zwischen zwei
Punkten einfach berechnen:

d = arccos[sin Lat1 * sin Lat2 +
cos Lat1 * cos Lat2 * cos(Lon2-Lon1)] * \pi * R / 180°

(mit Lat = Breite und Lon = Lànge der beiden Punkte.)
Das praktische Problem dabei ist, daß diese Rechnung sechs "teure"
trigonometrische Funktionen umfaßt, welche die Datenbank für jeden
einzelnen von potentiell mehreren 10.000 Eintràgen berechnen müsste.
Da führt natürlich zu einem erheblichen Rechenzeitbedarf...

Was Datenbanken im Allgemeinen aber recht gut ("billig") können, ist
Eintràge finden, die innerhalb eines gegebenen Intervalls liegen. Das
hat mich auf eine Idee gebracht: Man könnte ja die Datenbank dazu
veranlassen, alle Punkte, die *sicher* innerhalb des Kreises liegen ohne
o.g. Rechnung ins Ergebnis auzunehmen und ebenso alle Punkte, die
*sicher* außerhalb liegen entsprechend zu ignorieren. Die o.g.
Berechnung müsste dann nur für - hoffentlich kleinen - Rest durchgeführt
werden.
In der Ebene sàhe das dann so aus:

+-+
| - - |
| /+-+\ |
|| | | ||
| | * | |
|| | | ||
| \+-+/ |
| - - |
+-+

(Sorry für das schlechte ASCII-Bildchen... :-))
Alles was innerhalb des inneren Quadrats liegt, ist sicher im Kreis,
alles außerhalb des àußeren Quadrates sicher außerhalb des Kreises. Das
Einschließen bzw. Ausschließen von potentiellen Treffern làßt sich in
diesen Gebieten auf einfaches Prüfen von "(x,y) ist (nicht) in Intervall
([a, b], [c, d])" reduzieren.
In der Ebene funktioniert das wunderbar einfach und auch für kleine
Gebiete auf der Erdoberflàche könnte man das noch mit geringer
Fehlerrate anwenden.
Schwierig wird's aber bei großen Radien und/oder in Polnàhe.

Lange Rede, kurzer Sinn: Kennt Ihr evtl. einen Algorithmus, der abhàngig
von Mittelpunkt und Radius Parameter für einen Kreis, ein Drei- oder
Viereck ausspuckt, der/das in den gesuchten Kreis gerade eben
einbeschrieben ist bzw. den gesuchten Kreis gerade eben tangiert?
(Man muß ja nicht mit Gewalt jedes Mal das Rad neu erfinden... ;-))
Der Algorithmus kann auch ruhig etwas rechenintensiver sein - er muß ja
pro - seltener - Anfrage nur einmal ausgeführt werden und nicht pro
Datensatz.


Tschüs,

Sebastian

PS: Alternativ kann mir auch jemand beim Verstehen von MySQL-GIS helfen.
;-)
 

Lesen sie die antworten

#1 earthnut
31/12/2007 - 20:27 | Warnen spam
Sebastian Suchanek wrote:

In der Ebene sàhe das dann so aus:

+-+
| - - |
| /+-+\ |
|| | | ||
| | * | |
|| | | ||
| \+-+/ |
| - - |
+-+

(Sorry für das schlechte ASCII-Bildchen... :-))
Alles was innerhalb des inneren Quadrats liegt, ist sicher im Kreis,
alles außerhalb des àußeren Quadrates sicher außerhalb des Kreises. Das
Einschließen bzw. Ausschließen von potentiellen Treffern làßt sich in
diesen Gebieten auf einfaches Prüfen von "(x,y) ist (nicht) in Intervall
([a, b], [c, d])" reduzieren.



Ein solches Intervall [Lon-, Lon+] x [Lat-, Lat+] ist auf der
Erdoberflàche kein Rechteck, sondern ein Stück Orangenschale. Daher kann
man da nicht so einfach von Quadraten reden.

Auf jeden Fall reicht es die Latitude im Bereich

Lat +/- delta

zu durchforsten. (delta = d / R * 180 / pi)

Wenn ich mich nicht verrechnet habe, dann genügt es auch die Longitude
nur im Bereich

Lon +/- arcsin[sin delta / cos Lat]

zu betrachten (aber ohne Gewàhr), vorausgesetzt es ist kein Pol nàher
als d an (Lon/Lat).

Schwierig wird's aber bei großen Radien und/oder in Polnàhe.



In Polnàhe (der Einfachheit halber betrachte ich mal nur den Nordpol)
reicht es den Bereich zwischen

Lat - delta

und

pi - Lat - delta

zu durchforsten. Alle Punkte überhalb

pi - Lat - delta

sind automatisch enthalten.

Bastian

Ähnliche fragen