tile-cover - npm Package Compare versions

Comparing version 3.0.0 to 3.0.1

index.js

@@ -13,17 +13,17 @@ var tilebelt = require('tilebelt');
  */
-module.exports.geojson = function (geom, limits) {
-    var locked = getLocked(geom, limits);
-    var tileFeatures = locked.map(function (t) {
-        return {
-            type: 'Feature',
-            geometry: tilebelt.tileToGeoJSON(t),
-            properties: {}
-        };
-    });
+exports.geojson = function (geom, limits) {
     return {
         type: 'FeatureCollection',
-        features: tileFeatures
+        features: getTiles(geom, limits).map(tileToFeature)
     };
 };
 
+function tileToFeature(t) {
+    return {
+        type: 'Feature',
+        geometry: tilebelt.tileToGeoJSON(t),
+        properties: {}
+    };
+}
+
 /**
@@ -39,8 +39,4 @@ * Given a geometry, create cells and return them in their raw form,
  */
-module.exports.tiles = function (geom, limits) {
-    var locked = getLocked(geom, limits);
-    return locked;
-};
+exports.tiles = getTiles;
 
-
 /**
@@ -56,40 +52,34 @@ * Given a geometry, create cells and return them as
  */
-module.exports.indexes = function (geom, limits) {
-    var locked = getLocked(geom, limits);
-    return locked.map(function (tile) {
-        return tilebelt.tileToQuadkey(tile);
-    });
+exports.indexes = function (geom, limits) {
+    return getTiles(geom, limits).map(tilebelt.tileToQuadkey);
 };
 
-function getLocked (geom, limits) {
-    var locked,
-        i,
-        tileHash = {};
+function getTiles(geom, limits) {
+    var i, tile,
+        coords = geom.coordinates,
+        maxZoom = limits.max_zoom,
+        tileHash = {},
+        tiles = [];
 
     if (geom.type === 'Point') {
-        locked = [tilebelt.pointToTile(geom.coordinates[0], geom.coordinates[1], limits.max_zoom)];
+        return [tilebelt.pointToTile(coords[0], coords[1], maxZoom)];
+
     } else if (geom.type === 'MultiPoint') {
-        var quadkeys = {};
-        locked = [];
-        for(i = 0; i < geom.coordinates.length; i++) {
-            var tile = tilebelt.pointToTile(geom.coordinates[i][0], geom.coordinates[i][1], limits.max_zoom);
-            var quadkey = tilebelt.tileToQuadkey(tile);
-            if(!quadkeys[quadkey]) {
-                quadkeys[quadkey] = true;
-                locked.push(tile);
-            }
+        for (i = 0; i < coords.length; i++) {
+            tile = tilebelt.pointToTile(coords[i][0], coords[i][1], maxZoom);
+            tileHash[toID(tile[0], tile[1], tile[2])] = true;
         }
     } else if (geom.type === 'LineString') {
-        lineCover(tileHash, geom.coordinates, limits.max_zoom);
+        lineCover(tileHash, coords, maxZoom);
 
     } else if (geom.type === 'MultiLineString') {
-        for(i = 0; i < geom.coordinates.length; i++) {
-            lineCover(tileHash, geom.coordinates[i], limits.max_zoom);
+        for (i = 0; i < coords.length; i++) {
+            lineCover(tileHash, coords[i], maxZoom);
         }
     } else if (geom.type === 'Polygon') {
-        polyRingCover(tileHash, geom.coordinates, limits.max_zoom);
+        polygonCover(tileHash, tiles, coords, maxZoom);
 
     } else if (geom.type === 'MultiPolygon') {
-        for(i = 0; i < geom.coordinates.length; i++) {
-            polyRingCover(tileHash, geom.coordinates[i], limits.max_zoom);
+        for (i = 0; i < coords.length; i++) {
+            polygonCover(tileHash, tiles, coords[i], maxZoom);
         }
@@ -100,23 +90,27 @@ } else {
 
-    if (!locked) {
-        if (limits.min_zoom !== limits.max_zoom){
-            tileHash = mergeTiles(tileHash, limits);
+    if (limits.min_zoom !== maxZoom) {
+        // sync tile hash and tile array so that both contain the same tiles
+        var len = tiles.length;
+        appendHashTiles(tileHash, tiles);
+        for (i = 0; i < len; i++) {
+            var t = tiles[i];
+            tileHash[toID(t[0], t[1], t[2])] = true;
         }
-        locked = hashToArray(tileHash);
+        return mergeTiles(tileHash, tiles, limits);
     }
 
-    return locked;
+    appendHashTiles(tileHash, tiles);
+    return tiles;
 }
 
-function mergeTiles(tileHash, limits) {
-    var mergedTileHash = {};
+function mergeTiles(tileHash, tiles, limits) {
+    var mergedTiles = [];
 
     for (var z = limits.max_zoom; z > limits.min_zoom; z--) {
 
-        var keys = Object.keys(tileHash);
         var parentTileHash = {};
+        var parentTiles = [];
 
-        for (var i = 0; i < keys.length; i++) {
-            var id1 = +keys[i],
-                t = fromID(id1);
+        for (var i = 0; i < tiles.length; i++) {
+            var t = tiles[i];
 
@@ -129,3 +123,3 @@ if (t[0] % 2 === 0 && t[1] % 2 === 0) {
                 if (tileHash[id2] && tileHash[id3] && tileHash[id4]) {
-                    tileHash[id1] = false;
+                    tileHash[toID(t[0], t[1], t[2])] = false;
                     tileHash[id2] = false;
@@ -135,4 +129,9 @@ tileHash[id3] = false;
 
-                    var parentId = toID(t[0] / 2, t[1] / 2, z - 1);
-                    (z - 1 === limits.min_zoom ? mergedTileHash : parentTileHash)[parentId] = true;
+                    var parentTile = [t[0] / 2, t[1] / 2, z - 1];
+
+                    if (z - 1 === limits.min_zoom) mergedTiles.push(parentTile);
+                    else {
+                        parentTileHash[toID(t[0] / 2, t[1] / 2, z - 1)] = true;
+                        parentTiles.push(parentTile);
+                    }
                 }
@@ -142,146 +141,56 @@ }
 
-        for (var i = 0; i < keys.length; i++) {
-            if (tileHash[keys[i]]) {
-                mergedTileHash[+keys[i]] = true;
-            }
+        for (i = 0; i < tiles.length; i++) {
+            t = tiles[i];
+            if (tileHash[toID(t[0], t[1], t[2])]) mergedTiles.push(t);
         }
 
         tileHash = parentTileHash;
+        tiles = parentTiles;
     }
 
-    return mergedTileHash;
+    return mergedTiles;
 }
 
-function polyRingCover(tileHash, geom, max_zoom) {
-    var tiled = getTiledPoly(geom, max_zoom);
-    var y = tiled.minY;
-    while (y <= tiled.maxY) {
-        // calculate intersections at each tile top-line
-        var intersections = [];
-        for(var r = 0; r < tiled.geom.length; r++) {
-            var ring = tiled.geom[r];
-            for(var i = 0, len = ring.length, j = len - 1; i < len; j = i++) {
-                var intersection = intersectY(ring[j], ring[i], y, isLocalMin(j, ring) || isLocalMax(j, ring));
-                if (intersection !== null) {
-                    intersections.push(Math.round(intersection));
-                }
-            }
-        }
-        // sort intersections
-        intersections.sort(compareNum);
-        // add tiles between intersection pairs
-        for(var i = 0; i < intersections.length - 1; i += 2) {
-            var x = intersections[i];
-            while (x <= intersections[i+1]) {
-                tileHash[toID(x, y, max_zoom)] = true;
-                x++;
-            }
-        }
-        y++;
-    }
-    // add any missing tiles with a segments pass
-    for(var i = 0; i < geom.length; i++) {
-        lineCover(tileHash, geom[i], max_zoom);
-    }
-}
+function polygonCover(tileHash, tileArray, geom, zoom) {
+    var intersections = [];
 
-function compareNum(a, b) {
-    return a - b;
-}
+    for (var i = 0; i < geom.length; i++) {
+        var ring = [];
+        lineCover(tileHash, geom[i], zoom, ring);
 
-module.exports.getTiledPoly = getTiledPoly;
+        for (var j = 0, len = ring.length, k = len - 1; j < len; k = j++) {
+            var m = (j + 1) % len;
+            var y = ring[j][1];
 
-function getTiledPoly(geom, max_zoom) {
-    var minY = Infinity;
-    var maxY = -Infinity;
-    var tiled = [];
-    var ring;
-    var last;
-    for(var i = 0; i < geom.length; i++) {
-        tiledRing = [];
-        last = null;
-        for(var k = 0; k < geom[i].length; k++) {
-            var next = tilebelt.pointToTile(geom[i][k][0], geom[i][k][1], max_zoom);
-            // Degenerate segment
-            if (last && last[0] === next[0] && last[1] === next[1]) continue;
-            minY = Math.min(minY, next[1]);
-            maxY = Math.max(maxY, next[1]);
-            tiledRing.push(next);
-            last = next;
+            // add interesction if it's not local extremum or duplicate
+            if ((y > ring[k][1] || y > ring[m][1]) && // not local minimum
+                (y < ring[k][1] || y < ring[m][1]) && // not local maximum
+                y !== ring[m][1]) intersections.push(ring[j]);
         }
-        // Skip degenerate rings
-        if (tiledRing.length >= 4) tiled.push(tiledRing);
     }
-    return {
-        minY: minY,
-        maxY: maxY,
-        geom: tiled
-    };
-}
 
-// 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 prev                           o prev                o
-//  \                                \                   /
-//   \   o next                       x--------o--------/
-//    \ /                             ^        ^------------next
-//     x <-------- local minima       +-----local minima
-//
-module.exports.isLocalMin = isLocalMin;
-module.exports.isLocalMax = isLocalMax;
+    intersections.sort(compareTiles); // sort by y, then x
 
-function isLocalMin(i, ring) {
-    var mod = ring.length;
-    var prev = ring[i];
-    var curr = ring[(i+1) % mod];
-    var next = ring[(i+2) % mod];
-
-    // Not min in current segment.
-    if (curr[1] >= prev[1]) return false;
-
-    var j = (i+1) % mod;
-    while (j !== i && curr[1] === next[1]) {
-        next = ring[(j+2) % mod];
-        j = (j+1) % mod;
+    for (i = 0; i < intersections.length; i += 2) {
+        // fill tiles between pairs of intersections
+        y = intersections[i][1];
+        for (var x = intersections[i][0] + 1; x < intersections[i + 1][0]; x++) {
+            var id = toID(x, y, zoom);
+            if (!tileHash[id]) {
+                tileArray.push([x, y, zoom]);
+            }
+        }
     }
-
-    // Min vs next segment.
-    return curr[1] < next[1];
 }
 
-function isLocalMax(i, ring) {
-    var mod = ring.length;
-    var prev = ring[i];
-    var curr = ring[(i+1) % mod];
-    var next = ring[(i+2) % mod];
-
-    // Not max in current segment.
-    if (curr[1] <= prev[1]) return false;
-
-    var j = (i+1) % mod;
-    while (j !== i && curr[1] === next[1]) {
-        next = ring[(j+2) % mod];
-        j = (j+1) % mod;
-    }
-
-    // Min vs next segment.
-    return curr[1] > next[1];
+function compareTiles(a, b) {
+    return (a[1] - b[1]) || (a[0] - b[0]);
 }
 
-function intersectY(a, b, y, localMinMax) {
-    if ((a[1] === b[1]) ||
-        (a[1] > y && b[1] > y) ||
-        (a[1] < y && b[1] < y) ||
-        (!localMinMax && b[1] === y)) return null;
+function lineCover(tileHash, coords, maxZoom, ring) {
+    var prevX, prevY;
 
-    return (y - a[1]) * (b[0] - a[0]) / (b[1] - a[1]) + a[0];
-}
-
-function lineCover(tileHash, coords, max_zoom) {
     for (var i = 0; i < coords.length - 1; i++) {
-        var start = tilebelt.pointToTileFraction(coords[i][0], coords[i][1], max_zoom),
-            stop = tilebelt.pointToTileFraction(coords[i + 1][0], coords[i + 1][1], max_zoom),
+        var start = tilebelt.pointToTileFraction(coords[i][0], coords[i][1], maxZoom),
+            stop = tilebelt.pointToTileFraction(coords[i + 1][0], coords[i + 1][1], maxZoom),
             x0 = start[0],
@@ -292,19 +201,22 @@ y0 = start[1],
             dx = x1 - x0,
-            dy = y1 - y0,
-            sx = dx > 0 ? 1 : -1,
+            dy = y1 - y0;
+
+        if (dy === 0 && dx === 0) continue;
+
+        var 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),
+            tMaxX = dx === 0 ? Infinity : Math.abs(((dx > 0 ? 1 : 0) + x - x0) / dx),
+            tMaxY = dy === 0 ? Infinity : 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;
+        if (x !== prevX || y !== prevY) {
+            tileHash[toID(x, y, maxZoom)] = true;
+            if (ring && y !== prevY) ring.push([x, y]);
+            prevX = x;
+            prevY = y;
+        }
 
-        // handle edge cases
-        if (dy === 0 && dx === 0) continue;
-        if (isNaN(tMaxX)) tMaxX = Infinity;
-        if (isNaN(tMaxY)) tMaxY = Infinity;
-
         while (tMaxX < 1 || tMaxY < 1) {
@@ -318,14 +230,17 @@ if (tMaxX < tMaxY) {
             }
-            tileHash[toID(x, y, max_zoom)] = true;
+            tileHash[toID(x, y, maxZoom)] = true;
+            if (ring && y !== prevY) ring.push([x, y]);
+            prevX = x;
+            prevY = y;
         }
     }
+
+    if (ring && y === ring[0][1]) ring.pop();
 }
 
-function hashToArray(hash) {
+function appendHashTiles(hash, tiles) {
     var keys = Object.keys(hash);
-    var tiles = [];
-    for(var i = 0; i < keys.length; i++) {
+    for (var i = 0; i < keys.length; i++) {
         tiles.push(fromID(+keys[i]));
     }
-    return tiles;
 }
@@ -332,0 +247,0 @@

package.json

 {
   "name": "tile-cover",
-  "version": "3.0.0",
+  "version": "3.0.1",
   "description": "generate the minimum number of tiles to cover a geojson geometry",
@@ -10,3 +10,3 @@ "main": "index.js",
   "scripts": {
-    "test": "tape test/*.js",
+    "test": "eslint index.js && tape test/*.js",
     "doc": "dox < index.js | doxme"
@@ -34,2 +34,3 @@ },
     "doxme": "^1.8.2",
+    "eslint": "^1.3.1",
     "tape": "^4.2.0",
@@ -36,0 +37,0 @@ "turf-area": "^1.1.1",

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

Improved metrics

Number of package files

8

increased by14.29%

Worsened metrics

Total package byte prevSize

14137

decreased by-10.33%

Dev dependency count

9

increased by12.5%

Lines of code

251

decreased by-24.62%

No dependency changes