const W = document.documentElement.clientWidth;
const H = document.documentElement.clientHeight;
const pixelRatio = window.devicePixelRatio;

const canvas = document.getElementById('canvas');
canvas.style.width = W + 'px';
canvas.style.height = H + 'px';

const w = W * pixelRatio;
const h = H * pixelRatio;

canvas.width  = w;
canvas.height = h;

var indicator = document.getElementById('indicator');

const ctx = canvas.getContext('2d');
ctx.translate(w / 2, h / 2);
var N = 300;
var boxes = [];
var obbs = [];
var rotations = [];
var found = [], intersect = [], range, srange;
const wmin = 50, wmax = 100,
      hmin = 10, hmax = 50;

var gi;


function getAABB(x0, y0, w, h, angle = 0) {
  const hw = w / 2, hh = h / 2;
  const cx = x0 + hw, cy = y0 + hh;
  if (angle === 0) return [
    [cx - hw, cy - hh], [cx - hw, cy + hh],
    [cx + hw, cy + hh], [cx + hw, cy - hh]
  ];

  const sin = Math.sin(angle),
        cos = Math.cos(angle);
  let xr, yr, x, y;
  let minX, minY, maxX, maxY;

  x = -hw; y = -hh;
  xr = cx + x * cos - y * sin,
  yr = cy + x * sin + y * cos;
  minX = maxX = xr; minY = maxY = yr;


  x = -hw; y = hh;
  xr = cx + x * cos - y * sin;
  yr = cy + x * sin + y * cos;
  if (xr < minX) minX = xr; else if (xr > maxX) maxX = xr;
  if (yr < minY) minY = yr; else if (yr > maxY) maxY = yr;

  x = hw; y = hh;
  xr = cx + x * cos - y * sin;
  yr = cy + x * sin + y * cos;
  if (xr < minX) minX = xr; else if (xr > maxX) maxX = xr;
  if (yr < minY) minY = yr; else if (yr > maxY) maxY = yr;

  x = hw; y = -hh;
  xr = cx + x * cos - y * sin;
  yr = cy + x * sin + y * cos;
  if (xr < minX) minX = xr; else if (xr > maxX) maxX = xr;
  if (yr < minY) minY = yr; else if (yr > maxY) maxY = yr;

  return [minX, minY, maxX, maxY];
}


function getOBB(x0, y0, w, h, angle = 0) {
  const hw = w / 2, hh = h / 2;
  const cx = x0 + hw, cy = y0 + hh;
  if (angle === 0) return [
    [cx - hw, cy - hh], [cx - hw, cy + hh],
    [cx + hw, cy + hh], [cx + hw, cy - hh]
  ];

  const sin = Math.sin(angle),
        cos = Math.cos(angle);
  let xr, yr, x, y;
  const vertices = [];

  x = -hw; y = -hh;
  xr = cx + x * cos - y * sin,
  yr = cy + x * sin + y * cos;
  vertices.push([xr, yr]);

  x = -hw; y = hh;
  xr = cx + x * cos - y * sin;
  yr = cy + x * sin + y * cos;
  vertices.push([xr, yr]);

  x = hw; y = hh;
  xr = cx + x * cos - y * sin;
  yr = cy + x * sin + y * cos;
  vertices.push([xr, yr]);

  x = hw; y = -hh;
  xr = cx + x * cos - y * sin;
  yr = cy + x * sin + y * cos;
  vertices.push([xr, yr]);

  return vertices;
}


