Bestimmen, ob sich ein Lat-Long-Rechteck und ein Kreis auf einer Kugel überlappen

https://stackoverflow.com/questions/394201

23-08-2019
|

Frage

Angenommen, ich habe Folgendes:

Eine Region, die durch den minimalen und maximalen Breiten- und Längengrad definiert ist (üblicherweise ein „Breiten-Längen-Rect“, obwohl es außer in bestimmten Projektionen nicht wirklich rechteckig ist).
Ein Kreis, definiert durch einen Breiten-/Längengrad des Mittelpunkts und einen Radius

Wie kann ich Folgendes feststellen:

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

Ich suche nach einer vollständigen Formel/einem vollständigen Algorithmus und nicht nach einer Lektion in Mathematik an sich.

Lösung

Ja, wenn die Box Ecken der Kreis-Zentrum enthalten.
Ja, wenn eine der Box Ecken sind innerhalb des Radius des Kreises Zentrum.
Ja, wenn das Feld enthält die Länge von Kreis-Mitte und die Länge Kreuzung der Box-Breite am nächsten Kreis-Mitte-Breite innerhalb des Radius des Kreises Zentrums ist.
Ja, wenn das Feld die Breite des Kreises Zentrum enthält und den Punkt am Radius Abstand von Kreis-Zentrum auf kürzestem kreuzungsLager ist „jenseits“ der nächsten Box-Länge; wo kürzesten kreuzungsLager wird durch das Finden der anfänglichen Lager aus circle-Mitte zu einem Punkt bei Null und eine Länge bestimmt, die pi / 2 „jenseits“ der nächsten Box-Länge ist.
Nein, sonst.

Annahmen:

Sie können die anfänglichen Lager eines Mindestkurs von Punkt A nach Punkt B finden.
Sie können den Abstand zwischen zwei Punkten finden.

Die erste Prüfung ist trivial. Die zweite Prüfung erfordert nur die vier Strecken zu finden. Die dritte Überprüfung erfordert nur die Entfernung vom Kreiszentrum finden, um (nächste Box-Breite, Kreis-Mitte-Länge).

Die vierte Überprüfung erfordert die Länge Linie des Begrenzungsrahmen zu finden, die am nächsten zu dem Kreis-Zentrum ist. Dann finden Sie in der Mitte des großen Kreises, auf dem die Länge Linie liegt, die am weitesten vom Kreiszentrum. Finden Sie die Anfangslager von Kreis-Mitte zum Großkreis-Zentrum. Finden Sie den Punkt Kreis-Radius vom Kreiszentrum auf diesem Lager. Wenn dieser Punkt auf der anderen Seite der engsten-Länge-Linie von Kreis-Mitte ist, dann wird der Kreis und Begrenzungsrahmen auf der Seite schneiden.

Es scheint mir, dass es ein Fehler in diesem sein soll, aber ich habe nicht in der Lage gewesen, es zu finden.

Das eigentliche Problem, das ich nicht zu lösen scheinen kann, ist die Begrenzungs-Box zu finden, die perfekt den Kreis enthält (für Kreise, die keinen Pol enthalten). Das Lager auf die geographische Breite min / max erscheint eine Funktion der Breite des Kreiszentrums und circle-Radius / (sphere Umfang / 4) zu sein. In der Nähe des Äquators, fällt es auf pi / 2 (Ost) oder 3 * pi / 2 (West). Da das Zentrum nähert sich den Pol und der Radius nähert Kugelumfang / 4, wobei das Lager gegen Null (Nord) oder PI (Süden).

Andere Tipps

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

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

Kreis: center = lat = + 85deg, long = + 160deg, Radius = 20deg (zB bei Punkt A auf dem Kreis ist, und der Punkt C ist die Mitte des Kreises und Punkt O ist der Mittelpunkt der Kugel, dann Winkel AOC = 40deg ).

Diese

schneiden, aber die Mathematik ist wahrscheinlich mehr Fälle haben, Kreuzung / Eindämmung zu überprüfen. Die folgenden Punkte auf dem Kreis liegen, wie oben beschrieben: P1 = (+ 65deg lat, + 160deg lang), P2 = (+ 75deg lat, -20deg lang). P1 ist außerhalb der „Rechteck“ und P2 ist im Inneren des „Rechteck“ so der Kreis / „Rechteck“ in mindestens 2 Punkten schneiden.

OK, hier ist mein Schuss auf einem Umriss der Lösung:

sei C = Kreismittelpunkt mit dem Radius R (als Kugelwinkel ausgedrückt wie oben). C hat Breite und Länge LATCHE LONGC. Da das Wort „Rechteck“ ist eine Art von hier irreführend (Linien konstanter Breite sind nicht Segmente von großen Kreisen), werde ich die Begriff „Bounding Box“ verwenden.

