w8r/Readme.md

## Readme.md

      
    Raw
  

              Readme.md
            
          
    Spatial hash on morton curve

Virtual grid with that works like a flat spatial index

  
## index.html
<!DOCTYPE html>
<html>
<head>
  <title>Z-curve hash for boxes and segments with range queries</title>
  <script type="text/javascript" src="https://unpkg.com/splaytree@0.1.1/dist/splay.js"></script>
  <script type="text/javascript" src="https://unpkg.com/liang-barsky@1.0.1/dist/liang-barsky.js"></script>
  <script type="text/javascript" src="https://unpkg.com/d3-quadtree@1.0.3"></script>
  <script type="text/javascript" src="https://unpkg.com/d3-dispatch@1.0.3/build/d3-dispatch.js"></script>
  <script type="text/javascript" src="https://unpkg.com/d3-timer@1.0.7/build/d3-timer.js"></script>
  <script type="text/javascript" src="https://unpkg.com/d3-collection@1.0.4/build/d3-collection.js"></script>
  <script type="text/javascript" src="https://unpkg.com/d3-force@1.1.0/build/d3-force.js"></script>
  <script type="text/javascript" src="https://unpkg.com/bresenham-zingl@0.1.0/dist/bresenham.js"></script>
  <script type="text/javascript" src="https://unpkg.com/bezier-intersect@0.0.1/dist/bezier-intersect.js"></script>
  <script type="text/javascript" src="morton.js"></script>
  <script type="text/javascript" src="ubtree.js"></script>
  <style type="text/css">
    body, html, #canvas {
      width: 100%;
      height: 100%;
      margin: 0;
      padding: 0;
    }
    body {
      background: #ddd;
      font-family: "Helvetica Neue", Helvetica, Arial, sans-serif;
    }
    #canvas {
      background: #fff;
    }

    #control {
      position: absolute;
      top: 20px;
      right: 20px;
      background: #fff;
      box-shadow: 0 0 5px rgba(80,80,80, 0.5);
      padding: 5px 10px;
      border-radius: 5px;
    }

    #control p {
      padding: 0;
      margin: 4px;
    }

    #range {
      position: absolute;
      bottom: 20px;
      left: 20px;
      width: 90%;
    }

    #indicator {
      position: absolute;
      bottom: 50px;
      right: 20px;
      left: 20px;
      font-size: 1.5em;
      font-weight: 300;
      color: #222222;
    }
  </style>
</head>
<body>
  <canvas id="canvas"></canvas>
  <input type="range" id="range" min="10" max="10000" value="1000" />
  <div id="indicator">1000</div>
  <form id="control">
    <p><label><input type="checkbox" name="nodes" checked> nodes</label></p>
    <p><label><input type="checkbox" name="edges" checked> edges</label></p>
    <p><label><input type="checkbox" name="grid"> grid</label></p>
    <p><label><select name="level">
      <option value="1">1</option>
      <option value="2">2</option>
      <option value="3">3</option>
      <option value="4">4</option>
      <option value="5">5</option>
      <option value="6">6</option>
      <option value="7">7</option>
      <option value="8" selected>8</option>
      <option value="9">9</option>
      <option value="10">10</option>
      <option value="11">11</option>
      <option value="12">12</option>
    </select> level</label></p>
  </form>
  <script type="text/javascript" src="index.js"></script>
</body>
</html>

## index.js
const screenWidth  = document.documentElement.clientWidth;
const screenHeight = document.documentElement.clientHeight;

const pxRatio = window.devicePixelRatio;

const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');

const w = canvas.width = screenWidth * devicePixelRatio;
const h = canvas.height = screenHeight * devicePixelRatio;

const stats = {
  queries: 0,
  totalTime: 0,
  getAverage() {
    return `${this.totalTime / this.queries}ms`;
  },
  clear() {
    this.totalTime = this.queries = 0;
  }
};

canvas.style.width  = screenWidth + 'px';
canvas.style.height = screenHeight + 'px';


function scaleGraphToFitBounds(G, bounds) {
  var min = Math.min, max = Math.max;
  var bbox = getBounds(G);
  var cx = (bounds[0] + bounds[2]) / 2,
      cy = (bounds[1] + bounds[3]) / 2,
      gcx = (bbox[0] + bbox[2]) / 2,
      gcy = (bbox[1] + bbox[3]) / 2;

  var tx = cx - gcx,
      ty = cy - gcy;

  var scale = min(
    (bounds[2] - bounds[0]) / (bbox[2] - bbox[0]),
    (bounds[3] - bounds[1]) / (bbox[3] - bbox[1])
  );


  G.nodes.forEach(function (n) {
    n.x = cx + ((n.x + tx) - cx) * scale;
    n.y = cy + ((n.y + ty) - cy) * scale;
  });
}

function getBounds(g) {
  return g.nodes.reduce((b, n) => {
    b[0] = Math.min(b[0], n.x);
    b[1] = Math.min(b[1], n.y);
    b[2] = Math.max(b[2], n.x);
    b[3] = Math.max(b[3], n.y);
    return b;
  }, [Infinity, Infinity, -Infinity, -Infinity]);
}


