[gnome-maps/wip/jonasdn/geojson: 2/7] Add geojson-vt from Mapbox



commit a632ac8037c51c2bc4b4936e313208258b4a6cd4
Author: Jonas Danielsson <jonas threetimestwo org>
Date:   Fri Oct 23 12:18:39 2015 +0200

    Add geojson-vt from Mapbox
    
    Geojson-vt is A highly efficient JavaScript library for slicing GeoJSON data
    into vector tiles on the fly, primarily designed to enable rendering and
    interacting with large geospatial datasets on the browser side
    (without a server).
    
    https://github.com/mapbox/geojson-vt, see LICENSE for license.

 src/geojson-vt/LICENSE      |   13 +++
 src/geojson-vt/clip.js      |  151 ++++++++++++++++++++++++++++
 src/geojson-vt/convert.js   |  144 +++++++++++++++++++++++++++
 src/geojson-vt/index.js     |  231 +++++++++++++++++++++++++++++++++++++++++++
 src/geojson-vt/simplify.js  |   74 ++++++++++++++
 src/geojson-vt/tile.js      |   85 ++++++++++++++++
 src/geojson-vt/transform.js |   41 ++++++++
 src/geojson-vt/wrap.js      |   61 +++++++++++
 8 files changed, 800 insertions(+), 0 deletions(-)
