### 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

```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=1, 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 (Square, Square with triangle)

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;

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