// LL 2021

const precision = 30; // min=2 max=100 step=1
const thickness = 2; // min=1 max=3 step=1
const method = 0; // min=0, max=1, step=1 (Individual points,List of points)

// TODO:
// Performance: Spacial partitioning for line to segment intersection
// Experiment: Do hidden line ellimination at draw time instead of load time
// Quality: Only fill gaps for dangling points of adjacent segments


Canvas.setpenopacity(1);
const turtle = new Turtle();

var outliner;

function walk(i, t) {
    if (i==0) {
        // 1. Create Outliner with optional parameters
        outliner = new Outliner(turtle, precision, thickness);

        if (method == 0) {
            // Option 1: add points and segments one at a time        

            // 2. Specify points as ([x, y], radius)
            const p1 = outliner.addPoint([ 0,  30], 3);
            const p2 = outliner.addPoint([ 0, -30], 3);
            const p3 = outliner.addPoint([-30,  0], 3);
            const p4 = outliner.addPoint([ 30,  0], 3);
            const p5 = outliner.addPoint([ 57,  0], 6);
            const p6 = outliner.addPoint([ 70,  0], 9);

            // 3. Link points into segments
            outliner.addSegment(p1, p2);
            outliner.addSegment(p3, p4);
        } else {
            // Option 2: add a group of points and segments as a list

            // 2. Specify a list of points as [ [x, y], radius ]
            outliner.addPoints([ [[ 0, 30], 3], [[ 30, 60], 6], [[-30, 60], 2] ]);

            // 3. Link points into segments
            outliner.addSegments([ [0, 1], [1, 2], [0, 2] ]);
        }

        // 4. Build and optimize
        outliner.build();
    }

    // 5. Draw a little bit of the outlines in a loop until there is no more to draw
    if (!outliner.drawNext()) return false;

    // Slow down for effect
    sleep(5);

    return true;
}

function sleep(milliseconds) { start=Date.now(); while (Date.now()-start<milliseconds); }


/////////////////////////////////////////////////////////////////
// Outliner utility code v03 - Created by Lionel Lemarie 2021
// https://turtletoy.net/turtle/a206296e80
/////////////////////////////////////////////////////////////////

