Alexander Milevski w8r

Simple recursive quadtree

This one is quite slow due to function calls in recursion, and naive splitting.

It runs in about 300ms for 125k points (MBP 2.7 GHz Intel Core i5)

	function circleContainsCircle(cx, cy, cr, x, y, r) {
	const dx = cx - x;
	const dy = cy - y;
	const dr = cr - r;
	// reduce precision not to deal with square roots
	return (dx * dx + dy * dy) < (dr * dr + 1e-6);
	}

	function from2discs(ax, ay, bx, by, ar, br) {
	const dx = bx - ax;

	export default function sortedArrayToBST(data) {
	let root = {};
	const Q = [root];
	const stack = [0, data.length - 1];

	while (Q.length !== 0) {
	const right = stack.pop();
	const left = stack.pop();
	const cur = Q.pop();

	/**
	* Count leading zeros in binary representation
	* @param {number} m
	* @return {number} 0-32
	*/
	export default function clz(m) {
	let c = 1 << 31, i;
	for (let i = 0; i < 32; i += 1) {
	if (c & m) return i;
	c >>>= 1;

	export default class SinglyList {

	constructor () {
	this._length = 0;
	this.head = null;
	}

	add (value) {
	const newNode = new { data: value, next: null };
	let current = this.head;

	///////////////////////////////////////////////////////////////////////////
	// This file is part of Quicksilver - a bike messenger simulation game //
	// Copyright (C) 2005 Scott Czepiel <http://czep.net/> //
	// //
	// This program is free software; you can redistribute it and/or modify //
	// it under the terms of the GNU General Public License as published by //
	// the Free Software Foundation; either version 2 of the License, or //
	// (at your option) any later version. //
	// //
	// This program is distributed in the hope that it will be useful, //

	// class BallTree {
	// constructor (points) {
	// const X = new Array(points.length);
	// const Y = new Array(points.length);

	// for (let i = 0; i < points.length; i++) X[i] = Y[i] = i;

	// X.sort((a, b) => points[a].x - points[b].x);
	// Y.sort((a, b) => points[a].y - points[b].y);