Funktion InsideCircle(P) Erträge + 1,0 oder -1: +1, wenn der Punkt P innerhalb des Kreises ist, 0, wenn der Punkt P auf dem Kreis ist, und -1, wenn Punkt P der Kreis ist außerhalb: Berechnung der Orthodrome D (ausgedrückt als sphärische Winkel) zwischen C und einem beliebigen Punkt P wird Ihnen sagen, ob oder ob nicht innerhalb des Kreises P ist: InsideCircle(P) = sign(R-D) (As Benutzer @Die in Sente erwähnt, Großkreis Distanzen wurden auf diesem Forum an anderer Stelle)
Definieren PANG(x) = der Hauptwinkel von x = MOD (x + 180 Grad, 360 Grad) -180deg. PANG(x) immer zwischen -180deg und + 180 Grad, inklusive (+ 180 Grad sollten -180deg Karte).
den Begrenzungsrahmen zu definieren, müssen Sie 4 Zahlen kennen, aber es gibt ein kleines Problem mit Länge. LAT1 und LAT2 stellen die Begrenzungs Breiten (unter der Annahme LAT1
- LAT1 <= LATP und LATP <= LAT2 (das Teil liegt auf der Hand)
- abs (PANG (LONGP-LONGM))

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

PCORNER = 4 Ecken Begrenzungsrahmen
die Punkte Plat auf den Seiten des Begrenzungsrahmens (es gibt entweder keine oder 2), die die gleiche Breite wie den Mittelpunkt des Kreises teilen, , wenn LATCHE ist zwischen LAT1 und LAT2, wobei diese Punkte die Breite und Länge LATCHE Long1 und lang2.
die Punkte PLONG auf den Seiten des Begrenzungsrahmens (es gibt entweder keine oder 2 oder 4!), Die die gleiche Länge wie den Mittelpunkt des Kreises teilen. Diese Punkte haben ENTWEDER Länge = LONGC ODER Länge PANG (LONGC-180). Wenn abs (PANG (LONGC-LONGM))

Diese Punkte PLAT und PLONG wie oben aufgeführt sind die Punkte auf dem Begrenzungsrahmen, die „am nächsten“ den Kreis sind (wenn die Ecken sind nicht, ich „am nächsten“ in Anführungszeichen, im Sinne von lat / Langstrecke und nicht Orthodrome), und die Fälle, in denen die Mitte des Kreises auf der einen Seite liegt der Randbegrenzungsrahmen aber Punkte auf dem Kreis „schleichen über“ den Begrenzungsrahmen Grenze.

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

Wenn alle Punkte P in PTEST Rückkehr InsideCircle(P) == -1 (alle außerhalb des Kreises), dann wird der Kreis, die vollständig innerhalb des Begrenzungsrahmens.

Ansonsten gibt es mindestens einen Schnittpunkt zwischen dem Kreis und dem Begrenzungsrahmen. Beachten Sie, dass diese Berechnung nicht, wo diese Punkte sind, obwohl, wenn Sie nehmen jede 2 Punkte P1 und P2 in PTEST wo InsideCircle (P1) = -InsideCircle (P2), dann könnte man einen Schnittpunkt (ineffizienten) von bisection finden. (Wenn InsideCircle (P) 0 zurück, dann haben Sie einen Schnittpunkt, wenn Gleichheit in Gleitpunktarithmetik ist in der Regel nicht zu trauen ist.)

Es ist wahrscheinlich ein effizienter Weg, dies aber die oben zu tun, sollte funktionieren.

Mit dem stereographischer Projektion . Alle Kreise (insbesondere Breiten, Längen und Ihr Kreis) auf Kreise Karte (oder Zeilen) in der Ebene. Jetzt ist es nur eine Frage über Kreise und Linien in der ebenen Geometrie (noch besser, alle longitues sind Linien, die durch 0, und alle Breiten sind Kreise um 0)

Wie wäre es damit?

Vektor finden v der den Mittelpunkt des Rechtecks verbindet, Punkt Cr, zum Mittelpunkt des Kreises.Punkt finden i Wo v schneidet das Rechteck.Wenn ||i-Cr|| + r > ||v|| dann kreuzen 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 mittlere Verbindungsliniensegment).

Fundpunkt i dürfte der knifflige Teil sein, besonders wenn es auf eine Längengradkante fällt, aber Sie sollten in der Lage sein, schneller etwas zu finden als ich.

Bearbeiten:Mit dieser Methode kann nicht festgestellt werden, ob der Kreis vollständig innerhalb des Rechtecks liegt.Dazu müssten Sie den Abstand von der Mitte des Rechtecks zu allen vier Kanten des Rechtecks ermitteln.

Bearbeiten:Das Obige ist falsch. Wie Federico Ramponi vorgeschlagen hat, gibt es einige Fälle, in denen es nicht einmal in der euklidischen Geometrie funktioniert.Ich werde eine weitere Antwort posten.Bitte akzeptieren Sie dies nicht und stimmen Sie ruhig ab.Ich werde es in Kürze löschen.

Dies sollte für alle Punkte auf der Erde funktionieren.Wenn Sie es in eine Kugel mit einer anderen Größe ändern möchten, ändern Sie einfach kEarchRadiusKms auf den gewünschten Radius für Ihre Kugel.

Mit dieser Methode wird der Abstand zwischen Breiten- und Längenpunkten berechnet.

Ich habe diese Distanzformel von hier erhalten:http://www.codeproject.com/csharp/distancebetweenlocations.asp

