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

    //https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm
    //http://members.chello.at/easyfilter/bresenham.html
    function bresenhamLine(p0, p1) {
        //Sanitize:
        const [x0, y0] = p0.map(Math.round),
              [x1, y1] = p1.map(Math.round);
        
        //http://members.chello.at/easyfilter/bresenham.html
        const dx =  Math.abs(x1 - x0),
              dy = -Math.abs(y1 - y0),
              sx = (x0 < x1) ? 1 : -1,
              sy = (y0 < y1) ? 1 : -1;

        const points = [];
        let [x, y] = [x0, y0],
            err = dx + dy,
            e2;
        for (;;) {
            points.push([x, y]);

            if (x === x1 && y === y1) { break; }
            e2 = 2 * err;
            if (e2 >= dy) { err += dy; x += sx; }
            if (e2 <= dx) { err += dx; y += sy; }
        }
        
        return points;
    }

</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 = [70, 20];


    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 isInk(point) {
            return pixels[point[1]][point[0]];
        }

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

        //Distance going from b1 to b2.
        function bearingDist(b1, b2) {
            if(b1 === b2) { return 0; }
            const len = searchContext.size;

            let distForward;
            if(b2 < b1) {
                b2 += len;
            }
            distForward = b2 - b1;
            
            let distBack;
            if(b1 < b2) {
                b1 += len;
            }
            distBack = b1 - b2;

            if(distBack < distForward) {
                return -distBack;
            }
            return distForward;
        }

        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]);
            }
            
            function isLineCandidate(point, checkConnection = true) {
                let ok = isInk(point);
                if(checkConnection && (i > 0)) {
                    ok = ok && bresenhamLine(pos, point).every(c => isInk(c));
                }
                return ok;
            }

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

            let inkWidth = 0;
            const outsideLower = search(searchCoords, nearestHit, -1, c => !isLineCandidate(c)),
                  lowerBound = normBearing(outsideLower + 1),
                  outsideUpper = search(searchCoords, lowerBound, 1, c => {
                      const ok = isLineCandidate(c);
                      if(ok) { inkWidth++; }
                      return !ok;
                  }),
                  upperBound = normBearing(outsideUpper - 1);

            let newBearing;
            //Tracing along a narrow line. Just stay in the middle:
            if(inkWidth <= stroke) {
                newBearing = normBearing(outsideLower + inkWidth/2);
            }
            //E.g. crossing lines with many directions to choose from. Go as straight ahead as we can:
            else {
                const lowerPadded = normBearing(outsideLower + stroke/2),
                      upperPadded = normBearing(upperBound - stroke/2);
                if(bearingDist(lowerPadded, nearestHit) < 0) {
                    newBearing = lowerPadded;
                }
                else if(bearingDist(nearestHit, upperPadded) < 0) {
                    newBearing = upperPadded;
                }
                else {
                    newBearing = nearestHit;
                }
            }
            //console.log('bbb', lowerBound, upperBound, inkWidth, newBearing);

            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(Math.abs(bearingDist(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, [0, 255, 0]);
        }
        
        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);
        let prevPoint = traced[0];
        traced.forEach((p, i) => {
            const line = bresenhamLine(prevPoint, p);
            line.forEach(c => buffer.setPixel(c[0], c[1], [0, 200, 0]));
            prevPoint = p;
        });
        buffer.render();
    });

})();

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