Punkt im Polygonalgorithmus

Ich habe gesehen, dass der folgende Algorithmus funktioniert, um zu überprüfen, ob sich ein Punkt in einem bestimmten Polygon von diesem Link befindet:

int pnpoly(int nvert, float *vertx, float *verty, float testx, float testy)
{
  int i, j, c = 0;
  for (i = 0, j = nvert-1; i < nvert; j = i++) {
    if ( ((verty[i]>testy) != (verty[j]>testy)) &&
     (testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]) )
       c = !c;
  }
  return c;
}

Ich habe diesen Algorithmus ausprobiert und er funktioniert tatsächlich perfekt. Aber leider kann ich es nicht gut verstehen, nachdem ich einige Zeit damit verbracht habe, eine Vorstellung davon zu bekommen.

Wenn also jemand diesen Algorithmus verstehen kann, erkläre ihn mir bitte ein wenig.

Vielen Dank.

Der Algorithmus strahlt nach rechts. Bei jeder Iteration der Schleife wird der Testpunkt gegen eine der Kanten des Polygons geprüft. Die erste Zeile des if-Tests ist erfolgreich, wenn die y-Koordinate des Punktes innerhalb des Bereichs der Kante liegt. Die zweite Zeile überprüft, ob der Testpunkt links von der Zeile liegt (glaube ich – ich habe kein Zettel zur Hand, um das zu überprüfen). Wenn dies zutrifft, kreuzt die vom Testpunkt nach rechts gezogene Linie diese Kante.

Durch wiederholtes Invertieren des Wertes von c, zählt der Algorithmus, wie oft die rechte Linie das Polygon kreuzt. Wenn es eine ungerade Anzahl von Malen kreuzt, dann ist der Punkt innen; bei einer geraden Zahl liegt der Punkt außerhalb.

Ich hätte jedoch Bedenken hinsichtlich a) der Genauigkeit der Gleitkommaarithmetik und b) der Auswirkungen einer horizontalen Kante oder eines Testpunkts mit derselben y-Koordinate wie ein Scheitelpunkt.

Änderung 30.01.2022: Ich habe diese Antwort vor 9 Jahren geschrieben, als ich auf dem College war. Personen in der Chat-Konversation geben an, dass dies nicht korrekt ist. Sie sollten sich wahrscheinlich woanders umsehen. 🤷‍♂️

Chowlett ist in jeder Hinsicht, Form und Form korrekt. Der Algorithmus geht davon aus, dass, wenn Ihr Punkt auf der Linie des Polygons liegt, dieser außerhalb liegt – in einigen Fällen ist dies falsch. Das Ändern der beiden ‘>’-Operatoren in ‘>=’ und das Ändern von ‘<' in '<=' behebt das.

bool PointInPolygon(Point point, Polygon polygon) {
  vector<Point> points = polygon.getPoints();
  int i, j, nvert = points.size();
  bool c = false;
  
  for(i = 0, j = nvert - 1; i < nvert; j = i++) {
    if( ( (points[i].y >= point.y ) != (points[j].y >= point.y) ) &&
        (point.x <= (points[j].x - points[i].x) * (point.y - points[i].y) / (points[j].y - points[i].y) + points[i].x)
      )
      c = !c;
  }
  
  return c;
}

Ich habe die geändert Originalcode um es ein wenig besser lesbar zu machen (auch dies verwendet Eigen). Der Algorithmus ist identisch.

