Bestimmung, ob sich ein Lat-Long-Rechteck und ein Kreis auf einer Kugel überschneiden

Question

Angenommen, ich habe Folgendes:

• Ein Bereich, definiert durch minimalen und maximalen Breiten- und Längengrad (üblicherweise ein 'Breiten-Längen-Rechteck', obwohl es tatsächlich nur in bestimmten Projektionen rechteckig ist).
• Ein Kreis, definiert durch einen Mittelpunkt Breiten- und Längengrad und einem Radius.

Wie kann ich feststellen:

1. Ob sich die beiden Formen überschneiden?
2. Ob der Kreis vollständig im Rechteck enthalten ist?

Ich suche nach einer vollständigen Formel/Algorithmus, anstatt einer Lektion in Mathematik.

Answer 1

Warnung: Dies kann schwierig sein, wenn die Kreise / "Rechtecke" große Teile der Kugel umfassen, z.B.:

"Rechteck": min long = -90deg, max long = +90deg, min lat = +70deg, max lat = +80deg

Kreis: Zentrum = lat = +85deg, long = +160deg, Radius = 20deg (z.B. wenn Punkt A auf dem Kreis liegt und Punkt C das Zentrum des Kreises ist und Punkt O das Zentrum der Kugel ist, dann beträgt der Winkel AOC = 40deg).

Diese schneiden sich, aber die Mathematik hat wahrscheinlich mehrere Fälle zu überprüfen: Schnittpunkt/Enthalten. Die folgenden Punkte liegen auf dem oben beschriebenen Kreis: P1=(+65deg lat,+160deg long), P2=(+75deg lat, -20deg long). P1 liegt außerhalb des "Rechtecks" und P2 liegt innerhalb des "Rechtecks", daher schneiden sich Kreis/"Rechteck" mindestens an 2 Punkten.

OK, hier ist mein Versuch, eine Lösungsskizze zu geben:

---

Nehmen wir C = Kreiszentrum mit Radius R (ausgedrückt als sphärischer Winkel wie oben). C hat die Breitengrade LATC und Längengrade LONGC. Da das Wort "Rechteck" hier irgendwie irreführend ist (Linien konstanter Breitengrade sind keine Segmente großer Kreise), werde ich den Begriff "Begrenzungsrahmen" verwenden.

• Funktion InsideCircle(P) gibt +1,0 oder -1 zurück: +1, wenn der Punkt P innerhalb des Kreises liegt, 0 wenn der Punkt P auf dem Kreis liegt, und -1 wenn der Punkt P außerhalb des Kreises liegt: Die Berechnung des Großkreisabstands D (als sphärischer Winkel ausgedrückt) zwischen C und einem beliebigen Punkt P gibt Aufschluss darüber, ob P innerhalb des Kreises liegt oder nicht: InsideCircle(P) = Vorzeichen(R-D) (Wie Benutzer @Die in Sente erwähnt hat, wurden Großkreisabstände bereits anderswo in diesem Forum gefragt)

• Definiere PANG(x) = der Hauptwinkel von x = MOD(x+180deg, 360deg)-180deg. PANG(x) liegt immer zwischen -180deg und +180deg, inklusive (+180deg sollte auf -180deg abgebildet werden).

• Um den Begrenzungsrahmen zu definieren, benötigen Sie 4 Zahlen, aber es gibt eine leichte Problematik mit dem Längengrad. LAT1 und LAT2 repräsentieren die Begrenzungsbreiten (unter der Annahme, dass LAT1 < LAT2); dort besteht keine Mehrdeutigkeit. LONG1 und LONG2 repräsentieren die Begrenzungslängengrade eines Längengradintervalls, aber das wird knifflig, und es ist einfacher, dieses Intervall als Zentrum und Breite umzuschreiben, mit LONGM = das Zentrum dieses Intervalls und LONGW = Breite. BEACHTEN Sie, dass es immer 2 Möglichkeiten für Längengradintervalle gibt. Sie müssen angeben, um welche dieser Fälle es sich handelt, ob Sie den 180deg-Meridian einschließen oder ausschließen, z.B. das kürzeste Intervall von -179deg bis +177deg hat LONGM = +179deg und LONGW = 4deg, aber das andere Intervall von -179deg bis +177deg hat LONGM = -1deg und LONGW = 356deg. Wenn Sie naiv "normale" Vergleiche mit dem Intervall [-179,177] durchführen, werden Sie das größere Intervall verwenden und das ist wahrscheinlich nicht das, was Sie wollen. Als Randnotiz, Punkt P, mit Breitengrad LATP und Längengrad LONGP, liegt innerhalb des Begrenzungsrahmens, wenn beide der folgenden Aussagen wahr sind:

  • LAT1 <= LATP und LATP <= LAT2 (dieser Teil ist offensichtlich)
  • abs(PANG(LONGP-LONGM)) < LONGW/2

