Bestimmen, ob sich ein lat-long Rect und ein Kreis auf einer Kugel überlappen

• Ja, wenn die Ecken der Box den Kreismittelpunkt enthalten.
• Ja, wenn eine der Boxenecken innerhalb des Radius von Kreismittelpunkt liegt.
• Ja, wenn das Feld den Längengrad von Kreismittelpunkt enthält und der Längengradschnittpunkt des Kastens, der dem Kreismittelpunkt am nächsten liegt, Breitengrad innerhalb des Radius von Kreismittelpunkt ist.
• Ja, wenn das Feld die Breite des Kreismittelpunkts und der Punkt im Radiusabstand vom Kreismittelpunkt auf dem kürzesten Schnittpunktlager "jenseits" der nächsten Boxlänge enthält; wobei das Kürzeste-Schnitt-Peilung bestimmt wird, indem das Anfangs-Peilen von der Kreismitte zu einem Punkt bei der Breitengrße Null und einer Länge, die pi / 2 "jenseits" der nächsten Box-Länge ist, gefunden wird.
• Nein, sonst.

Annahmen:

• Sie können die Anfangsausrichtung eines Mindestkurses von Punkt A nach Punkt B finden.
• Sie können die Entfernung zwischen zwei Punkten finden.

Die erste Überprüfung ist trivial. Die zweite Überprüfung erfordert nur die Suche nach den vier Entfernungen. Die dritte Überprüfung erfordert nur die Suche nach der Entfernung von Kreis-Zentrum zu (nächstliegende-Box-Breite, Kreis-Zentrum-Länge).

Die vierte Überprüfung erfordert das Auffinden der Längengradlinie der Begrenzungsbox, die der Kreismitte am nächsten ist. Dann finden Sie das Zentrum des großen Kreises, auf dem die längste Linie liegt, die vom Kreismittelpunkt am weitesten entfernt ist. Finde das Anfangslager vom Kreismittelpunkt bis zum Großkreiszentrum. Finden Sie den Punkt Kreis-Radius von Kreis-Zentrum auf diesem Lager. Befindet sich dieser Punkt auf der anderen Seite der nächstgelegenen Längengradlinie von der Kreismitte aus, schneiden sich der Kreis und die Begrenzungsbox auf dieser Seite.

Es scheint mir, dass es einen Fehler darin geben sollte, aber ich konnte es nicht finden.

Das eigentliche Problem, das ich nicht lösen kann, ist, die Bounding-Box zu finden, die den Kreis perfekt enthält (für Kreise, die keinen Pol enthalten). Die Peilung zum Breitengrad min / max scheint eine Funktion der Breite von Kreismittelpunkt und Kreisradius / (Kugelumfang / 4) zu sein. In der Nähe des Äquators fällt es auf Pi / 2 (Osten) oder 3 * Pi / 2 (Westen). Wenn sich das Zentrum dem Pol nähert und der Radius sich dem Kugelumfang / 4 nähert, nähert sich das Lager Null (Nord) oder Pi (Süd).

Warnung: Dies kann schwierig sein, wenn die Kreise / "Rechtecke" große Teile der Sphäre überspannen, z. B .:

"Rechteck": min lang = -90 °, max lang = + 90 °, min lat = +70 °, max lat = + 80 °

circle: center = lat = + 85deg, long = + 160deg, radius = 20deg (wenn sich zB Punkt A auf dem Kreis befindet und Punkt C der Mittelpunkt des Kreises ist und Punkt O der Mittelpunkt der Kugel ist, dann Winkel AOC = 40 Grad ).

Diese kreuzen sich, aber die Mathematik hat wahrscheinlich mehrere Fälle, um die Schnittmenge / Eindämmung zu überprüfen. Die folgenden Punkte liegen auf dem oben beschriebenen Kreis: P1 = (+ 65 Grad lat, + 160 Grad lang), P2 = (+ 75 Grad Lat, -20 Grad lang). P1 ist außerhalb des "Rechtecks" und P2 ist innerhalb des "Rechtecks", so dass sich der Kreis / das "Rechteck" in mindestens 2 Punkten schneidet.

OK, hier ist meine Aufnahme für einen Überblick über die Lösung:

