(function (root, factory){
    if (typeof define === 'function' && define.amd){ // AMD
        define(factory);
    } else if (typeof module !== 'undefined' && module.exports) { // Node.js
        module.exports = factory();
    } else { // Browser
        root.geojsonvt = factory();
    }
})(this, function () {

    ////////
    ///simplify.js
    ////////

    // 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;
    }

    ////////
    ///Feature.js
    ////////

    //创建Feature
    function createFeature(tags, type, geom, id) {
        var feature = {
            id: id || null,
            type: type,
            geometry: geom,
            tags: tags || null,
            min: [Infinity, Infinity], // initial bbox values
            max: [-Infinity, -Infinity]
        };
        calcBBox(feature);
        return feature;
    }

    // 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]);
        }
    }

    ////////
    ///convert.js
    ////////

    // 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) {
        if (feature.geometry === null) {
            // ignore features with null geometry
            return;
        }

        var geom = feature.geometry,
            type = geom.type,
            coords = geom.coordinates,
            tags = feature.properties,
            id = feature.id,
            i, j, rings, projectedRing;

        if (type === 'Point') {
            features.push(createFeature(tags, 1, [projectPoint(coords)], id));

        } else if (type === 'MultiPoint') {
            features.push(createFeature(tags, 1, project(coords), id));

        } else if (type === 'LineString') {
            features.push(createFeature(tags, 2, [project(coords, tolerance)], id));

        } else if (type === 'MultiLineString' || type === 'Polygon') {
            rings = [];
            for (i = 0; i < coords.length; i++) {
                projectedRing = project(coords[i], tolerance);
                if (type === 'Polygon') projectedRing.outer = (i === 0);
                rings.push(projectedRing);
            }
            features.push(createFeature(tags, type === 'Polygon' ? 3 : 2, rings, id));

        } else if (type === 'MultiPolygon') {
            rings = [];
            for (i = 0; i < coords.length; i++) {
                for (j = 0; j < coords[i].length; j++) {
                    projectedRing = project(coords[i][j], tolerance);
                    projectedRing.outer = (j === 0);
                    rings.push(projectedRing);
                }
            }
            features.push(createFeature(tags, 3, rings, id));

        } 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 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 < 0 ? 0 :
            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;
    }

    ////////
    ///tile.js
    ////////

    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);
			consol.log('features: %d, points: %d, simplified: %d',
                            tile.numFeatures, tile.numPoints, tile.numSimplified)
            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++;
                }

                if (type === 3) rewind(simplifiedRing, ring.outer);

                simplified.push(simplifiedRing);
            }
        }

        if (simplified.length) {
            var tileFeature = {
                geometry: simplified,
                type: type,
                tags: feature.tags || null
            };
            if (feature.id !== null) {
                tileFeature.id = feature.id;
            }
            tile.features.push(tileFeature);
        }
    }

    function rewind(ring, clockwise) {
        var area = signedArea(ring);
        if (area < 0 === clockwise) ring.reverse();
    }

    function signedArea(ring) {
        var sum = 0;
        for (var i = 0, len = ring.length, j = len - 1, p1, p2; i < len; j = i++) {
            p1 = ring[i];
            p2 = ring[j];
            sum += (p2[0] - p1[0]) * (p1[1] + p2[1]);
        }
        return sum;
    }

    ////////
    ///transform.js
    ////////

    // 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];
    }

    //tile = transformTile;
    //point = transformPoint;
    transform = {
        tile: transformTile,
        point:transformPoint
    };

    ////////
    ///clip.js
    ////////

    //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(createFeature(feature.tags, type, slices, feature.id));
            }
        }

        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,
                outer = points.outer,
                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, outer);

                    } 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, outer);

                    } 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, outer);

                    } else if (bk > k2) { // |  ---|-->
                        slice.push(intersect(a, b, k2));
                        if (!closed) slice = newSlice(slices, slice, area, dist, outer);
                    }
                    // | --> |
                }
            }

            // 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, outer);
        }

        return slices;
    }

    function newSlice(slices, slice, area, dist, outer) {
        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;
            if (outer !== undefined) slice.outer = outer;

            slices.push(slice);
        }
        return [];
    }

    ////////
    ///wrap.js
    ////////

    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(createFeature(feature.tags, type, newGeometry, feature.id));
        }

        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;
    }

    ////////
    ///geojson-vt.js
    ////////

    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,
            solid = null;

        // 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;

            // 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;
            }

            // stop tiling if the tile is solid clipped square
            if (!options.solidChildren && isClippedSquare(tile, options.extent, options.buffer)) {
                if (cz) solid = z; // and remember the zoom if we're drilling down
                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 (features.length) {
                stack.push(tl || [], z + 1, x * 2,     y * 2);
                stack.push(bl || [], z + 1, x * 2,     y * 2 + 1);
                stack.push(tr || [], z + 1, x * 2 + 1, y * 2);
                stack.push(br || [], z + 1, x * 2 + 1, y * 2 + 1);
            }
        }

        return solid;
    };

    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 || !parent.source) return null;

        // if we found a parent tile containing the original geometry, we can drill down from it
        if (debug > 1) console.log('found parent tile z%d-%d-%d', z0, x0, y0);

        // it parent tile is a solid clipped square, return it instead since it's identical
        if (isClippedSquare(parent, extent, options.buffer)) return transform.tile(parent, extent);

        if (debug > 1) console.time('drilling down');
        var solid = this.splitTile(parent.source, z0, x0, y0, z, x, y);
        if (debug > 1) console.timeEnd('drilling down');

        // one of the parent tiles was a solid clipped square
        if (solid !== null) {
            var m = 1 << (z - solid);
            id = toID(solid, Math.floor(x / m), Math.floor(y / m));
        }

        return this.tiles[id] ? transform.tile(this.tiles[id], extent) : null;
    };

    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;
    }

    function geojsonvt(data, options)
    {
        return new GeoJSONVT(data, options)
    } 
    return geojsonvt;
});