pseudocode for radius search in quadtrees

gistfile1.txt

function doRectanglesIntersert(r1_x0, r1_y0, r1_x1, r1_y1, r2_x0, r2_y0, r2_x1, r2_y1) {
  // magic
}

function pointInRectangle(x0, y0, x1, y1, qx, qy) {
  // magic
}

function pointInCircle(cx, cy, radius, qx, qy) {
  // magic
}

function visit(node, x, y, radius, collector) {
  // construct rectangle boundary (x0,y0)-(x1,y1)
  const x0 = x - radius
  const y0 = y - radius
  const x1 = x + radius
  const y1 = y + radius

  // do rectangle rectangle intersection...
  if (!doRectanglesIntersert(x0,y0,x1,y1,node.x0,node.y0,node.x1,node.y1)) {
    return
  }

  // rectangles do intersect, so lets go deeper
  if (node.children.length) {
    // has splits, search inside
    for (childNode in node.children) {
      visit(childNode, x, y, radius, collector)
    }
  } else {
    // is a leaf node, contains data we are interested in
    // is the node itself within the rectangle?
    if (pointInRectangle(x0, y0, x1, y1, node.data.x, node.data.y)) {
      collector.push(node.data)
    }
  }
}

const collector = []
visit(root, queryX, queryY, 500, collector)
// collector will have all the nodes that are within the broader rectangle
const rCollector = []
for (node in collector) {
  if (pointInRadius(node.x, node.y, 500, queryX, queryY)) {
    rCollector.push(node)
  }
}

// rCollector has the data we are interested in