// This uses the ray-casting algorithm to decide whether the point is inside
// the given polygon. See https://en.wikipedia.org/wiki/Point_in_polygon#Ray_casting_algorithm
bool pnpoly(const Eigen::MatrixX2d &poly, float x, float y)
{
    // If we never cross any lines we're inside.
    bool inside = false;

    // Loop through all the edges.
    for (int i = 0; i < poly.rows(); ++i)
    {
        // i is the index of the first vertex, j is the next one.
        // The original code uses a too-clever trick for this.
        int j = (i + 1) % poly.rows();

        // The vertices of the edge we are checking.
        double xp0 = poly(i, 0);
        double yp0 = poly(i, 1);
        double xp1 = poly(j, 0);
        double yp1 = poly(j, 1);

        // Check whether the edge intersects a line from (-inf,y) to (x,y).

        // First check if the line crosses the horizontal line at y in either direction.
        if ((yp0 <= y) && (yp1 > y) || (yp1 <= y) && (yp0 > y))
        {
            // If so, get the point where it crosses that line. This is a simple solution
            // to a linear equation. Note that we can't get a division by zero here -
            // if yp1 == yp0 then the above if be false.
            double cross = (xp1 - xp0) * (y - yp0) / (yp1 - yp0) + xp0;

            // Finally check if it crosses to the left of our test point. You could equally
            // do right and it should give the same result.
            if (cross < x)
                inside = !inside;
        }
    }
    return inside;
}

Dies könnte so detailliert sein, wie es für die Erklärung des Raytracing-Algorithmus im tatsächlichen Code sein könnte. Es kann sein, dass es nicht optimiert ist, aber das muss immer nach einem vollständigen Verständnis des Systems erfolgen.

    //method to check if a Coordinate is located in a polygon
public boolean checkIsInPolygon(ArrayList<Coordinate> poly){
    //this method uses the ray tracing algorithm to determine if the point is in the polygon
    int nPoints=poly.size();
    int j=-999;
    int i=-999;
    boolean locatedInPolygon=false;
    for(i=0;i<(nPoints);i++){
        //repeat loop for all sets of points
        if(i==(nPoints-1)){
            //if i is the last vertex, let j be the first vertex
            j= 0;
        }else{
            //for all-else, let j=(i+1)th vertex
            j=i+1;
        }

        float vertY_i= (float)poly.get(i).getY();
        float vertX_i= (float)poly.get(i).getX();
        float vertY_j= (float)poly.get(j).getY();
        float vertX_j= (float)poly.get(j).getX();
        float testX  = (float)this.getX();
        float testY  = (float)this.getY();

        // following statement checks if testPoint.Y is below Y-coord of i-th vertex
        boolean belowLowY=vertY_i>testY;
        // following statement checks if testPoint.Y is below Y-coord of i+1-th vertex
        boolean belowHighY=vertY_j>testY;

        /* following statement is true if testPoint.Y satisfies either (only one is possible) 
        -->(i).Y < testPoint.Y < (i+1).Y        OR  
        -->(i).Y > testPoint.Y > (i+1).Y

        (Note)
        Both of the conditions indicate that a point is located within the edges of the Y-th coordinate
        of the (i)-th and the (i+1)- th vertices of the polygon. If neither of the above
        conditions is satisfied, then it is assured that a semi-infinite horizontal line draw 
        to the right from the testpoint will NOT cross the line that connects vertices i and i+1 
        of the polygon
        */
        boolean withinYsEdges= belowLowY != belowHighY;

        if( withinYsEdges){
            // this is the slope of the line that connects vertices i and i+1 of the polygon
            float slopeOfLine   = ( vertX_j-vertX_i )/ (vertY_j-vertY_i) ;

            // this looks up the x-coord of a point lying on the above line, given its y-coord
            float pointOnLine   = ( slopeOfLine* (testY - vertY_i) )+vertX_i;

            //checks to see if x-coord of testPoint is smaller than the point on the line with the same y-coord
            boolean isLeftToLine= testX < pointOnLine;

            if(isLeftToLine){
                //this statement changes true to false (and vice-versa)
                locatedInPolygon= !locatedInPolygon;
            }//end if (isLeftToLine)
        }//end if (withinYsEdges
    }

    return locatedInPolygon;
}

