find method

T? find(int x, int y, [ double? r ])

返回离给定搜索半径的位置⟨x,y⟩最近的基准点。 如果没有指定半径，默认为无穷大。 如果在搜索范围内没有基准点，则返回未定义

Implementation

T? find(int x, int y, [double? r]) {
  T? data;
  num x0 = _x0;
  num y0 = _y0;
  num x1 = 0, y1 = 0, x2 = 0, y2 = 0;
  num x3 = _x1;
  num y3 = _y1;
  List<InnerQuad> quads = [];

  QuadNode? node = _root;
  int i = 0;
  if (node != null) {
    quads.add(InnerQuad(node, x0, y0, x3, y3));
  }

  double radius;
  if (r == null) {
    radius = double.infinity;
  } else {
    x0 = (x - r);
    y0 = (y - r);
    x3 = (x + r);
    y3 = (y + r);
    radius = r * r;
  }

  while (quads.isNotEmpty) {
    InnerQuad q = quads.removeLast();
    // 如果此象限不能包含更近的节点，请停止搜索
    node = q.node;
    if (node == null || (x1 = q.x0) > x3 || (y1 = q.y0) > y3 || (x2 = q.x1) < x0 || (y2 = q.y1) < y0) {
      continue;
    }
    //将当前象限一分为二.
    if (node.hasChild) {
      int xm = ((x1 + x2) / 2).round(), ym = ((y1 + y2) / 2).round();
      if (node[3] != null) {
        quads.add(InnerQuad(node[3]!, xm, ym, x2, y2));
      }
      if (node[2] != null) {
        quads.add(InnerQuad(node[2]!, x1, ym, xm, y2));
      }
      if (node[1] != null) {
        quads.add(InnerQuad(node[1]!, xm, y1, x2, ym));
      }
      if (node[0] != null) {
        quads.add(InnerQuad(node[0]!, x1, y1, xm, ym));
      }

      //首先访问最近的象限
      if ((i = _toInt(y >= ym) << 1 | _toInt(x >= xm)) != 0) {
        q = quads[quads.length - 1];
        quads[quads.length - 1] = quads[quads.length - 1 - i];
        quads[quads.length - 1 - i] = q;
      }
    } else {
      // 访问此点（不需要访问重合点！）
      var dx = x - xFun(node.data), dy = y - yFun(node.data);
      double d2 = (dx * dx + dy * dy);
      if (d2 < radius) {
        radius = d2;
        var d = sqrt(radius);
        x0 = x - d;
        y0 = y - d;
        x3 = x + d;
        y3 = y + d;
        data = node.data!;
      }
    }
  }
  return data;
}