function generateDenseTree(N = 550, width = 1000, height = 1000) {
  let counter = 0;
  return {
    nodes: new Array(N).fill(0).map(function(_, i) {
      counter++;
      return {
        id: i,
        text: 'Node #' + i,
        x: Math.random() * width,
        y: Math.random() * height,
        r: 3 + Math.random() * 8
      };
    }),
    edges: new Array(N - 1).fill(0).map(function(_, i) {
      counter++;
      return {
        id: i,
        curvature: (i % 3 === 0) ? 1 : 1,
        //curvature: 0,
        source: Math.floor(Math.sqrt(i)),
        target: i + 1
      };
    })
  };
}

var N = 1000;
var data, nodesMap, simulation;
const SZ = 5;
var flatStorage;
let foundNodes = [];
let foundEdges = [];
let selectedNode = null;
let showIndex = false;

function populate(n) {
  N = n;
  foundNodes = [];
  foundEdges = [];
  selectedNode = null;

  if (simulation) simulation.stop();
  data = generateDenseTree(N, w, h);
  nodesMap = data.nodes.reduce((a, n) => {
    a[n.id] = n;
    return a;
  }, {});
  flatStorage = new Float32Array(SZ * 2 * N);


  simulation = layout(data, onLayoutDone);
}

const qBounds = [0, 0, 0, 0];

function render() {
  ctx.clearRect(0, 0, w, h);

  if (showIndex) {
    ctx.lineWidth = 0.5;
    renderIndex();

    ctx.lineWidth = 1;
    ctx.beginPath();
    U._checkedNodes.forEach((n) => {
      const b = U.keyToBBox(n.key);
      ctx.rect(b[0], b[1], b[2] - b[0], b[3] - b[1]);
    });
    ctx.globalAlpha = 0.2;
    ctx.fillStyle = 'blue';
    ctx.fill();
    ctx.globalAlpha = 1;
  }


  const Nn = data.nodes.length;
  // const { nodes, edges } = U.size === 0 ? data : U.query([0, 0, w, h])
  //   .reduce((a, id) => {
  //     if (!a.ids[id]) {
  //       a.ids[id] = true;
  //       if (id >= Nn) a.edges.push(data.edges[id - Nn]);
  //       else          a.nodes.push(data.nodes[id]);
  //     }
  //     return a;
  //   }, { nodes: [], edges: [], ids: {} });

  const { nodes, edges } = data;

  // edges
  ctx.beginPath();
  ctx.strokeStyle = '#707070';
  edges.forEach((e) => {
    const s = nodesMap[e.source],
          t = nodesMap[e.target];
    ctx.moveTo(s.x, s.y);
    if (e.curvature === 0) {
      ctx.lineTo(t.x, t.y);
    } else {
      const cp = getQuadraticControlPoint(s.x, s.y, t.x, t.y);
      ctx.quadraticCurveTo(cp.x, cp.y, t.x, t.y);
    }
  });
  ctx.stroke();
  ctx.closePath();

  // highlighted edges
  ctx.beginPath();
  ctx.fillStyle   = 'red';
  ctx.strokeStyle = '#505050';
  ctx.lineWidth = 5;
  foundEdges.forEach((e) => {
    const s = nodesMap[e.source],
          t = nodesMap[e.target];
    ctx.moveTo(s.x, s.y);

    if (e.curvature === 0) {
      ctx.lineTo(t.x, t.y);
    } else {
      const cp = getQuadraticControlPoint(s.x, s.y, t.x, t.y);
      ctx.quadraticCurveTo(cp.x, cp.y, t.x, t.y);
    }
  });
  ctx.stroke();

  // nodes;
  ctx.beginPath();
  ctx.fillStyle   = 'orange';
  ctx.strokeStyle = '#333333';
  ctx.lineWidth = 1;
  nodes.forEach((n) => {
    ctx.moveTo(n.x + n.r, n.y);
    ctx.arc(n.x, n.y, n.r, 0, 2 * Math.PI, false);
  });
  ctx.stroke();
  ctx.fill();

  if (selectedNode) {
    ctx.beginPath();
    ctx.fillStyle   = 'red';
    ctx.strokeStyle = '#333333';
    ctx.moveTo(selectedNode.x + selectedNode.r, selectedNode.y);
    ctx.arc(selectedNode.x, selectedNode.y, selectedNode.r, 0, 2 * Math.PI, false);
    ctx.stroke();
    ctx.fill();
  }

  ctx.beginPath();
  ctx.fillStyle   = 'red';
  ctx.strokeStyle = '#333333';
  ctx.lineWidth = 15;
  foundNodes.forEach((n) => {
    ctx.moveTo(n.x + n.r, n.y);
    ctx.arc(n.x, n.y, n.r, 0, 2 * Math.PI, false);
  });
  ctx.stroke();
  ctx.fill();

  ctx.lineWidth = 1;
  // query
  ctx.beginPath();
  ctx.strokeStyle = 'brown';
  ctx.rect(qBounds[0], qBounds[1], qBounds[2] - qBounds[0], qBounds[3] - qBounds[1]);
  ctx.closePath();
  ctx.stroke();
}


