webentwicklung-frage-antwort-db.com.de

Wie kann ich feststellen, ob sich ein Punkt in einem konvexen 2D-Polygon befindet?

Ich habe ein konvexes Polygon (normalerweise nur ein gedrehtes Quadrat) und kenne alle 4 Punkte. Wie bestimme ich, ob ein bestimmter Punkt (gelb/grün) innerhalb des Polygons liegt?

enter image description here

BEARBEITEN: Für dieses spezielle Projekt habe ich keinen Zugriff auf alle Bibliotheken des JDK, wie z. B. AWT.

20
NPike

Diese Seite: http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html zeigt, wie Sie dies für jedes Polygon tun.

Ich habe eine Java-Implementierung davon, aber es ist zu groß, um sie hier vollständig zu posten. Sie sollten es jedoch in der Lage sein, es herauszufinden:

class Boundary {
    private final Point[] points; // Points making up the boundary
    ...


    /**
     * Return true if the given point is contained inside the boundary.
     * See: http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html
     * @param test The point to check
     * @return true if the point is inside the boundary, false otherwise
     *
     */
    public boolean contains(Point test) {
      int i;
      int j;
      boolean result = false;
      for (i = 0, j = points.length - 1; i < points.length; j = i++) {
        if ((points[i].y > test.y) != (points[j].y > test.y) &&
            (test.x < (points[j].x - points[i].x) * (test.y - points[i].y) / (points[j].y-points[i].y) + points[i].x)) {
          result = !result;
         }
      }
      return result;
    }
}

Und hier ist eine Skizze der Point-Klasse

/**
 * Two dimensional cartesian point.
 */
public class Point {
  public final double x;
  public final double y;
  ...
}
69
Dean Povey

Für diejenigen, die verstehen möchten, wie die von Dean Povey oben beschriebene Methode funktioniert, ist hier die Erklärung:

Die Methode betrachtet einen "Strahl", der an der getesteten Stelle beginnt und auf die rechte Seite der X-Achse bis unendlich reicht. Für jedes Polygonsegment wird geprüft, ob der Strahl es kreuzt. Wenn die Gesamtzahl der Segmentkreuzungen ungerade ist, wird der getestete Punkt innerhalb des Polygons betrachtet, andernfalls - außerhalb von .

.__ Um zu verstehen, wie die Kreuzung berechnet wird, betrachten Sie die folgende Abbildung:

            v2
            o
           /
          / c (intersection)
o--------x----------------------> to infinity
t       /
       /   
      /
     o
     v1

Damit der Schnittpunkt auftritt, muss getestet.y zwischen den y-Werten der Scheitelpunkte des Segments (v1 und v2) liegen. Dies ist die erste Bedingung der if-Anweisung in der Methode. Wenn dies der Fall ist, muss die horizontale Linie das Segment schneiden. Es bleibt nur noch festzustellen, ob die Kreuzung rechts vom getesteten Punkt oder links davon liegt. Dies erfordert das Finden der x-Koordinate des Schnittpunkts. Dies ist:

              t.y - v1.y
c.x = v1.x + ----------- * (v2.x - v1.x)
             v2.y - v1.y

Es bleibt nur noch die Feinheiten zu untersuchen:

  • Wenn v1.y == v2.y, dann geht der Strahl das Segment entlang und Daher hat das Segment keinen Einfluss auf das Ergebnis. Tatsächlich gibt der erste Teil .__ der if-Anweisung in diesem Fall false zurück.
  • Der Code multipliziert zuerst und teilt sich dann. Dies wird gemacht, um Sehr kleine Unterschiede zwischen v1.x und v2.x zu unterstützen, die nach der Division aufgrund der Rundung ..__ zu einer Null führen können.
  • Schließlich sollte das Problem der Kreuzung auf einem Scheitelpunkt __. Adressiert werden. Betrachten Sie die folgenden zwei Fälle:
         o                    o
         |                     \     o
         | A1                C1 \   /
         |                       \ / C2  
o--------x-----------x------------x--------> to infinity
        /           / \
    A2 /        B1 /   \ B2
      /           /     \ 
     o           /       o
                o

Um zu überprüfen, ob es funktioniert, prüfen Sie selbst, was für jede Der 4 Segmente durch die if-Bedingung im Method body . Zurückgegeben wird ) erhalten ein positives Ergebnis, während die darunter (A2, B1, B2) ein negatives Eins erhalten. Dies bedeutet, dass der A-Scheitelpunkt eine ungerade Zahl (1) zur Kreuzung Beiträgt, während B und C eine gerade Zahl (0 bzw. 2) beitragen, die genau das ist, was gewünscht wird. A ist tatsächlich eine echte Kreuzung des Polygons, während B Und C nur zwei Fälle von "Vorbeiflug" sind.

30
Nadav

Angenommen, Ihr Punkt befindet sich an der Y-Koordinate y, berechnen Sie einfach die x-Positionen, an denen die einzelnen Linien der Polygone (nicht horizontal) y kreuzen. Zähle die Anzahl der x-Positionen, die Kleiner sind als die x-Position deines Punktes. Wenn die Anzahl der x-Positionen ungerade ist, befindet sich Ihr Punkt im Polygon Hinweis: Dies funktioniert für alle Polygone, nicht nur für die Konvexität. Stellen Sie sich das so vor: Ziehen Sie eine Linie von unendlich weit direkt zu Ihrem Punkt. Wenn diese Linie eine Polygonlinie kreuzt, befindet sie sich jetzt innerhalb des Polygons. Überquere die Linie wieder draußen. Erneut überqueren, innen (und so weiter). Hoffe das hilft!

17
Jim

Die Java.awt.Polygon-Klasse verfügt über eine Reihe von contains(...)-Methoden, wenn Sie Polygon -Objekte verwenden, um Ihr Polygon darzustellen.

9
Kavka

Zum Hinzufügen einer (einfachen) Java-Implementierung des Originalcodes in C aus von @Dean Povey vorgeschlagenem (Ich weiß nicht, warum @Dean Povey auf eine große Implementierung verweist):

static boolean pnpoly(double[] vertx, double[] verty, double testx, double testy)
{
    int nvert = vertx.length;
    int i, j;
    boolean c = false;
    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 den Fall nicht geändert, um die Java-Regel einzuhalten, um die minimalen erforderlichen Änderungen anzuzeigen. Ich habe es auch in einfachen Fällen getestet und es funktioniert gut.

4
Eypros

Angenommen, x [] ist das Array von x Punkten und y [] ist das Array von y Punkten.
Sie sollen 1 zurückgeben, wenn der Punkt im Polygon vorhanden ist, und 2, falls nicht. Dabei ist (planeX, planeY) der zu überprüfende Punkt.

//check like this
return new Polygon(x,y,x.length).contains(planeX, planeY)?1:2;
1
Apoorva Ambhoj

Prüfen Sie, ob sie sich auf derselben Seite der 4 Halbebenen befindet, die durch die Linien definiert werden, die die Liniensegmente enthalten, aus denen die Seiten des Quaders bestehen.

Hier ist eine gute Erklärung.

1
user1118321

Polygons Abszissen x_array: Array[Integer]

Polygons Ordinaten: y_array: Array[Integer]

Punkt: x: Integer, y: Integer

import Java.awt.Polygon
import Java.awt.Point
...

final boolean isInPolygon = 
    new Polygon(x_array,y_array,x_array.length).contains(new Point(x, y));

In diesem Beispiel erstellen wir ein Objekt Java.awt.Polygon und überprüfen anhand der in der Methode enthaltenen Methode, ob Ihre Koordinaten der von Ihnen entworfenen Form entsprechen.

Ich benutze das Objekt Java.awt.Point zur Darstellung der Koordinaten, um den Code elegant zu gestalten. Dies ist jedoch optional. Sie können .contains(x, y) direkt verwenden.

0
Seraf