Überprüfen Sie, ob sich der Punkt innerhalb eines Polygons befindet

75

Ich möchte überprüfen, ob ein Punkt innerhalb eines bestimmten Polygons liegt. Das Polygon lautet:

 polygon=   [ [-73.89632720118, 40.8515320489962],
              [-73.8964878416508, 40.8512476593594],
              [-73.8968799791431, 40.851375925454],
              [-73.8967188588015, 40.851660158514],
              [-73.89632720118, 40.8515320489962] ]

Die Punkte, die ich überprüfen möchte, sind:

1 = [40.8515320489962,-73.89632720118]
2 = [40.8512476593594,-73.8964878416508]
3 = [40.851375925454,-73.8968799791431]
4 = [40.851660158514,-73.8967188588015]
5 = [40.8515320489962,-73.89632720118]

Wie kann ich feststellen, ob jeder dieser Punkte innerhalb dieses Polygons liegt?

Der folgende Algorithmus funktioniert nicht. Ich weiß nicht warum.

pt[lat,long]

function isPointInPoly(poly, pt){
    for(var c = false, i = -1, l = poly.length, j = l - 1; ++i < l; j = i)
        ((poly[i][1] <= pt[1] && pt[1] < poly[j][1]) || (poly[j][1] <= pt[1] && pt[1] < poly[i].y))
        && (pt[0] < (poly[j][0] - poly[i][0]) * (pt[1] - poly[i][1]) / (poly[j][1] - poly[i][1]) + poly[i][0])
        && (c = !c);
    return c;
}

Ich möchte keine Drittanbieterlösung wie die Google Maps-API oder diese https://github.com/mattwilliamson/Google-Maps-Point-in-Polygon verwenden .

Mein Versuch ist hier: http://jsfiddle.net/nvNNF/2/

user3378649
quelle
4
Wählen Sie einen Punkt außerhalb der Polygonprüfung aus und prüfen Sie, ob eine Linie von diesem Punkt zu Ihrem Punkt eine ungerade Anzahl von Linien schneidet, die den Umfang des Polygons definieren.
Hogan
Sie können den Code hier live überprüfen: Ich habe einen Punkt in das Polygon jsfiddle.net/nvNNF/2 eingefügt und er gibt "False" zurück
user3378649
poly[i].ysollte poly[i][1]am Ende von Zeile 3 stehen. Außerdem prüft diese Funktion, ob der Punkt innerhalb des Polygons liegt und nicht, ob der Punkt zum Polygon gehört.
Ben
Kein Grund für Ihre for-Schleife, so viele Variablen zu haben, was die Lesbarkeit beeinträchtigt. Sie können jede Bedingung einzeln testen und dann alarmieren. Sobald Sie das Ende Ihres Codes erreicht haben, kombinieren Sie alle Ihre Bedingungen und überprüfen sie erneut.
fast ein Anfänger

Antworten:

111

Auf Github gibt es ein Projekt mit dem folgenden Code: https://github.com/substack/point-in-polygon (MIT-Lizenz):

function inside(point, vs) {
    // ray-casting algorithm based on
    // https://wrf.ecse.rpi.edu/Research/Short_Notes/pnpoly.html/pnpoly.html
    
    var x = point[0], y = point[1];
    
    var inside = false;
    for (var i = 0, j = vs.length - 1; i < vs.length; j = i++) {
        var xi = vs[i][0], yi = vs[i][1];
        var xj = vs[j][0], yj = vs[j][1];
        
        var intersect = ((yi > y) != (yj > y))
            && (x < (xj - xi) * (y - yi) / (yj - yi) + xi);
        if (intersect) inside = !inside;
    }
    
    return inside;
};

Verwendung:

// array of coordinates of each vertex of the polygon
var polygon = [ [ 1, 1 ], [ 1, 2 ], [ 2, 2 ], [ 2, 1 ] ];
inside([ 1.5, 1.5 ], polygon); // true

Die Testfunktion finden Sie hier: https://github.com/substack/point-in-polygon/blob/master/index.js

Hinweis: Dieser Code funktioniert nicht zuverlässig, wenn der Punkt eine Ecke des Polygons oder eine Kante ist. Hier gibt es eine verbesserte Version: https://github.com/mikolalysenko/robust-point-in-polygon

Aaron Digulla
quelle
Ich denke, es ist in Ordnung, einen Code zu kopieren und einzufügen, vorausgesetzt, Sie haben die Referenz eingefügt. Es wird die Gutschrift an den ursprünglichen Autor geben.
Chathuranga Chandrasekara
1
@ AaronDigulla das ist nicht ganz richtig. Versuchen Sie diese einfache Sache in Javascript: 0,3 - 0,2 und console.log die Ausgabe
Pedro Silva
2
@PedroSilva Lassen Sie es mich so sagen: Es funktioniert entweder in C / C ++, Java und JavaScript oder es funktioniert für keines der drei. Sie alle verwenden genau dieselbe Methode, um Zahlen darzustellen. Die Verwendung eines Compilers verleiht Programmiersprachen keine mythischen Merkmale. Die C / C ++ - und Java-Bibliotheken können das Ergebnis beim Drucken nur ein wenig besser abrunden.
Aaron Digulla
1
danke, hat super funktioniert, aber gerade festgestellt, dass es gemischte Ergebnisse für Punkte gibt, die an den Kanten oder Ecken des Polygons liegen ... wie könnte es bearbeitet werden, um diese wie immer im Inneren zu akzeptieren?
Bäumeeal7
1
Wenn Sie die Koordinaten des Polygons an diese Funktion übergeben, um zu überprüfen, ob sie sich in sich selbst befinden, erhalten Sie die Hälfte davon.
Alexander Pravdin
15