function renderIndex() {
  const map = {};
  const nodesToDraw = [];
  U.forEach((n) => {
    if (!map[n.key]) {
      map[n.key] = true;
      nodesToDraw.push(n);
    }
  });

  ctx.beginPath();
  nodesToDraw.forEach((n) => {
    const b = U.keyToBBox(n.key);
    ctx.rect(b[0], b[1], b[2] - b[0], b[3] - b[1]);
  });
  ctx.closePath();
  ctx.stroke();
}


function getRandomColor() {
  const letters = '0123456789ABCDEF';
  let color = '#';
  for (var i = 0; i < 6; i++) {
    color += letters[Math.floor(Math.random() * 16)];
  }
  return color;
}

canvas.addEventListener('mousemove', ({ clientX, clientY }) => {
  const x = clientX * pxRatio;
  const y = clientY * pxRatio;

  const offset = 10 * pxRatio;

  foundNodes.length = 0;
  foundEdges.length = 0;

  qBounds[0] = x - offset;
  qBounds[1] = y - offset;
  qBounds[2] = x + offset;
  qBounds[3] = y + offset;

  const Nn = data.nodes.length;
  const before = Date.now();
  U.query(qBounds).forEach((id) => {
    if (id >= Nn) {
      foundEdges.push(data.edges[id - Nn]);
    } else {
      foundNodes.push(data.nodes[id]);
    }
  });
  stats.totalTime += (Date.now() - before);
  stats.queries++;

  requestAnimationFrame(render);
});

canvas.addEventListener('click', ({ clientX, clientY }) => {
  const mx = clientX * pxRatio;
  const my = clientY * pxRatio;

  requestAnimationFrame(render);
});

function onLayoutDone() {
  indexNodes();
  indexEdges();
}


function indexNodes() {
  console.time('insert nodes into UB');
  data.nodes.forEach(({ x, y, r }, i) => {
    const bbox = [x - r, y - r, x + r, y + r];

    const pos = i * SZ;
    flatStorage[pos + 0] = bbox[0];
    flatStorage[pos + 1] = bbox[1];
    flatStorage[pos + 2] = bbox[2];
    flatStorage[pos + 3] = bbox[3];
    flatStorage[pos + 4] = POLYGON;

    U.insert(i);
  });
  console.timeEnd('insert nodes into UB');
}

function indexEdges() {
  console.time('insert edges into UB');
  const offset = data.nodes.length;
  data.edges.forEach(({ source, target, curvature }, i) => {
    const s = nodesMap[source],
          t = nodesMap[target];
    const pos = SZ * (offset + i);

    // console.log(source, target);

    flatStorage[pos + 0] = /*s.x; */ source;
    flatStorage[pos + 1] = /*s.y; */ target;
    flatStorage[pos + 2] = curvature; // t.x;
    flatStorage[pos + 3] = t.y;
    flatStorage[pos + 4] = curvature === 0 ? LINESTRING : CURVE;

    U.insert(offset + i);
  });
  console.timeEnd('insert edges into UB');
}


function updateNodes() {
  data.nodes.map((n, i) => {
    const { x, y, r } = n;
    const pos = i * SZ;
    flatStorage[pos + 0] = x - r;
    flatStorage[pos + 1] = y - r;
    flatStorage[pos + 2] = x + r;
    flatStorage[pos + 3] = y + r;
    flatStorage[pos + 4] = POLYGON;

    U.update(i);
  });
}

function updateEdges() {
  const offset = data.nodes.length;
  data.edges.forEach(({ source, target }, i) => {
    const s = nodesMap[source],
          t = nodesMap[target];
    const pos = SZ * (offset + i);

    flatStorage[pos + 0] = source; //s.x;
    flatStorage[pos + 1] = target; //s.y;
    flatStorage[pos + 2] = t.x;
    flatStorage[pos + 3] = t.y;
    flatStorage[pos + 4] = LINESTRING;

    U.update(offset + i);
  });
}


function clearNodesIndex() {
  console.time('clear nodes');
  data.nodes.forEach((e, i) => U.remove(i))
  console.timeEnd('clear nodes');
}

function clearEdgesIndex() {
  console.time('clear edges');
  const offset = data.nodes.length;
  data.edges.forEach((e, i) => U.remove(offset + i));
  console.timeEnd('clear edges');
}

