Centerline tracing

centerline-tracing.markdown

Centerline tracing

A Pen by Andreas Borgen on CodePen.

License.

index.html

<script>console.clear();</script>


<h2>Centerline tracing</h2>
<h4>Black: Original bitmap. Green: Traced polyline</h4>
<main id="app">
    <canvas id="c"></canvas>
</main>


<!-- JS utils -->
<script>
    class CanvasPixelBuffer {
        constructor(canvas, w, h) {
            this.w = canvas.width  = (w || canvas.width);
            this.h = canvas.height = (h || canvas.height);
            this.targetContext = canvas.getContext('2d');
            this.sync();
        }

        //http://stackoverflow.com/questions/13917139/fastest-way-to-iterate-pixels-in-a-canvas-and-copy-some-of-them-in-another-one
        setPixel(x, y, rgb) {
            if ((x >= this.w) || (y >= this.h)) { return; }

            x = Math.round(x);
            y = Math.round(y);
            const index = (y * this.w + x) * 4, //Index of the current pixel
                  data = this.targetData.data;
            //console.log('set', x, y, rgb);
            data[index]     = rgb[0]; //r
            data[index + 1] = rgb[1]; //g
            data[index + 2] = rgb[2]; //b
            data[index + 3] = (rgb.length > 3) ? rgb[3] : 255; //a
        }

        getPixel(x, y) {
            const index = (y * this.w + x) * 4,
                  data = this.targetData.data;
            return [
                data[index],
                data[index + 1],
                data[index + 2],
                data[index + 3],
            ];
        }

        render() {
            this.targetContext.putImageData(this.targetData, 0,0);
        }

        //Useful if shapes are drawn using normal canvas methods.
        sync() {
            this.targetData = this.targetContext.getImageData(0,0, this.w,this.h);
        }

        clear() {
            this.targetContext.clearRect(0,0, this.w,this.h);
            this.sync();
        }
    }

    /*
     * Function for circle-generation using Bresenham's algorithm
     * https://www.geeksforgeeks.org/bresenhams-circle-drawing-algorithm/
     */
    function bresenhamCircle(xc, yc, r) {

        function bresenhamOctant(r) {
            let x = 0,
                y = r,
                d = 3 - 2 * r;

            const relCoords = [[x, y]];
            while (true) {
                x++; 
                //Check for decision parameter and correspondingly update d, x, y 
                if (d > 0) { 
                    y--;  
                    if(y < x) { break; }
                    d += 4 * (x - y) + 10; 
                } 
                else {
                    d += 4 * x + 6;
                }

                relCoords.push([x, y]);
            }

            return relCoords;
        }

        function mirrorOctant(relCoords) {
            let i, x, y;

            /* Mirror the coordinates for each octant, in order (counter-clockwise) */

            //45 -> 90 deg
            i = relCoords.length;
            while(i--) {
                [x, y] = relCoords[i];
                //Don't duplicate the 45 degree "corner" pixel:
                if(x !== y) {
                    relCoords.push([y, x]);
                }
            }
            //90 -> 180 deg
            i = relCoords.length - 1;
            while(i--) {
                [x, y] = relCoords[i];
                relCoords.push([x, -y]);
            }
            //180 -> 360 deg
            i = relCoords.length - 1;
            while(i-- > 1) {
                [x, y] = relCoords[i];
                relCoords.push([-x, y]);
            }
        }

        const relCoords = bresenhamOctant(r);
        mirrorOctant(relCoords);
        //console.log('c', relCoords.length);
        return relCoords.map(([x, y]) => [xc + x, yc + y]);
    }
</script>

script.js

/*
    Additional canvas/drawing utils kept out of the way in the HTML panel:
      - CanvasPixelBuffer
      - bresenhamCircle
*/


