tile-cover - npm Package Compare versions

Comparing version 1.0.0 to 2.0.0

index.js

@@ -1,9 +0,5 @@
-var tilebelt = require('tilebelt'),
-    extent = require('geojson-extent'),
-    bboxIntersects = require('bbox-intersect'),
-    intersect = require('turf-intersect');
+var tilebelt = require('tilebelt');
 
 module.exports.geojson = function (geom, limits) {
     var locked = getLocked(geom, limits);
-
     var tileFeatures = locked.map(function (t) {
@@ -20,3 +16,2 @@ return tilebelt.tileToGeoJSON(t);
     var locked = getLocked(geom, limits);
-
     return locked;
@@ -27,3 +22,2 @@ };
     var locked = getLocked(geom, limits);
-
     return locked.map(function (tile) {
@@ -36,3 +30,2 @@ return tilebelt.tileToQuadkey(tile);
     var locked = [];
-
     if (geom.type === 'Point') {
@@ -50,9 +43,28 @@ locked.push(tilebelt.pointToTile(geom.coordinates[0], geom.coordinates[1], limits.max_zoom));
         }
+    } else if (geom.type === 'LineString') {
+        locked = hashToArray(lineCover(geom.coordinates, limits.max_zoom));
+    } else if (geom.type === 'MultiLineString') {
+        var tileHash = {};
+        for(var i = 0; i < geom.coordinates.length; i++) {
+            tileHash = hashMerge(tileHash, lineCover(geom.coordinates[i], limits.max_zoom));
+        }
+        locked = hashToArray(tileHash);
+    } else if (geom.type === 'Polygon') {
+        var tileHash = polyRingCover(geom.coordinates, limits.max_zoom);
+        locked = hashToArray(tileHash);
+    } else if (geom.type === 'MultiPolygon') {
+        var tileHash = {};
+        for(var i = 0; i < geom.coordinates.length; i++) {
+            var polyHash = Object.keys(polyRingCover(geom.coordinates[i], limits.max_zoom));
+            for(var k = 0; k < polyHash.length; k++) {
+                tileHash[polyHash[k]] = true;
+            }
+        }
+        locked = hashToArray(tileHash);
     } else {
-        var seed = tilebelt.bboxToTile(extent(geom));
-        if (!seed[3]) seed = [0, 0, 0];
-        splitSeek(seed, geom, locked, limits);
+        throw new Error('Geoemtry type not implemented');
+    }
+    if(limits.min_zoom !== limits.max_zoom){
         locked = mergeTiles(locked, limits);
     }
-
     return locked;
@@ -87,28 +99,314 @@ }
 
-function splitSeek (tile, geom, locked, limits) {
-    var tileCovers = true;
-    var doIntersect = needsIntersect(tilebelt.tileToGeoJSON(tile), geom);
-    var intersects;
-    if (doIntersect) {
-        try {
-            intersects = intersect(fc(tilebelt.tileToGeoJSON(tile)), fc(feature(geom)));
+function polyRingCover(ring, max_zoom) {
+    var segments = getSegments(ring);
+    var tileHash = {};
+    var min = [null,Infinity];
+    var max = [null,-Infinity];
+    for(var i = 0; i < ring[0].length; i++) { 
+        if(ring[0][i][1] < min[1]) {
+            min = ring[0][i];
+        } else if (ring[0][i][1] > max[1]) {
+            max = ring[0][i];
         }
-        catch(err) {
-            throw new Error(err.message)
+    }
+    var minTile = tilebelt.pointToTile(min[0], min[1], max_zoom);
+    var maxTile = tilebelt.pointToTile(max[0], max[1], max_zoom);
+    var y = maxTile[1];
+    while(y <= minTile[1]) {
+        // calculate intersections at each tile top-line
+        var intersections = [];
+        var tileTop = tilebelt.tileToBBOX([0, y, max_zoom])[3];
+        for(var i = 0; i < segments.length; i++) {
+            var localMin = isLocalMin(i, segments);
+            var localMax = isLocalMax(i, segments);
+            var intersection = lineIntersects(
+                0, tileTop,
+                1, tileTop,
+                segments[i][0][0], segments[i][0][1],
+                segments[i][1][0], segments[i][1][1],
+                localMin || localMax);
+            if (intersection !== false) {
+                intersections.push(intersection);
+            }
         }
+        // sort intersections by x
+        intersections = intersections.sort(function(a, b) {
+            return a[0] - b[0];
+        });
+        // add tiles between intersection pairs
+        for(var i = 0; i < intersections.length - 1; i++) {
+            if(i % 2 === 0){
+                var enter = tilebelt.pointToTile(intersections[i][0], intersections[i][1], max_zoom)[0];
+                var exit = tilebelt.pointToTile(intersections[i+1][0], intersections[i+1][1], max_zoom)[0];
+                var x = enter;
+                while (x <= exit) {
+                    tileHash[x+'/'+y+'/'+max_zoom] = true;
+                    x++;
+                }
+            }
+        }
+        y++;
     }
-    if (!intersects || intersects.features[0].type === 'GeometryCollection') {
-        tileCovers = false;
+    // add any missing tiles with a segments pass
+    for(var i = 0; i < ring.length; i++) {
+        tileHash = hashMerge(tileHash, lineCover(ring[i], max_zoom));
     }
+    
+    return tileHash;
+}
 
-    if (tile[2] === 0 || (tileCovers && tile[2] < limits.max_zoom)) {
-        var children = tilebelt.getChildren(tile);
-        children.forEach(function (t) {
-            splitSeek(t, intersects.features[0], locked, limits);
-        });
-    } else if (tileCovers) {
-        locked.push(tile);
+// Convert a set of rings into segments connecting coordinates.
+// Drops degenerate segments and merges sequential horizontal segments.
+module.exports.getSegments = getSegments;
+function getSegments(ring) {
+    // construct segments
+    var segments = [];
+    var last = null;
+    var start;
+    var end;
+    for(var i = 0; i < ring.length; i++) {
+        for(var k = 0; k < ring[i].length - 1; k++) {
+            start = ring[i][k];
+            end = ring[i][k+1];
+            // Degenerate segment (start === end). Skip.
+            if (start[0] === end[0] && start[1] === end[1]) {
+                continue;
+            // Horizontal segment that continues previous horizontal segment. Merge.
+            } else if (last && last[0][1] === last[1][1] && last[0][1] === start[1] && last[1][1] === end[1]) {
+                last[1] = end;
+            // Add in new segment.
+            } else {
+                last = [ start, end ];
+                segments.push(last);
+            }
+        }
+        last = null;
     }
+    return segments;
 }
 
+// Determines if the end y value of segment @ i is a local minima.
+// If the segment is horizontal will continue iterating through next
+// segments until it can be determined if the entire horizontal segment
+// is a local minima.
+//
+// o current                        o current             o
+//  \                                \                   /
+//   \   o next                       x-----------------/
+//    \ /                             ^
+//     x <-------- local minima       +-----local minima
+//
+module.exports.isLocalMin = isLocalMin;
+module.exports.isLocalMax = isLocalMax;
+function isLocalMin(i, segments) {
+    var seek = 1;
+    var current = segments[i];
+    var next = segments[i+seek];
+
+    // Not min in current segment.
+    if (current[1][1] >= current[0][1]) return false;
+
+    while (next && current[1][1] === next[1][1]) {
+        seek++;
+        next = segments[i+seek];
+    }
+
+    // No next segment.
+    if (!next) return false;
+
+    // Not min vs next segment.
+    if (current[1][1] > next[1][1]) return false;
+
+    return current[1][1] < next[1][1];
+}
+
+function isLocalMax(i, segments) {
+    var seek = 1;
+    var current = segments[i];
+    var next = segments[i+seek];
+
+    // Not min in current segment.
+    if (current[1][1] <= current[0][1]) return false;
+
+    while (next && current[1][1] === next[1][1]) {
+        seek++;
+        next = segments[i+seek];
+    }
+
+    // No next segment.
+    if (!next) return false;
+
+    // Not max vs next segment.
+    if (current[1][1] < next[1][1]) return false;
+
+    return current[1][1] > next[1][1];
+}
+
+// modified from http://jsfiddle.net/justin_c_rounds/Gd2S2/light/
+// line1 is an infinite line, and line2 is a finite segment
+function lineIntersects(line1StartX, line1StartY, line1EndX, line1EndY, line2StartX, line2StartY, line2EndX, line2EndY, localMinMax) {
+    var denominator,
+        a, 
+        b,
+        numerator1,
+        numerator2,
+        onLine1= false,
+        onLine2= false,
+        res = [null, null];
+
+    denominator = ((line2EndY - line2StartY) * (line1EndX - line1StartX)) - ((line2EndX - line2StartX) * (line1EndY - line1StartY));
+    if (denominator === 0) {
+        if(res[0] !== null && res[1] !== null) {
+            return res;
+        } else {
+            return false;
+        }
+    }
+    a = line1StartY - line2StartY;
+    b = line1StartX - line2StartX;
+    numerator1 = ((line2EndX - line2StartX) * a) - ((line2EndY - line2StartY) * b);
+    numerator2 = ((line1EndX - line1StartX) * a) - ((line1EndY - line1StartY) * b);
+    a = numerator1 / denominator;
+    b = numerator2 / denominator;
+
+    // if we cast these lines infinitely in both directions, they intersect here:
+    res[0] = line1StartX + (a * (line1EndX - line1StartX));
+    res[1] = line1StartY + (a * (line1EndY - line1StartY));
+
+    // if line2 is a segment and line1 is infinite, they intersect if:
+    if ((b > 0 && b < 1) ||
+        (res[0] === line2StartX && res[1] === line2StartY) ||
+        (localMinMax && res[0] === line2EndX && res[1] === line2EndY)) {
+        return res;
+    } else {
+        return false;
+    }
+}
+
+function lineCover(coordinates, max_zoom) {
+    var tileHash = {};
+    // break into segments and calculate bbox
+    var segments = [];
+    for(var i = 0; i < coordinates.length - 1; i++) {
+        var iNext = i+1;
+        // add endpoint tiles in case line is contained withing a single tile
+        tileHash[tilebelt.pointToTile(coordinates[i][0], coordinates[i][1], max_zoom).join('/')] = true;
+        tileHash[tilebelt.pointToTile(coordinates[iNext][0], coordinates[iNext][1], max_zoom).join('/')] = true;
+        // encode segments as tile fractions
+        var start = pointToTileFraction(coordinates[i][0], coordinates[i][1], max_zoom);
+        var stop = pointToTileFraction(coordinates[iNext][0], coordinates[iNext][1], max_zoom);
+        segments.push([[start[0], start[1]], [stop[0], stop[1]]]);
+    }
+    for (var i = 0; i < segments.length; i++) {  
+        var x0 = segments[i][0][0];
+            y0 = segments[i][0][1];
+            x1 = segments[i][1][0];
+            y1 = segments[i][1][1];
+        // verify x0,y0 is far left
+        if(x0 > x1) {
+            var firstX = x0;
+            var firstY = y0;
+            x0 = x1;
+            y0 = y1;
+            x1 = firstX;
+            y1 = firstY;
+        }
+        var x0Floor = Math.floor(x0);
+        var y0Floor = Math.floor(y0);
+        var x1Floor = Math.floor(x1);
+        var y1Floor = Math.floor(y1);
+        /*
+        vertical intersects:   
+
+        |  |  |  |
+        |  |  |  |
+        |  |  |  |
+
+        */
+        var x = 0;
+        while(x0+x <= x1Floor+1) {
+            var intersection = lineIntersects(Math.floor(x0+x), y0-10000, Math.floor(x0+x), y0+10000, 
+                                              x0, y0, x1, y1);
+
+            // add tile to the left and right of the intersection
+            //todo: check intersect and the two tiles being hashed
+            if(intersection){
+                tileHash[Math.floor(intersection[0]-1)+'/'+Math.floor(intersection[1])+'/'+max_zoom] = true;
+                tileHash[Math.floor(intersection[0])+'/'+Math.floor(intersection[1])+'/'+max_zoom] = true;
+            }
+            x++;
+        }
+
+        /*
+        horizontal intersects
+
+        ________
+        ________
+        ________
+
+        */
+        // verify x0,y0 is top
+        if(y0 < y1) {
+            var firstX = x0;
+            var firstY = y0;
+            x0 = x1;
+            y0 = y1;
+            x1 = firstX;
+            y1 = firstY;
+        }
+        var x0Floor = Math.floor(x0);
+        var y0Floor = Math.floor(y0);
+        var x1Floor = Math.floor(x1);
+        var y1Floor = Math.floor(y1);
+        var y = 0;
+        while(y0+y >= y1Floor) {
+            var intersection = lineIntersects(x0-1000, Math.floor(y0+y), x0+1000, Math.floor(y0+y), 
+                                              x0, y0, x1, y1);
+
+            // add tile above and below the intersection
+            if(intersection){
+                tileHash[Math.floor(intersection[0])+'/'+Math.floor(intersection[1])+'/'+max_zoom] = true;
+                tileHash[Math.floor(intersection[0])+'/'+Math.floor(intersection[1]-1)+'/'+max_zoom] = true;
+            }
+            y--;
+        }
+    }
+    return tileHash;
+}
+
+function pointToTileFraction (lon, lat, z) {
+    var tile = tilebelt.pointToTile(lon, lat, z);
+    var bbox = tilebelt.tileToBBOX(tile);
+    var tileNW = [bbox[0], bbox[3]];
+    var tileSE = [bbox[2], bbox[1]];
+
+    var xTileOffset = tileSE[0] - tileNW[0];
+    var xPointOffset = lon - tileNW[0];
+    var xPercentOffset = xPointOffset / xTileOffset;
+
+    var yTileOffset = tileSE[1] - tileNW[1];
+    var yPointOffset = lat - tileNW[1];
+    var yPercentOffset = yPointOffset / yTileOffset;
+
+    return [tile[0]+xPercentOffset, tile[1]+yPercentOffset];
+}
+
+function hashMerge(hash1, hash2) {
+    var keys = Object.keys(hash2);
+    for(var i = 0; i < keys.length; i++) {
+        hash1[keys[i]] = true;
+    }
+    return hash1;
+}
+
+function hashToArray(hash) {
+    keys = Object.keys(hash);
+    var tiles = [];
+    for(var i = 0; i < keys.length; i++) {
+        var tileStrings = keys[i].split('/');
+        tiles.push([parseInt(tileStrings[0]), parseInt(tileStrings[1]), parseInt(tileStrings[2])]);
+    }
+    return tiles;
+}
+
 function feature (geom) {
@@ -128,7 +426,1 @@ return {
 }
-
-function needsIntersect (tile, geom) {
-    var bboxGeom = extent(geom);
-    var bboxTile = extent(tile);
-    return bboxIntersects(bboxGeom, bboxTile);
-}

package.json

 {
   "name": "tile-cover",
-  "version": "1.0.0",
+  "version": "2.0.0",
   "description": "generate the minimum number of tiles to cover a geojson geometry",
@@ -29,11 +29,11 @@ "main": "index.js",
   "devDependencies": {
-    "tape": "^2.14.0"
+    "benchmark": "^1.0.0",
+    "tape": "^2.14.0",
+    "turf-erase": "^0.1.3",
+    "turf-intersect": "1.0.1",
+    "turf-merge": "0.0.2"
   },
   "dependencies": {
-    "bbox-intersect": "^0.1.0",
-    "geojson-extent": "^0.3.0",
-    "tilebelt": "^0.5.2",
-    "turf-inside": "^0.1.4",
-    "turf-intersect": "0.0.0"
+    "tilebelt": "^0.5.2"
   }
 }

README.md

@@ -23,7 +23,19 @@ tile-cover
 
-cover.geojson(poly, limits);
-cover.tiles(poly, limits);
-cover.indexes(poly, limits);
+cover.geojson(poly.geom, limits);
+cover.tiles(poly.geom, limits);
+cover.indexes(poly.geom, limits);
 ```
 
+###Tests
+
+```bash
+npm test
+```
+
+###Benchmarks
+
+```bash
+node bench.js
+```
+
 ###Examples
@@ -30,0 +42,0 @@

test/test.js

@@ -5,30 +5,4 @@ var cover = require('../'),
 
-test('uk', function(t){
-    var uk = JSON.parse(fs.readFileSync(__dirname+'/fixtures/uk.geojson'));
-    var limits = {
-        min_zoom: 7,
-        max_zoom: 9
-    };
+var REGEN = process.env.REGEN;
 
-    t.ok(cover.geojson(uk.geometry, limits), 'uk geojson');
-    t.ok(cover.tiles(uk.geometry, limits).length, 'uk tiles');
-    t.ok(cover.indexes(uk.geometry, limits).length, 'uk indexes');
-    fs.writeFileSync(__dirname+'/fixtures/uk_out.geojson', JSON.stringify(cover.geojson(uk.geometry, limits)));
-    t.end();
-});
-
-test('line', function(t){
-    var line = JSON.parse(fs.readFileSync(__dirname+'/fixtures/line.geojson'));
-    var limits = {
-        min_zoom: 1,
-        max_zoom: 12
-    };
-
-    t.ok(cover.geojson(line.geometry, limits), 'line geojson');
-    t.ok(cover.tiles(line.geometry, limits).length, 'line tiles');
-    t.ok(cover.indexes(line.geometry, limits).length, 'line indexes');
-    fs.writeFileSync(__dirname+'/fixtures/line_out.geojson', JSON.stringify(cover.geojson(line.geometry, limits)));
-    t.end();
-});
-
 test('point', function(t){
@@ -55,58 +29,53 @@ var point = {
     t.notEqual(cover.indexes(point.geometry, limits)[0], '');
-    t.equal(typeof cover.tiles(point.geometry, limits)[0][0], 'number')
-    t.equal(typeof cover.tiles(point.geometry, limits)[0][1], 'number')
-    t.equal(typeof cover.tiles(point.geometry, limits)[0][2], 'number')
-    fs.writeFileSync(__dirname+'/fixtures/point_out.geojson', JSON.stringify(cover.geojson(point.geometry, limits)));
+    t.equal(typeof cover.tiles(point.geometry, limits)[0][0], 'number');
+    t.equal(typeof cover.tiles(point.geometry, limits)[0][1], 'number');
+    t.equal(typeof cover.tiles(point.geometry, limits)[0][2], 'number');
+    compareFixture(t, point.geometry, limits, __dirname+'/fixtures/point_out.geojson');
     t.end();
 });
 
-test('russia', function(t){
-    var russia = JSON.parse(fs.readFileSync(__dirname+'/fixtures/russia.geojson'));
+test('line', function(t){
+    var line = JSON.parse(fs.readFileSync(__dirname+'/fixtures/line.geojson'));
     var limits = {
-        min_zoom: 6,
-        max_zoom: 6
+        min_zoom: 1,
+        max_zoom: 12
     };
 
-    t.ok(cover.geojson(russia, limits), 'russia geojson');
-    t.ok(cover.tiles(russia, limits).length, 'russia tiles');
-    t.ok(cover.indexes(russia, limits).length, 'russia indexes');
-    t.equal(cover.indexes(russia, limits).length, 457)
-    fs.writeFileSync(__dirname+'/fixtures/russia_out.geojson', JSON.stringify(cover.geojson(russia, limits), 'russia tiles'));
+    t.ok(cover.geojson(line.geometry, limits), 'line geojson');
+    t.ok(cover.tiles(line.geometry, limits).length, 'line tiles');
+    t.ok(cover.indexes(line.geometry, limits).length, 'line indexes');
+    compareFixture(t, line.geometry, limits, __dirname+'/fixtures/line_out.geojson');
     t.end();
 });
 
-function f(g, name){
-    return {
-        type:'Feature',
-        properties: {name: name},
-        geometry: g
-    }
-}
+test('edgeline', function(t){
+    var line = JSON.parse(fs.readFileSync(__dirname+'/fixtures/edgeline.geojson'));
+    var limits = {
+        min_zoom: 14,
+        max_zoom: 14
+    };
 
+    t.ok(cover.geojson(line.geometry, limits), 'edgeline geojson');
+    t.deepEqual(cover.tiles(line.geometry, limits), [ [ 4543, 6612, 14 ], [ 4544, 6612, 14 ] ], 'edgeline tiles');
+    t.deepEqual(cover.indexes(line.geometry, limits).length, 2, 'edgeline indexes');
+    compareFixture(t, line.geometry, limits, __dirname+'/fixtures/edgeline_out.geojson');
+    t.end();
+});
+
+test('polygon', function(t){
+    var polygon = JSON.parse(fs.readFileSync(__dirname+'/fixtures/polygon.geojson'));
+    var limits = {
+        min_zoom: 1,
+        max_zoom: 15
+    };
+
+    t.ok(cover.geojson(polygon, limits), 'polygon geojson');
+    t.ok(cover.tiles(polygon, limits).length, 'polygon tiles');
+    t.ok(cover.indexes(polygon, limits).length, 'polygon indexes');
+    compareFixture(t, polygon, limits, __dirname+'/fixtures/polygon_out.geojson');
+    t.end();
+});
+
 test('multipoint', function(t){
-    var multipoint = {
-        "type": "Feature",
-        "properties": {},
-        "geometry": {
-            "type": "MultiPoint",
-            "coordinates": [
-                [
-                    -84.48486328124999,
-                    43.40504748787035,
-                ],
-                [
-                    -90.87890625,
-                    39.90973623453719
-                ],
-                [
-                    -84.55078125,
-                    43.45291889355468
-                ],
-                [
-                    -90.8349609375,
-                    39.93711893299021
-                ]
-            ]
-        }
-    };
+    var multipoint = JSON.parse(fs.readFileSync(__dirname+'/fixtures/multipoint.geojson'));
     var limits = {
@@ -121,12 +90,90 @@ min_zoom: 1,
     t.notEqual(cover.indexes(multipoint.geometry, limits)[0], '');
-    t.equal(cover.tiles(multipoint.geometry, limits).length, 3)
+    t.equal(cover.tiles(multipoint.geometry, limits).length, 3);
     t.equal(cover.indexes(multipoint.geometry, limits).length, 3);
     t.equal(cover.geojson(multipoint.geometry, limits).features.length, 3);
-    t.equal(typeof cover.tiles(multipoint.geometry, limits)[0][0], 'number')
-    t.equal(typeof cover.tiles(multipoint.geometry, limits)[0][1], 'number')
-    t.equal(typeof cover.tiles(multipoint.geometry, limits)[0][2], 'number')
-    fs.writeFileSync(__dirname+'/fixtures/multipoint_out.geojson', JSON.stringify(cover.geojson(multipoint.geometry, limits)));
+    t.equal(typeof cover.tiles(multipoint.geometry, limits)[0][0], 'number');
+    t.equal(typeof cover.tiles(multipoint.geometry, limits)[0][1], 'number');
+    t.equal(typeof cover.tiles(multipoint.geometry, limits)[0][2], 'number');
+    compareFixture(t, multipoint.geometry, limits, __dirname+'/fixtures/multipoint_out.geojson');
     t.end();
 });
 
+test('multiline', function(t){
+    var multiline = JSON.parse(fs.readFileSync(__dirname+'/fixtures/multiline.geojson'));
+    var limits = {
+        min_zoom: 1,
+        max_zoom: 8
+    };
+
+    t.ok(cover.geojson(multiline.geometry, limits), 'multiline geojson');
+    t.ok(cover.tiles(multiline.geometry, limits).length, 'multiline tiles');
+    t.ok(cover.indexes(multiline.geometry, limits).length, 'multiline indexes');
+    t.notEqual(cover.indexes(multiline.geometry, limits)[0], '');
+    t.equal(cover.tiles(multiline.geometry, limits).length, 20);
+    t.equal(cover.indexes(multiline.geometry, limits).length, 20);
+    t.equal(cover.geojson(multiline.geometry, limits).features.length, 20);
+    t.equal(typeof cover.tiles(multiline.geometry, limits)[0][0], 'number');
+    t.equal(typeof cover.tiles(multiline.geometry, limits)[0][1], 'number');
+    t.equal(typeof cover.tiles(multiline.geometry, limits)[0][2], 'number');
+    compareFixture(t, multiline.geometry, limits, __dirname+'/fixtures/multiline_out.geojson');
+    t.end();
+});
+
+test('uk', function(t){
+    var uk = JSON.parse(fs.readFileSync(__dirname+'/fixtures/uk.geojson'));
+    var limits = {
+        min_zoom: 7,
+        max_zoom: 9
+    };
+
+    t.ok(cover.geojson(uk.geometry, limits), 'uk geojson');
+    t.ok(cover.tiles(uk.geometry, limits).length, 'uk tiles');
+    t.ok(cover.indexes(uk.geometry, limits).length, 'uk indexes');
+    compareFixture(t, uk.geometry, limits, __dirname+'/fixtures/uk_out.geojson');
+    t.end();
+});
+
+test('building', function(t){
+    var building = JSON.parse(fs.readFileSync(__dirname+'/fixtures/building.geojson'));
+    var limits = {
+        min_zoom: 18,
+        max_zoom: 18
+    };
+
+    t.ok(cover.geojson(building, limits), 'building geojson');
+    t.ok(cover.tiles(building, limits).length, 'building tiles');
+    t.ok(cover.indexes(building, limits).length, 'building indexes');
+    compareFixture(t, building, limits, __dirname+'/fixtures/building_out.geojson');
+    t.end();
+});
+
+test('donut', function(t){
+    var fixture = JSON.parse(fs.readFileSync(__dirname+'/fixtures/donut.geojson'));
+    var limits = {
+        min_zoom: 16,
+        max_zoom: 16
+    };
+
+    t.ok(cover.geojson(fixture, limits), 'donut geojson');
+    t.ok(cover.tiles(fixture, limits).length, 'donut tiles');
+    t.ok(cover.indexes(fixture, limits).length, 'donut indexes');
+    compareFixture(t, fixture, limits, __dirname+'/fixtures/donut_out.geojson');
+    t.end();
+});
+
+test('russia', function(t){
+    var russia = JSON.parse(fs.readFileSync(__dirname+'/fixtures/russia.geojson'));
+    var limits = {
+        min_zoom: 6,
+        max_zoom: 6
+    };
+
+    t.ok(cover.geojson(russia, limits), 'russia geojson');
+    t.ok(cover.tiles(russia, limits).length, 'russia tiles');
+    t.ok(cover.indexes(russia, limits).length, 'russia indexes');
+    t.equal(cover.indexes(russia, limits).length, 259);
+    compareFixture(t, russia, limits, __dirname+'/fixtures/russia_out.geojson');
+    t.end();
+});
+
 test('invalid polygon --- hourglass', function(t) {
@@ -166,7 +213,94 @@ var invalid = {
     try {
-        cover.tiles(invalid, limits)
+        cover.tiles(invalid, limits);
     } catch(err) {
-        t.equal(err.toString(), 'Error: found non-noded intersection between LINESTRING ( -12.060413360595701 8.899826693726117, -12.036380767822266 8.873199368734273 ) and LINESTRING ( -12.059383392333983 8.871418491385919, -12.034835815429688 8.901183448260598 ) [ (-12.047632938440815, 8.885666404927512) ]')
+        t.equal(err.toString(), 'Error: found non-noded intersection between LINESTRING ( -12.060413360595701 8.899826693726117, -12.036380767822266 8.873199368734273 ) and LINESTRING ( -12.059383392333983 8.871418491385919, -12.034835815429688 8.901183448260598 ) [ (-12.047632938440815, 8.885666404927512) ]');
     }
     t.end();
-})
+});
+
+test('high zoom', function(t){
+    var building = {"properties":{"osm_id":0},"geometry":{"type":"Polygon","coordinates":[[[-77.04474940896034,38.90019399459534],[-77.04473063349724,38.90019399459534],[-77.04473063349724,38.90027122854152],[-77.04474672675133,38.900273315944304],[-77.04474672675133,38.900457007149065],[-77.04394474625587,38.90017520794709],[-77.04394206404686,38.900173120541425],[-77.04384550452232,38.9001710331357],[-77.04384550452232,38.900141809449025],[-77.04365238547325,38.90007501240577],[-77.04365238547325,38.89989340762676],[-77.04371139407158,38.899916369176196],[-77.04371139407158,38.89986209641103],[-77.04369261860847,38.89986209641103],[-77.04369261860847,38.89969927786663],[-77.04452946782112,38.89969719044697],[-77.04460456967354,38.89967214140626],[-77.04460725188255,38.89969510302724],[-77.04474672675133,38.89969719044697],[-77.04474940896034,38.90019399459534],[-77.04474940896034,38.90019399459534],[-77.04474940896034,38.90019399459534]]]},"type":"Feature"};
+    building = building.geometry;
+
+    var limits = {
+        min_zoom: 23,
+        max_zoom: 23
+    };
+
+    t.ok(cover.geojson(building, limits), 'building geojson');
+    t.ok(cover.tiles(building, limits).length, 'building tiles');
+    t.ok(cover.indexes(building, limits).length, 'building indexes');
+    compareFixture(t, building, limits, __dirname+'/fixtures/highzoom_out.geojson');
+    t.end();
+});
+
+test('small polygon', function(t){
+    var building = JSON.parse(fs.readFileSync(__dirname+'/fixtures/small_poly.geojson'));
+    var limits = {
+        min_zoom: 10,
+        max_zoom: 10
+    };
+
+    t.ok(cover.geojson(building, limits), 'small_poly geojson');
+    t.ok(cover.tiles(building, limits).length, 'small_poly tiles');
+    t.ok(cover.indexes(building, limits).length, 'small_poly indexes');
+    compareFixture(t, building, limits, __dirname+'/fixtures/small_poly_out.geojson');
+    t.end();
+});
+
+test('spiked polygon', function(t){
+    var spiked = JSON.parse(fs.readFileSync(__dirname+'/fixtures/spiked.geojson'));
+    var limits = {
+        min_zoom: 10,
+        max_zoom: 10
+    };
+
+    t.ok(cover.geojson(spiked, limits), 'spiked geojson');
+    t.ok(cover.tiles(spiked, limits).length, 'spiked tiles');
+    t.ok(cover.indexes(spiked, limits).length, 'spiked indexes');
+    compareFixture(t, spiked, limits, __dirname+'/fixtures/spiked_out.geojson');
+    t.end();
+});
+
+function f(g, name){
+    return {
+        type:'Feature',
+        properties: {name: name},
+        geometry: g
+    };
+}
+
+function compareFixture(t, geom, limits, filepath) {
+    var result = cover.geojson(geom, limits);
+    result.features.push({
+        type: 'Feature',
+        properties: {name:'original', stroke:'#f44', fill:'#f44'},
+        geometry: geom
+    });
+    // Sort features to ensure changes such that changes to tile cover
+    // order is not considered significant.
+    result.features.sort(function(a, b) {
+        if (a.properties.name === 'original') return 1;
+        if (b.properties.name === 'original') return -1;
+        return a.geometry.coordinates[0][0] < b.geometry.coordinates[0][0] ? -1 :
+            a.geometry.coordinates[0][0] > b.geometry.coordinates[0][0] ? 1 :
+            a.geometry.coordinates[0][1] < b.geometry.coordinates[0][1] ? -1 :
+            a.geometry.coordinates[0][1] > b.geometry.coordinates[0][1] ? 1 : 0;
+    });
+
+    if (REGEN) fs.writeFileSync(filepath, JSON.stringify(result, roundify, 2));
+    var expected = JSON.parse(JSON.stringify(JSON.parse(fs.readFileSync(filepath)), roundify, 2));
+
+    // Skip the massive deepEquals diff if feature length is not the same.
+    if (result.features.length !== expected.features.length) {
+        t.equal(result.features.length, expected.features.length);
+    } else {
+        t.deepEqual(JSON.parse(JSON.stringify(result, roundify, 2)), expected);
+    }
+}
+
+function roundify(key, val) {
+    if (typeof val !== 'number') return val;
+    return parseFloat(val.toFixed(8));
+}
+

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Major refactor

Supply chain risk

Package has recently undergone a major refactor. It may be unstable or indicate significant internal changes. Use caution when updating to versions that include significant changes.

Found 1 instance in 1 package

Environment variable access

Supply chain risk

Package accesses environment variables, which may be a sign of credential stuffing or data theft.

Found 1 instance in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

2785607

increased by221.89%

Dependency count

1

decreased by-80%

Number of package files

215

increased by1243.75%

Lines of code

2359

increased by783.52%

Number of lines in readme file

53

increased by29.27%

Worsened metrics

Dev dependency count

5

increased by400%

Number of low supply chain risk alerts

5

increased by400%

Number of medium supply chain risk alerts

1

increased byInfinity%

Dependency changes

• - Removedbbox-intersect@^0.1.0

• - Removedgeojson-extent@^0.3.0

• - Removedturf-inside@^0.1.4

• - Removedturf-intersect@0.0.0

• - Removedansicolors@0.2.1(transitive)

• - Removedarray-buffer-byte-length@1.0.1(transitive)

• - Removedarraybuffer.prototype.slice@1.0.3(transitive)

• - Removedavailable-typed-arrays@1.0.7(transitive)

• - Removedbase64-js@0.0.2(transitive)

• - Removedbbox-intersect@0.1.2(transitive)

• - Removedbops@0.0.6(transitive)

• - Removedcall-bind@1.0.7(transitive)

• - Removedcardinal@0.4.4(transitive)

• - Removedconcat-stream@1.2.1(transitive)

• - Removeddata-view-buffer@1.0.1(transitive)

• - Removeddata-view-byte-length@1.0.1(transitive)

• - Removeddata-view-byte-offset@1.0.0(transitive)

• - Removeddefine-data-property@1.1.4(transitive)

• - Removeddefine-properties@1.2.1(transitive)

• - Removedes-abstract@1.23.5(transitive)

• - Removedes-define-property@1.0.0(transitive)

• - Removedes-errors@1.3.0(transitive)

• - Removedes-object-atoms@1.0.0(transitive)

• - Removedes-set-tostringtag@2.0.3(transitive)

• - Removedes-to-primitive@1.2.1(transitive)

• - Removedesprima@1.0.4(transitive)

• - Removedextent@0.2.0(transitive)

• - Removedfor-each@0.3.3(transitive)

• - Removedfunction-bind@1.1.2(transitive)

• - Removedfunction.prototype.name@1.1.6(transitive)

• - Removedfunctions-have-names@1.2.3(transitive)

• - Removedgeojson-coords@0.0.0(transitive)

• - Removedgeojson-extent@0.3.2(transitive)

• - Removedgeojson-flatten@0.1.0(transitive)

• - Removedgeojson-normalize@0.0.0(transitive)

• - Removedget-intrinsic@1.2.4(transitive)

• - Removedget-symbol-description@1.0.2(transitive)

• - Removedglobalthis@1.0.4(transitive)

• - Removedgopd@1.0.1(transitive)

• - Removedhas-bigints@1.0.2(transitive)

• - Removedhas-property-descriptors@1.0.2(transitive)

• - Removedhas-proto@1.0.3(transitive)

• - Removedhas-symbols@1.0.3(transitive)

• - Removedhas-tostringtag@1.0.2(transitive)

• - Removedhasown@2.0.2(transitive)

• - Removedinternal-slot@1.0.7(transitive)

• - Removedis-array-buffer@3.0.4(transitive)

• - Removedis-bigint@1.0.4(transitive)

• - Removedis-boolean-object@1.1.2(transitive)

• - Removedis-callable@1.2.7(transitive)

• - Removedis-data-view@1.0.1(transitive)

• - Removedis-date-object@1.0.5(transitive)

• - Removedis-negative-zero@2.0.3(transitive)

• - Removedis-number-object@1.0.7(transitive)

• - Removedis-regex@1.1.4(transitive)

• - Removedis-shared-array-buffer@1.0.3(transitive)

• - Removedis-string@1.0.7(transitive)

• - Removedis-symbol@1.0.4(transitive)

• - Removedis-typed-array@1.1.13(transitive)

• - Removedis-weakref@1.0.2(transitive)

• - Removedisarray@2.0.5(transitive)

• - Removedjavascript.util@0.10.1(transitive)

• - Removedjsts@0.13.4(transitive)

• - Removedminimist@0.0.5(transitive)

• - Removedobject-inspect@1.13.3(transitive)

• - Removedobject-keys@1.1.1(transitive)

• - Removedobject.assign@4.1.5(transitive)

• - Removedpossible-typed-array-names@1.0.0(transitive)

• - Removedredeyed@0.4.4(transitive)

• - Removedregexp.prototype.flags@1.5.3(transitive)

• - Removedrw@0.1.4(transitive)

• - Removedsafe-array-concat@1.1.2(transitive)

• - Removedsafe-regex-test@1.0.3(transitive)

• - Removedset-function-length@1.2.2(transitive)

• - Removedset-function-name@2.0.2(transitive)

• - Removedsharkdown@0.1.1(transitive)

• - Removedside-channel@1.0.6(transitive)

• - Removedsplit@0.2.10(transitive)

• - Removedstring.prototype.trim@1.2.9(transitive)

• - Removedstring.prototype.trimend@1.0.8(transitive)

• - Removedstring.prototype.trimstart@1.0.8(transitive)

• - Removedthrough@2.3.8(transitive)

• - Removedto-utf8@0.0.1(transitive)

• - Removedtraverse@0.6.10(transitive)

• - Removedturf-featurecollection@0.1.0(transitive)

• - Removedturf-inside@0.1.4(transitive)

• - Removedturf-intersect@0.0.0(transitive)

• - Removedtyped-array-buffer@1.0.2(transitive)

• - Removedtyped-array-byte-length@1.0.1(transitive)

• - Removedtyped-array-byte-offset@1.0.2(transitive)

• - Removedtyped-array-length@1.0.6(transitive)

• - Removedtypedarray.prototype.slice@1.0.3(transitive)

• - Removedunbox-primitive@1.0.2(transitive)

• - Removedwhich-boxed-primitive@1.0.2(transitive)

• - Removedwhich-typed-array@1.1.15(transitive)