---
diff --git a/src/geojson-vt/LICENSE b/src/geojson-vt/LICENSE
new file mode 100644
index 0000000..00e9914
--- /dev/null
+++ b/src/geojson-vt/LICENSE
@@ -0,0 +1,13 @@
+Copyright (c) 2015, Mapbox
+
+Permission to use, copy, modify, and/or distribute this software for any purpose
+with or without fee is hereby granted, provided that the above copyright notice
+and this permission notice appear in all copies.
+
+THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH
+REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND
+FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT,
+INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS
+OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
+TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF
+THIS SOFTWARE.
diff --git a/src/geojson-vt/clip.js b/src/geojson-vt/clip.js
new file mode 100644
index 0000000..f657ad8
--- /dev/null
+++ b/src/geojson-vt/clip.js
@@ -0,0 +1,151 @@
+'use strict';
+
+module.exports = clip;
+
+/* clip features between two axis-parallel lines:
+ *     |        |
+ *  ___|___     |     /
+ * /   |   \____|____/
+ *     |        |
+ */
+
+function clip(features, scale, k1, k2, axis, intersect, minAll, maxAll) {
+
+    k1 /= scale;
+    k2 /= scale;
+
+    if (minAll >= k1 && maxAll <= k2) return features; // trivial accept
+    else if (minAll > k2 || maxAll < k1) return null; // trivial reject
+
+    var clipped = [];
+
+    for (var i = 0; i < features.length; i++) {
+
+        var feature = features[i],
+            geometry = feature.geometry,
+            type = feature.type,
+            min, max;
+
+        min = feature.min[axis];
+        max = feature.max[axis];
+
+        if (min >= k1 && max <= k2) { // trivial accept
+            clipped.push(feature);
+            continue;
+        } else if (min > k2 || max < k1) continue; // trivial reject
+
+        var slices = type === 1 ?
+                clipPoints(geometry, k1, k2, axis) :
+                clipGeometry(geometry, k1, k2, axis, intersect, type === 3);
+
+        if (slices.length) {
+            // if a feature got clipped, it will likely get clipped on the next zoom level as well,
+            // so there's no need to recalculate bboxes
+            clipped.push({
+                geometry: slices,
+                type: type,
+                tags: features[i].tags || null,
+                min: feature.min,
+                max: feature.max
+            });
+        }
+    }
+
+    return clipped.length ? clipped : null;
+}
+
+function clipPoints(geometry, k1, k2, axis) {
+    var slice = [];
+
+    for (var i = 0; i < geometry.length; i++) {
+        var a = geometry[i],
+            ak = a[axis];
+
+        if (ak >= k1 && ak <= k2) slice.push(a);
+    }
+    return slice;
+}
+
+function clipGeometry(geometry, k1, k2, axis, intersect, closed) {
+
+    var slices = [];
+
+    for (var i = 0; i < geometry.length; i++) {
+
+        var ak = 0,
+            bk = 0,
+            b = null,
+            points = geometry[i],
+            area = points.area,
+            dist = points.dist,
+            len = points.length,
+            a, j, last;
+
+        var slice = [];
+
+        for (j = 0; j < len - 1; j++) {
+            a = b || points[j];
+            b = points[j + 1];
+            ak = bk || a[axis];
+            bk = b[axis];
+
+            if (ak < k1) {
+
+                if ((bk > k2)) { // ---|-----|-->
+                    slice.push(intersect(a, b, k1), intersect(a, b, k2));
+                    if (!closed) slice = newSlice(slices, slice, area, dist);
+
+                } else if (bk >= k1) slice.push(intersect(a, b, k1)); // ---|-->  |
+
+            } else if (ak > k2) {
+
+                if ((bk < k1)) { // <--|-----|---
+                    slice.push(intersect(a, b, k2), intersect(a, b, k1));
+                    if (!closed) slice = newSlice(slices, slice, area, dist);
+
+                } else if (bk <= k2) slice.push(intersect(a, b, k2)); // |  <--|---
+
+            } else {
+
+                slice.push(a);
+
+                if (bk < k1) { // <--|---  |
+                    slice.push(intersect(a, b, k1));
+                    if (!closed) slice = newSlice(slices, slice, area, dist);
+
+                } else if (bk > k2) { // |  ---|-->
+                    slice.push(intersect(a, b, k2));
+                    if (!closed) slice = newSlice(slices, slice, area, dist);
+                }
+                // | --> |
+            }
+        }
+
+        // add the last point
+        a = points[len - 1];
+        ak = a[axis];
+        if (ak >= k1 && ak <= k2) slice.push(a);
+
+        // close the polygon if its endpoints are not the same after clipping
+
+        last = slice[slice.length - 1];
+        if (closed && last && (slice[0][0] !== last[0] || slice[0][1] !== last[1])) slice.push(slice[0]);
+
+        // add the final slice
+        newSlice(slices, slice, area, dist);
+    }
+
+    return slices;
+}
+
+function newSlice(slices, slice, area, dist) {
+    if (slice.length) {
+        // we don't recalculate the area/length of the unclipped geometry because the case where it goes
+        // below the visibility threshold as a result of clipping is rare, so we avoid doing unnecessary work
+        slice.area = area;
+        slice.dist = dist;
+
+        slices.push(slice);
+    }
+    return [];
+}
diff --git a/src/geojson-vt/convert.js b/src/geojson-vt/convert.js
new file mode 100644
index 0000000..920498e
--- /dev/null
+++ b/src/geojson-vt/convert.js
@@ -0,0 +1,144 @@
+'use strict';
+
+module.exports = convert;
+
+var simplify = require('./simplify');
+
+// converts GeoJSON feature into an intermediate projected JSON vector format with simplification data
+
+function convert(data, tolerance) {
+    var features = [];
+
+    if (data.type === 'FeatureCollection') {
+        for (var i = 0; i < data.features.length; i++) {
+            convertFeature(features, data.features[i], tolerance);
+        }
+    } else if (data.type === 'Feature') {
+        convertFeature(features, data, tolerance);
+
+    } else {
+        // single geometry or a geometry collection
+        convertFeature(features, {geometry: data}, tolerance);
+    }
+    return features;
+}
+
+function convertFeature(features, feature, tolerance) {
+    var geom = feature.geometry,
+        type = geom.type,
+        coords = geom.coordinates,
+        tags = feature.properties,
+        i, j, rings;
+
+    if (type === 'Point') {
+        features.push(create(tags, 1, [projectPoint(coords)]));
+
+    } else if (type === 'MultiPoint') {
+        features.push(create(tags, 1, project(coords)));
+
+    } else if (type === 'LineString') {
+        features.push(create(tags, 2, [project(coords, tolerance)]));
+
+    } else if (type === 'MultiLineString' || type === 'Polygon') {
+        rings = [];
+        for (i = 0; i < coords.length; i++) {
+            rings.push(project(coords[i], tolerance));
+        }
+        features.push(create(tags, type === 'Polygon' ? 3 : 2, rings));
+
+    } else if (type === 'MultiPolygon') {
+        rings = [];
+        for (i = 0; i < coords.length; i++) {
+            for (j = 0; j < coords[i].length; j++) {
+                rings.push(project(coords[i][j], tolerance));
+            }
+        }
+        features.push(create(tags, 3, rings));
+
+    } else if (type === 'GeometryCollection') {
+        for (i = 0; i < geom.geometries.length; i++) {
+            convertFeature(features, {
+                geometry: geom.geometries[i],
+                properties: tags
+            }, tolerance);
+        }
+
+    } else {
+        throw new Error('Input data is not a valid GeoJSON object.');
+    }
+}
+
+function create(tags, type, geometry) {
+    var feature = {
+        geometry: geometry,
+        type: type,
+        tags: tags || null,
+        min: [2, 1], // initial bbox values;
+        max: [-1, 0]  // note that coords are usually in [0..1] range
+    };
+    calcBBox(feature);
+    return feature;
+}
+
+function project(lonlats, tolerance) {
+    var projected = [];
+    for (var i = 0; i < lonlats.length; i++) {
+        projected.push(projectPoint(lonlats[i]));
+    }
+    if (tolerance) {
+        simplify(projected, tolerance);
+        calcSize(projected);
+    }
+    return projected;
+}
+
+function projectPoint(p) {
+    var sin = Math.sin(p[1] * Math.PI / 180),
+        x = (p[0] / 360 + 0.5),
+        y = (0.5 - 0.25 * Math.log((1 + sin) / (1 - sin)) / Math.PI);
+
+    y = y < -1 ? -1 :
+        y > 1 ? 1 : y;
+
+    return [x, y, 0];
+}
+
+// calculate area and length of the poly
+function calcSize(points) {
+    var area = 0,
+        dist = 0;
+
+    for (var i = 0, a, b; i < points.length - 1; i++) {
+        a = b || points[i];
+        b = points[i + 1];
+
+        area += a[0] * b[1] - b[0] * a[1];
+
+        // use Manhattan distance instead of Euclidian one to avoid expensive square root computation
+        dist += Math.abs(b[0] - a[0]) + Math.abs(b[1] - a[1]);
+    }
+    points.area = Math.abs(area / 2);
+    points.dist = dist;
+}
+
+// calculate the feature bounding box for faster clipping later
+function calcBBox(feature) {
+    var geometry = feature.geometry,
+        min = feature.min,
+        max = feature.max;
+
+    if (feature.type === 1) calcRingBBox(min, max, geometry);
+    else for (var i = 0; i < geometry.length; i++) calcRingBBox(min, max, geometry[i]);
+
+    return feature;
+}
+
+function calcRingBBox(min, max, points) {
+    for (var i = 0, p; i < points.length; i++) {
+        p = points[i];
+        min[0] = Math.min(p[0], min[0]);
+        max[0] = Math.max(p[0], max[0]);
+        min[1] = Math.min(p[1], min[1]);
+        max[1] = Math.max(p[1], max[1]);
+    }
+}
diff --git a/src/geojson-vt/index.js b/src/geojson-vt/index.js
new file mode 100644
index 0000000..4cf532e
--- /dev/null
+++ b/src/geojson-vt/index.js
@@ -0,0 +1,231 @@
+'use strict';
+
+module.exports = geojsonvt;
+
+var convert = require('./convert'),     // GeoJSON conversion and preprocessing
+    transform = require('./transform'), // coordinate transformation
+    clip = require('./clip'),           // stripe clipping algorithm
+    wrap = require('./wrap'),           // date line processing
+    createTile = require('./tile');     // final simplified tile generation
+
+
+function geojsonvt(data, options) {
+    return new GeoJSONVT(data, options);
+}
+
+function GeoJSONVT(data, options) {
+    options = this.options = extend(Object.create(this.options), options);
+
+    var debug = options.debug;
+
+    if (debug) console.time('preprocess data');
+
+    var z2 = 1 << options.maxZoom, // 2^z
+        features = convert(data, options.tolerance / (z2 * options.extent));
+
+    this.tiles = {};
+    this.tileCoords = [];
+
+    if (debug) {
+        console.timeEnd('preprocess data');
+        console.log('index: maxZoom: %d, maxPoints: %d', options.indexMaxZoom, options.indexMaxPoints);
+        console.time('generate tiles');
+        this.stats = {};
+        this.total = 0;
+    }
+
+    features = wrap(features, options.buffer / options.extent, intersectX);
+
+    // start slicing from the top tile down
+    if (features.length) this.splitTile(features, 0, 0, 0);
+
+    if (debug) {
+        if (features.length) console.log('features: %d, points: %d', this.tiles[0].numFeatures, 
this.tiles[0].numPoints);
+        console.timeEnd('generate tiles');
+        console.log('tiles generated:', this.total, JSON.stringify(this.stats));
+    }
+}
+
+GeoJSONVT.prototype.options = {
+    maxZoom: 14,            // max zoom to preserve detail on
+    indexMaxZoom: 5,        // max zoom in the tile index
+    indexMaxPoints: 100000, // max number of points per tile in the tile index
+    solidChildren: false,   // whether to tile solid square tiles further
+    tolerance: 3,           // simplification tolerance (higher means simpler)
+    extent: 4096,           // tile extent
+    buffer: 64,             // tile buffer on each side
+    debug: 0                // logging level (0, 1 or 2)
+};
+
+GeoJSONVT.prototype.splitTile = function (features, z, x, y, cz, cx, cy) {
+
+    var stack = [features, z, x, y],
+        options = this.options,
+        debug = options.debug;
+
+    // avoid recursion by using a processing queue
+    while (stack.length) {
+        y = stack.pop();
+        x = stack.pop();
+        z = stack.pop();
+        features = stack.pop();
+
+        var z2 = 1 << z,
+            id = toID(z, x, y),
+            tile = this.tiles[id],
+            tileTolerance = z === options.maxZoom ? 0 : options.tolerance / (z2 * options.extent);
+
+        if (!tile) {
+            if (debug > 1) console.time('creation');
+
+            tile = this.tiles[id] = createTile(features, z2, x, y, tileTolerance, z === options.maxZoom);
+            this.tileCoords.push({z: z, x: x, y: y});
+
+            if (debug) {
+                if (debug > 1) {
+                    console.log('tile z%d-%d-%d (features: %d, points: %d, simplified: %d)',
+                        z, x, y, tile.numFeatures, tile.numPoints, tile.numSimplified);
+                    console.timeEnd('creation');
+                }
+                var key = 'z' + z;
+                this.stats[key] = (this.stats[key] || 0) + 1;
+                this.total++;
+            }
+        }
+
+        // save reference to original geometry in tile so that we can drill down later if we stop now
+        tile.source = features;
+
+        // stop tiling if the tile is solid clipped square
+        if (!options.solidChildren && isClippedSquare(tile, options.extent, options.buffer)) continue;
+
+        // if it's the first-pass tiling
+        if (!cz) {
+            // stop tiling if we reached max zoom, or if the tile is too simple
+            if (z === options.indexMaxZoom || tile.numPoints <= options.indexMaxPoints) continue;
+
+        // if a drilldown to a specific tile
+        } else {
+            // stop tiling if we reached base zoom or our target tile zoom
+            if (z === options.maxZoom || z === cz) continue;
+
+            // stop tiling if it's not an ancestor of the target tile
+            var m = 1 << (cz - z);
+            if (x !== Math.floor(cx / m) || y !== Math.floor(cy / m)) continue;
+        }
+
+        // if we slice further down, no need to keep source geometry
+        tile.source = null;
+
+        if (debug > 1) console.time('clipping');
+
+        // values we'll use for clipping
+        var k1 = 0.5 * options.buffer / options.extent,
+            k2 = 0.5 - k1,
+            k3 = 0.5 + k1,
+            k4 = 1 + k1,
+            tl, bl, tr, br, left, right;
+
+        tl = bl = tr = br = null;
+
+        left  = clip(features, z2, x - k1, x + k3, 0, intersectX, tile.min[0], tile.max[0]);
+        right = clip(features, z2, x + k2, x + k4, 0, intersectX, tile.min[0], tile.max[0]);
+
+        if (left) {
+            tl = clip(left, z2, y - k1, y + k3, 1, intersectY, tile.min[1], tile.max[1]);
+            bl = clip(left, z2, y + k2, y + k4, 1, intersectY, tile.min[1], tile.max[1]);
+        }
+
+        if (right) {
+            tr = clip(right, z2, y - k1, y + k3, 1, intersectY, tile.min[1], tile.max[1]);
+            br = clip(right, z2, y + k2, y + k4, 1, intersectY, tile.min[1], tile.max[1]);
+        }
+
+        if (debug > 1) console.timeEnd('clipping');
+
+        if (tl) stack.push(tl, z + 1, x * 2,     y * 2);
+        if (bl) stack.push(bl, z + 1, x * 2,     y * 2 + 1);
+        if (tr) stack.push(tr, z + 1, x * 2 + 1, y * 2);
+        if (br) stack.push(br, z + 1, x * 2 + 1, y * 2 + 1);
+    }
+};
+
+GeoJSONVT.prototype.getTile = function (z, x, y) {
+    var options = this.options,
+        extent = options.extent,
+        debug = options.debug;
+
+    var z2 = 1 << z;
+    x = ((x % z2) + z2) % z2; // wrap tile x coordinate
+
+    var id = toID(z, x, y);
+    if (this.tiles[id]) return transform.tile(this.tiles[id], extent);
+
+    if (debug > 1) console.log('drilling down to z%d-%d-%d', z, x, y);
+
+    var z0 = z,
+        x0 = x,
+        y0 = y,
+        parent;
+
+    while (!parent && z0 > 0) {
+        z0--;
+        x0 = Math.floor(x0 / 2);
+        y0 = Math.floor(y0 / 2);
+        parent = this.tiles[toID(z0, x0, y0)];
+    }
+
+    if (!parent) return null;
+
+    if (debug > 1) console.log('found parent tile z%d-%d-%d', z0, x0, y0);
+
+    // if we found a parent tile containing the original geometry, we can drill down from it
+    if (parent.source) {
+        if (isClippedSquare(parent, extent, options.buffer)) return transform.tile(parent, extent);
+
+        if (debug > 1) console.time('drilling down');
+        this.splitTile(parent.source, z0, x0, y0, z, x, y);
+        if (debug > 1) console.timeEnd('drilling down');
+    }
+
+    if (!this.tiles[id]) return null;
+
+    return transform.tile(this.tiles[id], extent);
+};
+
+function toID(z, x, y) {
+    return (((1 << z) * y + x) * 32) + z;
+}
+
+function intersectX(a, b, x) {
+    return [x, (x - a[0]) * (b[1] - a[1]) / (b[0] - a[0]) + a[1], 1];
+}
+function intersectY(a, b, y) {
+    return [(y - a[1]) * (b[0] - a[0]) / (b[1] - a[1]) + a[0], y, 1];
+}
+
+function extend(dest, src) {
+    for (var i in src) dest[i] = src[i];
+    return dest;
+}
+
+// checks whether a tile is a whole-area fill after clipping; if it is, there's no sense slicing it further
+function isClippedSquare(tile, extent, buffer) {
+
+    var features = tile.source;
+    if (features.length !== 1) return false;
+
+    var feature = features[0];
+    if (feature.type !== 3 || feature.geometry.length > 1) return false;
+
+    var len = feature.geometry[0].length;
+    if (len !== 5) return false;
+
+    for (var i = 0; i < len; i++) {
+        var p = transform.point(feature.geometry[0][i], extent, tile.z2, tile.x, tile.y);
+        if ((p[0] !== -buffer && p[0] !== extent + buffer) ||
+            (p[1] !== -buffer && p[1] !== extent + buffer)) return false;
+    }
+
+    return true;
+}
diff --git a/src/geojson-vt/simplify.js b/src/geojson-vt/simplify.js
new file mode 100644
index 0000000..fe9eea6
--- /dev/null
+++ b/src/geojson-vt/simplify.js
@@ -0,0 +1,74 @@
+'use strict';
+
+module.exports = simplify;
+
+// calculate simplification data using optimized Douglas-Peucker algorithm
+
+function simplify(points, tolerance) {
+
+    var sqTolerance = tolerance * tolerance,
+        len = points.length,
+        first = 0,
+        last = len - 1,
+        stack = [],
+        i, maxSqDist, sqDist, index;
+
+    // always retain the endpoints (1 is the max value)
+    points[first][2] = 1;
+    points[last][2] = 1;
+
+    // avoid recursion by using a stack
+    while (last) {
+
+        maxSqDist = 0;
+
+        for (i = first + 1; i < last; i++) {
+            sqDist = getSqSegDist(points[i], points[first], points[last]);
+
+            if (sqDist > maxSqDist) {
+                index = i;
+                maxSqDist = sqDist;
+            }
+        }
+
+        if (maxSqDist > sqTolerance) {
+            points[index][2] = maxSqDist; // save the point importance in squared pixels as a z coordinate
+            stack.push(first);
+            stack.push(index);
+            first = index;
+
+        } else {
+            last = stack.pop();
+            first = stack.pop();
+        }
+    }
+}
+
+// square distance from a point to a segment
+function getSqSegDist(p, a, b) {
+
+    var x = a[0], y = a[1],
+        bx = b[0], by = b[1],
+        px = p[0], py = p[1],
+        dx = bx - x,
+        dy = by - y;
+
+    if (dx !== 0 || dy !== 0) {
+
+        var t = ((px - x) * dx + (py - y) * dy) / (dx * dx + dy * dy);
+
+        if (t > 1) {
+            x = bx;
+            y = by;
+
+        } else if (t > 0) {
+            x += dx * t;
+            y += dy * t;
+        }
+    }
+
+    dx = px - x;
+    dy = py - y;
+
+    return dx * dx + dy * dy;
+}
diff --git a/src/geojson-vt/tile.js b/src/geojson-vt/tile.js
new file mode 100644
index 0000000..4e6ccb1
--- /dev/null
+++ b/src/geojson-vt/tile.js
@@ -0,0 +1,85 @@
+'use strict';
+
+module.exports = createTile;
+
+function createTile(features, z2, tx, ty, tolerance, noSimplify) {
+    var tile = {
+        features: [],
+        numPoints: 0,
+        numSimplified: 0,
+        numFeatures: 0,
+        source: null,
+        x: tx,
+        y: ty,
+        z2: z2,
+        transformed: false,
+        min: [2, 1],
+        max: [-1, 0]
+    };
+    for (var i = 0; i < features.length; i++) {
+        tile.numFeatures++;
+        addFeature(tile, features[i], tolerance, noSimplify);
+
+        var min = features[i].min,
+            max = features[i].max;
+
+        if (min[0] < tile.min[0]) tile.min[0] = min[0];
+        if (min[1] < tile.min[1]) tile.min[1] = min[1];
+        if (max[0] > tile.max[0]) tile.max[0] = max[0];
+        if (max[1] > tile.max[1]) tile.max[1] = max[1];
+    }
+    return tile;
+}
+
+function addFeature(tile, feature, tolerance, noSimplify) {
+
+    var geom = feature.geometry,
+        type = feature.type,
+        simplified = [],
+        sqTolerance = tolerance * tolerance,
+        i, j, ring, p;
+
+    if (type === 1) {
+        for (i = 0; i < geom.length; i++) {
+            simplified.push(geom[i]);
+            tile.numPoints++;
+            tile.numSimplified++;
+        }
+
+    } else {
+
+        // simplify and transform projected coordinates for tile geometry
+        for (i = 0; i < geom.length; i++) {
+            ring = geom[i];
+
+            // filter out tiny polylines & polygons
+            if (!noSimplify && ((type === 2 && ring.dist < tolerance) ||
+                                (type === 3 && ring.area < sqTolerance))) {
+                tile.numPoints += ring.length;
+                continue;
+            }
+
+            var simplifiedRing = [];
+
+            for (j = 0; j < ring.length; j++) {
+                p = ring[j];
+                // keep points with importance > tolerance
+                if (noSimplify || p[2] > sqTolerance) {
+                    simplifiedRing.push(p);
+                    tile.numSimplified++;
+                }
+                tile.numPoints++;
+            }
+
+            simplified.push(simplifiedRing);
+        }
+    }
+
+    if (simplified.length) {
+        tile.features.push({
+            geometry: simplified,
+            type: type,
+            tags: feature.tags || null
+        });
+    }
+}
diff --git a/src/geojson-vt/transform.js b/src/geojson-vt/transform.js
new file mode 100644
index 0000000..5ee426a
--- /dev/null
+++ b/src/geojson-vt/transform.js
@@ -0,0 +1,41 @@
+'use strict';
+
+exports.tile = transformTile;
+exports.point = transformPoint;
+
+// Transforms the coordinates of each feature in the given tile from
+// mercator-projected space into (extent x extent) tile space.
+function transformTile(tile, extent) {
+    if (tile.transformed) return tile;
+
+    var z2 = tile.z2,
+        tx = tile.x,
+        ty = tile.y,
+        i, j, k;
+
+    for (i = 0; i < tile.features.length; i++) {
+        var feature = tile.features[i],
+            geom = feature.geometry,
+            type = feature.type;
+
+        if (type === 1) {
+            for (j = 0; j < geom.length; j++) geom[j] = transformPoint(geom[j], extent, z2, tx, ty);
+
+        } else {
+            for (j = 0; j < geom.length; j++) {
+                var ring = geom[j];
+                for (k = 0; k < ring.length; k++) ring[k] = transformPoint(ring[k], extent, z2, tx, ty);
+            }
+        }
+    }
+
+    tile.transformed = true;
+
+    return tile;
+}
+
+function transformPoint(p, extent, z2, tx, ty) {
+    var x = Math.round(extent * (p[0] * z2 - tx)),
+        y = Math.round(extent * (p[1] * z2 - ty));
+    return [x, y];
+}
diff --git a/src/geojson-vt/wrap.js b/src/geojson-vt/wrap.js
new file mode 100644
index 0000000..0eefbb5
--- /dev/null
+++ b/src/geojson-vt/wrap.js
@@ -0,0 +1,61 @@
+'use strict';
+
+var clip = require('./clip');
+
+module.exports = wrap;
+
+function wrap(features, buffer, intersectX) {
+    var merged = features,
+        left  = clip(features, 1, -1 - buffer, buffer,     0, intersectX, -1, 2), // left world copy
+        right = clip(features, 1,  1 - buffer, 2 + buffer, 0, intersectX, -1, 2); // right world copy
+
+    if (left || right) {
+        merged = clip(features, 1, -buffer, 1 + buffer, 0, intersectX, -1, 2); // center world copy
+
+        if (left) merged = shiftFeatureCoords(left, 1).concat(merged); // merge left into center
+        if (right) merged = merged.concat(shiftFeatureCoords(right, -1)); // merge right into center
+    }
+
+    return merged;
+}
+
+function shiftFeatureCoords(features, offset) {
+    var newFeatures = [];
+
+    for (var i = 0; i < features.length; i++) {
+        var feature = features[i],
+            type = feature.type;
+
+        var newGeometry;
+
+        if (type === 1) {
+            newGeometry = shiftCoords(feature.geometry, offset);
+        } else {
+            newGeometry = [];
+            for (var j = 0; j < feature.geometry.length; j++) {
+                newGeometry.push(shiftCoords(feature.geometry[j], offset));
+            }
+        }
+
+        newFeatures.push({
+            geometry: newGeometry,
+            type: type,
+            tags: feature.tags,
+            min: [feature.min[0] + offset, feature.min[1]],
+            max: [feature.max[0] + offset, feature.max[1]]
+        });
+    }
+
+    return newFeatures;
+}
+
+function shiftCoords(points, offset) {
+    var newPoints = [];
+    newPoints.area = points.area;
+    newPoints.dist = points.dist;
+
+    for (var i = 0; i < points.length; i++) {
+        newPoints.push([points[i][0] + offset, points[i][1], points[i][2]]);
+    }
+    return newPoints;
+}


[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]