{$R+}
type
  TBox = record x1,y1,x2,y2:Int32; end;
  TPoint = record x,y:Int32; end;
  TPointArray = array of TPoint;

  TQuadNode = record
    Bounds: TBox;
    Points: array of TPoint;
    NorthWest, NorthEast: Int32;  //Holds indices of the pos in the Tree-Array
    SouthWest, SouthEast: Int32;
  end;

  TQuadTree = record
    NODE_CAPACITY: UInt8;
    Data: array of TQuadNode;
  end;



function TQuadTree.AddBox(x1,y1,x2,y2:Int32): Int32;
begin
  Result := Length(self.Data);
  SetLength(self.Data, Result+1);
  with self.Data[Result] do
  begin
    Bounds.x1 := x1;
    Bounds.y1 := y1;
    Bounds.x2 := x2;
    Bounds.y2 := y2;

    NorthWest := -1;
    NorthEast := -1;
    SouthWest := -1;
    SouthEast := -1;
  end;
end;


procedure TQuadTree.Init(area:TBox; capacity:Int32=2);
begin
  self.AddBox(area.x1, area.y1, area.x2, area.y2);
  self.NODE_CAPACITY := capacity;
end;


// Insert a point into the QuadTree
function TQuadTree.Insert(p:TPoint; idx:Int32 = 0): Boolean;
begin
  try
    WriteLn('Range check: (index:' + ToString(idx) + ', size:' + ToString(Length(self.data))+')');
    //outside this box?
      if (self.Data[idx].Bounds.x1 > p.x) or (self.Data[idx].Bounds.x2 < p.x) or (self.Data[idx].Bounds.y1 > p.y) or (self.Data[idx].Bounds.y2 < p.y) then
        Exit(False);

      //can we fit it here?
      if (Length(self.Data[idx].Points) < NODE_CAPACITY) then
      begin
        self.Data[idx].Points += p;
        Exit(True);
      end;

      // Otherwise, subdivide and then add the point to whichever node will accept it
      if (self.Data[idx].northWest = -1) then
      begin
        WriteLn('Dividing! (',self.Data[idx].northWest, ', ', self.Data[idx].northEast, ', ', self.Data[idx].southWest, ', ', self.Data[idx].southEast, ')');
        self.SubDivide(idx);
      end;
      WriteLn(self.Data[idx].northWest, ', ', self.Data[idx].northEast, ', ', self.Data[idx].southWest, ', ', self.Data[idx].southEast);

      if self.Insert(p, self.Data[idx].northWest) then Exit(True);
      if self.Insert(p, self.Data[idx].northEast) then Exit(True);
      if self.Insert(p, self.Data[idx].southWest) then Exit(True);
      if self.Insert(p, self.Data[idx].southEast) then Exit(True);
  except
    // This should _never_ happen!
    RaiseException('Range check: (index:' + ToString(idx) + ', size:' + ToString(Length(self.data))+')');
  end;
end;


// Insert a point into the QuadTree
procedure TQuadTree.SubDivide(idx:Int32);
var
  mid:TPoint;
begin
  WriteLn('Divide got idx: ', idx);

  mid.X := (self.Data[idx].Bounds.X1 + self.Data[idx].Bounds.X2) shr 1;
  mid.Y := (self.Data[idx].Bounds.Y1 + self.Data[idx].Bounds.Y2) shr 1;

  self.Data[idx].northWest := self.AddBox(self.Data[idx].bounds.x1, self.Data[idx].bounds.y1, mid.x, mid.y);
  self.Data[idx].northEast := self.AddBox(mid.x, self.Data[idx].bounds.y1, self.Data[idx].bounds.x2, mid.y);
  self.Data[idx].southWest := self.AddBox(self.Data[idx].bounds.x1, mid.y, mid.x, self.Data[idx].bounds.y2);
  self.Data[idx].southEast := self.AddBox(mid.x, mid.y, self.Data[idx].bounds.x2, self.Data[idx].bounds.y2);
end;


function TPAFromBox(B:TBox): TPointArray;
var x,y:Int32;
begin
  for y:=B.x1 to B.y2 do
    for x:=B.x1 to B.x2 do
      Result += TPoint([x,y]);
end;


var
  Tree : TQuadTree;
  TPA: TPointArray;
  i:Int32;
begin
  TPA := TPAFromBox([0,0,10,10]);
  Tree.Init([0,0,11,11]);

  for i:=0 to High(TPA) do
  begin
    Tree.Insert(TPA[i]);
    WriteLn('----------------------');
  end;
end.