Verifica in quale regione è presente un indicatore di posizione

Questo problema geografico è chiamato Punto in poligono , e c'è una soluzione in Python here .

Per completezza qui è in JavaScript con alcuni esempi:

// x,y are point coordinates
// poly is a list of tuples [[x,y], [x,y], ....]
function isPointInPolygon(x,y,poly) {
    var num = poly.length,
        i = 0;
        j = num - 1;
        c = false;

    for( i = 0; i < num; i++ ) {
        if( ((poly[i][1] > y) != (poly[j][1] > y)) && (x < (poly[j][0] - poly[i][0]) * (y - poly[i][1]) / (poly[j][1] - poly[i][1]) + poly[i][0]) ) {
            c = !c;
        }
        j = i;
    }
    return(c);
}

isPointInPolygon(5,1, [[0,0], [7,3], [9,0]]); // true
isPointInPolygon(5,3, [[0,0], [7,3], [9,0]]); // false

Questo non dovrebbe essere usato per le coordinate lat / lng per aree molto grandi. Tuttavia, la scala della città dovrebbe andare bene.

Aggiornamento

Rileggendo la domanda non sono sicuro di aver risposto a sufficienza. Ho aggiunto un nuovo codice in cui il browser del client funzionerà molto meglio di O (NrMarkers * NrPolygons) a patto che i poligoni non si sovrappongano troppo. Questo codice espanso crea e può memorizzare rettangoli di delimitazione per poligoni per ridurre le chiamate costose a isPointInPolygon .

// Not to be used for large areas or near equator or 0/180 longitude
// x,y are point coordinates
// poly is a list of tuples [[x,y], [x,y], ....]
function isPointInPolygon(x, y, poly) {
  var num = poly.length,
      i = 0;
  j = num - 1;
  c = false;

  for (i = 0; i < num; i++) {
    if (((poly[i][1] > y) != (poly[j][1] > y)) && (x < (poly[j][0] - poly[i][0]) * (y - poly[i][1]) / (poly[j][1] - poly[i][1]) + poly[i][0])) {
      c = !c;
    }
    j = i;
  }
  return (c);
}

function arePointsInPolygons(points, polygons) {
    var pointnum = points.length,
        polynum = polygons.length,
        vertnum,
        pb = polybounds,
        results = [],
        pt, pg, v;

    if( pb.length === 0 ) {
        // get the polygon bounds for each polygon
        for( pg = 0; pg < polynum; pg++ ) {
            pb.push([false, false, false, false]);
            vertnum = polygons[pg].length;

            for( v = 0; v < vertnum; v++ ) {
                // north
                if( pb[pg][0] === false || polygons[pg][v][1] > pb[pg][0] ) {
                    pb[pg][0] = polygons[pg][v][1];
                }
                // east
                if( pb[pg][1] === false || polygons[pg][v][0] > pb[pg][1] ) {
                    pb[pg][1] = polygons[pg][v][0];
                }
                // south
                if( pb[pg][2] === false || polygons[pg][v][1] < pb[pg][2] ) {
                    pb[pg][2] = polygons[pg][v][1];
                }
                // west
                if( pb[pg][3] === false || polygons[pg][v][0] < pb[pg][3] ) {
                    pb[pg][3] = polygons[pg][v][0];
                }
            }
        }
        polybounds = pb;
    }

    // check which points fall within the bounds, if yes call isPointInPolygon
    for( pt = 0; pt < pointnum; pt++ ) {
        results.push([]);
        for( pg = 0; pg < polynum; pg++ ) {
            if( points[pt][0] > pb[pg][3] && points[pt][0] < pb[pg][1] &&
               points[pt][1] > pb[pg][2] && points[pt][1] < pb[pg][0] ) {
                if( isPointInPolygon(points[pt][0], points[pt][1], polygons[pg]) ) {
                    results[pt].push(pg);
                }
            }
        }
    }

    return(results);
}

// Test
var i,
    inside,
    numiter = 1000000,
    points = [];
for( i = 0; i < numiter; i++ ) {
    points.push([parseInt(Math.random()*10,10), parseInt(Math.random()*10,10)]);
}

// test isPointInPolygon for list of many points
inside = 0;
var start = new Date().getTime();
for( i = 0; i < numiter; i++ ) {
    inside += isPointInPolygon(points[i][0], points[i][1], [[0, 0], [7, 3], [9, 0]]) ? 1 : 0;
}
console.log(new Date().getTime() - start);


// do same test with optimization
var polybounds = [];
var start = new Date().getTime();
arePointsInPolygons(points, [[[0, 1], [7, 3], [9, 0]],[[0, 3], [3, 3], [3, -1]]]);
console.log(new Date().getTime() - start); // slower, builds polybounds

var start = new Date().getTime();
arePointsInPolygons(points, [[[0, 1], [7, 3], [9, 0]],[[0, 3], [3, 3], [3, -1]]]);
console.log(new Date().getTime() - start);

// arePointsInPolygons returns array of length equal to number of points containing arrays of polygon indexes in which the points fall - empty indicates not in any.

Aggiornamento delle limitazioni

Guarda la mappa qui sotto: ( source )

Il confine settentrionale, che segue il 49 ° parallelo, è a volte dritto e talvolta curvo sulle mappe. Per le mappe Web la proiezione utilizzata mostra il bordo come orizzontale. Il pericolo si trova quando un punto rientra nell'area in una proiezione ma non nell'altra. Il percorso lungo una superficie curva è ambiguo. Vedi diagramma:

Speriamo che non sia troppo tardi ... Sto avendo un problema simile, tranne per il fatto che il numero dei miei punti è espresso in miliardi e il numero di poligoni potrebbe essere in migliaia.

Anche se questa idea non mi è stata di aiuto, potrebbe aiutarti: se l'area coperta dai poligoni è relativamente piccola e / o la risoluzione non è troppo fine, puoi creare una griglia di tutti i punti nell'area e ogni punto pre-computa il poligono al quale appartiene. Quindi, in fase di esecuzione, troverai i 4 punti della griglia che si estendono su un quadrato / rettangolo che contiene il tuo punto interrogativo, e per ogni punto della griglia ti capirai il suo poligono, allora avrai 4 poligoni con cui lavorare.

Nel complesso, sono d'accordo con @MichaelIT che i database spaziali sono piuttosto veloci e PostGIS (estensione PostgreSQL) può facilmente memorizzare nella cache le forme dei poligoni con cui lavori, quindi non sarà più lento della tua abitudine codice.