Feature Request: Tileable graphs

[morgajel]

It would be cool to allow for Tileable graphs ala http://brianin3d-demos.appspot.com/static/demos/random/voronoi.xml

and selectively choosing x, y or x/y tiling would be a bonus (with the end goal being to create a map to wrap around a globe.)

[kishalmi]

here's my inexpert way of achieving x-tileable diagrams:

function mirrorPointsX(points, width) {
    // create copies of the original points
    var pLeft = points.slice();
    var pRight = points.slice();
    // loop and add offsets
    pLeft.forEach(function (p) {
        if (p.x < width / 2) return;
        points.push({
            x: p.x - width,
            y: p.y
        });
    });
    pRight.forEach(function (p) {
        if (p.x > width / 2) return;
        points.push({
            x: p.x + width,
            y: p.y
        });
    });
}

mirrorPointsX(points, wTex);
bbox.xl -= wTex/2;
bbox.xr += wTex/2;

var diagram = voronoi.compute(points, bbox);

in short: copy the points in each half beyond the boundaries of the area we're actually interested in using and adjust the bounding box accordingly.

most likely horribly inefficient, but works.

maybe it would be sufficient to follow an edge down from the top-right and top-left vertices and only copy over those two columns? but you'd have to compute the diagram once, to do that.

looking forward to Raymond showing us how this should be done properly! until then, hth :)

[gorhill]

in short: copy the points in each half beyond the boundaries of the area we're actually interested in using and adjust the bounding box accordingly. most likely horribly inefficient, but works.

That's a nice idea (and simple, always a good thing).