function layout(data, callback = () => {}) {
  const m = data.nodes.length < 1000 ? 1.2 : 1;
  return d3.forceSimulation(data.nodes)
    .force('charge', d3.forceManyBody())
    .force('link', d3.forceLink(data.edges.map((e) => ({
        id: e.id,
        target: e.target,
        source: e.source
      }))
    )
      .id((d) => d.id)
      .distance(25 * m))
    .force('collision', d3.forceCollide(15 * m))
    .force('center', d3.forceCenter(w / 2, h / 2))
    .force("y", d3.forceY(0))
    .force("x", d3.forceX(0))
    .alphaDecay(0.1)
    .on('tick', render)
    .on('end', callback);
}

const U = new UBTree(6);

const form = document.querySelector('#control');
form.addEventListener('change', function() {
  setTimeout(function() {
    var nodesIndex = form['nodes'].checked;
    var edgesIndex = form['edges'].checked;
    var level      = form['level'].value;

    U.clear();
    U.setLevel(level);

    if (nodesIndex) indexNodes();
    if (edgesIndex) indexEdges();

    showIndex = form['grid'].checked;
    render();
  }, 50);
});

const indicator  = document.querySelector('#indicator');
const rangeInput = document.querySelector('#range');
var populateTimer = 0;
function onGraphChanged() {
  clearTimeout(populateTimer);
  populateTimer = requestAnimationFrame(() => {
    N = parseInt(rangeInput.value);
    indicator.innerHTML = `G = (${N}<sub>V</sub> &times; ${N}<sub>E</sub>)`;
    populate(N);
  });
}
rangeInput.addEventListener('change', onGraphChanged);

onGraphChanged();

## morton.js
// Morton lookup tables.
// Based on http://graphics.stanford.edu/~seander/bithacks.html#InterleaveTableLookup
(function (f) {
    if (typeof module !== 'undefined') module.exports = f();
    else window.morton = f();
}) (function() {

var X = [ 0, 1 ], Y = [ 0, 2 ];
for (var i = 4; i < 0xFFFF; i <<= 2) {
    for (var j = 0, l = X.length; j < l; j++) {
        X.push((X[j] | i));
        Y.push((X[j] | i) << 1);
    }
}

// Only works for 24 bit input numbers (up to 16777215).
function morton(x, y) {
    return (Y[y         & 0xFF] | X[x         & 0xFF]) +
           (Y[(y >> 8)  & 0xFF] | X[(x >> 8)  & 0xFF]) * 0x10000 +
           (Y[(y >> 16) & 0xFF] | X[(x >> 16) & 0xFF]) * 0x100000000;
};

morton.code = function code(z, x, y) {
    if (z > 24) throw 'Morton codes are only supported up to Z=24';
    var Z = 1 << (24 - z);
    return morton(x * Z, y * Z);
};

morton.range = function range(z, x, y) {
    if (z > 24) throw 'Morton ranges are only supported up to Z=24';
    var Z = 1 << (24 - z);
    var lower = morton(x * Z, y * Z);
    return [ lower, lower + Z * Z - 1 ];
};

var rX, rY;
function reverse(c, dest = []) {
    if (c > 0xFFFFFFFFFFFF) throw 'Only morton codes up to 48 bits are supported.';
    if (!rX) {
        // Create reverse lookup tables.
        rX = {}; rY = {};
        for (var i = 0; i < 256; i++) {
            rX[morton(i, 0)] = i;
            rY[morton(0, i)] = i;
        }
    }

    var x = rX[c & 0x5555];
    var y = rY[c & 0xAAAA];
    if (c > 0xFFFF) {
        c /= 0x10000;
        x |= rX[c & 0x5555] << 8;
        y |= rY[c & 0xAAAA] << 8;
        if (c > 0xFFFF) {
            c /= 0x10000;
            x |= rX[c & 0x5555] << 16;
            y |= rY[c & 0xAAAA] << 16;
        }
    }

    dest[0] = x;
    dest[1] = y;

    return dest;
}
morton.reverse = reverse;

morton.decode = function decode(z, c) {
    var output = reverse(c);
    var Z = 1 << (24 - z);
    return [ output[0] / Z, output[1] / Z ];
};

morton.min = function min(lhs, rhs) {
   // Isolate the encoded coordinates.
   var lhsX = lhs & 0x55555555; // lhsX = -f-e -d-c -b-a -9-8 -7-6 -5-4 -3-2 -1-0
   var rhsX = rhs & 0x55555555; // rhsX = -f-e -d-c -b-a -9-8 -7-6 -5-4 -3-2 -1-0
   var lhsY = lhs & 0xAAAAAAAA; // lhsY = f-e- d-c- b-a- 9-8- 7-6- 5-4- 3-2- 1-0-
   var rhsY = rhs & 0xAAAAAAAA; // rhsY = f-e- d-c- b-a- 9-8- 7-6- 5-4- 3-2- 1-0-

   // Find the minimum of the encoded coordinates and combine them into a single word.
   return Math.min(lhsX, rhsX) + Math.min(lhsY, rhsY);
}

return morton;
});

## preview.png

      
    Raw
  

              preview.png
            
          
## thumbnail.png

      
    Raw
  

              thumbnail.png
            
          
