1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:

type
  PPtQTree=^TPtQTree;
  TPtQTree=record
    child1,child2,child3,child4:PPtQTree;
    Points:Array of TPoint;
  end;
  TQTree=class
    public
      mPtMinX:Integer=0;
      mPtMinY:Integer=0;
      mPtMaxX:Integer=1919;
      mPtMaxY:Integer=1919;
      maxDepth:Integer=20;
      maxEntries:Integer=7;
      PtQTree:PPtQTree;
      curAddPoint:TPoint;
      FoundPoints:Array of TPoint;
//...

procedure TQTree.FreePtQTree(var Tree:PPtQTree);
begin
  if(Tree=nil) then exit;
  FreePtQTree(Tree.child1);
  FreePtQTree(Tree.child2);
  FreePtQTree(Tree.child3);
  FreePtQTree(Tree.child4);
  Finalize(Tree^);
  Tree:=nil;
end;

procedure TQTree.AddPoint(const Pt: TPoint);
begin
  curAddPoint:=Pt;
  AddPoint(PtQTree,0,mPtMinX,mPtMaxX,mPtMinY,mPtMaxY);
end;

procedure TQTree.AddPoint(var Tree:PPtQTree;depth,cX1,cX2,cY1,cY2: Integer);
var i:Integer;
    savePt:TPoint;
begin
  //Tree is empty-->target is this tree
  if(Tree=nil) then begin
    new(Tree);
    Tree.child1:=nil;
    Tree.child2:=nil;
    Tree.child3:=nil;
    Tree.child4:=nil;
    SetLength(Tree.Points,1);
    Tree.Points[0]:=curAddPoint;
    exit;
  end;
  //has child(s) --> get right child as target
  if(Tree.child1<>nil) or (Tree.child2<>nil) or (Tree.child3<>nil) or (Tree.child4<>nil) then begin
    if(curAddPoint.X<(cX2+cX1) div 2) then begin
      if(curAddPoint.Y<(cY2+cY1) div 2) then AddPoint(Tree.child1,depth+1,cX1,(cX2+cX1) div 2,cY1,(cY2+cY1) div 2)
      else AddPoint(Tree.child3,depth+1,cX1,(cX2+cX1) div 2,(cY2+cY1) div 2+1,cY2);
    end else begin
      if(curAddPoint.Y<(cY2+cY1) div 2) then AddPoint(Tree.child2,depth+1,(cX2+cX1) div 2+1,cX2,cY1,(cY2+cY1) div 2)
      else AddPoint(Tree.child4,depth+1,(cX2+cX1) div 2+1,cX2,(cY2+cY1) div 2+1,cY2);
    end;
    exit;
  end;
  //maxDepth reached or still have place for one more Point-->add
  if(depth>=maxDepth) or (Length(Tree.Points)<maxEntries) then begin
    SetLength(Tree.Points,Length(Tree.Points)+1);
    Tree.Points[High(Tree.Points)]:=curAddPoint;
    exit;
  end;
  //No place for points-->clear current node and add them to subnodes
  savePt:=curAddPoint;
  for i := 0 to Length(Tree.Points) - 1 do begin
    curAddPoint:=Tree.Points[i];
    if(curAddPoint.X<(cX2+cX1) div 2) then begin
      if(curAddPoint.Y<(cY2+cY1) div 2) then AddPoint(Tree.child1,depth+1,cX1,(cX2+cX1) div 2,cY1,(cY2+cY1) div 2)
      else AddPoint(Tree.child3,depth+1,cX1,(cX2+cX1) div 2,(cY2+cY1) div 2+1,cY2);
    end else begin
      if(curAddPoint.Y<(cY2+cY1) div 2) then AddPoint(Tree.child2,depth+1,(cX2+cX1) div 2+1,cX2,cY1,(cY2+cY1) div 2)
      else AddPoint(Tree.child4,depth+1,(cX2+cX1) div 2+1,cX2,(cY2+cY1) div 2+1,cY2);
    end;
  end;
  SetLength(Tree.Points,0);
  curAddPoint:=savePt;
  if(curAddPoint.X<(cX2+cX1) div 2) then begin
    if(curAddPoint.Y<(cY2+cY1) div 2) then AddPoint(Tree.child1,depth+1,cX1,(cX2+cX1) div 2,cY1,(cY2+cY1) div 2)
    else AddPoint(Tree.child3,depth+1,cX1,(cX2+cX1) div 2,(cY2+cY1) div 2+1,cY2);
  end else begin
    if(curAddPoint.Y<(cY2+cY1) div 2) then AddPoint(Tree.child2,depth+1,(cX2+cX1) div 2+1,cX2,cY1,(cY2+cY1) div 2)
    else AddPoint(Tree.child4,depth+1,(cX2+cX1) div 2+1,cX2,(cY2+cY1) div 2+1,cY2);
  end;
end;