But I see this more as a nice tool in some kind of rhill-voronoi-more.js (actually this would work for any voronoi implementation, since it's all in the positioning of sites, right?) Why not make it a separate project which used this voronoi implementation? As said elsewhere, I already consider I put too many bits in the core which do not really qualify as core IMO, I want to extract these bits in a ..more.js file. Ultimately, countless utilities can be coded which uses the core, and I believe this is the case with tileable graph.

[kishalmi]

As said elsewhere, I already consider I put too many bits in the core

absolutely agreed, keep the core clean. like you did with the relaxation code (Lloyd's algorithm) in the demo, easy enough to add that as a seperate method processing diagram data.

as with producing tileable graphs, some useful additional data might be much easier to add during the sweep. e.g. which cells are at which edge of the bounding box (top, left, bottom, right). not sure if storing a few more properties in cells or edges would have much of a performance-impact though, this would need testing.

...meanwhile I tried reducing the number of relevant sites to copy to the minimum: (same dataset as in the shot before, but no relaxation)

since halfedges are ordered CCW, checking for !halfedge.edge.rSite works to find the cells on the edges of the boundingbox:

diagram.cells.forEach(function(cell) {
    var border = false;
    cell.halfedges.forEach(function(he) {
        if(he.edge.rSite) return;
        border = true;
    });
    if(!border) return;
    /* ... render yellow filled cell ... */
});

so assuming that this will be sufficient to produce a tileable graph, the idea is to copy the bottom up, the top down - for y tiling left side to the right and right side to the left - for x tiling additionally each of the 4 corners into the diagonally opposed corner - for xy tiling then compute the diagram and remove all excess data

haven't found a nice way yet to reliably tell which edge of the bounding box a cell belongs to. this is what I think could easily be done in the core during the sweep. in Voronoi.closeCells() maybe?

[kishalmi]

might be on to something.. assuming that cell 0 is always part of the top border ( @gorhill can you confirm this? ) I cycle the cells counterclockwise and set bitflags accordingly. (for now, since I'm only rendering, not copying) after finding the halfedge pointing towards the border (halfedge.edge.rSite == null) the cell left to it is the one with the id of the next (CCW) halfedges edge sites (that doesn't have the current id) in case the previous (CW) halfedges edge lacks an rSite, the current cell must be a corner.

NOTE: this might need an additional check for cell 0 being in the top-right corner.

var border = 1, // TLBR - 1 top, 2 left, 4 bottom, 8 right
    idStart = 0, // cell 0 is always at top border - TODO: ask Raymond!
    idCurrent = idStart,
    cellCurrent;
do {
    cellCurrent = diagram.cells[idCurrent]; // TODO: global :(
    cellCurrent.border = 0;
    var nH = cellCurrent.halfedges.length,
        iH = nH,
        eRight, eLeft;
    while (iH--) {
        if (!cellCurrent.halfedges[iH].edge.rSite) {
            // halfedge towards the border
            cellCurrent.border |= border; // set border bitflag
                eRight = cellCurrent.halfedges[(nH + iH - 1) % nH].edge;
            if (!eRight.rSite) {
                // this is a corner
                border = border < 8 ? border << 1 : 1; // shift left
                cellCurrent.border |= border;
            }
                eLeft = cellCurrent.halfedges[(iH + 1) % nH].edge;
            idCurrent = (eLeft.rSite.voronoiId != idCurrent) ? eLeft.rSite.voronoiId : eLeft.lSite.voronoiId;
            break;
        }
    }
    /* ... render cell accoring to cellCurrent.border ... */
} while (idCurrent != idStart);

as you can see, this works rather nicely, taking 4ms to compute, although, it does still rely on the diagram being computed once before. (taking 20ms on this box with this dataset)

so if Raymond could confirm that cell 0 is always at the top, I'd wrap this up in a nice clean function that does one initial compute, copy sites, compute once more (using recycle) and clean up afterwards.

maybe it can even become another demo :)

[morgajel]

Since you're already there, would it make sense to set a variable to flag cells as "graph edges"? It's very useful generic information.

[kishalmi]

exactly my earlier guess, that those could be flagged in Voronoi.closeCells() with ease.

turns out meanwhile, that the intended way of walking along the border fails in various - literally "corner" - cases:

so back to the original idea of copying over sites:

/**
 * compute a seamlessly tileable diagram
 *  by copying the outermost sites over to the other side of the bounding box
 *  NOTE: tileX or tileY each triple the computed dataset,
 *      both result in computing 9 times the amount of sites!
 * @param {Voronoi} voronoi
 * @param {Array} sites
 * @param {Object} bbox - bounding box xl-xr, yt-yb
 * @param {Boolean=true}tileX
 * @param {Boolean=true} tileY
 * @return {Voronoi.Diagram}
 */
function computeTileable(voronoi, sites, bbox, tileX, tileY) {
    if (tileX === undefined) tileX = true;
    if (tileY === undefined) tileY = true;

    var tileSites = sites.slice(), // leave original sites intact
        bbW = bbox.xr - bbox.xl,
        bbH = bbox.yt - bbox.yb;

    // loop sites and copy according to tiling
    var site, i = sites.length;
    while (i--) {
        site = sites[i];
        if (tileX) {
            tileSites.push({copy: i, x: site.x - bbW, y: site.y});
            tileSites.push({copy: i, x: site.x + bbW, y: site.y});
        }
        if (tileY) {
            tileSites.push({copy: i, x: site.x, y: site.y - bbH});
            tileSites.push({copy: i, x: site.x, y: site.y + bbH});
        }
        if (tileX && tileY) {
            tileSites.push({copy: i, x: site.x - bbW, y: site.y - bbH});
            tileSites.push({copy: i, x: site.x + bbW, y: site.y - bbH});
            tileSites.push({copy: i, x: site.x + bbW, y: site.y + bbH});
            tileSites.push({copy: i, x: site.x - bbW, y: site.y + bbH});
        }
    }

    // compute diagram with extended dataset
    var diagram = voronoi.compute(tileSites, bbox);

    // remove cells of site-copies
    i = diagram.cells.length;
    while (i--) {
        if (diagram.cells[i].site.copy !== undefined)
            diagram.cells.splice(i, 1);
    }
    // restore edges sites
    i = diagram.edges.length;
    while (i--) {
        var edge = diagram.edges[i];
        if (edge.lSite.copy !== undefined)
            edge.lSite = sites[edge.lSite.copy];
        if (edge.rSite && edge.rSite.copy !== undefined)
            edge.rSite = sites[edge.rSite.copy];
    }

    return diagram;
}

[gorhill]

This kind of tool belongs more to some kind of toolset project rather than this core library.