tile-cover - npm Package Compare versions

Comparing version 2.1.1 to 2.1.2

bench.js

@@ -9,3 +9,4 @@ var Benchmark = require('benchmark');
 var russia = JSON.parse(fs.readFileSync('./test/fixtures/russia.geojson'));
-var zooms = [6,8,10,12,18];
+var russiaLine = {type: 'LineString', coordinates: russia.coordinates[0]};
+var zooms = [6,8,10,12,18,20,25,28];
 
@@ -27,5 +28,10 @@ var suite = new Benchmark.Suite('tile-cover',{
 zooms.slice(0, 3).forEach(function(zoom){
-    addBench(suite, russia, 'russia', zoom, zoom);
+    addBench(suite, russia, 'russia polygon', zoom, zoom);
 });
+zooms.slice(0, 3).forEach(function(zoom){
+    addBench(suite, russiaLine, 'russia polyline', zoom, zoom);
+});
 
+addBench(suite, russia, 'russia polygon multizoom', 0, 9);
+
 suite.on('cycle', function(event) {
@@ -32,0 +38,0 @@ console.log(String(event.target));

index.js

@@ -29,10 +29,11 @@ 'use strict';
 function getLocked (geom, limits) {
-    var locked = [],
+    var locked,
         tileHash = {};
 
     if (geom.type === 'Point') {
-        locked.push(tilebelt.pointToTile(geom.coordinates[0], geom.coordinates[1], limits.max_zoom));
+        locked = [tilebelt.pointToTile(geom.coordinates[0], geom.coordinates[1], limits.max_zoom)];
 
     } else if (geom.type === 'MultiPoint') {
         var quadkeys = {};
+        locked = [];
         for(var i = 0; i < geom.coordinates.length; i++) {
@@ -49,3 +50,2 @@ var tile = tilebelt.pointToTile(geom.coordinates[i][0], geom.coordinates[i][1], limits.max_zoom);
         lineCover(tileHash, geom.coordinates, limits.max_zoom);
-        locked = hashToArray(tileHash);
 
@@ -56,7 +56,5 @@ } else if (geom.type === 'MultiLineString') {
         }
-        locked = hashToArray(tileHash);
 
     } else if (geom.type === 'Polygon') {
         polyRingCover(tileHash, geom.coordinates, limits.max_zoom);
-        locked = hashToArray(tileHash);
 
@@ -67,3 +65,2 @@ } else if (geom.type === 'MultiPolygon') {
         }
-        locked = hashToArray(tileHash);
 
@@ -74,32 +71,51 @@ } else {
 
-    if (limits.min_zoom !== limits.max_zoom){
-        locked = mergeTiles(locked, limits);
+    if (!locked) {
+        if (limits.min_zoom !== limits.max_zoom){
+            tileHash = mergeTiles(tileHash, limits);
+        }
+        locked = hashToArray(tileHash);
     }
+
     return locked;
 }
 
-function mergeTiles (tiles, limits) {
-    var merged = [];
-    var changed = false;
-    tiles.forEach(function (t) {
-        // top left and has all siblings -- merge
-        if ((t[0] % 2 === 0 && t[1] % 2 === 0) && tilebelt.hasSiblings(t, tiles)) {
-            if (t[2] > limits.min_zoom) {
-                merged.push(tilebelt.getParent(t));
-                changed = true;
-            } else {
-                merged = merged.concat(tilebelt.getSiblings(t));
+function mergeTiles(tileHash, limits) {
+    var mergedTileHash = {};
+
+    for (var z = limits.max_zoom; z > limits.min_zoom; z--) {
+
+        var keys = Object.keys(tileHash);
+        var parentTileHash = {};
+
+        for (var i = 0; i < keys.length; i++) {
+            var id1 = +keys[i],
+                t = fromID(id1);
+
+            if (t[0] % 2 === 0 && t[1] % 2 === 0) {
+                var id2 = toID(t[0] + 1, t[1], z),
+                    id3 = toID(t[0], t[1] + 1, z),
+                    id4 = toID(t[0] + 1, t[1] + 1, z);
+
+                if (tileHash[id2] && tileHash[id3] && tileHash[id4]) {
+                    tileHash[id1] = false;
+                    tileHash[id2] = false;
+                    tileHash[id3] = false;
+                    tileHash[id4] = false;
+
+                    var parentId = toID(t[0] / 2, t[1] / 2, z - 1);
+                    (z - 1 === limits.min_zoom ? mergedTileHash : parentTileHash)[parentId] = true;
+                }
             }
         }
-        // does not have all siblings -- add
-        else if (!tilebelt.hasSiblings(t, tiles)) {
-            merged.push(t);
+
+        for (var i = 0; i < keys.length; i++) {
+            if (tileHash[keys[i]]) {
+                mergedTileHash[+keys[i]] = true;
+            }
         }
-    });
-    // stop if the last round had no merges
-    if (!changed) {
-        return merged;
-    } else {
-        return mergeTiles(merged, limits);
+
+        tileHash = parentTileHash;
     }
+
+    return mergedTileHash;
 }
@@ -162,4 +178,2 @@
     }
-
-    return tileHash;
 }
@@ -299,90 +313,39 @@
 
-function lineCover(tileHash, coordinates, max_zoom) {
-    // 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[toID.apply(null, tilebelt.pointToTile(coordinates[i][0], coordinates[i][1], max_zoom))] = true;
-        tileHash[toID.apply(null, tilebelt.pointToTile(coordinates[iNext][0], coordinates[iNext][1], max_zoom))] = 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:
+function lineCover(tileHash, coords, max_zoom) {
+    for (var i = 0; i < coords.length - 1; i++) {
+        var start = pointToTileFraction(coords[i][0], coords[i][1], max_zoom),
+            stop = pointToTileFraction(coords[i + 1][0], coords[i + 1][1], max_zoom),
+            x0 = start[0],
+            y0 = start[1],
+            x1 = stop[0],
+            y1 = stop[1],
+            dx = x1 - x0,
+            dy = y1 - y0,
+            sx = dx > 0 ? 1 : -1,
+            sy = dy > 0 ? 1 : -1,
+            x = Math.floor(x0),
+            y = Math.floor(y0),
+            tMaxX = Math.abs(((dx > 0 ? 1 : 0) + x - x0) / dx),
+            tMaxY = Math.abs(((dy > 0 ? 1 : 0) + y - y0) / dy),
+            tdx = Math.abs(sx / dx),
+            tdy = Math.abs(sy / dy);
 
-        |  |  |  |
-        |  |  |  |
-        |  |  |  |
+        tileHash[toID(x, y, max_zoom)] = true;
 
-        */
-        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);
+        // handle edge cases
+        if (dy === 0 && dx === 0) continue;
+        if (isNaN(tMaxX)) tMaxX = Infinity;
+        if (isNaN(tMaxY)) tMaxY = Infinity;
 
-            // add tile to the left and right of the intersection
-            //todo: check intersect and the two tiles being hashed
-            if(intersection){
-                tileHash[toID(Math.floor(intersection[0]-1), Math.floor(intersection[1]), max_zoom)] = true;
-                tileHash[toID(Math.floor(intersection[0]), Math.floor(intersection[1]), max_zoom)] = true;
+        while (tMaxX < 1 || tMaxY < 1) {
+            if (tMaxX < tMaxY) {
+                tMaxX += tdx;
+                x += sx;
+            } else {
+                tMaxY += tdy;
+                y += sy;
             }
-            x++;
+            tileHash[toID(x, y, max_zoom)] = true;
         }
-
-        /*
-        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[toID(Math.floor(intersection[0]), Math.floor(intersection[1]), max_zoom)] = true;
-                tileHash[toID(Math.floor(intersection[0]), Math.floor(intersection[1]-1), max_zoom)] = true;
-            }
-            y--;
-        }
     }
-    return tileHash;
 }
@@ -389,0 +352,0 @@

package.json

 {
   "name": "tile-cover",
-  "version": "2.1.1",
+  "version": "2.1.2",
   "description": "generate the minimum number of tiles to cover a geojson geometry",
@@ -5,0 +5,0 @@ "main": "index.js",

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

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

Worsened metrics

Total package byte prevSize

4311207

decreased by-0.06%

Lines of code

4132

decreased by-0.89%

No dependency changes