Missing Tiles

README.md

Usage:

node missingtiles.js database.bigtiles > missing.txt node filter_blank.js database.bigtiles missing.txt > missing_filtered.txt node generate_coords.js missing_filtered.txt > missing.json

Note: the first task takes pretty long, like a couple of hours.

missingtiles.js and filter_blank.js output tms coordinates generate_coords.js outputs xyz coordinates

filter_blank.js

var fs = require('fs');
var sqlite3 = require('sqlite3');
var path = require('path');
var argv = require('optimist')
    .usage('Usage: $0 [database] [missing.txt]')
    .demand(2)
    .argv;


var file = fs.readFileSync(argv._[1], 'utf8').split('\n');

var db = new sqlite3.Database(path.resolve(argv._[0]), sqlite3.OPEN_READONLY, function(err) {
    if (err) throw err;
    for (var i = 0; i < 8; i++) {
        next();
    }
});

var blank = 0;
var nonblank = 0;


function next() {
    var tile = file.shift();
    if (tile) {
        tile = tile.split('/');
        check({ z: tile[0]|0, x: tile[1]|0, y: tile[2]|0 });
    }
}

function check(tile) {
    db.get('SELECT length(data) AS length from tiles WHERE zxy = ?', tile.z*1e14 + tile.x*1e7 + tile.y, function(err, row) {
        if (err) throw err;
        if (row && row.length !== 116) {
            nonblank++;
            console.log(tile.z + '/' + tile.x + '/' + tile.y);
        } else if (row) {
            blank++;
        }
        next();
    });
}

process.on('exit', function() {
    console.warn('blank', blank);
    console.warn('nonblank', nonblank);
});

generate_coords.js

var fs = require('fs');
var argv = require('optimist')
    .usage('Usage: $0 [missing.txt]')
    .default('maxzoom', 16)
    .demand(1)
    .argv;

var file = fs.readFileSync(argv._[0], 'utf8').split('\n').filter(function(line) {
    return line.trim().length;
}).forEach(function(line) {
    var tile = line.split('/').map(parseFloat);
    tile[2] = Math.pow(2, tile[0]) - 1 - tile[2];
    generateCoords(tile);
});

function generateCoords(tile) {
    var a = [ tile[0]+1, tile[1]*2, tile[2]*2 ];
    var b = [ tile[0]+1, tile[1]*2+1, tile[2]*2 ];
    var c = [ tile[0]+1, tile[1]*2, tile[2]*2+1 ];
    var d = [ tile[0]+1, tile[1]*2+1, tile[2]*2+1 ];
    console.log(a[0] + '/' + a[1] + '/' + a[2]);
    console.log(b[0] + '/' + b[1] + '/' + b[2]);
    console.log(c[0] + '/' + c[1] + '/' + c[2]);
    console.log(d[0] + '/' + d[1] + '/' + d[2]);

    if (a[0] < argv.maxzoom) {
        generateCoords(a);
        generateCoords(b);
        generateCoords(c);
        generateCoords(d);
    }
}

missingtiles.js

var cluster = require('cluster');
var sqlite3 = require('sqlite3');


function Tile(z, x, y) {
    this.z = z;
    this.x = x;
    this.y = y;
}

Tile.fromZXY = function(num) {
    var y = num % 1e7;
    var n = (num - y) % 1e14;
    return new Tile((num - y - n) / 1e14, n / 1e7, y);
};