Sei C = Kreismittelpunkt mit Radius R (ausgedrückt als sphärischer Winkel wie oben). C hat den Breitengrad LATC und den Längengrad LONGC. Da das Wort "Rechteck" hier etwas irreführend ist (Zeilen mit konstanter Breite sind keine Segmente von Großkreisen), verwende ich den Begriff "Begrenzungsbox".

• Funktion InsideCircle(P) gibt + 1,0 zurück, oder -1: +1, wenn Punkt P innerhalb des Kreises liegt, 0 wenn Punkt P auf dem Kreis ist, und -1 wenn Punkt P liegt außerhalb des Kreises: Berechnung der Großkreisdistanz D (ausgedrückt als Kugelwinkel) zwischen C und einem beliebigen Punkt P zeigt an, ob P innerhalb des Kreises liegt: InsideCircle(P) = sign(R-D) (Wie Benutzer @Die in Sente erwähnt, Großkreis Entfernungen wurden in diesem Forum an anderer Stelle gefragt)

• Definieren Sie PANG(x) = den Hauptwinkel von x = MOD (x + 180 °, 360 °) -180 °. PANG(x) liegt immer zwischen -180deg und + 180deg (+ 180deg sollte -180deg zugeordnet werden).

• Um die Bounding Box zu definieren, müssen Sie 4 Zahlen kennen, aber es gibt ein kleines Problem mit der Länge. LAT1 und LAT2 stellen die begrenzenden Breiten dar (unter der Annahme LAT1 & lt; LAT2); Da ist keine Zweideutigkeit. LONG1 und LONG2 stellen die Begrenzungslänge eines Längenintervalls dar, aber dies wird schwierig, und es ist einfacher, dieses Intervall als Zentrum und Breite neu zu schreiben, wobei LONGM = das Zentrum dieses Intervalls und LONGW = Breite ist. Beachten Sie, dass es immer 2 Möglichkeiten für Längenintervalle gibt. Sie müssen angeben, welcher dieser Fälle es ist, ob Sie den 180 Grad-Meridian einschließen oder ausschließen, z. 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 versuchen, "normale" Vergleiche mit dem Intervall [-179,177] zu machen, werden Sie am Ende das größere Intervall verwenden, und das ist wahrscheinlich nicht das, was Sie wollen. Nebenbei, Punkt P, mit Breitengrad LATP und Längengrad LONGP, ist innerhalb des Begrenzungsrahmens, wenn beide der folgenden Bedingungen zutreffen:

  • LAT1 & lt; = LATP und LATP & lt; = LAT2 (dieser Teil ist offensichtlich)
  • abs (PANG (LANGP-LONGM)) & lt; LONGW / 2

Der Kreis schneidet die Begrenzungsbox, wenn einer der folgenden Punkte P in PTEST = union (PCORNER, PLAT, PLONG) wie unten beschrieben nicht alle dasselbe Ergebnis für InsideCircle() :

• PCORNER = die Ecken der Bounding Box
• die Punkte PLAT auf den Seiten der Begrenzungsbox (es gibt entweder keine oder 2), die den gleichen Breitengrad wie die Mitte des Kreises haben, wenn LATC zwischen LAT1 und LAT2 liegt, in diesem Fall haben diese Punkte der Breitengrad LATC und Längengrad LONG1 und LONG2.
• Die Punkte PONG auf den Seiten der Begrenzungsbox (es gibt entweder keine oder 2 oder 4!), die die gleiche Länge wie die Mitte des Kreises haben. Diese Punkte haben ENTWEDER Längengrad = LONGC ODER Längengrad PANG (LONGC-180). Wenn abs (PANG (LANGZ-LONGM)) & lt; LONGW / 2 dann ist LONGC eine gültige Länge. Wenn abs (PANG (LONGC-180-LONGM)) & lt; LONGW / 2 dann PANG (LONGC-180) ist eine gültige Länge. Eine oder beide oder keine dieser Längen können innerhalb des Längenintervalls der Begrenzungsbox liegen. Wählen Sie die Punkte PONG mit gültigen Längen und Breiten LAT1 und LAT2.