(function() {
    const img = `
data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAMgAAAC1AQMAAAAgKiLCAAAABlBMVEX8//sBBAA5mpm0AAA
BzklEQVRYw+3WQarbMBAG4BFazOZhXSDY1/Aita7SI3jpRSE6SA+jo0xvIOhGCxNVztOmT/PTYgIPHvkhk5CPxGgkS6ZX
Xvm/lJJ1cKWUoIqvklS5Edm7KvlQDazU4oImsRaOivBRjCjiHjUpMj7qpsi11T5z+2WftV0NCYdepI0KiRFNwIBM+5sNy
hXKAmWE4qBwQGIjEoNFkFCCsqG+0QzlAmUEc0rkoLCydlB7ru3ddjJCGQg1jgNqHMfb+3ed2F9l14V+t5v+eye3OIkuPp
j8aEYnE9FdFxfJ6+KloirfEtmkyryR2VXZFiKvSpoCTUETcUIsqthMNilihArRrkmkSWjRxe00hV6O+S+BgXixURe7G+m
Fj1JiAjKlDMQWJOT3Xtx7LXEFq9eXKi4o4sqRv+StDeshpIiRCkkTSmstqqxQZihXKCOUAYpD3SFOSCwW6WcB7gfUAsUk
tLvY/FHsv+XnRzFN+ILEvaFNfhqQLJ1Qkx+MJHMAx3OyUReOVcBjgBFd7kS68I7E5/pBPTJupMhCBLa+qb5YtDOQS02Eo
p6OpkJuAjKcEH6q2HBCIhJzQkieKgnK+lSZT8jlhAyfvnjOLBFzTl555cvmD7p/w9LY82UIAAAAAElFTkSuQmCC`.replace(/\s+/g, ''),
          lineWidth = 3,
          startPoint = [150, 85];


    function init(url) {
        const promise = new Promise((resolve, reject) => {
            const canvas = document.querySelector('#c'),
                  ctx = canvas.getContext('2d'),
                  image = new Image();
            image.onload = (e) => {
                const buffer = new CanvasPixelBuffer(canvas, image.naturalWidth, image.naturalHeight);
                ctx.drawImage(image, 0,0);
                buffer.sync();
                resolve(buffer);
            }
            image.src = url;
        });
        return promise;
    }

    function trace(pixels, config) {
        const { start, stroke, sample, setPixels } = config;
        //console.log('px', pixels);
        //console.log('ol', isOnLine(77, 22));

        function isOnLine(x, y) {
            return pixels[y][x];
        }

        function mark(point, r = 2, color = [0, 255, 0]) {
            const coords = bresenhamCircle(...point, r);
            //console.log('marked', coords);
            setPixels(coords, color);
        }


        //mark(start);
        let pos = start,
            points = [],
            bearing = 0,
            searchContext;

        function normBearing(b) {
            const len = searchContext.size;
            while(b < 0) {
                b += len;
            }
            b = Math.round(b) % len;
            return b;
        }

        function bearingDiff(b1, b2) {
            const len = searchContext.size;

            let diff = Math.abs(b1 - b2);
            if(diff > (len / 2)) {
                diff = len - diff;
            }
            return diff;
        }

        function search(circle, startBearing, direction, predicate) {
            if(predicate(circle[startBearing])) {
                return startBearing;
            }

            const len = circle.length;
            let i;
            if(direction === 0) {
                for(let offset = 1; offset < len/2; offset++) {
                    i = normBearing(startBearing - offset);
                    if(predicate(circle[i])) { return i; }
                    i = normBearing(startBearing + offset);
                    if(predicate(circle[i])) { return i; }
                }
            }
            // 1 or -1
            else {
                for(let offset = 1; offset < len; offset++) {
                    i = normBearing(startBearing + (offset * direction));
                    if(predicate(circle[i])) { return i; }
                }
            }
            return false;
        }

        for(let i = 0; i < 1000; i++) {
            const searchCoords = bresenhamCircle(...pos, sample),
                  len = searchCoords.length;
            if(i === 0) {
                searchContext = {
                    size: len,
                    drawPass: false,
                };
                setPixels(searchCoords, [0, 160, 255]);
            }

            const nearestHit = search(searchCoords, bearing, 0, c => isOnLine(...c));
            if(nearestHit === false) { break; }

            /*
            let inkWidth = 0;
            const lowerBound = search(searchCoords, nearestHit, -1, c => !isOnLine(...c)),
                  upperBound = search(searchCoords, normBearing(lowerBound + 1),  1, c => {
                      const isInk = isOnLine(...c);
                      if(isInk) { inkWidth++; }
                      return !isInk;
                  });
            let newBearing;
            if((inkWidth > stroke) && (nearestHit === bearing)) {
                newBearing = nearestHit;
            }
            else {
                newBearing = normBearing(lowerBound + inkWidth/2);
            }
            console.log('bbb', lowerBound, upperBound, inkWidth, newBearing);
            */
            const newBearing = nearestHit;

            if(i === 0) {
                searchContext.startPoint = searchCoords[newBearing];
                bearing = newBearing;
            }
            if(i === 1) {
                searchContext.firstBearing = newBearing;
            }

            //Almost a 180 degree turn. This probably means we have reached the end of our line:
            if(bearingDiff(newBearing, bearing) >= (len/2 - stroke)) {
                console.log('eol ' + i, pos, bearing, newBearing, len);
                mark(pos, stroke);
                //If this is the first time we reach and end,
                //backtrack and trace in the other direction to find the whole line:
                if(!searchContext.drawPass) {
                    points.reverse();

                    pos = searchContext.startPoint;
                    bearing = normBearing(searchContext.firstBearing + len/2);

                    searchContext.drawPass = true;
                    continue;
                }
                break;
            }

            pos = searchCoords[newBearing];
            bearing = newBearing;
            
            points.push(pos);
            //mark(pos, 1, [100, 100, 255]);
        }
        
        return points;
    }


    init(img).then(buffer => {
        const { w, h } = buffer,
              pxRows = [];

        for(let y = 0; y < buffer.h; y++) {
            const row = [];
            for(let x = 0; x < buffer.w; x++) {
                //Expect dark lines on a light background. Just checking the intensity of the R channel here..
                const rgba = buffer.getPixel(x, y),
                      isLine = rgba[0] < 100;
                row.push(isLine ? 1 : 0);
            }
            pxRows.push(row);
        }

        const traced = trace(pxRows, {
            start: startPoint,
            stroke: lineWidth,
            sample: lineWidth * 2,
            setPixels: (coords, rgb) => {
                coords.forEach(c => buffer.setPixel(c[0], c[1], rgb || [255, 0, 0]));
                buffer.render();
            },
        });

        //console.log(traced);
        const ctx = document.querySelector('#c').getContext('2d');
        ctx.beginPath();
        ctx.strokeStyle = 'lime';
        traced.forEach((c, i) => i ? ctx.lineTo(...c) : ctx.moveTo(...c));
        ctx.stroke();
    });

})();

style.scss

html, body {
    height: 100%;
}
body {
    display: flex;
    flex-flow: column;
    margin: 0;
    justify-content: center;
    align-items: center;

    font-family: Georgia, sans-serif;

    h1, h2, h3, h4 {
        margin: 0;
    }
    button, input, select {
        font: inherit;
        padding: .2em .4em;
    }
}

canvas {
    width: 100vmin;
    height: auto;

    //https://css-tricks.com/almanac/properties/i/image-rendering/
    //https://developer.mozilla.org/en-US/docs/Web/CSS/image-rendering#Browser_compatibility
    image-rendering: crisp-edges;
    image-rendering: pixelated;
}