Der Kreis schneidet den Begrenzungsrahmen, wenn IRGENDEIN der folgenden Punkte P in PTEST = Vereinigung (PCORNER, PLAT, PLONG), wie unten beschrieben, nicht alle das gleiche Ergebnis für InsideCircle() zurückgeben:

• PCORNER = die 4 Ecken des Begrenzungsrahmens
• die Punkte PLAT auf den Seiten des Begrenzungsrahmens (es gibt entweder keine oder 2), die dieselbe Breite wie das Zentrum des Kreises teilen, wenn LATC zwischen LAT1 und LAT2 liegt, in welchem Fall diese Punkte den Breitengrad LATC und den Längengrad LONG1 und LONG2 haben.
• die Punkte PLONG auf den Seiten des Begrenzungsrahmens (es gibt entweder keine oder 2 oder 4!), die dieselbe Länge wie das Zentrum des Kreises teilen. Diese Punkte haben ENTWEDER Längengrad = LONGC ODER Längengrad PANG(LONGC-180). Wenn abs(PANG(LONGC-LONGM)) < LONGW/2 gilt, dann ist LONGC ein gültiger Längengrad. Wenn abs(PANG(LONGC-180-LONGM)) < LONGW/2 gilt, dann ist PANG(LONGC-180) ein gültiger Längengrad. Einer oder beide oder keiner dieser Längengrade können innerhalb des Längengradintervalls des Begrenzungsrahmens liegen. Wählen Sie Punkte PLONG mit gültigen Längengraden und Breitengraden LAT1 und LAT2.

Diese Punkte PLAT und PLONG wie oben aufgeführt sind die Punkte auf dem Begrenzungsrahmen, die dem Kreis am "nächsten" liegen (wenn die Ecken es nicht sind; ich verwende "nächste" im Sinne von Breiten- und Längengradentfernung und nicht Großkreisentfernung) und decken die Fälle ab, in denen das Zentrum des Kreises auf einer Seite der Begrenzungslinie des Begrenzungsrahmens liegt, aber Punkte auf dem Kreis "durchschlüpfen" die Begrenzungslinie des Begrenzungsrahmens.

Wenn alle Punkte P in PTEST InsideCircle(P) == +1 zurückgeben (alle innerhalb des Kreises), dann enthält der Kreis den Begrenzungsrahmen in seiner Gesamtheit.

Wenn alle Punkte P in PTEST InsideCircle(P) == -1 zurückgeben (alle außerhalb des Kreises), dann ist der Kreis vollständig im Begrenzungsrahmen enthalten.

Ansonsten gibt es mindestens einen Schnittpunkt zwischen dem Kreis und dem Begrenzungsrahmen. Beachten Sie, dass dies nicht berechnet, wo diese Punkte sind, obwohl, wenn Sie irgendeine 2 Punkte P1 und P2 in PTEST nehmen, wo InsideCircle(P1) = -InsideCircle(P2), könnten Sie einen Schnittpunkt (ineffizient) durch Bisektion finden. (Wenn InsideCircle(P) 0 zurückgibt, haben Sie einen Schnittpunkt, obwohl Gleichheit in der Gleitkommamathematik im Allgemeinen nicht vertraut werden sollte.)

Es gibt wahrscheinlich eine effizientere Möglichkeit, dies zu tun, aber das oben Genannte sollte funktionieren.

Answer 2

Verwenden Sie die stereographische Projektion. Alle Kreise (insbesondere Breitenkreise, Längenkreise und Ihr Kreis) werden auf Kreise (oder Linien) in der Ebene abgebildet. Jetzt geht es nur noch um Kreise und Linien in der ebenen Geometrie (besser gesagt, alle Längengrade sind Linien durch 0, und alle Breitengrade sind Kreise um 0)

Answer 3

Wie wäre es damit?

Finde den Vektor v, der das Zentrum des Rechtecks, Punkt Cr, mit dem Zentrum des Kreises verbindet. Finde den Punkt i, an dem v das Rechteck schneidet. Wenn ||i-Cr|| + r > ||v|| ist, dann schneiden sie sich.

Anders ausgedrückt sollte die Länge des Segments innerhalb des Rechtecks plus die Länge des Segments innerhalb des Kreises größer sein als die Gesamtlänge (von v, dem Zentrum-Verbindungslinien-Segment).

Die Suche nach dem Punkt i könnte knifflig sein, besonders wenn er auf einer Längenkante liegt, aber du solltest in der Lage sein, schneller etwas zu finden als ich.

Bearbeitung: Diese Methode kann nicht bestimmen, ob der Kreis vollständig innerhalb des Rechtecks liegt. Du müsstest den Abstand von seinem Zentrum zu allen vier Kanten des Rechtecks finden.

Bearbeitung: Das obige ist falsch. Es gibt einige Fälle, wie Federico Ramponi vorgeschlagen hat, in denen es sogar in der euklidischen Geometrie nicht funktioniert. Ich werde eine andere Antwort posten. Bitte nimm diese zurück und fühle dich frei, sie abzulehnen. Ich werde sie bald löschen.