## ubtree.js

      
    Raw
  

              ubtree.js
            
          
            View raw
              (Sorry about that, but we can’t show files that are this big right now.)
	<!DOCTYPE html>
	<html>
	<head>
	<title>Z-curve hash for boxes and segments with range queries</title>
	<script type="text/javascript" src="https://unpkg.com/splaytree@0.1.1/dist/splay.js"></script>
	<script type="text/javascript" src="https://unpkg.com/liang-barsky@1.0.1/dist/liang-barsky.js"></script>
	<script type="text/javascript" src="https://unpkg.com/d3-quadtree@1.0.3"></script>
	<script type="text/javascript" src="https://unpkg.com/d3-dispatch@1.0.3/build/d3-dispatch.js"></script>
	<script type="text/javascript" src="https://unpkg.com/d3-timer@1.0.7/build/d3-timer.js"></script>
	<script type="text/javascript" src="https://unpkg.com/d3-collection@1.0.4/build/d3-collection.js"></script>
	<script type="text/javascript" src="https://unpkg.com/d3-force@1.1.0/build/d3-force.js"></script>
	<script type="text/javascript" src="https://unpkg.com/bresenham-zingl@0.1.0/dist/bresenham.js"></script>
	<script type="text/javascript" src="https://unpkg.com/bezier-intersect@0.0.1/dist/bezier-intersect.js"></script>
	<script type="text/javascript" src="morton.js"></script>
	<script type="text/javascript" src="ubtree.js"></script>
	<style type="text/css">
	body, html, #canvas {
	width: 100%;
	height: 100%;
	margin: 0;
	padding: 0;
	}
	body {
	background: #ddd;
	font-family: "Helvetica Neue", Helvetica, Arial, sans-serif;
	}
	#canvas {
	background: #fff;
	}

	#control {
	position: absolute;
	top: 20px;
	right: 20px;
	background: #fff;
	box-shadow: 0 0 5px rgba(80,80,80, 0.5);
	padding: 5px 10px;
	border-radius: 5px;
	}

	#control p {
	padding: 0;
	margin: 4px;
	}

	#range {
	position: absolute;
	bottom: 20px;
	left: 20px;
	width: 90%;
	}

	#indicator {
	position: absolute;
	bottom: 50px;
	right: 20px;
	left: 20px;
	font-size: 1.5em;
	font-weight: 300;
	color: #222222;
	}
	</style>
	</head>
	<body>
	<canvas id="canvas"></canvas>
	<input type="range" id="range" min="10" max="10000" value="1000" />
	<div id="indicator">1000</div>
	<form id="control">
	<p><label><input type="checkbox" name="nodes" checked> nodes</label></p>
	<p><label><input type="checkbox" name="edges" checked> edges</label></p>
	<p><label><input type="checkbox" name="grid"> grid</label></p>
	<p><label><select name="level">
	<option value="1">1</option>
	<option value="2">2</option>
	<option value="3">3</option>
	<option value="4">4</option>
	<option value="5">5</option>
	<option value="6">6</option>
	<option value="7">7</option>
	<option value="8" selected>8</option>
	<option value="9">9</option>
	<option value="10">10</option>
	<option value="11">11</option>
	<option value="12">12</option>
	</select> level</label></p>
	</form>
	<script type="text/javascript" src="index.js"></script>
	</body>
	</html>
	const screenWidth = document.documentElement.clientWidth;
	const screenHeight = document.documentElement.clientHeight;

	const pxRatio = window.devicePixelRatio;

	const canvas = document.getElementById('canvas');
	const ctx = canvas.getContext('2d');

	const w = canvas.width = screenWidth * devicePixelRatio;
	const h = canvas.height = screenHeight * devicePixelRatio;

	const stats = {
	queries: 0,
	totalTime: 0,
	getAverage() {
	return `${this.totalTime / this.queries}ms`;
	},
	clear() {
	this.totalTime = this.queries = 0;
	}
	};

	canvas.style.width = screenWidth + 'px';
	canvas.style.height = screenHeight + 'px';


	function scaleGraphToFitBounds(G, bounds) {
	var min = Math.min, max = Math.max;
	var bbox = getBounds(G);
	var cx = (bounds[0] + bounds[2]) / 2,
	cy = (bounds[1] + bounds[3]) / 2,
	gcx = (bbox[0] + bbox[2]) / 2,
	gcy = (bbox[1] + bbox[3]) / 2;

	var tx = cx - gcx,
	ty = cy - gcy;

	var scale = min(
	(bounds[2] - bounds[0]) / (bbox[2] - bbox[0]),
	(bounds[3] - bounds[1]) / (bbox[3] - bbox[1])
	);


	G.nodes.forEach(function (n) {
	n.x = cx + ((n.x + tx) - cx) * scale;
	n.y = cy + ((n.y + ty) - cy) * scale;
	});
	}

	function getBounds(g) {
	return g.nodes.reduce((b, n) => {
	b[0] = Math.min(b[0], n.x);
	b[1] = Math.min(b[1], n.y);
	b[2] = Math.max(b[2], n.x);
	b[3] = Math.max(b[3], n.y);
	return b;
	}, [Infinity, Infinity, -Infinity, -Infinity]);
	}


	function generateDenseTree(N = 550, width = 1000, height = 1000) {
	let counter = 0;
	return {
	nodes: new Array(N).fill(0).map(function(_, i) {
	counter++;
	return {
	id: i,
	text: 'Node #' + i,
	x: Math.random() * width,
	y: Math.random() * height,
	r: 3 + Math.random() * 8
	};
	}),
	edges: new Array(N - 1).fill(0).map(function(_, i) {
	counter++;
	return {
	id: i,
	curvature: (i % 3 === 0) ? 1 : 1,
	//curvature: 0,
	source: Math.floor(Math.sqrt(i)),
	target: i + 1
	};
	})
	};
	}

	var N = 1000;
	var data, nodesMap, simulation;
	const SZ = 5;
	var flatStorage;
	let foundNodes = [];
	let foundEdges = [];
	let selectedNode = null;
	let showIndex = false;

	function populate(n) {
	N = n;
	foundNodes = [];
	foundEdges = [];
	selectedNode = null;

	if (simulation) simulation.stop();
	data = generateDenseTree(N, w, h);
	nodesMap = data.nodes.reduce((a, n) => {
	a[n.id] = n;
	return a;
	}, {});
	flatStorage = new Float32Array(SZ * 2 * N);


	simulation = layout(data, onLayoutDone);
	}

	const qBounds = [0, 0, 0, 0];

	function render() {
	ctx.clearRect(0, 0, w, h);

	if (showIndex) {
	ctx.lineWidth = 0.5;
	renderIndex();

	ctx.lineWidth = 1;
	ctx.beginPath();
	U._checkedNodes.forEach((n) => {
	const b = U.keyToBBox(n.key);
	ctx.rect(b[0], b[1], b[2] - b[0], b[3] - b[1]);
	});
	ctx.globalAlpha = 0.2;
	ctx.fillStyle = 'blue';
	ctx.fill();
	ctx.globalAlpha = 1;
	}


	const Nn = data.nodes.length;
	// const { nodes, edges } = U.size === 0 ? data : U.query([0, 0, w, h])
	// .reduce((a, id) => {
	// if (!a.ids[id]) {
	// a.ids[id] = true;
	// if (id >= Nn) a.edges.push(data.edges[id - Nn]);
	// else a.nodes.push(data.nodes[id]);
	// }
	// return a;
	// }, { nodes: [], edges: [], ids: {} });

	const { nodes, edges } = data;

	// edges
	ctx.beginPath();
	ctx.strokeStyle = '#707070';
	edges.forEach((e) => {
	const s = nodesMap[e.source],
	t = nodesMap[e.target];
	ctx.moveTo(s.x, s.y);
	if (e.curvature === 0) {
	ctx.lineTo(t.x, t.y);
	} else {
	const cp = getQuadraticControlPoint(s.x, s.y, t.x, t.y);
	ctx.quadraticCurveTo(cp.x, cp.y, t.x, t.y);
	}
	});
	ctx.stroke();
	ctx.closePath();

	// highlighted edges
	ctx.beginPath();
	ctx.fillStyle = 'red';
	ctx.strokeStyle = '#505050';
	ctx.lineWidth = 5;
	foundEdges.forEach((e) => {
	const s = nodesMap[e.source],
	t = nodesMap[e.target];
	ctx.moveTo(s.x, s.y);

	if (e.curvature === 0) {
	ctx.lineTo(t.x, t.y);
	} else {
	const cp = getQuadraticControlPoint(s.x, s.y, t.x, t.y);
	ctx.quadraticCurveTo(cp.x, cp.y, t.x, t.y);
	}
	});
	ctx.stroke();

	// nodes;
	ctx.beginPath();
	ctx.fillStyle = 'orange';
	ctx.strokeStyle = '#333333';
	ctx.lineWidth = 1;
	nodes.forEach((n) => {
	ctx.moveTo(n.x + n.r, n.y);
	ctx.arc(n.x, n.y, n.r, 0, 2 * Math.PI, false);
	});
	ctx.stroke();
	ctx.fill();

	if (selectedNode) {
	ctx.beginPath();
	ctx.fillStyle = 'red';
	ctx.strokeStyle = '#333333';
	ctx.moveTo(selectedNode.x + selectedNode.r, selectedNode.y);
	ctx.arc(selectedNode.x, selectedNode.y, selectedNode.r, 0, 2 * Math.PI, false);
	ctx.stroke();
	ctx.fill();
	}

	ctx.beginPath();
	ctx.fillStyle = 'red';
	ctx.strokeStyle = '#333333';
	ctx.lineWidth = 15;
	foundNodes.forEach((n) => {
	ctx.moveTo(n.x + n.r, n.y);
	ctx.arc(n.x, n.y, n.r, 0, 2 * Math.PI, false);
	});
	ctx.stroke();
	ctx.fill();

	ctx.lineWidth = 1;
	// query
	ctx.beginPath();
	ctx.strokeStyle = 'brown';
	ctx.rect(qBounds[0], qBounds[1], qBounds[2] - qBounds[0], qBounds[3] - qBounds[1]);
	ctx.closePath();
	ctx.stroke();
	}


	function renderIndex() {
	const map = {};
	const nodesToDraw = [];
	U.forEach((n) => {
	if (!map[n.key]) {
	map[n.key] = true;
	nodesToDraw.push(n);
	}
	});

	ctx.beginPath();
	nodesToDraw.forEach((n) => {
	const b = U.keyToBBox(n.key);
	ctx.rect(b[0], b[1], b[2] - b[0], b[3] - b[1]);
	});
	ctx.closePath();
	ctx.stroke();
	}


	function getRandomColor() {
	const letters = '0123456789ABCDEF';
	let color = '#';
	for (var i = 0; i < 6; i++) {
	color += letters[Math.floor(Math.random() * 16)];
	}
	return color;
	}

	canvas.addEventListener('mousemove', ({ clientX, clientY }) => {
	const x = clientX * pxRatio;
	const y = clientY * pxRatio;

	const offset = 10 * pxRatio;

	foundNodes.length = 0;
	foundEdges.length = 0;

	qBounds[0] = x - offset;
	qBounds[1] = y - offset;
	qBounds[2] = x + offset;
	qBounds[3] = y + offset;

	const Nn = data.nodes.length;
	const before = Date.now();
	U.query(qBounds).forEach((id) => {
	if (id >= Nn) {
	foundEdges.push(data.edges[id - Nn]);
	} else {
	foundNodes.push(data.nodes[id]);
	}
	});
	stats.totalTime += (Date.now() - before);
	stats.queries++;

	requestAnimationFrame(render);
	});

	canvas.addEventListener('click', ({ clientX, clientY }) => {
	const mx = clientX * pxRatio;
	const my = clientY * pxRatio;

	requestAnimationFrame(render);
	});

	function onLayoutDone() {
	indexNodes();
	indexEdges();
	}


	function indexNodes() {
	console.time('insert nodes into UB');
	data.nodes.forEach(({ x, y, r }, i) => {
	const bbox = [x - r, y - r, x + r, y + r];

	const pos = i * SZ;
	flatStorage[pos + 0] = bbox[0];
	flatStorage[pos + 1] = bbox[1];
	flatStorage[pos + 2] = bbox[2];
	flatStorage[pos + 3] = bbox[3];
	flatStorage[pos + 4] = POLYGON;

	U.insert(i);
	});
	console.timeEnd('insert nodes into UB');
	}

	function indexEdges() {
	console.time('insert edges into UB');
	const offset = data.nodes.length;
	data.edges.forEach(({ source, target, curvature }, i) => {
	const s = nodesMap[source],
	t = nodesMap[target];
	const pos = SZ * (offset + i);

	// console.log(source, target);

	flatStorage[pos + 0] = /s.x; / source;
	flatStorage[pos + 1] = /s.y; / target;
	flatStorage[pos + 2] = curvature; // t.x;
	flatStorage[pos + 3] = t.y;
	flatStorage[pos + 4] = curvature === 0 ? LINESTRING : CURVE;

	U.insert(offset + i);
	});
	console.timeEnd('insert edges into UB');
	}


	function updateNodes() {
	data.nodes.map((n, i) => {
	const { x, y, r } = n;
	const pos = i * SZ;
	flatStorage[pos + 0] = x - r;
	flatStorage[pos + 1] = y - r;
	flatStorage[pos + 2] = x + r;
	flatStorage[pos + 3] = y + r;
	flatStorage[pos + 4] = POLYGON;

	U.update(i);
	});
	}

	function updateEdges() {
	const offset = data.nodes.length;
	data.edges.forEach(({ source, target }, i) => {
	const s = nodesMap[source],
	t = nodesMap[target];
	const pos = SZ * (offset + i);

	flatStorage[pos + 0] = source; //s.x;
	flatStorage[pos + 1] = target; //s.y;
	flatStorage[pos + 2] = t.x;
	flatStorage[pos + 3] = t.y;
	flatStorage[pos + 4] = LINESTRING;

	U.update(offset + i);
	});
	}


	function clearNodesIndex() {
	console.time('clear nodes');
	data.nodes.forEach((e, i) => U.remove(i))
	console.timeEnd('clear nodes');
	}

	function clearEdgesIndex() {
	console.time('clear edges');
	const offset = data.nodes.length;
	data.edges.forEach((e, i) => U.remove(offset + i));
	console.timeEnd('clear edges');
	}

	function layout(data, callback = () => {}) {
	const m = data.nodes.length < 1000 ? 1.2 : 1;
	return d3.forceSimulation(data.nodes)
	.force('charge', d3.forceManyBody())
	.force('link', d3.forceLink(data.edges.map((e) => ({
	id: e.id,
	target: e.target,
	source: e.source
	}))
	)
	.id((d) => d.id)
	.distance(25 * m))
	.force('collision', d3.forceCollide(15 * m))
	.force('center', d3.forceCenter(w / 2, h / 2))
	.force("y", d3.forceY(0))
	.force("x", d3.forceX(0))
	.alphaDecay(0.1)
	.on('tick', render)
	.on('end', callback);
	}

	const U = new UBTree(6);

	const form = document.querySelector('#control');
	form.addEventListener('change', function() {
	setTimeout(function() {
	var nodesIndex = form['nodes'].checked;
	var edgesIndex = form['edges'].checked;
	var level = form['level'].value;

	U.clear();
	U.setLevel(level);

	if (nodesIndex) indexNodes();
	if (edgesIndex) indexEdges();

	showIndex = form['grid'].checked;
	render();
	}, 50);
	});

	const indicator = document.querySelector('#indicator');
	const rangeInput = document.querySelector('#range');
	var populateTimer = 0;
	function onGraphChanged() {
	clearTimeout(populateTimer);
	populateTimer = requestAnimationFrame(() => {
	N = parseInt(rangeInput.value);
	indicator.innerHTML = `G = (${N}<sub>V</sub> × ${N}<sub>E</sub>)`;
	populate(N);
	});
	}
	rangeInput.addEventListener('change', onGraphChanged);

	onGraphChanged();
	// Morton lookup tables.
	// Based on http://graphics.stanford.edu/~seander/bithacks.html#InterleaveTableLookup
	(function (f) {
	if (typeof module !== 'undefined') module.exports = f();
	else window.morton = f();
	}) (function() {

	var X = [ 0, 1 ], Y = [ 0, 2 ];
	for (var i = 4; i < 0xFFFF; i <<= 2) {
	for (var j = 0, l = X.length; j < l; j++) {
	X.push((X[j] \| i));
	Y.push((X[j] \| i) << 1);
	}
	}

	// Only works for 24 bit input numbers (up to 16777215).
	function morton(x, y) {
	return (Y[y & 0xFF] \| X[x & 0xFF]) +
	(Y[(y >> 8) & 0xFF] \| X[(x >> 8) & 0xFF]) * 0x10000 +
	(Y[(y >> 16) & 0xFF] \| X[(x >> 16) & 0xFF]) * 0x100000000;
	};

	morton.code = function code(z, x, y) {
	if (z > 24) throw 'Morton codes are only supported up to Z=24';
	var Z = 1 << (24 - z);
	return morton(x * Z, y * Z);
	};

	morton.range = function range(z, x, y) {
	if (z > 24) throw 'Morton ranges are only supported up to Z=24';
	var Z = 1 << (24 - z);
	var lower = morton(x * Z, y * Z);
	return [ lower, lower + Z * Z - 1 ];
	};

	var rX, rY;
	function reverse(c, dest = []) {
	if (c > 0xFFFFFFFFFFFF) throw 'Only morton codes up to 48 bits are supported.';
	if (!rX) {
	// Create reverse lookup tables.
	rX = {}; rY = {};
	for (var i = 0; i < 256; i++) {
	rX[morton(i, 0)] = i;
	rY[morton(0, i)] = i;
	}
	}

	var x = rX[c & 0x5555];
	var y = rY[c & 0xAAAA];
	if (c > 0xFFFF) {
	c /= 0x10000;
	x \|= rX[c & 0x5555] << 8;
	y \|= rY[c & 0xAAAA] << 8;
	if (c > 0xFFFF) {
	c /= 0x10000;
	x \|= rX[c & 0x5555] << 16;
	y \|= rY[c & 0xAAAA] << 16;
	}
	}

	dest[0] = x;
	dest[1] = y;

	return dest;
	}
	morton.reverse = reverse;

	morton.decode = function decode(z, c) {
	var output = reverse(c);
	var Z = 1 << (24 - z);
	return [ output[0] / Z, output[1] / Z ];
	};

	morton.min = function min(lhs, rhs) {
	// Isolate the encoded coordinates.
	var lhsX = lhs & 0x55555555; // lhsX = -f-e -d-c -b-a -9-8 -7-6 -5-4 -3-2 -1-0
	var rhsX = rhs & 0x55555555; // rhsX = -f-e -d-c -b-a -9-8 -7-6 -5-4 -3-2 -1-0
	var lhsY = lhs & 0xAAAAAAAA; // lhsY = f-e- d-c- b-a- 9-8- 7-6- 5-4- 3-2- 1-0-
	var rhsY = rhs & 0xAAAAAAAA; // rhsY = f-e- d-c- b-a- 9-8- 7-6- 5-4- 3-2- 1-0-

	// Find the minimum of the encoded coordinates and combine them into a single word.
	return Math.min(lhsX, rhsX) + Math.min(lhsY, rhsY);
	}

	return morton;
	});