const sub = ([x1, y1], [x2, y2]) => [x1 - x2, y1 - y2];
const dot = ([x1, y1], [x2, y2]) => x1 * x2 + y1 * y2;
const mul = ([x, y], f) => [f * x, f * y];
const dist = (p1, p2) => Math.hypot(...sub(p1, p2));

const minDistPointSegment = (q, [p1, p2]) => {
    const dp = sub(p2, p1);
    const dq = sub(q, p1);

    const a = Math.max(0, Math.min(1, dot(dq, dp) / dot(dp, dp)));
    return dist(dq, mul(dp, a));
};

const minDist = ([[x1, y1], [x2, y2]], [x, y, r]) => {
    if (x1 <= x && x <= x2 && y1 <= y && y <= y2) {
        return 0;
    }

    return Math.max(0, Math.min(
        minDistPointSegment([x, y], [[x1, y1], [x2, y1]]),
        minDistPointSegment([x, y], [[x2, y1], [x2, y2]]),
        minDistPointSegment([x, y], [[x2, y2], [x1, y2]]),
        minDistPointSegment([x, y], [[x1, y2], [x1, y1]])
    ) - r);
};

const maxDist = ([[x1, y1], [x2, y2]], [x, y, r]) => Math.max(0, Math.max(
    dist([x, y], [x1, y1]),
    dist([x, y], [x2, y1]),
    dist([x, y], [x2, y2]),
    dist([x, y], [x1, y2])
) - r);

const aMin = a => a.reduce((a, b) => Math.min(a, b), Infinity);

const selectDisks = (rect, disks) => {
    const h = aMin(disks.map(d => maxDist(rect, d)));
    if (h == 0) {
        for (const d of disks) {
            if (maxDist(rect, d) == 0) {
                return [d];
            }
        }
    }
    return disks.filter(d => minDist(rect, d) <= h);
};

const buildSearchTree = (depth, length, rect, disks) => {
    const selected = selectDisks(rect, disks);
    if (selected.length <= length || depth <= 0) {
        const maxRadius = (x, y) => [
            Math.max(0, aMin(selected.map(
                ([cx, cy, r]) => Math.hypot(x - cx, y - cy) - r
            ))),
            depth,
            selected.length
        ];
        return [maxRadius, rect, []];
    }
    const [[x1, y1], [x2, y2]] = rect;
    const xm = (x1 + x2) / 2;
    const ym = (y1 + y2) / 2;

    const subtrees = [
        buildSearchTree(depth - 1, length, [[x1, y1], [xm, ym]], selected),
        buildSearchTree(depth - 1, length, [[xm, y1], [x2, ym]], selected),
        buildSearchTree(depth - 1, length, [[x1, ym], [xm, y2]], selected),
        buildSearchTree(depth - 1, length, [[xm, ym], [x2, y2]], selected)
    ];

    const maxRadius = (x, y) => subtrees[
        (x < xm) ? ((y < ym)? 0 : 2) : ((y < ym)? 1 : 3)
    ][0](x, y);

    return [maxRadius, rect, subtrees];
};

const makeRect = (svg, [[x1, y1], [x2, y2]]) => {
    const rect = document.createElementNS(
        'http://www.w3.org/2000/svg',
        'rect'
    );
    rect.setAttribute('x', x1);
    rect.setAttribute('y', y1);
    rect.setAttribute('width', x2 - x1);
    rect.setAttribute('height', y2 - y1);
    rect.setAttribute('stroke', 'grey');
    rect.setAttribute('fill', 'none');
    svg.appendChild(rect);
};

const makeCircle = (svg, [x, y, r]) => {
    const circle = document.createElementNS(
        'http://www.w3.org/2000/svg',
        'circle'
    );
    circle.setAttribute('cx', x);
    circle.setAttribute('cy', y);
    circle.setAttribute('r', r);
    circle.setAttribute('stroke', 'red');
    circle.setAttribute('fill', 'none');
    svg.appendChild(circle);
};

const makeDisk = svg => {

    const group = document.createElementNS('http://www.w3.org/2000/svg', 'g');
    svg.appendChild(group);

    const moveGroup = (x, y) => {
        const ctm = group.getCTM();
        ctm.e = x;
        ctm.f = y;

        const t = svg.createSVGTransform();
        t.setMatrix(ctm);

        group.transform.baseVal.initialize(t);
    };

    const center = document.createElementNS(
        'http://www.w3.org/2000/svg',
        'circle'
    );
    center.setAttribute('r', 2);
    center.setAttribute('stroke', 'black');
    center.setAttribute('fill', 'black');
    group.appendChild(center);

    const circle = document.createElementNS(
        'http://www.w3.org/2000/svg',
        'circle'
    );
    circle.setAttribute('stroke', 'black');
    circle.setAttribute('fill', 'none');
    group.appendChild(circle);

    const text = document.createElementNS(
        'http://www.w3.org/2000/svg',
        'text'
    );
    group.appendChild(text);

    return {
        'move': moveGroup,
        'setRadius': r => circle.setAttribute('r', r),
        'setText': t => text.textContent = t
    };
};

const x3 = x => (-2 * x + 3) * x * x;
const random2 = () => x3(x3(Math.random()));

const main = () => {
    const body = document.getElementsByTagName('body')[0];

    const svg = document.createElementNS(
        'http://www.w3.org/2000/svg',
        'svg'
    );
    const width = 600;
    const height = 200;
    svg.setAttribute('width', width);
    svg.setAttribute('height', height);
    body.appendChild(svg);

    // const n = 100000;
    const n = 100;
    const maxR = 40;
    const disks = [];
    for (let i = 0; i < n; ++i) {
        disks.push([
            width * random2(),
            height * random2(),
            maxR * Math.random()
        ]);
    }

    const maxDepth = 10;
    const size = Math.max(width, height);
    const tree = buildSearchTree(
        maxDepth,
        5,
        [[0, 0], [size, size]],
        disks
    );

    const drawTree = tree => {
        makeRect(svg, tree[1]);
        tree[2].forEach(drawTree);
    };
    drawTree(tree);

    disks.forEach(d => makeCircle(svg, d));

    const disk = makeDisk(svg);

    svg.onmousemove = e => {
        const p = svg.createSVGPoint();
        p.x = e.clientX;
        p.y = e.clientY;
        const {x, y} = p.matrixTransform(svg.getScreenCTM().inverse());
        disk.move(x, y);

        const [r, depth, length] = tree[0](x, y);
        disk.setRadius(r);
        disk.setText(`${maxDepth - depth}+${length}`);
    };
};

document.addEventListener('DOMContentLoaded', main);