Die Feststellung, ob eine Koordinate vorhanden ist, innerhalb eines Polygons

Ich arbeite an einer open-source-tracking und die geofence-software-Anwendung und habe ein wenig Schwierigkeiten herauszufinden, die Mathematik für das geofencing.

Ich brauche, um zu bestimmen, ob ein Koordinatensystem existiert, in der ein polygon. Aber der schwierige Teil ist, dass das polygon hat keine festgelegte Anzahl von Seiten. Ich muss in der Lage sein zu berechnen, auf fünfzig Seiten oder fünf Seiten.

Meine Forschung sagt, dass der einfachste Weg ist, dass ich meine Stelle (die ich nenne Sie mal x) und einen Punkt außerhalb des Polygons (nennen wir es y) und bestimmen, ob die Leitung ((xx, xy), (yx, yy)) schneidet das polygon-Grenzen. Wenn es schneidet eine ungerade Anzahl von Zeiten, Punkt x müssen innerhalb des Polygons.

Wissen, dass, aber, ich kann nicht herausfinden, wie ich das Ausdrücken soll in einem Algorithmus.. ich offensichtlich benötigen, um eine Schleife durch die verschiedenen Linien konstruieren Sie das polygon aber die check ich tun, entzieht sich mir. Kann mir jemand behilflich sein? Bitte wisst, dass ich mich nicht zu Fragen, für die Lösung unbedingt. Alles, was wird mir helfen, es herauszufinden, die Antwort ist eine große Hilfe.

Sehr geschätzt.

  • Ist das polygon konvex?
  • Gibt es einen link oder den Namen Ihrer Anwendung, ich mache auch eins. Danke im Voraus
  • mögliche Duplikate von Punkt in Polygon aka hit test
InformationsquelleAutor | 2010-01-13
  1. 6

    Sehen hier

    Grundsätzlich gibt es einen Ansatz (ich glaube, seine der Jordan-Kurve Theorem), dass zählt die Anzahl der Zeiten, die der Strahl schneidet die Liniensegmente des Polygons. Wenn das Ergebnis auch, dann ist der Punkt außerhalb des Polygons, sonst liegt der Punkt innerhalb des Polygons.

    HTH

    BEARBEITEN
    Es ist eine andere Frage, die bezieht sich auf diese Frage gefunden werden kann hier

    InformationsquelleAutor Rippo
  2. 1

    Einen Schlüssel hier ist zu erkennen, dass Sie sind frei, wählen Sie einen beliebigen Punkt Y, die Sie mögen. Eine wirklich gute Wahl, ist der Punkt (xx, -infinity). In anderen Worten, der Punkt direkt nach unten aus dem Punkt in Frage, und unendlich weit entfernt. Nun stellt sich die Frage: wie viele von den polygon-Kanten kreuzen Sie Ihre X-Koordinate unter dem Punkt in Frage. Also nur die Linien, die Spagat-die X-Koordinate berücksichtigt werden müssen.

    Wenn Ihr Punkt ist P = (x,y), und segment Ende Punkte sind P1 = (x1,y1) und P2 = (x2,y2) die y-Koordinate des Segments, wo es kreuzt x ist gegeben durch sy = (x-x1)*(y2-y1)/(x2-x1) + y1

    Prüfen, ob sy < y (nur wenn x1 < x < x2 oder x2 < x < x1). Wenn es eine ungerade Anzahl von diesen dann P ist im inneren.

    Gibt es subtile Probleme mit dieser, wenn eine der verticies des Polygons ist an genau der gleichen y-position wie der Punkt in Frage. Sie müssen vorsichtig sein, über diesem Fall.

    InformationsquelleAutor phkahler
  3. 1

    Justin,

    Müssen Sie möglicherweise auch, um besser zu definieren "außerhalb des Polygons" zu konstruieren einen segment.

    Nehmen die min & max alle x & y-Koordinaten und konstruieren ein Rechteck (xmin,ymin),(xmax,ymin),(xmax,ymax),(xmin,ymax). Jeder Punkt außerhalb des Rechtecks auf jeden Fall wäre außerhalb der polygon - dann weiter wie andere, haben oben gezeigt. Jedes polygon segment und die konstruierte Linie ist definiert durch eine Gleichung y = ax + b und für jedes segment eine Reihe xlo und xhi. Ihr konstruiert line kreuzt ein segment in dem Bereich oder nicht. Das heißt, die Lösung der beiden Gleichungssysteme im segment-Bereich, die entweder vorhanden ist oder nicht. Nur die Anzahl der Lösungen, die es gibt, um die Anzahl der Kreuzungen.

    InformationsquelleAutor Grembo
  4. 0

    Ich nehme an du bist in einer Ebene (2D).

    • Berechnen Sie die Pisten von jeder Seite (in einem Koordinatensystem) und der Steigung der Linie von Punkt X zu Punkt Y (Linie XY).
    • Für alle Seiten, wo der Hang ist nicht gleich Hang XY, berechnen Sie den Schnittpunkt.
    • Für jeden Punkt, bestimmen, ob der Schnittpunkt auf der Linie segment XY und das Liniensegment definieren Sie die Seite. Wenn es ist, überquerte Sie, die Seite. (Überprüfen Sie die Koordinaten der Kreuzung und sehen, ob der x-und y-Komponenten enthalten sind, die in den Bereich der Werte für jedes Liniensegment.)
    • Zählen Sie die Anzahl der überfahrten, und Sie haben Ihre Antwort.
    InformationsquelleAutor John
  5. 0

    Berechnen Sie die Wicklung Anzahl der das polygon und der Punkt.

    • Es wäre schön, wenn Wikipedia zur Verfügung gestellt, die geschlossene form, die integral entlang einer Linie segment. Diese könnten dann zusammengefasst werden um das polygon zu erhalten, die Wicklung Anzahl. Ich kann fast sehen, es, und es ist nicht schön - der Winkel, gebildet durch P und der Endpunkte.
    InformationsquelleAutor Steve Emmerson
  6. 0

    Versuchen, diese,

    public static bool PointinPolygon( Point[] points, Point p )
    {
        bool result = false;

        for( int i = 0; i < points.Length - 1; i++ )
        {
            if( ( ( ( points[ i + 1 ].Y <= p.Y ) && ( p.Y < points[ i ].Y ) ) || ( ( points[ i ].Y <= p.Y ) && ( p.Y < points[ i + 1 ].Y ) ) ) && ( p.X < ( points[ i ].X - points[ i + 1 ].X ) * ( p.Y - points[ i + 1 ].Y ) /( points[ i ].Y - points[ i + 1 ].Y ) + points[ i + 1 ].X ) )
            {
                result = !result;
            }
        }
        return result;
    }
    • Anstatt nur nach einem block von code, bitte erklären, warum dieser code löst das gestellte problem. Ohne eine Erklärung, das ist nicht ein Antwort.
    InformationsquelleAutor Jerry Knauss
Schreibe einen Kommentar