KD Tree 🌲

Subdivide rectangles either horizontal or vertical until it has reached a minimal size.

- balance1: how much to be splitted from center
- balance2: how much the size should be taken in account for choosing horizontal or vertical split
- balance3: how much chance to stop continuing splitting up

#kdtree

Log in to post a comment.

const turtle = new Turtle();

const balance1 = 0.50; // min=0.0, max=1.0, step=0.01  
const balance2 = 0.85; // min=0, max=1, step=0.01  
const balance3 = 0.15; // min=0, max=1, step=0.01  

const sizeX = 185; // min=50, max=200, step=5 
const sizeY = 185; // min=50, max=200, step=5

const minSize = 6; // min=2, max=50, step=0.1  
const spacing = 1.5; // min=0, max=10, step=0.1  
const shape = 0; // min=0, max=1, step=1

const startPos = [-sizeX/2, -sizeY/2];

const areas = [
    [0, 0, sizeX, sizeY],
];

function walk(i) {
    if (i === 0) {
        for (const area of areas.slice()) {
            subdivide(area);
        }
    }
    
    let area = areas.shift();
    const a = [area[0], area[1]];
    const b = [(area[0] + area[2]), (area[1] + area[3])];
    
    let s = spacing*.5;
    add2(a, startPos);
    add2(b, startPos);
    add2(a, [s,s]);
    add2(b, [-s,-s]);
    
    s = spacing * 2/3;
    if (shape == 0) {
        turtle.jump(a[0], a[1]);
        turtle.goto(b[0], a[1]);
        turtle.goto(b[0], b[1]);
        turtle.goto(a[0], b[1]);
        turtle.goto(a[0], a[1]);
    } else if (shape == 1) {
        if (Math.random() > balance1 * balance2 * balance3) {
            turtle.jump(a[0], a[1]);
            turtle.goto(b[0] - s, a[1]);
            turtle.goto(a[0], b[1] - s);
            turtle.goto(a[0], a[1]);
            
            turtle.jump(b[0], a[1] + s);
            turtle.goto(b[0] , b[1]);
            turtle.goto(a[0] + s, b[1]);
            turtle.goto(b[0], a[1]+ s);
        } else {
            turtle.jump(a[0], a[1]+s);
            turtle.goto(b[0]-s, b[1]);
            turtle.goto(a[0], b[1]);
            turtle.goto(a[0], a[1]+s);
            
            turtle.jump(b[0], b[1]-s);
            turtle.goto(a[0]+s, a[1]);
            turtle.goto(b[0], a[1]);
            turtle.goto(b[0], b[1]-s);
        }
    }
    
    return areas.length;
}

Array.prototype.remove = function(item) {
    var idx;
    while ((idx = this.indexOf(item)) !== -1) {
        this.splice(idx, 1);
    }
    return this;
}

function subdivide(area) {
    const b1 = 1 - balance1;
    let r = 0.5 - (b1 / 2) + Math.random() * b1 / 2;
    let verticalSplit = Math.random() > 0.5;
    if (Math.random() < balance2) verticalSplit = area[2] < area[3]
    const area1 = verticalSplit ?
                    [area[0], area[1], area[2], area[3]*r]
                : 
                    [area[0], area[1], area[2]*r, area[3]];
                    
    const area2 = !verticalSplit ?
                    [area[0] + area[2]*r, area[1], area[2]*(1-r), area[3]]
                :
                    [area[0], area[1] + area[3]*r, area[2], area[3]*(1-r)];

    areas.remove(area);
    areas.push(area1);
    areas.push(area2);
    
    const minWidth = Math.max(minSize + spacing, spacing);
    const minHeight = Math.max(minSize + spacing, spacing)
    if ((area1[2] > minWidth) && (area1[3] > minHeight)) {
        if (Math.random() > Math.pow(balance3, 3)) subdivide(area1);
    }
    if ((area2[2] > minWidth) && (area2[3] > minHeight)) {
        if (Math.random() > Math.pow(balance3, 3)) subdivide(area2);
    }
}

function add2(p, v) { p[0] += v[0]; p[1] += v[1]; return p }