public static double Calc(double Lat1, double Long1, double Lat2, double Long2)
{
    double dDistance = Double.MinValue;
    double dLat1InRad = Lat1 * (Math.PI / 180.0);
    double dLong1InRad = Long1 * (Math.PI / 180.0);
    double dLat2InRad = Lat2 * (Math.PI / 180.0);
    double dLong2InRad = Long2 * (Math.PI / 180.0);

    double dLongitude = dLong2InRad - dLong1InRad;
    double dLatitude = dLat2InRad - dLat1InRad;

    // Intermediate result a.
    double a = Math.Pow(Math.Sin(dLatitude / 2.0), 2.0) +
               Math.Cos(dLat1InRad) * Math.Cos(dLat2InRad) *
               Math.Pow(Math.Sin(dLongitude / 2.0), 2.0);

    // Intermediate result c (great circle distance in Radians).
    double c = 2.0 * Math.Atan2(Math.Sqrt(a), Math.Sqrt(1.0 - a));

    // Distance.
    // const Double kEarthRadiusMiles = 3956.0;
    const Double kEarthRadiusKms = 6376.5;
    dDistance = kEarthRadiusKms * c;

    return dDistance;
}

Wenn der Abstand zwischen den Eckpunkten des Rechtecks kleiner ist als der Radius des Kreises, überlappen sich Kreis und Rechteck.Wenn der Abstand zwischen dem Mittelpunkt des Kreises und allen Eckpunkten größer als der Radius des Kreises ist und alle diese Abstände kürzer als die Breite und Höhe des Rechtecks sind, sollte sich der Kreis innerhalb des Rechtecks befinden.

Fühlen Sie sich frei, meinen Code zu korrigieren, wenn Sie ein Problem damit finden, da ich mir sicher bin, dass es einen Zustand gibt, an den ich nicht gedacht habe.

Außerdem bin ich mir nicht sicher, ob dies für ein Rechteck funktioniert, das die Enden der Halbkugeln überspannt, da die Abstandsgleichung möglicherweise zusammenbricht.

public string Test(double cLat,
    double cLon,
    double cRadius,
    double rlat1,
    double rlon1,
    double rlat2,
    double rlon2,
    double rlat3,
    double rlon3,
    double rlat4,
    double rlon4)
{
    double d1 = Calc(cLat, cLon, rlat1, rlon1);
    double d2 = Calc(cLat, cLon, rlat2, rlon2);
    double d3 = Calc(cLat, cLon, rlat3, rlon3);
    double d4 = Calc(cLat, cLon, rlat4, rlon4);

    if (d1 <= cRadius ||
        d2 <= cRadius ||
        d3 <= cRadius ||
        d4 <= cRadius)
    {

        return "Circle and Rectangle intersect...";
    }

    double width = Calc(rlat1, rlon1, rlat2, rlon2);
    double height = Calc(rlat1, rlon1, rlat4, rlon4);

    if (d1 >= cRadius &&
        d2 >= cRadius &&
        d3 >= cRadius &&
        d4 >= cRadius &&
        width >= d1 &&
        width >= d2 &&
        width >= d3 &&
        width >= d4 &&
        height >= d1 &&
        height >= d2 &&
        height >= d3 &&
        height >= d4)
    {
        return "Circle is Inside of Rectangle!";
    }



    return "NO!";
}

Ein weiterer Versuch in diese ...

ich glaube, die Lösung eine Reihe von Punkten zu testen, so wie Jason S vorgeschlagen hat, aber ich stimme nicht mit seiner Auswahl von Punkten, die ich denke, mathematisch falsch ist.

Sie müssen die Punkte auf den Seiten der lat / long-Box zu finden, wo der Abstand zum Mittelpunkt des Kreises ein lokales Minimum oder Maximum ist. Fügen Sie diese Punkte auf den Satz von Ecken und dann sollte der Algorithmus oben korrekt sein.

D.h., im Stich gelassen Länge der x-Dimension und Breitengrad der y-Dimension sein, lassen Sie jede Seite des Kastens ein parametrischer Kurve P (t) = P0 + t (P1-P0) sein, für o <= t <= 1,0, wobei P0 und P1 sind zwei benachbarte Ecken.

Es sei f (P) = f (P.x, P.y) der Abstand von der Mitte des Kreises.

Dann f (P0 + t (P1-P0)) ist eine Abstandsfunktion von t: g (t). Finden Sie alle Punkte, an denen die Ableitung der Abstandsfunktion Null ist: G '(t) == 0. (Verwerfen von Lösungen, die die Domäne Übergröße 0 <= t <= 1,0, natürlich)

Leider muss diese die Null eines transzendentalen Ausdrucks finden, so gibt es keine Lösung in geschlossener Form. Diese Art der Gleichung kann nur gelöst durch Newton-Raphson-Iteration.

OK, ich merke, dass Sie Code wollte, nicht die Mathematik. Aber die Mathematik ist alles, was ich habe.

Für die euklidische Geometrie Antwort finden Sie unter: Kreis-Rechteck Kollisionserkennung (Kreuzung)

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow