Wie kann ich feststellen, ob ein 2D-Punkt innerhalb eines Polygons liegt?

Zur Grafik würde ich eher nicht bevorzugen, zahlen. Viele Systeme verwenden Ganzzahlen für die UI-Malerei (Pixel sind int-Werte, nachdem alle), aber macOS zum Beispiel nutzt float für alles. macOS kennt nur Punkte und einen Punkt übersetzen kann, um ein pixel, aber je nach monitor Auflösung, könnte es übersetzen, um etwas anderes. Auf retina-screens von einem halben Punkt (0.5/0.5) ist pixel. Trotzdem habe ich nie bemerkt, dass macOS UIs sind deutlich langsamer als andere UIs. Nachdem alle 3D-APIs (OpenGL oder Direct3D) funktioniert auch mit Schwimmern und moderne Grafik-Bibliotheken sehr oft nutzen die GPU-Beschleunigung.

Nun Sie sagte, die Geschwindigkeit ist Ihr Hauptanliegen, okay, let ' s go for speed. Vor dem ausführen einer ausgefeilten Algorithmus, der zuerst einen einfachen test. Erstellen Sie eine Achse ausgerichtet Begrenzungsrahmen um das polygon. Dies ist sehr einfach, schnell und kann bereits sicher, dass Sie eine Menge von Berechnungen. Wie funktioniert das? Iterieren über alle Punkte des Polygons und finden Sie die min/max Werte von X und Y.

E. g. Sie haben die Punkte (9/1), (4/3), (2/7), (8/2), (3/6). Dies bedeutet Xmin 2 Xmax ist 9, Ymin 1 Ymax ist 7. Ein Punkt außerhalb des Rechtecks mit den zwei Kanten (2/1) und (9/7) nicht innerhalb des Polygons.

//p is your point, p.x is the x coord, p.y is the y coord
if (p.x < Xmin || p.x > Xmax || p.y < Ymin || p.y > Ymax) {
    //Definitely not within the polygon!
}

Dies ist der erste test laufen für jeden Punkt. Wie Sie sehen können, dieser test ist ultra schnell, aber es ist auch sehr grob. Behandeln Punkte, die innerhalb der bounding-Rechteck, brauchen wir ein ausgefeilter Algorithmus. Es gibt ein paar Möglichkeiten, wie dieser berechnet werden kann. Die Methode funktioniert, hängt auch von der Tatsache, ob das polygon können Löcher oder immer solide. Hier sind Beispiele von festen, (einen konvexen, einen konkaven):

Und hier ist eine mit einem Loch:

Den grünen hat in der Mitte ein Loch!

Der einfachste Algorithmus kann mit allen drei oben genannten Fälle und ist immer noch ziemlich schnell ist benannt ray-casting. Die Idee des Algorithmus ist ziemlich einfach: Zeichnen Sie einen virtuellen Strahl von irgendwo außerhalb des Polygons zu Ihrem Punkt und zählen Sie, wie oft es schlägt in eine Seite des Polygons. Wenn die Anzahl der Treffer auch ist, es ist außerhalb des Polygons, wenn es seltsam ist, es ist von innen.

Den winding number Algorithmus wäre eine alternative, es ist genauer, für die Punkte sehr nahe in ein polygon-Linie, aber es ist auch viel langsamer. Ray-casting kann fehlschlagen, um die Punkte zu nah, um ein polygon Seite, wegen der begrenzten floating-point-Präzision und Rundung Probleme, aber in Wirklichkeit ist kaum ein problem, da liegt ein Punkt, der in der Nähe einer Seite, ist es oft optisch gar nicht möglich ist-für die Betrachter zu erkennen, wenn es schon innerhalb oder noch außerhalb.

Haben Sie immer noch die bounding box von oben erinnern Sie sich? Wählen Sie einfach einen Punkt außerhalb der bounding-box und verwenden Sie es als Ausgangspunkt für Ihre ray. E. g. der Punkt (Xmin - e/p.y) außerhalb des Polygons sicher.

Aber was ist e? Gut, e (eigentlich epsilon) gibt die bounding-box einige Polsterung. Als ich sagte, ray-tracing fehl, wenn wir beginnen zu schließen, um eine polygonlinie. Da die bounding-box kann gleich das polygon (wenn das polygon einer Achse ausgerichtet Rechteck die umgebende box ist gleich dem polygon selbst!), wir benötigen eine Polsterung, machen diese sicher, das ist alles. Wie groß sollten Sie e? Nicht zu groß ist. Es hängt vom Koordinatensystem skalieren verwenden Sie für das zeichnen. Wenn Ihr pixel-Schrittweite ist 1.0, dann wählen Sie einfach die 1.0 (noch 0.1 gearbeitet haben würde)

Nun, dass wir das ray mit seiner start-und end-Koordinaten, das problem verschiebt sich vom "ist der Punkt innerhalb des Polygons" zu "wie oft kommt der Strahl schneidet ein polygon Seite". Deshalb können wir nicht nur die Arbeit mit dem polygon-Punkte wie vorher, jetzt müssen wir die eigentlichen Seiten. Eine Seite ist immer durch zwei Punkte definiert.

side 1: (X1/Y1)-(X2/Y2)
side 2: (X2/Y2)-(X3/Y3)
side 3: (X3/Y3)-(X4/Y4)
:

Müssen Sie testen, den ray gegen alle Seiten. Berücksichtigen ray ein Vektor und jeder Seite ein Vektor. Der ray hat zu schlagen jeder Seite genau einmal oder gar nicht. Es kann nicht auf die gleiche Seite zweimal. Zwei Linien im 2D-Raum wird immer schneiden sich genau einmal, wenn Sie parallel sind, in welchem Fall Sie nie kreuzen. Da jedoch die Vektoren haben eine begrenzte Länge, zwei Vektoren kann nicht parallel sein, und noch nie schneiden, weil Sie sind zu kurz, um jemals aufeinander treffen.

//Test the ray against all sides
int intersections = 0;
for (side = 0; side < numberOfSides; side++) {
    //Test if current side intersects with ray.
    //If yes, intersections++;
}
if ((intersections & 1) == 1) {
    //Inside of polygon
} else {
    //Outside of polygon
}

Soweit So gut, aber wie wollen Sie testen, ob zwei Vektoren schneiden? Hier sind einige C-code (nicht getestet), das sollte den trick tun:

#define NO 0
#define YES 1
#define COLLINEAR 2

int areIntersecting(
    float v1x1, float v1y1, float v1x2, float v1y2,
    float v2x1, float v2y1, float v2x2, float v2y2
) {
    float d1, d2;
    float a1, a2, b1, b2, c1, c2;

    //Convert vector 1 to a line (line 1) of infinite length.
    //We want the line in linear equation standard form: A*x + B*y + C = 0
    //See: http://en.wikipedia.org/wiki/Linear_equation
    a1 = v1y2 - v1y1;
    b1 = v1x1 - v1x2;
    c1 = (v1x2 * v1y1) - (v1x1 * v1y2);

    //Every point (x,y), that solves the equation above, is on the line,
    //every point that does not solve it, is not. The equation will have a
    //positive result if it is on one side of the line and a negative one 
    //if is on the other side of it. We insert (x1,y1) and (x2,y2) of vector
    //2 into the equation above.
    d1 = (a1 * v2x1) + (b1 * v2y1) + c1;
    d2 = (a1 * v2x2) + (b1 * v2y2) + c1;

    //If d1 and d2 both have the same sign, they are both on the same side
    //of our line 1 and in that case no intersection is possible. Careful, 
    //0 is a special case, that's why we don't test ">=" and "<=", 
    //but "<" and ">".
    if (d1 > 0 && d2 > 0) return NO;
    if (d1 < 0 && d2 < 0) return NO;

    //The fact that vector 2 intersected the infinite line 1 above doesn't 
    //mean it also intersects the vector 1. Vector 1 is only a subset of that
    //infinite line 1, so it may have intersected that line before the vector
    //started or after it ended. To know for sure, we have to repeat the
    //the same test the other way round. We start by calculating the 
    //infinite line 2 in linear equation standard form.
    a2 = v2y2 - v2y1;
    b2 = v2x1 - v2x2;
    c2 = (v2x2 * v2y1) - (v2x1 * v2y2);

    //Calculate d1 and d2 again, this time using points of vector 1.
    d1 = (a2 * v1x1) + (b2 * v1y1) + c2;
    d2 = (a2 * v1x2) + (b2 * v1y2) + c2;

    //Again, if both have the same sign (and neither one is 0),
    //no intersection is possible.
    if (d1 > 0 && d2 > 0) return NO;
    if (d1 < 0 && d2 < 0) return NO;

    //If we get here, only two possibilities are left. Either the two
    //vectors intersect in exactly one point or they are collinear, which
    //means they intersect in any number of points from zero to infinite.
    if ((a1 * b2) - (a2 * b1) == 0.0f) return COLLINEAR;

    //If they are not collinear, they must intersect in exactly one point.
    return YES;
}

Werden die Eingangswerte der zwei Endpunkte von Vektor 1 (v1x1/v1y1 und v1x2/v1y2) und Vektor 2 (v2x1/v2y1 und v2x2/v2y2). So haben Sie 2 Vektoren, 4 Punkte, 8 Koordinaten. YES und NO sind klar. YES erhöht Kreuzungen NO nichts.

Was KOLLINEAR? Es bedeutet, dass beide Vektoren liegen auf einer unendlichen Linie, abhängig von position und Länge, die Sie nicht schneiden, oder Sie schneiden sich in einer unendlichen Anzahl von Punkten. Ich bin mir nicht absolut sicher, wie in diesem Fall behandeln, würde ich mich nicht verlassen es als Kreuzung oder so. Gut, dieser Fall ist in der Praxis eher selten weil eh von floating-point-Rundungsfehler; es ist besser, code zu haben, würde wahrscheinlich nicht testen == 0.0f sondern für so etwas wie < epsilonwo epsilon ist eine relativ kleine Nummer.

Wenn Sie brauchen, um zu testen eine größere Anzahl von Punkten, können Sie sicher Geschwindigkeit bis die ganze Sache ein wenig durch die Beibehaltung der linearen Gleichung die gängigen Formen der polygon-Seiten im Speicher, so dass Sie nicht haben, um neu berechnen, diese jedes mal. Dadurch sparen Sie zwei Fließkomma-Multiplikationen und drei floating-point-Abzüge auf jeden test, den im Austausch für die Speicherung von drei floating-point-Werte pro polygon Seite im Speicher. Es ist eine typische Speicher-vs-Berechnung time-trade-off.

Last but not least: Wenn Sie können, verwenden Sie 3D-hardware, um das problem zu lösen, gibt es eine interessante alternative. Lass einfach die GPU die ganze Arbeit für Sie. Erstellen Sie eine Malerei-Oberfläche, die außerhalb des Bildschirms. Füllen Sie es vollständig mit der Farbe schwarz. Lassen Sie uns nun OpenGL oder Direct3D-malen Sie Ihr polygon (oder sogar alle Ihre Polygone wenn Sie nur wollen, um zu testen, ob der Punkt innerhalb jeder von Ihnen, aber Sie kümmern sich nicht für die one) und füllen Sie das polygon(en) mit einer anderen Farbe, z.B. weiß. Um zu überprüfen, ob ein Punkt innerhalb des Polygons, die Farbe von diesem Punkt aus der Zeichnung der Oberfläche. Dies ist nur ein O(1) Speicher Holen.

Natürlich ist diese Methode nur geeignet, wenn Ihre Zeichenfläche nicht zu groß sein. Wenn es passt nicht in den GPU-Speicher, diese Methode ist langsamer als wenn man es auf die CPU. Wenn es sein müsste, eine riesige und deine GPU unterstützt moderne Shader, können Sie immer noch die GPU durch die Implementierung des ray-casting-oben als ein GPU-shader, das ist absolut möglich. Für eine größere Anzahl von Polygonen oder eine große Anzahl von Punkten zu testen, das wird sich auszahlen, betrachten einige GPUs werden in der Lage sein, um test-64 auf 256 Punkte parallel. Beachten Sie jedoch, dass die übertragung der Daten von der CPU zur GPU und zurück ist immer teurer, so zum testen nur ein paar Punkte, die gegen ein paar einfache Polygone, bei denen entweder die Punkte oder der Polygone sind dynamisch und ändern sich Häufig, eine GPU-Ansatz wird nur selten auszahlen.

InformationsquelleAutor der Antwort Mecki

Hier ist ein C# - version der Antwort von nirgdie kommt aus das RPI-professor. Bitte beachten Sie, dass der code aus, dass die RPI-source-erfordert die Quellenangabe.

Einer bounding-box überprüfen, wurde oben Hinzugefügt. Jedoch, als James Brown weist darauf hin, der Haupt-code ist fast so schnell wie die bounding-box prüfen Sie selbst, also die bounding-box prüfen kann tatsächlich verlangsamen den gesamten Vorgang, in dem Fall, dass die meisten der Punkte, die Sie überprüfen, die innerhalb der bounding-box. So könnten Sie verlassen die bounding-box check-out, oder wäre eine alternative vorausberechnen den Begrenzungsrahmen Ihrer Polygone, wenn Sie nicht die Form verändern zu oft.

public bool IsPointInPolygon( Point p, Point[] polygon )
{
    double minX = polygon[ 0 ].X;
    double maxX = polygon[ 0 ].X;
    double minY = polygon[ 0 ].Y;
    double maxY = polygon[ 0 ].Y;
    for ( int i = 1 ; i < polygon.Length ; i++ )
    {
        Point q = polygon[ i ];
        minX = Math.Min( q.X, minX );
        maxX = Math.Max( q.X, maxX );
        minY = Math.Min( q.Y, minY );
        maxY = Math.Max( q.Y, maxY );
    }

    if ( p.X < minX || p.X > maxX || p.Y < minY || p.Y > maxY )
    {
        return false;
    }

    //http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html
    bool inside = false;
    for ( int i = 0, j = polygon.Length - 1 ; i < polygon.Length ; j = i++ )
    {
        if ( ( polygon[ i ].Y > p.Y ) != ( polygon[ j ].Y > p.Y ) &&
             p.X < ( polygon[ j ].X - polygon[ i ].X ) * ( p.Y - polygon[ i ].Y ) / ( polygon[ j ].Y - polygon[ i ].Y ) + polygon[ i ].X )
        {
            inside = !inside;
        }
    }

    return inside;
}

InformationsquelleAutor der Antwort M Katz

Berechnen Sie die orientierte Summe der Winkel zwischen dem Punkt p und jeweils das polygon apices. Wenn die Summe orientierte Winkel ist 360 Grad, der Punkt ist im inneren. Wenn die Summe 0 ist, wird der Punkt außerhalb.

Diese Methode gefällt mir besser, weil es stabiler und weniger abhängig von der numerischen Genauigkeit.

Methoden, die berechnen die Ebenheit der Anzahl der Kreuzungen sind begrenzt, weil Sie können 'Treffer' eine Spitze bei der Berechnung der Anzahl der Kreuzungen.

EDIT: Übrigens funktioniert diese Methode mit konkaven und konvexen Polygonen.

EDIT: vor kurzem fand ich eine ganze Wikipedia-Artikel auf das Thema.

InformationsquelleAutor der Antwort David S.

Diese Frage ist so interessant. Ich habe noch eine praktikable Idee unterscheidet sich von anderen Antworten zu diesem Beitrag.

Die Idee ist, die Summe der Winkel, um zu entscheiden, ob das Ziel innerhalb oder außerhalb. Wenn das Ziel ist, innerhalb einer Fläche, die Summe der Winkel bilden, die durch das Ziel und alle zwei Grenzübergängen werden 360. Wenn sich das Ziel außerhalb, wird die Summe nicht 360. Die Winkel für die Richtung hat. Wenn der Winkel rückwärts, der Winkel ist negativ. Diese ist genau wie die Berechnung der Wicklung Anzahl.

Beziehen sich auf dieses Bild, um ein grundlegendes Verständnis der Idee:

Mein Algorithmus übernimmt der im Uhrzeigersinn ist die positive Richtung. Hier ist eine mögliche Eingabe:

[[-122.402015, 48.225216], [-117.032049, 48.999931], [-116.919132, 45.995175], [-124.079107, 46.267259], [-124.717175, 48.377557], [-122.92315, 47.047963], [-122.402015, 48.225216]]

Im folgenden ist der python-code implementiert die Idee:

def isInside(self, border, target):
degree = 0
for i in range(len(border) - 1):
    a = border[i]
    b = border[i + 1]

    # calculate distance of vector
    A = getDistance(a[0], a[1], b[0], b[1]);
    B = getDistance(target[0], target[1], a[0], a[1])
    C = getDistance(target[0], target[1], b[0], b[1])

    # calculate direction of vector
    ta_x = a[0] - target[0]
    ta_y = a[1] - target[1]
    tb_x = b[0] - target[0]
    tb_y = b[1] - target[1]

    cross = tb_y * ta_x - tb_x * ta_y
    clockwise = cross < 0

    # calculate sum of angles
    if(clockwise):
        degree = degree + math.degrees(math.acos((B * B + C * C - A * A) /(2.0 * B * C)))
    else:
        degree = degree - math.degrees(math.acos((B * B + C * C - A * A) /(2.0 * B * C)))

if(abs(round(degree) - 360) <= 3):
    return True
return False

InformationsquelleAutor der Antwort Junbang Huang

Wirklich wie in der Lösung geschrieben von Nirg und bearbeitet von bobobobo. Ich schaffte es gerade noch javascript freundlich und ein wenig besser lesbar ist für meine Verwendung:

function insidePoly(poly, pointx, pointy) {
    var i, j;
    var inside = false;
    for (i = 0, j = poly.length - 1; i < poly.length; j = i++) {
        if(((poly[i].y > pointy) != (poly[j].y > pointy)) && (pointx < (poly[j].x-poly[i].x) * (pointy-poly[i].y) /(poly[j].y-poly[i].y) + poly[i].x) ) inside = !inside;
    }
    return inside;
}

InformationsquelleAutor der Antwort Dave Seidman

David zweiter kolbenringstoss Antwort ist so ziemlich der standard Allgemeine Antwort, und Richard T ist die gemeinsame Optimierung, obwohl therre gibt einige andere. Andere starke Optimierungen basieren auf weniger Allgemeine Lösungen. Zum Beispiel, wenn Sie gehen, um zu überprüfen, das gleiche polygon mit der Menge der Punkte, die triangulation des Polygons kann die Dinge beschleunigen enorm, da gibt es eine Reihe von sehr schnellen ZINN-Suche-algorithmen. Ein anderes ist, wenn das polygon und die Punkte werden auf einer begrenzten Ebene mit niedriger Auflösung, beispielsweise eine Bildschirm-Anzeige, können Sie die Farbe des Polygons auf eine memory-mapped display-Puffer in einer bestimmten Farbe, und überprüfen Sie die Farbe eines bestimmten pixels, um zu sehen, ob es liegt in den Polygonen.

Wie viele Optimierungen, diese basieren auf spezifischen statt Allgemeinen Fällen und Ertrag beneifits basierend auf fortgeführten Zeit eher als einmaligen Verwendung.

In diesem Bereich zu arbeiten, fand ich Joeseph O ' Rourke 'Berechnung der Geometrie in C' ISBN 0-521-44034-3 eine große Hilfe.

InformationsquelleAutor der Antwort Shane MacLaughlin

Ich weiß, das ist alt, aber hier ist ein ray-casting-Algorithmus implementiert, in Kakao, falls es jemanden interessiert. Nicht sicher, es ist der effizienteste Weg, Dinge zu tun, aber es kann jemand helfen.

- (BOOL)shape:(NSBezierPath *)path containsPoint:(NSPoint)point
{
    NSBezierPath *currentPath = [path bezierPathByFlatteningPath];
    BOOL result;
    float aggregateX = 0; //I use these to calculate the centroid of the shape
    float aggregateY = 0;
    NSPoint firstPoint[1];
    [currentPath elementAtIndex:0 associatedPoints:firstPoint];
    float olderX = firstPoint[0].x;
    float olderY = firstPoint[0].y;
    NSPoint interPoint;
    int noOfIntersections = 0;

    for (int n = 0; n < [currentPath elementCount]; n++) {
        NSPoint points[1];
        [currentPath elementAtIndex:n associatedPoints:points];
        aggregateX += points[0].x;
        aggregateY += points[0].y;
    }

    for (int n = 0; n < [currentPath elementCount]; n++) {
        NSPoint points[1];

        [currentPath elementAtIndex:n associatedPoints:points];
        //line equations in Ax + By = C form
        float _A_FOO = (aggregateY/[currentPath elementCount]) - point.y;  
        float _B_FOO = point.x - (aggregateX/[currentPath elementCount]);
        float _C_FOO = (_A_FOO * point.x) + (_B_FOO * point.y);

        float _A_BAR = olderY - points[0].y;
        float _B_BAR = points[0].x - olderX;
        float _C_BAR = (_A_BAR * olderX) + (_B_BAR * olderY);

        float det = (_A_FOO * _B_BAR) - (_A_BAR * _B_FOO);
        if (det != 0) {
            //intersection points with the edges
            float xIntersectionPoint = ((_B_BAR * _C_FOO) - (_B_FOO * _C_BAR)) /det;
            float yIntersectionPoint = ((_A_FOO * _C_BAR) - (_A_BAR * _C_FOO)) /det;
            interPoint = NSMakePoint(xIntersectionPoint, yIntersectionPoint);
            if (olderX <= points[0].x) {
                //doesn't matter in which direction the ray goes, so I send it right-ward.
                if ((interPoint.x >= olderX && interPoint.x <= points[0].x) && (interPoint.x > point.x)) {  
                    noOfIntersections++;
                }
            } else {
                if ((interPoint.x >= points[0].x && interPoint.x <= olderX) && (interPoint.x > point.x)) {
                     noOfIntersections++;
                } 
            }
        }
        olderX = points[0].x;
        olderY = points[0].y;
    }
    if (noOfIntersections % 2 == 0) {
        result = FALSE;
    } else {
        result = TRUE;
    }
    return result;
}

InformationsquelleAutor der Antwort diatrevolo

Auch ich dachte 360 addieren funktioniert nur für konvexe Polygone, aber das ist nicht wahr.

Diese Website hat ein nettes Diagramm zeigt genau das, und eine gute Erklärung auf Treffer testen:
Gamasutra - Absturz in das Neue Jahr: Collision Detection

InformationsquelleAutor der Antwort

Java-Version:

public class Geocode {
    private float latitude;
    private float longitude;

    public Geocode() {
    }

    public Geocode(float latitude, float longitude) {
        this.latitude = latitude;
        this.longitude = longitude;
    }

    public float getLatitude() {
        return latitude;
    }

    public void setLatitude(float latitude) {
        this.latitude = latitude;
    }

    public float getLongitude() {
        return longitude;
    }

    public void setLongitude(float longitude) {
        this.longitude = longitude;
    }
}

public class GeoPolygon {
    private ArrayList<Geocode> points;

    public GeoPolygon() {
        this.points = new ArrayList<Geocode>();
    }

    public GeoPolygon(ArrayList<Geocode> points) {
        this.points = points;
    }

    public GeoPolygon add(Geocode geo) {
        points.add(geo);
        return this;
    }

    public boolean inside(Geocode geo) {
        int i, j;
        boolean c = false;
        for (i = 0, j = points.size() - 1; i < points.size(); j = i++) {
            if (((points.get(i).getLongitude() > geo.getLongitude()) != (points.get(j).getLongitude() > geo.getLongitude())) &&
                    (geo.getLatitude() < (points.get(j).getLatitude() - points.get(i).getLatitude()) * (geo.getLongitude() - points.get(i).getLongitude()) /(points.get(j).getLongitude() - points.get(i).getLongitude()) + points.get(i).getLatitude()))
                c = !c;
        }
        return c;
    }

}

InformationsquelleAutor der Antwort YongJiang Zhang

Gibt es nichts mehr wunderschöne als eine induktive definition eines Problems. Der Vollständigkeit halber hier haben Sie eine version im prolog, die sich vielleicht auch klären, die thoughs hinter ray-casting:

Basiert auf der simulation der Einfachheit Algorithmus in http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html

Einige Helfer Prädikate:

exor(A,B):- \+A,B;A,\+B.
in_range(Coordinate,CA,CB) :- exor((CA>Coordinate),(CB>Coordinate)).

inside(false).
inside(_,[_|[]]).
inside(X:Y, [X1:Y1,X2:Y2|R]) :- in_range(Y,Y1,Y2), X > ( ((X2-X1)*(Y-Y1))/(Y2-Y1) +      X1),toggle_ray, inside(X:Y, [X2:Y2|R]); inside(X:Y, [X2:Y2|R]).

get_line(_,_,[]).
get_line([XA:YA,XB:YB],[X1:Y1,X2:Y2|R]):- [XA:YA,XB:YB]=[X1:Y1,X2:Y2]; get_line([XA:YA,XB:YB],[X2:Y2|R]).

Die Gleichung der Linie, angegeben 2 Punkte A und B (Zeile(A,B)) ist:

                    (YB-YA)
           Y - YA = ------- * (X - XA) 
                    (XB-YB) 

Ist es wichtig, dass die Drehrichtung für die Linie ist
setted clock-wise für Grenzen und anti-clock-wise für Löcher.
Werden wir zu prüfen, ob der Punkt (X,Y), ich.e der getestete Punkt ist auf der linken Seite
halbebene, die von unserer Linie (es ist eine Frage des Geschmacks ist, könnte es auch sein
der rechten Seite, sondern auch die Richtung der Grenzen, die Zeilen geändert werden in
diesem Fall), ist dieses Projekt der Strahl von dem Punkt nach rechts (oder Links)
und bestätigen Sie die Kreuzung mit der Linie. Wir haben uns entschieden Projekt
der Strahl in der horizontalen Richtung (wieder ist es eine Frage des Geschmacks,
es könnte auch getan werden, in der vertikalen mit ähnlichen Einschränkungen), so haben wir:

               (XB-XA)
           X < ------- * (Y - YA) + XA
               (YB-YA) 

Nun müssen wir wissen, wenn der Punkt auf der linken (oder rechten) Seite von
das Liniensegment, nicht die gesamte Ebene, also müssen wir
Schränken Sie die Suche nur auf dieses segment, aber das ist einfach da
im segment mit nur einem Punkt in die Linie kann höher sein
als Y in der vertikalen Achse. Da dies eine stärkere Einschränkung es
muss der erste sein zu überprüfen, also nehmen wir zuerst nur die Zeilen
die Erfüllung dieser Forderung und dann überprüfen Sie seine Position. Der Jordan
Kurve theorem jede ray projiziert, um ein polygon muss sich in ein
noch Anzahl der Zeilen. So wir sind fertig, wir werfen den Strahl auf die
die Rechte und dann jedesmal, wenn es kreuzt eine Linie, wechseln Ihren Zustand.
Aber in unserer Umsetzung sind wir goint zu prüfen, die Länge der
die Tasche von Lösungen, treffen die gegebenen Beschränkungen und entscheiden
innership auf. für jede Zeile in der polygon dies zu tun.

is_left_half_plane(_,[],[],_).
is_left_half_plane(X:Y,[XA:YA,XB:YB], [[X1:Y1,X2:Y2]|R], Test) :- [XA:YA, XB:YB] =  [X1:Y1, X2:Y2], call(Test, X , (((XB - XA) * (Y - YA)) /(YB - YA) + XA)); 
                                                        is_left_half_plane(X:Y, [XA:YA, XB:YB], R, Test).

in_y_range_at_poly(Y,[XA:YA,XB:YB],Polygon) :- get_line([XA:YA,XB:YB],Polygon),  in_range(Y,YA,YB).
all_in_range(Coordinate,Polygon,Lines) :- aggregate(bag(Line),    in_y_range_at_poly(Coordinate,Line,Polygon), Lines).

traverses_ray(X:Y, Lines, Count) :- aggregate(bag(Line), is_left_half_plane(X:Y, Line, Lines, <), IntersectingLines), length(IntersectingLines, Count).

% This is the entry point predicate
inside_poly(X:Y,Polygon,Answer) :- all_in_range(Y,Polygon,Lines), traverses_ray(X:Y, Lines, Count), (1 is mod(Count,2)->Answer=inside;Answer=outside).

InformationsquelleAutor der Antwort jdavid_1385

Heres ein point-in-polygon-test in C, die nicht mit ray-casting. Und es kann für überlappende Bereiche (selbst-Kreuzungen), sehen die use_holes argument.

/* math lib (defined below) */
static float dot_v2v2(const float a[2], const float b[2]);
static float angle_signed_v2v2(const float v1[2], const float v2[2]);
static void copy_v2_v2(float r[2], const float a[2]);

/* intersection function */
bool isect_point_poly_v2(const float pt[2], const float verts[][2], const unsigned int nr,
                         const bool use_holes)
{
    /* we do the angle rule, define that all added angles should be about zero or (2 * PI) */
    float angletot = 0.0;
    float fp1[2], fp2[2];
    unsigned int i;
    const float *p1, *p2;

    p1 = verts[nr - 1];

    /* first vector */
    fp1[0] = p1[0] - pt[0];
    fp1[1] = p1[1] - pt[1];

    for (i = 0; i < nr; i++) {
        p2 = verts[i];

        /* second vector */
        fp2[0] = p2[0] - pt[0];
        fp2[1] = p2[1] - pt[1];

        /* dot and angle and cross */
        angletot += angle_signed_v2v2(fp1, fp2);

        /* circulate */
        copy_v2_v2(fp1, fp2);
        p1 = p2;
    }

    angletot = fabsf(angletot);
    if (use_holes) {
        const float nested = floorf((angletot / (float)(M_PI * 2.0)) + 0.00001f);
        angletot -= nested * (float)(M_PI * 2.0);
        return (angletot > 4.0f) != ((int)nested % 2);
    }
    else {
        return (angletot > 4.0f);
    }
}

/* math lib */

static float dot_v2v2(const float a[2], const float b[2])
{
    return a[0] * b[0] + a[1] * b[1];
}

static float angle_signed_v2v2(const float v1[2], const float v2[2])
{
    const float perp_dot = (v1[1] * v2[0]) - (v1[0] * v2[1]);
    return atan2f(perp_dot, dot_v2v2(v1, v2));
}

static void copy_v2_v2(float r[2], const float a[2])
{
    r[0] = a[0];
    r[1] = a[1];
}

Hinweis: dies ist eine der weniger optimalen Methoden, denn es enthält eine Menge Anrufe zu atan2faber es kann von Interesse sein, die Entwickler Lesen dieses Threads (in meinen tests hat seine ~23x langsamer, dann über den line-intersection-Methode).

InformationsquelleAutor der Antwort ideasman42

Umzugehen, mit den folgenden besonderen Fällen in Ray-casting-Algorithmus:

1. Der Strahl überlappt ein polygon-Seite.
2. Der Punkt innerhalb des Polygons und der Strahl geht durch einen Eckpunkt des Polygons.
3. Der Punkt außerhalb des Polygons und der Strahl berührt nur einer der polygon-Winkel.

Überprüfen Die Bestimmung, Ob Ein Punkt In Einem Komplexen Polygon. Der Artikel bietet eine einfache Möglichkeit, Sie zu lösen, so gibt es keine Besondere Behandlung erforderlich, für die genannten Fälle.

InformationsquelleAutor der Antwort Justin

Wenn Sie auf der Suche für ein java-script-Bibliothek gibt es ein javascript, google-maps-v3-Erweiterung für die Polygon-Klasse zu erkennen, ob ein Punkt innerhalb wohnt.

var polygon = new google.maps.Polygon([], "#000000", 1, 1, "#336699", 0.3);
var isWithinPolygon = polygon.containsLatLng(40, -90);

Google Extention Github

InformationsquelleAutor der Antwort shana

Die Antwort hängt davon ab, ob die einfache oder komplexe Polygone. Einfache Polygone dürfen keine Liniensegmente Schnittpunkte. So können Sie die Löcher, aber die Linien nicht kreuzen einander. Komplexe Regionen kann die Linie Schnittpunkte - so können Sie die überlappenden Regionen, oder von Regionen, die einander berühren, nur durch einen einzigen Punkt.

Für einfache Polygone, den besten Algorithmus ist Ray casting (Crossing number) - Algorithmus. Für komplexe Polygone der Algorithmus erkennt nicht die Punkte, die innerhalb der überlappenden Regionen. Also für komplexe Polygone verwenden Sie die Winding number Algorithmus.

Hier ist ein exzellenter Artikel mit C Implementierung von algorithmen. Ich versuchte Sie, und Sie funktionieren gut.

http://geomalgorithms.com/a03-_inclusion.html

InformationsquelleAutor der Antwort Timmy_A

Habe ich eine Python-Implementierung von nirg ' s c++ code:

Eingänge

• bounding_points: Knoten, aus denen das polygon.

• bounding_box_positions: Kandidaten Punkte zu filtern. (In meiner Implementierung erstellt von der bounding-box.

  (Die Eingänge Listen, Tupel im format: [(xcord, ycord), ...])

Gibt

• Alle Punkte innerhalb des Polygons.

def polygon_ray_casting(self, bounding_points, bounding_box_positions):
    # Arrays containing the x- and y-coordinates of the polygon's vertices.
    vertx = [point[0] for point in bounding_points]
    verty = [point[1] for point in bounding_points]
    # Number of vertices in the polygon
    nvert = len(bounding_points)
    # Points that are inside
    points_inside = []

    # For every candidate position within the bounding box
    for idx, pos in enumerate(bounding_box_positions):
        testx, testy = (pos[0], pos[1])
        c = 0
        for i in range(0, nvert):
            j = i - 1 if i != 0 else nvert - 1
            if( ((verty[i] > testy ) != (verty[j] > testy))   and
                    (testx < (vertx[j] - vertx[i]) * (testy - verty[i]) / (verty[j] - verty[i]) + vertx[i]) ):
                c += 1
        # If odd, that means that we are inside the polygon
        if c % 2 == 1: 
            points_inside.append(pos)


    return points_inside

Wieder, die Idee stammt aus hier

InformationsquelleAutor der Antwort Noresourses