if (cluster.isMaster) {
    var argv = require('optimist')
        .usage('Usage: $0 [filename]')
        .demand(1)
        .default('minzoom', 0)
        .default('maxzoom', 16)
        .default('bbox', '-180,-85,180,85')
        .default('concurrency', 8)
        .argv;

    argv.bbox = argv.bbox.split(',').map(parseFloat);
    argv.filename = require('path').resolve(argv._[0]);

    var lastSecond = 0;
    var checked = 0;
    var total = 0;
    var parents = 0;
    function log(msg) {
        if (msg.cmd === 'childless') {
            console.log(msg.tile.z + '/' + msg.tile.x + '/' + msg.tile.y);
        } else if (msg.cmd === 'checked') {
            checked += msg.checked;
            lastSecond += msg.checked;
            parents += msg.parents;
        }
    }

    // Fork workers.
    var workers = [];
    var remainingWorkers = 0;
    for (var i = 0; i < 8; i++) {
        var worker = cluster.fork();
        worker.on('message', log);
        workers.push(worker);
        remainingWorkers++;
    }

    function reportProgress() {
        console.warn('checked ' + checked + '\t\t' + parents + '/' + total + ' parents\t\t' + lastSecond + '/s\t' + remainingWorkers + ' workers remaining');
        lastSecond = 0;
    }

    var db = new sqlite3.Database(argv.filename, sqlite3.OPEN_READONLY);
    db.get('SELECT COUNT(zxy) AS length FROM map WHERE zxy >= ? AND zxy < ?',
        argv.minzoom*1e14, (argv.minzoom+1)*1e14, function(err, row) {
        if (err) throw err;

        setInterval(reportProgress, 1000);

        var offset = 0;
        total = row.length;
        var chunk = Math.ceil(row.length / 8);
        for (var i = 0; i < workers.length; i++) {
            workers[i].send({
                'cmd': 'start',
                argv: argv,
                offset: offset,
                limit: i == workers.length - 1 ? row.length - offset : chunk
            });
            offset += chunk;
        }
    });

    cluster.on('death', function(worker) {
        console.warn('worker ' + worker.pid + ' exited');
        remainingWorkers--;
        if (remainingWorkers === 0) {
            reportProgress();
            process.exit(0);
        }
    });
} else {
    var db, iterator, checker;
    var stack = [];
    var maxzoom;
    var available = 0;
    var running = 0;
    var checked = 0;
    var parents = 0;

    var interval = setInterval(report, 100);
    process.on('message', starter);

    function starter(msg) {
        if (msg.cmd === 'start') {
            process.removeListener('message', starter);
            run(msg.argv, msg.offset, msg.limit);
        }
    }

    function report() {
        process.send({ cmd: 'checked', checked: checked, parents: parents });
        parents = 0;
        checked = 0;
    }

    function run(argv, offset, limit) {
        available = argv.concurrency;
        maxzoom = argv.maxzoom - 1;
        db = new sqlite3.Database(argv.filename, sqlite3.OPEN_READONLY);
        iterator = db.prepare('SELECT zxy FROM tiles WHERE zxy >= ? AND zxy < ? LIMIT ?, ?',
            argv.minzoom*1e14, (argv.minzoom+1)*1e14, offset, limit, function(err) {
            if (err) throw err;

            checker = db.prepare('SELECT zxy FROM tiles WHERE zxy IN (?, ?, ?, ?)', function(err) {
                if (err) throw err;
                while (available > 0) next();
            });
        });
    }

    function next() {
        running++;
        available--;

        if (stack.length) {
            return query(stack.pop());
        }

        // The stack is empty. Fall back to scanline for the top zoom level.
        iterator.get(function(err, row) {
            if (err) throw err;
            if (row) {
                parents++;
                return query(Tile.fromZXY(row.zxy));
            } else {
                running--;
                available++;
                if (running === 0) {
                    report();
                    iterator.finalize();
                    checker.finalize();
                    clearInterval(interval);
                    db.close(function() {
                        setTimeout(function() {
                            process.exit(0);
                        }, 1000);
                    });
                }
            }
        });
    };

    function query(tile) {
        var child = (tile.z+1)*1e14 + tile.x*2e7 + tile.y*2;

        checker.all(child, child+1e7, child+1, child+1e7+1, function check(err, rows) {
                running--;
                available++;
                checked++;
                if (err) {
                    console.warn(err.stack);
                } else if (!rows.length) {
                    // There's no child tile.
                    process.send({ cmd: 'childless', tile: tile });
                } else if (tile.z < maxzoom) {
                    for (var i = 0; i < rows.length; i++) {
                        stack.push(Tile.fromZXY(rows[i].zxy));
                    }
                }

                while (available > 0) next();
            });
    }
}

package.json

{
    "name": "missingtiles",
    "version": "0.0.1",

    "engines": {
        "node": "~0.6.0"
    },

    "dependencies": {
        "sphericalmercator": "~1.0.1",
        "sqlite3": "~2.1.1",
        "optimist": "~0.3.1"
    }
}