Ihr Polygonarray sieht aus wie ein coordinatesArray in der GeoJSON-Polygonstruktur (weitere Informationen finden Sie unter https://macwright.org/2015/03/23/geojson-second-bite.html und http://geojson.org ). Vielleicht können Sie Bibliotheken verwenden, die mit geoJSON-Daten arbeiten? Antworten und Kommentare zu OP in anzeigen Ist es möglich, mithilfe von JavasScript festzustellen, ob sich ein GeoJSON-Punkt innerhalb eines GeoJSON-Polygons befindet?

Kurz gesagt, mein Tag wurde von turf( https://github.com/turfjs/turf ) gespeichert. Es gibt auch d3( https://github.com/d3/d3-geo#geoContains ), aber ich hatte Probleme damit.

UPD: Mir ist aufgefallen, turfdass inkonsistente Ergebnisse erzielt werden, wenn der Punkt auf der Kante des Polygons liegt. Ich habe ein Problem erstellt und warte auf die Antwort der Entwickler.

UPD2: Das Problem mit den turfGrenzpunkten wird mithilfe der neuesten Version von behoben (ich habe 3.0.14 anstelle von 4.6.1 verwendet). Jetzt ist alles in Ordnung.

Surfrider
quelle
10

Hier ist die Funktion, die ich endlich zum Laufen gebracht habe. Ich habe es bekommen, indem ich von hier aus C-Code in Javascript übernommen habe (mit Erklärung).

function checkcheck (x, y, cornersX, cornersY) {

    var i, j=cornersX.length-1 ;
    var odd = false;

    var pX = cornersX;
    var pY = cornersY;

    for (i=0; i<cornersX.length; i++) {
        if ((pY[i]< y && pY[j]>=y ||  pY[j]< y && pY[i]>=y)
            && (pX[i]<=x || pX[j]<=x)) {
              odd ^= (pX[i] + (y-pY[i])*(pX[j]-pX[i])/(pY[j]-pY[i])) < x; 
        }

        j=i; 
    }

return odd;
}

Wobei cornersX= Array mit x oder Breitenscheitel Array, cornersY= Array mit y oder Längengrad Array. X, Y - Breite und Länge des getesteten Punktes.

Markkillah
quelle
Vielen Dank! Funktioniert super. Ich konnte das anpassen. Die Rückgabewerte sind entweder false, 0 oder 1. Ich habe in var oddNodes = 0 geändert und oddNodes == 1 zurückgegeben, um einen endgültigen Booleschen Wert zu erhalten.
Turbo
Es funktioniert nicht für mich. Ich bekomme immer 1. was auch immer drinnen oder draußen ist. Bitte hilf mir.
Krishna
Das funktioniert nicht; Gibt es überhaupt eine OpenSource-Funktion, um einen Bereich mit einer Farbe zu füllen? In diesem Fall müssen lediglich alle gefüllten Punkte mit bestimmten Koordinaten verglichen werden, was für komplexe Polygone viel zuverlässiger ist.
Jumpjack
0

In meinem Fall habe ich folgendes getan, es funktioniert gut für mich

function isLatLngInZone(latLngs,lat,lng){
  // latlngs = [{"lat":22.281610498720003,"lng":70.77577162868579},{"lat":22.28065743343672,"lng":70.77624369747241},{"lat":22.280860953131217,"lng":70.77672113067706},{"lat":22.281863655593973,"lng":70.7762061465462}];
  vertices_y = new Array();
  vertices_x = new Array();
  longitude_x = lng;
  latitude_y = lat;
  latLngs = JSON.parse(latLngs);
  var r = 0;
  var i = 0;
  var j = 0;
  var c = 0;
  var point = 0;

  for(r=0; r<latLngs.length; r++){
   vertices_y.push(latLngs[r].lat);
   vertices_x.push(latLngs[r].lng);
  }
  points_polygon = vertices_x.length;
  for(i = 0, j = points_polygon; i < points_polygon; j = i++){
   point = i;
   if(point == points_polygon)
    point = 0;
   if ( ((vertices_y[point]  >  latitude_y != (vertices_y[j] > latitude_y)) && (longitude_x < (vertices_x[j] - vertices_x[point]) * (latitude_y - vertices_y[point]) / (vertices_y[j] - vertices_y[point]) + vertices_x[point]) ) )
    c = !c;
  }
return c;
}
Renish Gotecha
quelle