### Optimized KD Tree ðŸŒ²

Works as the fork KD Tree ðŸŒ², but after gathering all the rectangles an optimization pass is done which checks if there is a same size rect is next or below and merges them into one.

```// Forked from "KD Tree ðŸŒ²" by markknol
// https://turtletoy.net/turtle/182d91df0d

const turtle = new Turtle();
const seed = 1.0; // min=1, max=1000, step=1

const balance1 = 1.0; /// min=0.0, max=1.0, step=0.01
const balance2 = 0.75; // min=0, max=1, step=0.01
const balance3 = 0.0; // 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 = 1.5; // min=1, max=50, step=0.5
const spacing = 1.5; // min=0, max=10, step=0.5

const optimizations = 3; // min=0, max=6, step=1
const shuffleBeforeOptimize = 0 // min=0, max=1, step=1 (no,yes)

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

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

let rects = [];

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;
rects.push([a[0],a[1], b[0]-a[0], b[1]-a[1]]);

if (!areas.length) {
for(let ii=0;ii<optimizations;ii++) {
rects = optimizeRects(rects);
}
rects.forEach(rect=>drawRect(rect));
}
return areas.length;
}

let rseed = seed;
function rand() {
let r = 1103515245 * (((rseed) >> 1) ^ (rseed++));
r = 1103515245 * (r ^ (r>>3));
r = r ^ (r >> 16);
return r / 1103515245 % 1;
}

function optimizeRects(rects) {
if (shuffleBeforeOptimize) shuffle(rects);
for (let rect1 of rects) {
for (let rect2 of rects) {
if (rect1 !== rect2) {
if (rand() > 0.25 && rect1[1]==rect2[1] && rect1[3]==rect2[3] && rect1[0]+rect1[2]+spacing == rect2[0] ) {
// next with same height
rects.remove(rect2);
rect1[2] += spacing + rect2[2];
continue;
} else if (rand() > 0.25 && rect1[0]==rect2[0] && rect1[2]==rect2[2] && rect1[1]+rect1[3]+spacing == rect2[1] ) {
// below with same width
rects.remove(rect2);
rect1[3] += spacing + rect2[3];
} else if (rand() > 0.25 && rect1[0]==rect2[0] && rect1[2]==rect2[2] && rect1[1]-spacing == rect2[1]+rect2[3]  ) {
// up with same width
rects.remove(rect2);
rect1[3] += spacing + rect2[3];
rect1[1] -= spacing + rect2[3];
continue;
} else if (rand() > 0.25 && rect1[1]==rect2[1] && rect1[3]==rect2[3] && rect1[0]-spacing == rect2[0]+rect2[2]  ) {
// up with same width
rects.remove(rect2);
rect1[2] += spacing + rect2[2];
rect1[0] -= spacing + rect2[2];
continue;
}
}
}
}
return rects;
}

function drawRect(rect) {
let [x,y,w,h] = rect;
turtle.jump(x,y)
turtle.goto(x+w,y)
turtle.goto(x+w,y+h)
turtle.goto(x,y+h)
turtle.goto(x,y)
}

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) + rand() * b1 / 2;
let verticalSplit = rand() > 0.5;
if (rand() < 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 (rand() > Math.pow(balance3, 3)) subdivide(area1);
}
if ((area2[2] > minWidth) && (area2[3] > minHeight)) {
if (rand() > Math.pow(balance3, 3)) subdivide(area2);
}
}

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

function shuffle(array) {
for (let i = array.length - 1; i > 0; i--) {
const j = Math.floor(rand() * (i + 1));
[array[i], array[j]] = [array[j], array[i]];
}
}```