Diese Punkte PLAT und PLONG sind die Punkte auf der Begrenzungsbox, die dem Kreis "am nächsten" sind (wenn die Ecken nicht sind; ich verwende "am nächsten" in Anführungszeichen, im Sinne von lat / long distance und nicht Großkreis-Entfernung), und decken die Fälle ab, in denen der Mittelpunkt des Kreises auf einer Seite der Grenze des Begrenzungsrahmens liegt, aber auf dem Kreis "über die Grenze des Begrenzungsrahmens" zeigt.

Wenn alle Punkte P in PTEST InsideCircle(P) == +1 (alle innerhalb des Kreises) zurückgeben, enthält der Kreis die Begrenzungsbox in ihrer Gesamtheit.

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

Ansonsten gibt es mindestens einen Schnittpunkt zwischen dem Kreis und der Begrenzungsbox.Beachten Sie, dass dies nicht berechnet, wo diese Punkte sind, obwohl, wenn Sie irgendwelche 2 Punkte P1 und P2 in PTEST nehmen, wo InsideCircle (P1) = -InsideCircle (P2), dann können Sie einen Schnittpunkt (ineffizient) durch Bisektion finden. (Wenn InsideCircle (P) 0 zurückgibt, haben Sie einen Schnittpunkt, obwohl die Gleichheit in Fließkomma-Berechnungen im Allgemeinen nicht vertrauenswürdig ist.)

Es gibt wahrscheinlich einen effizienteren Weg, dies zu tun, aber das obige sollte funktionieren.

Wie wäre es damit?

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

Mit anderen Worten, die Länge des Segments innerhalb des Rechtecks ​​plus die Länge des Segments innerhalb des Kreises sollte größer sein als die Gesamtlänge (von v , das Verbindungssegment in der Mitte).

Das Finden des Punktes i sollte der schwierigste Teil sein, besonders wenn es auf eine Longitudinalkante fällt, aber Sie sollten etwas schneller finden können als ich.

Bearbeiten: Diese Methode kann nicht feststellen, ob der Kreis vollständig innerhalb des Rechtecks ​​liegt. Sie müssen den Abstand von seiner Mitte zu allen vier Kanten des Rechtecks ​​dafür finden.

Bearbeiten: Das obige ist falsch. Es gibt einige Fälle, wie Federico Ramponi vorgeschlagen hat, wo es nicht einmal in euklidischer Geometrie funktioniert. Ich werde eine andere Antwort posten. Bitte akzeptieren Sie dies nicht und fühlen Sie sich frei, abzustimmen. Ich werde es in Kürze löschen.

Noch ein Versuch ...

Ich denke, die Lösung besteht darin, eine Reihe von Punkten zu testen, genau wie Jason S. vorgeschlagen hat, aber ich stimme seiner Auswahl von Punkten nicht zu, was meiner Meinung nach mathematisch falsch ist.

Sie müssen die Punkte an den Seiten der lat / long Box finden, wo der Abstand zur Mitte des Kreises ein lokales Minimum oder Maximum ist. Fügen Sie diese Punkte zur Menge der Ecken hinzu, und dann sollte der obige Algorithmus korrekt sein.

I.e, lasst die Länge die x-Dimension sein und die Breite die y-Dimension, lass jede Seite der Box sei eine parametrische Kurve P (t) = P0 + t (P1-P0) für o & lt; = t & lt; = 1,0, wobei P0 und P1 sind zwei benachbarte Ecken.

Sei f (P) = f (P.x, P.y) die Entfernung vom Mittelpunkt des Kreises.

Dann ist f (P0 + t (P1-P0)) eine Abstandsfunktion von t: g (t). Finde alle Punkte, an denen die Ableitung der Abstandsfunktion Null ist: g '(t) == 0. (Verwerfen von Lösungen überdimensioniert die Domäne 0 & lt; = t & lt; = 1,0, natürlich)

Leider muss dies den Nullpunkt eines transzendentalen Ausdrucks finden, also gibt es keine geschlossene Form. Diese Art von Gleichung kann nur durch Newton-Raphson-Iteration gelöst werden.

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

Für die Antwort auf die euklidische Geometrie siehe: Kreis-Rechteck-Kollisionserkennung (Schnittpunkt)