Nur ein Wort zur Optimierung: Es stimmt nicht, dass der kürzeste (und/oder kürzeste) Code am schnellsten implementiert ist. Es ist ein viel schnellerer Prozess, ein Element aus einem Array zu lesen und zu speichern und es (möglicherweise) viele Male innerhalb der Ausführung des Codeblocks zu verwenden, als jedes Mal, wenn es erforderlich ist, auf das Array zuzugreifen. Dies ist besonders wichtig, wenn das Array extrem groß ist. Indem jeder Begriff eines Arrays in einer gut benannten Variablen gespeichert wird, ist es meiner Meinung nach auch einfacher, seinen Zweck zu beurteilen und somit einen viel besser lesbaren Code zu bilden. Nur meine zwei Cent…

Der Algorithmus wird auf die notwendigsten Elemente reduziert. Nachdem es entwickelt und getestet wurde, wurde alles Unnötige entfernt. Als Ergebnis kann man es nicht leicht verstehen, aber es macht den Job und auch in sehr guter Leistung.

Ich habe mir erlaubt, es zu übersetzen ActionScript-3:

// not optimized yet (nvert could be left out)
public static function pnpoly(nvert: int, vertx: Array, verty: Array, x: Number, y: Number): Boolean
{
    var i: int, j: int;
    var c: Boolean = false;
    for (i = 0, j = nvert - 1; i < nvert; j = i++)
    {
        if (((verty[i] > y) != (verty[j] > y)) && (x < (vertx[j] - vertx[i]) * (y - verty[i]) / (verty[j] - verty[i]) + vertx[i]))
            c = !c;
    }
    return c;
}

Dieser Algorithmus funktioniert in jedem geschlossenen Polygon, solange sich die Seiten des Polygons nicht kreuzen. Dreieck, Fünfeck, Quadrat, sogar ein sehr kurviges, stückweise lineares Gummiband, das sich nicht kreuzt.

1) Definieren Sie Ihr Polygon als gerichtete Gruppe von Vektoren. Damit ist gemeint, dass jede Seite des Polygons durch einen Vektor beschrieben wird, der von Scheitelpunkt an zu Scheitelpunkt an+1 geht. Die Vektoren sind so ausgerichtet, dass der Kopf des einen den Schwanz des nächsten berührt, bis der letzte Vektor den Schwanz des ersten berührt.

2) Wählen Sie den zu testenden Punkt innerhalb oder außerhalb des Polygons aus.

3) Finde für jeden Vektor Vn entlang des Umfangs des Polygons den Vektor Dn, der am Testpunkt beginnt und am Ende von Vn endet. Berechnen Sie den Vektor Cn definiert als DnXVn/DN*VN (X steht für Kreuzprodukt; * steht für Punktprodukt). Benennen Sie die Größe von Cn mit dem Namen Mn.

4) Addiere alles Mn und nenne diese Menge K.

5) Wenn K Null ist, liegt der Punkt außerhalb des Polygons.

6) Wenn K nicht Null ist, liegt der Punkt innerhalb des Polygons.

Theoretisch führt ein Punkt, der AUF der Kante des Polygons liegt, zu einem undefinierten Ergebnis.

Die geometrische Bedeutung von K ist der Gesamtwinkel, um den der Floh, der auf unserem Testpunkt saß, die Ameise “sah”, die am Rand des Polygons nach links ging, abzüglich des Winkels, der nach rechts ging. In einem geschlossenen Kreislauf endet die Ameise dort, wo sie begonnen hat. Außerhalb des Polygons ist die Antwort unabhängig vom Standort Null.
Innerhalb des Polygons lautet die Antwort unabhängig von der Position “einmal um den Punkt herum”.

Diese Methode prüft, ob der Strahl vom Punkt (testx, testy) bis O (0,0) die Seiten des Polygons schneidet oder nicht.

Es gibt eine bekannte Schlussfolgerung hier: Wenn ein Strahl von 1 Punkt aus die Seiten eines Polygons für eine ungerade Zeit schneidet, gehört dieser Punkt zum Polygon, andernfalls befindet sich dieser Punkt außerhalb des Polygons.