Answer 4

• Ja, wenn die Ecken der Box den Kreis-Mittelpunkt enthalten.
• Ja, wenn eine der Ecken der Box innerhalb des Radius des Kreis-Mittelpunkts liegt.
• Ja, wenn die Box den Längengrad des Kreis-Mittelpunkts enthält und der Längengrad-Schnitt der Box-Breite, der am nächsten zum Breitengrad des Kreis-Mittelpunkts liegt, innerhalb des Radius des Kreis-Mittelpunkts liegt.
• Ja, wenn die Box den Breitengrad des Kreis-Mittelpunkts enthält und der Punkt auf Abstand Radius vom Kreis-Mittelpunkt auf dem kürzesten Schnitt-Bearing "jenseits" des nächsten Box-Längengrads liegt; wobei das kürzeste Schnitt-Bearing bestimmt wird, indem der initiale Kurs vom Kreis-Mittelpunkt zu einem Punkt bei Breitengrad Null und einem Längengrad, der pi/2 "jenseits" des nächsten Box-Längengrads liegt, gefunden wird.
• Nein, sonst.

Annahmen:

• Sie können den Initial-Kurs von Punkt A zu Punkt B finden.
• Sie können die Entfernung zwischen zwei Punkten finden.

Der erste Check ist trivial. Der zweite Check erfordert nur das Finden der vier Entfernungen. Der dritte Check erfordert nur das Finden der Entfernung vom Kreis-Mittelpunkt zum (nächsten-Box-Breitengrad, Kreis-Mittelpunkt-Längengrad).

Der vierte Check erfordert das Finden der Längengrad-Linie der Begrenzungsbox, die dem Kreis-Mittelpunkt am nächsten liegt. Finden Sie dann das Zentrum des Großkreises, auf dem diese Längengrad-Linie ruht, das am weitesten vom Kreis-Mittelpunkt entfernt ist. Finden Sie den initialen Kurs vom Kreis-Mittelpunkt zum Großkreis-Mittelpunkt. Finden Sie den Punkt Radius vom Kreis-Mittelpunkt auf diesem Kurs. Wenn dieser Punkt auf der anderen Seite der nächsten Längengrad-Linie vom Kreis-Mittelpunkt liegt, dann schneiden sich Kreis und Begrenzungsbox auf dieser Seite.

Es scheint mir, dass hier ein Fehler sein sollte, aber ich konnte ihn nicht finden.

Das eigentliche Problem, das ich nicht lösen kann, besteht darin, die Begrenzungsbox zu finden, die den Kreis perfekt enthält (für Kreise, die keinen Pol enthalten). Die Peilung zum Breitengrad min/max scheint eine Funktion des Breitengrads des Kreis-Mittelpunkts und des Kreis-Radius / (Kugelumfang / 4) zu sein. In der Nähe des Äquators fällt sie auf pi/2 (Ost) oder 3*pi/2 (West). Wenn sich der Mittelpunkt dem Pol nähert und der Radius den Kugelumfang / 4 erreicht, nähert sich die Peilung null (Nord) oder pi (Süd) an.

Answer 5

Noch ein Versuch...

Ich glaube, die Lösung besteht darin, einen Satz von Punkten zu testen, so wie Jason S vorgeschlagen hat, aber ich stimme seiner Auswahl von Punkten nicht zu, die meiner Meinung nach mathematisch falsch ist.

Sie müssen die Punkte an den Seiten der Breiten/Längen-Box finden, wo die Entfernung zum Mittelpunkt des Kreises ein lokales Minimum oder Maximum ist. Fügen Sie diese Punkte zu den Ecken hinzu und dann sollte der obige Algorithmus korrekt sein.

D.h., wobei die Längengrad die x-Dimension und der Breitengrad die y-Dimension ist, lassen Sie jede Seite der Box eine parametrische Kurve P(t) = P0 + t (P1-P0) für 0 <= t <= 1.0 sein, wobei P0 und P1 zwei benachbarte Ecken sind.

Lassen Sie f(P) = f(P.x, P.y) der Abstand vom Mittelpunkt des Kreises sein.

Dann ist f (P0 + t (P1-P0)) eine Abstandsfunktion von t: g(t). Finden Sie alle Punkte, an denen die Ableitung der Abstandsfunktion null ist: g'(t) == 0. (Natürlich Lösungen außerhalb des Bereichs 0 <= t <= 1.0 verwerfen)

Leider muss dies die Null eines transzendentalen Ausdrucks finden, daher gibt es keine geschlossene Formulierung. Diese Art von Gleichung kann nur durch Newton-Raphson-Iteration gelöst werden.

OK, ich verstehe, dass Sie Code wollten, nicht Mathe. Aber die Mathematik ist alles, was ich habe.