function Outliner(tt_=turtle, precision_=20, thickness_=1, fast_=false) {
    const timers = {}
    const timer_list = [];

    function startTimer(name) {
        const now = performance.now();
        if (!(name in timers)) {
            timers[name] = [1, -now];
            timer_list.push(name);
        } else {
            timers[name][0]++;
            timers[name][1]-=now;
        }
    }
    
    function stopTimer(name) {
        const now = performance.now();
        if (name in timers) {
            timers[name][1]+=now;
        }
    }
    
    function printTimers() {
        console.log("");
        function numberWithCommas(x) { return x.toString().replace(/\B(?=(\d{3})+(?!\d))/g, ","); }
        timer_list.forEach(name => {
            var elapsed = timers[name][1], count = timers[name][0], unit = "ms";
            if (elapsed > 1000) { unit = "sec"; elapsed /= 1000; if (elapsed > 60) { unit = "min"; elapsed /= 60; } }
            console.log(`Outliner: ${name} - calls: ${numberWithCommas(count)} - total: ${elapsed.toFixed(1)} ${unit}`);
        });
    }
    
    startTimer("Total time");
    const lines_to_draw = [];
    const figure_points = [];
    const figure_segments = [];
    
    const epsilon = 0.0001;

    function createPointOutline(point) {
        const step = 1 / precision_;
        for (var a=0; a<1; a+=step) {
            const x0 = point[0] + point[2] * Math.cos(a * Math.PI * 2);
            const y0 = point[1] + point[2] * Math.sin(a * Math.PI * 2);
            const x1 = point[0] + point[2] * Math.cos((a+step) * Math.PI * 2);
            const y1 = point[1] + point[2] * Math.sin((a+step) * Math.PI * 2);
            addLine([ [x0, y0], [x1, y1] ]);
        }
    }
    
    function rotX(x, y, a) { return Math.cos(a) * x - Math.sin(a) * y; }
    function rotY(x, y, a) { return Math.sin(a) * x + Math.cos(a) * y; }
    
    function createSegmentOutline(segment) {
        const l = Math.hypot(segment[1][0]-segment[0][0], segment[1][1]-segment[0][1]);
        if (l < epsilon) return [];
    
        var px11 = (segment[0][0] + segment[0][2] * rotX(segment[0][0] - segment[1][0], segment[0][1] - segment[1][1], -0.5 * Math.PI) / l);
        var py11 = (segment[0][1] + segment[0][2] * rotY(segment[0][0] - segment[1][0], segment[0][1] - segment[1][1], -0.5 * Math.PI) / l);
        var px12 = (segment[0][0] + segment[0][2] * rotX(segment[0][0] - segment[1][0], segment[0][1] - segment[1][1],  0.5 * Math.PI) / l);
        var py12 = (segment[0][1] + segment[0][2] * rotY(segment[0][0] - segment[1][0], segment[0][1] - segment[1][1],  0.5 * Math.PI) / l);
        var px21 = (segment[1][0] + segment[1][2] * rotX(segment[1][0] - segment[0][0], segment[1][1] - segment[0][1], -0.5 * Math.PI) / l);
        var py21 = (segment[1][1] + segment[1][2] * rotY(segment[1][0] - segment[0][0], segment[1][1] - segment[0][1], -0.5 * Math.PI) / l);
        var px22 = (segment[1][0] + segment[1][2] * rotX(segment[1][0] - segment[0][0], segment[1][1] - segment[0][1],  0.5 * Math.PI) / l);
        var py22 = (segment[1][1] + segment[1][2] * rotY(segment[1][0] - segment[0][0], segment[1][1] - segment[0][1],  0.5 * Math.PI) / l);
    
        addSubDivLine([[px11, py11], [px22, py22]]);
        addSubDivLine([[px12, py12], [px21, py21]]);
    }
    
    function addSubDivLine(line) {
        const step = 1 / precision_;
        for (t=0; t<(1-epsilon); t+=step) {
            const x1 = line[0][0] + (line[1][0]-line[0][0]) * t;
            const y1 = line[0][1] + (line[1][1]-line[0][1]) * t;
            const x2 = line[0][0] + (line[1][0]-line[0][0]) * (t+step);
            const y2 = line[0][1] + (line[1][1]-line[0][1]) * (t+step);
            addLine([[x1, y1], [x2, y2]]);
        }
    }
    
    const binSize = 1;
    const bins = {};
    
    function point_key(point) {
        return Math.floor(point[1]/binSize) * 100000 + Math.floor(point[0]/binSize);
    }
    
    function getBinListForPoint(point) {
        var bin_list = [];
        const key0 = point_key(point);
        if (key0 in bins) bin_list.push(bins[key0]);

        var found_good = false;
        bin_list.forEach(bin => bin.forEach(index => found_good |= !inBlacklist(index)));
        if (!found_good) {
            bin_list = [];
            const search_radius = 2;
            for (var y=-search_radius; y<=search_radius+0.1; y+=1) {
                for (var x=-search_radius; x<=search_radius+0.1; x+=1) {
                    if (x==0 && y==0) continue;
                    const key = point_key([point[0]+x*binSize, point[1]+y*binSize]);
                    if (key in bins) bin_list.push(bins[key]);
                }
            }
        }
        return bin_list;
    }

    function getBinListForLine(line) {
        const bin_list = [];
        const key0 = point_key(line[0]);
        if (key0 in bins) bin_list.push(bins[key0]);
        const key1 = point_key(line[1]);
        if (key1 in bins) bin_list.push(bins[key1]);
        return bin_list;
    }
    
    function addToBin(line, index) {
        for (var i=0; i<2; i++) {
            const key = point_key(line[i]);
            if (!(key in bins)) bins[key] = [];
            bins[key].push(index);
        }
    }
    
    function checkOverlap(line1, line2) {
        const distance00 = distance2(line1[0], line2[0]);
        const distance01 = distance2(line1[0], line2[1]);
        const distance10 = distance2(line1[1], line2[0]);
        const distance11 = distance2(line1[1], line2[1]);
        const value = ! ( ((distance00 > epsilon) || (distance11 > epsilon)) && ((distance01 > epsilon) || (distance10 > epsilon)) );
        return value;
    }
    
    function addLine(line) {
        startTimer("addLine");
        var ok_to_add = true;

        if (!fast_) {
            startTimer(`addLine - figure_points ${figure_points.length}`);
            for (var i=0; i<figure_points.length && ok_to_add; i++) {
                const dist0 = distance2(line[0], figure_points[i]) * (1+epsilon);
                const dist1 = distance2(line[1], figure_points[i]) * (1+epsilon);
                ok_to_add &= dist0 > (figure_points[i][2]**2);
                ok_to_add &= dist1 > (figure_points[i][2]**2);
            }
            stopTimer(`addLine - figure_points ${figure_points.length}`);
    
            startTimer(`addLine - figure_segments ${figure_segments.length}`);
            for (var i=0; i<figure_segments.length && ok_to_add; i++) {
                const segment = [0,1].map(si => figure_points[figure_segments[i][si]]);
                ok_to_add &= !pointInSegment(line[0], segment) && !pointInSegment(line[1], segment);
            }
            stopTimer(`addLine - figure_segments ${figure_segments.length}`);
    
            getBinListForLine(line).forEach(bin => {
                for (var i=0; i<bin.length && ok_to_add; i++) {
                    ok_to_add &= !checkOverlap(line, lines_to_draw[bin[i]]);
                }
            });
        }

        if (ok_to_add) {
            addToBin(line, lines_to_draw.length);
            lines_to_draw.push(line);
        }
        stopTimer("addLine");
    }
    
    function distance2(point1, point2) {
        const dist2 = (point1[0]-point2[0]) * (point1[0]-point2[0]) + (point1[1]-point2[1]) * (point1[1]-point2[1]);
        return dist2;
    }
    
    function distanceToSegmentFactor(point, segment) {
        var l2 = distance2(segment[0], segment[1]);
        if (l2 < epsilon) return 0;
        var t = ((point[0] - segment[0][0]) * (segment[1][0] - segment[0][0]) + (point[1] - segment[0][1]) * (segment[1][1] - segment[0][1])) / l2;
        t = Math.max(0, Math.min(1, t));
        return t;
    }
    
    function distance2ToSegmentWithFactor(point, segment, t) {
        const dist2 = distance2(point, [segment[0][0] + t * (segment[1][0] - segment[0][0]), segment[0][1] + t * (segment[1][1] - segment[0][1])]);
        return dist2;
    }
    
    function pointInSegment(point, segment) {
        const t = distanceToSegmentFactor(point, segment);
        const radius = segment[0][2] * (1-t) + segment[1][2] * t;
        const inside = distance2ToSegmentWithFactor(point, segment, t) < radius*radius*(1-epsilon);
        return inside;
    }
    
    function fillGaps() {
        if (fast_) return;
        const dangling_points = [];
        for (var i1=0; i1<lines_to_draw.length; i1++) {
            for (var j1=0; j1<2; j1++) {
                var found_close = false;
                getBinListForPoint(lines_to_draw[i1][j1]).forEach(bin => {
                    var closest_point = [];
                    var closest_distance = NaN;
                    for (var i2=0; i2<bin.length; i2++) {
                        if (checkOverlap(lines_to_draw[i1], lines_to_draw[bin[i2]])) continue;
                        for (var j2=0; j2<2; j2++) {
                            const dist2 = distance2(lines_to_draw[i1][j1], lines_to_draw[bin[i2]][j2]);
                            if (isNaN(closest_distance) || dist2 < closest_distance) {
                                closest_distance = dist2;
                                closest_point = lines_to_draw[bin[i2]][j2];
                            }
                        }
                    }
                    if (!isNaN(closest_distance) && closest_distance < epsilon) {
                        found_close = true;
                    }
                });
                if (!found_close) dangling_points.push(lines_to_draw[i1][j1]);
            }
        }

        const extra_lines = [];
        while (dangling_points.length > 1) {
            const point1 = dangling_points.shift();
            var closest_index = -1;
            var closest_distance = NaN;
            for (var i=0; i<dangling_points.length; i++) {
                const dist2 = distance2(dangling_points[i], point1);
                if (closest_index < 0 || dist2 < closest_distance) {
                    closest_distance = dist2;
                    closest_index = i;
                }
            }
            if (closest_index >= 0 && closest_distance < 10) {
                const point2 = dangling_points[closest_index];
                dangling_points.splice(closest_index, 1);
                extra_lines.push([point1, point2]);
            }
        }
    
        extra_lines.forEach(l => { addToBin(l, lines_to_draw.length); lines_to_draw.push(l); });
    }
    
    const blacklist = [];
    var blacklist_count = 0;
    
    function inBlacklist(index) {
        while (blacklist.length <= index) blacklist.push(false);
        const value = blacklist[index];
        return value;
    }
    
    function addToBlacklist(index) {
        while (blacklist.length <= index) blacklist.push(false);
        blacklist[index] = true;
        blacklist_count++;
    }
    
    function drawNextLine() {
        startTimer("drawNextLine");
        if (lines_to_draw.length == 0) return false;
        
        const position = tt_.position();
        var closest_distance = 1000000;
        var closest_line_index = -1;
        var closest_point_index = -1;

        if (!fast_) {
            startTimer("drawNextLine - bins");
            getBinListForPoint(position).forEach(bin => {
                for (var i=0; i<bin.length; i++) {
                    if (inBlacklist(bin[i])) continue;
                    for (var j=0; j<2; j++) {
                        const dist2 = distance2(position, lines_to_draw[bin[i]][j]);
                        if (closest_line_index < 0 || dist2 < closest_distance) {
                            closest_distance = dist2;
                            closest_line_index = bin[i];
                            closest_point_index = j;
                        }
                    }
                }
            });
            stopTimer("drawNextLine - bins");
            
            if (closest_line_index < 0) {
                startTimer("drawNextLine - all");
                for (var i=0; i<lines_to_draw.length && closest_distance > 1; i++) {
                    if (inBlacklist(i)) continue;
                    for (var j=0; j<2; j++) {
                        const dist2 = distance2(position, lines_to_draw[i][j]);
                        if (closest_line_index < 0 || dist2 < closest_distance) {
                            closest_distance = dist2;
                            closest_line_index = i;
                            closest_point_index = j;
                        }
                    }
                }
                stopTimer("drawNextLine - all");
            }
        }
        
        if (closest_line_index < 0) {
            startTimer("drawNextLine - last restort");
            closest_line_index = 0;
            closest_point_index = 0;
            closest_distance = 1;
            while (inBlacklist(closest_line_index)) closest_line_index++;
            stopTimer("drawNextLine - last restort");
        }

        if (closest_line_index < lines_to_draw.length && closest_point_index < lines_to_draw[closest_line_index].length) {
            if (closest_distance > 0.01) {
                tt_.jump(lines_to_draw[closest_line_index][closest_point_index]);    
            }
            tt_.down();
            tt_.goto(lines_to_draw[closest_line_index][1-closest_point_index]);
        }

        if (fast_) lines_to_draw.splice(closest_line_index, 1);
        else addToBlacklist(closest_line_index);

        stopTimer("drawNextLine");
        const more_to_do = lines_to_draw.length - blacklist_count > 0;
        
        if (!more_to_do) {
            stopTimer("Total time");
            printTimers();
        }
        return more_to_do;
    }
    
    function applyThickness() {
        const original_count = lines_to_draw.length;
        const offset = 0.2;
        for (var ty=0; ty<thickness; ty++) {
            for (var tx=0; tx<thickness; tx++) {
                if (tx==0 && ty==0) continue;
                for (var i=0; i<original_count; i++) {
                    const line = lines_to_draw[i].map(p => [p[0]-tx*offset, p[1]-ty*offset, p[2]]);
                    addToBin(line, lines_to_draw.length);
                    lines_to_draw.push(line);
                }
            }
        }
    }
    
    function buildOutline() {
        startTimer("buildOutline");
        for (var i=0; i<figure_points.length; i++) {
            createPointOutline(figure_points[i]);
        }
    
        for (var i=0; i<figure_segments.length; i++) {
            const segment = [0,1].map(si => figure_points[figure_segments[i][si]]);
            createSegmentOutline(segment);
        }
        
        fillGaps();
        
        applyThickness();
        stopTimer("buildOutline");
    }

    function newPoint(point, radius) {
        figure_points.push([point[0], point[1], radius]);
        return figure_points.length - 1;
    }
    
    function newSegment(index1, index2) {
        figure_segments.push([index1, index2]);
        return figure_segments.length - 1;
    }
    
    return {
        addPoint: (point, radius) => newPoint(point, radius),
        addSegment: (index1, index2) => newSegment(index1, index2),
        addPoints: (point_list) => point_list.forEach(p => newPoint(p[0], p[1])),
        addSegments: (segment_list) => segment_list.forEach(s => newSegment(s[0], s[1])),
        build: () => buildOutline(),
        drawNext: () => drawNextLine(),
        unsortedLines: lines_to_draw
    };
}