2

I'm trying to code this in Leaflet, but the key is finding the formula to do this.

Give a polygon (filled in the image), how can I expand it to fit a grid (lat/lon, outer line in image) ?

Fill - input polygon. Line - expected outcome.

This is reminiscent of polgyon/raster intersection tools available in GIS programs, but in order to create this in leaflet/javascript, I need to know the actual formula.

A simple formula without frequent iterations is needed, since at time the shape can be much bigger than the grids and might be slow if I am simply checking for intersections at each grid and changing directions depending on the outcome.

  • Just create a polygons for each grid cell and check if they intersect with your polygone. What do you mean by expand? – wittich Feb 6 '16 at 23:54
  • My approach would be to find the bounding box (with corners rounded to the snap coordinates) and then trim away at that box spiraling inwards. I realize that's far from a solution, but it might help. – barrycarter Feb 9 '16 at 17:55
1

Check out turf.js, which should give you the geospatial capabilities to do what you need in browser. In particular, turf.squareGrid and turf.merge and (edited) the extension turf-overlaps.

Something like this might get you most of the way there:

var poly = <geoJSONPolygon>;

var grid = turf.squareGrid(turf.extent(poly), cellWidth, unit);

var gridOverlaps = grid.features.filter(function(gridFeature) {
  return overlaps(poly, gridFeature);
});

var boundingGrid = turf.merge(turf.featurecollection(gridOverlaps));
  • I don't think merge works the way you described, it looks like it merges all features regardless of overlap. This should give just one big rectangle, though when I tried it it just gave me back my original polygon. – Anika Halota Feb 8 '16 at 22:38
  • @AnikaHalota ah yes, you're right. We'd be looking for something to select the overlap, and merge that. Unfortunately, turf's joins don't support polygon-to-polygon support (only point-to-polygon), otherwise turf.inside would work. After some googling, I found this extension for turf-overlaps. updating my answer. – James Conkling Feb 9 '16 at 0:14
0

This problem is looking for a supercover DDA line, or just a DDA (Digital differential analyzer) line. Once the line is found (perimeter), it is simple enough to find the interior cells as well.

A description of the problem and difference can be found here: Bresenheim modified supercover algorithm

One useful code solution is shown here: Line Drawing on a Grid This isn't a supercover line, just a simple DDA line. The code shown here is very clear javascript and easy to implement. The only addition, if needed, is the "Point" class that is used but not detailed.

Another solution is shown on a stackoverflow post (can't link due to low reputation, search "supercover-dda-algorithm". This solution did not work out for me, but it was off just a tiny bit with some sort of rounding error, so it might work for someone else if they find what the trouble was.

This is a detailed description of the code I used to solve the above problem in javascript with Leaflet. The grid cells represent an underlying data matrix I am trying to extract data from given a user defined polygon.

1) Create conversion functions to convert from latitude longitude into a grid starting at (0,0). This was the easiest way I found to avoid any +- issues with lat/lon. My functions are for 1/4 degree grid cells, adjust to your needs.

function latLngToGrid(lat, lng){
  var x = (lng+179.875)*4;
  var y = (lat-89.875)*-4;
  return {y:y,x:x};
}

function gridToLatLng(x,y){
  var lng = x/4-179.875;
  var lat = y/-4+89.875;
  return {lat:lat,lng:lng};
}

2) Use the code from "Line Drawing on a Grid" along with the Point class in order to get the "line" function. You could also use the Leaflet point class.(Note some extended options available on that site if you're interested)

function Point(x,y){
  this.x = x;
  this.y = y;
}

3) Call the line function repeatedly on all points of the input polygon to get the collection of perimeter points. I am storing them in an x/y dictionary because I wanted to access them by index and not store doubles. (This might not be ideal, but it worked for me)

function getGridPerimeter(p){
  var p0,p1,ln;
  var perim = {};
  var pts = p.getLatLngs();

  p1 = latLngToGrid(pts[0].lat,pts[0].lng);

  var i,j;
  for (i=0; i< pts.length-1; i++){
    p0 = p1;
    p1 = latLngToGrid(pts[i+1].lat,pts[i+1].lng)
    ln = line(p0,p1);
    for (j=0; j<ln.length;j++){
        if (typeof perim[ln[j].x] == 'undefined'){
            perim[ln[j].x] = {};
        }
        perim[ln[j].x][ln[j].y] = true;
    }
  }

  //Separately redo the process for last point to first point.
  p0 = p1;
  p1 = latLngToGrid(pts[0].lat,pts[0].lng);
  ln = line(p0,p1);
  for (j=0; j<ln.length;j++){
    if (typeof perim[ln[j].x] == 'undefined'){
        perim[ln[j].x] = {};
    }
    perim[ln[j].x][ln[j].y] = true;
  }

  return perim;
}

4) Scan the list of perimeter points by each column. If any gaps are detected between two subsequent points in a column, add these to the final list of points. Does not work properly on concave polygons

function getGridPoints(p){
  var points,xs,ys,y0,y1;
  var perim = getGridPerimeter(p);
  xs = Object.keys(perim).map(Number).sort();

  for (var i=0; i < xs.length; i++){
    ys = Object.keys(perim[xs[i]]).map(Number).sort();
    if (ys.length == 1){
        continue;
    } else {
        y1 = ys[0];
        for (var j = 0 ; j<ys.length; j+=1){
            y0 = y1;
            y1 = ys[j+1];
            while (y0 < y1){
                y0 +=1;

                perim[xs[i]][y0] = true;
            }               
        }
    }
  }
  return perim;
}

5) Finally, if you were working in grid space, you can mark these on your map by reconverting to latLng space. This is one example, it will place a marker in the center of every selected cell.

function testGP(p,map){
  var all = getGridPoints(p);
  markGridPoints(all,map);
}

function markGridPoints(pts,map){
  var xs,ys;

  xs = Object.keys(pts).map(Number).sort(); 
  for (var i=0; i < xs.length; i++){
    ys = Object.keys(pts[xs[i]]).map(Number).sort();
    for (j=0; j<ys.length;j++){
        L.marker(gridToLatLng(xs[i],ys[j]), {title: 'x: ' + xs[i] + ' y: ' + ys[j]}).addTo(map);            
    }
  }

}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.