function render() {
  var b, v, o;
  ctx.clearRect(-w/2, -h/2, w, h);

  if (N < 1000) {
    // AABBs
    ctx.lineWidth = 1;
    ctx.strokeStyle = '#dfdfdf';
    ctx.beginPath();
    for (let i = 0; i < boxes.length; i++) {
      b = boxes[i];
      o = getAABB(b[0], b[1], b[2], b[3], rotations[i]);
      ctx.moveTo(o[0], o[1]);
      ctx.rect(o[0], o[1], o[2] - o[0], o[3] - o[1]);
    }
    ctx.stroke();
  }

  ctx.lineWidth = 1;
  ctx.strokeStyle = '#999999';
  ctx.beginPath();
  for (let i = 0; i < boxes.length; i++) {
    b = boxes[i];
    v = getOBB(b[0], b[1], b[2], b[3], rotations[i]);

    ctx.moveTo(v[0][0], v[0][1]);
    for (let j = 0; j < 4; j++) ctx.lineTo(v[j][0], v[j][1]);
    ctx.lineTo(v[0][0], v[0][1]);
  }
  ctx.stroke();


  ctx.strokeStyle = '#aaaaaa';
  ctx.lineWidth = 4;
  ctx.beginPath();
  for (let i = 0; i < found.length; i++) {
    b = boxes[found[i]];
    v = getOBB(b[0], b[1], b[2], b[3], rotations[found[i]]);

    ctx.moveTo(v[0][0], v[0][1]);
    for (let j = 0; j < 4; j++) ctx.lineTo(v[j][0], v[j][1]);
    ctx.lineTo(v[0][0], v[0][1]);
  }
  ctx.stroke();

  ctx.strokeStyle = '#990000';
  ctx.lineWidth = 4;
  ctx.beginPath();
  for (let i = 0; i < intersect.length; i++) {
    b = boxes[intersect[i]];
    v = getOBB(b[0], b[1], b[2], b[3], rotations[intersect[i]]);

    ctx.moveTo(v[0][0], v[0][1]);
    for (let j = 0; j < 4; j++) ctx.lineTo(v[j][0], v[j][1]);
    ctx.lineTo(v[0][0], v[0][1]);
  }
  ctx.stroke();

  if (srange) {
    ctx.strokeStyle = '#dd0000';
    ctx.lineWidth = 2;
    ctx.beginPath();

    ctx.moveTo(srange[0], srange[1]);
    ctx.rect(srange[0], srange[1], srange[2] - srange[0], srange[3] - srange[1]);

    ctx.stroke();
  }

  if (range) {
    ctx.strokeStyle = '#999900';
    ctx.lineWidth = 4;
    ctx.beginPath();

    ctx.moveTo(range[0][0], range[0][1]);
    for (let j = 0; j < 4; j++) ctx.lineTo(range[j][0], range[j][1]);
    ctx.lineTo(range[0][0], range[0][1]);

    ctx.stroke();
  }

  indicator.innerHTML = N;
}

var q;
var aabbs = [];

function populate() {
  N = parseInt(rangeInput.value);
  boxes = []; obbs = []; found = []; intersect = [], aabbs = [];
  // gi = new GridIndex(Math.max(w, h), 16, 1);
  q = new Quadtree(i => aabbs[i], 20, undefined, i => i);
  for (let i = 0; i < N; i++) {
    const x = Math.round(Math.random() * w) - w / 2, y = Math.round(Math.random() * h) - h / 2;
    const dx = Math.round(wmin + (wmax - wmin) * Math.random());
    const dy = Math.round(hmin + (hmax - hmin) * Math.random());
    boxes.push([x, y, dx, dy]);
    rotations.push(Math.PI * Math.random());
    obbs.push(getOBB(x, y, dx, dy, rotations[i]));
  }

  console.time('insert into grid index');
  var obb, aabb;
  // k.load(boxes);
  for (let i = 0; i < N; i++) {
    obb  = boxes[i];
    aabb = getAABB(obb[0], obb[1], obb[2], obb[3], rotations[i]);
    //gi.insert(i, aabb[0], aabb[1], aabb[2], aabb[3]);
    aabbs.push(aabb);
    q.insert(i);
  }
  console.timeEnd('insert into grid index');

  requestAnimationFrame(render);
}

var ends = [];

function getAverage() {
  return ends.reduce((a, v) => {
    return a + v;
  }, 0) / ends.length;
}

canvas.addEventListener('mousemove', (evt) => {
  const x = evt.clientX * pixelRatio - (w/2), y = evt.clientY * pixelRatio - (h/2);
  const S = 20;
  range = [x - S, y - S, x + S, y + S];
  var st = performance.now();
  srange = getAABB(range[0], range[1], range[2] - range[0], range[3] - range[1], Math.PI / 4);
  // found = gi.query(srange[0], srange[1], srange[2], srange[3]);
  found = q.query(srange);

  range = getOBB(range[0], range[1], S * 2, S * 2, Math.PI / 4);
  intersect = found.filter((i) => testCollision(obbs[i], range));
  ends.push(performance.now() - st);

  if (ends.length === 1000) console.log(getAverage());

  requestAnimationFrame(render);
});

requestAnimationFrame(render);

var repopulateTimer = 0;
var rangeInput = document.getElementById('range');
rangeInput.addEventListener('change', function (e) {
  clearTimeout(repopulateTimer);
  repopulateTimer = setTimeout(() => {
    populate();
  }, 200);
});

populate();