type
  PTreeData = ^TTreeData;
  TTreeData = record
    Split: TPoint;
    L, R : PTreeData;
  end;

  T2DTree = Array of TTreeData;

  TInfoPoint = record
    Dist:Single;
    PT:  TPoint;
  end;


function TPointArray.Slice(Left, Right:Integer): TPointArray;
var i:Integer;
begin
  SetLength(Result, Right-Left);
  for i:=Left to Right-1 do
    Result[i-left] := Self[i];
end;


//Based on KDTree base, but only to work with 2D trees.
function PointTree(var Nodes: T2DTree; TPA:TPointArray; depth:Integer=0): PTreeData;
var
  hi,mid: Integer;
  TMP: TTreeData;
begin
  hi := Length(TPA);
  if (hi=0) then
    Exit(nil);

  case (depth mod 2 = 0) and True of
    True : SortTPAByX(TPA, False);
    False: SortTPAByY(TPA, False);
  end;

  mid := hi div 2;
  TMP := [
    {split} TPA[mid],
    {left } PointTree(Nodes, TPA.Slice(0, mid),   depth+1),
    {right} PointTree(Nodes, TPA.Slice(mid+1,hi), depth+1)
  ];

  hi := Length(Nodes);
  SetLength(Nodes, hi+1);
  Nodes[hi] := TMP;

  Result := @Nodes[hi];
end;