program new;

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;



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;


(*
 Recurse down the tree, and print element - will fail if somthing that is not nil should be nil.
*)
procedure PrintTree(Tree: PTreeData; Depth:Integer=-1; Side:String=' [root]');
var
  str: String;
  i: Integer;
begin
  for i:=0 to depth+depth do
    Str := Str + '-';
  Str := Str + ' ';

  WriteLn(Str, '(', Tree^.Split.x, ', ', Tree^.Split.y, ')', side);
  if Tree^.L <> nil then
    PrintTree(Tree^.L, Depth+1, ' [left]');
  if Tree^.R <> nil then
  PrintTree(Tree^.R, Depth+1, ' [right]');
end;


(*
 Recurse down the tree, will fail if somthing that is not nil should be nil.
*)
procedure RecurseTree(Tree: PTreeData; Depth:Integer=0);
begin
  if Tree^.L <> nil then
    RecurseTree(Tree^.L, Depth+1);
  if Tree^.R <> nil then
    RecurseTree(Tree^.R, Depth+1);
end;



(*
 Simple random tpa, with some extra parameters compared to what SCAR offers.
*)
function RandomTPA(Amount:Integer; MinX,MinY,MaxX,MaxY:Integer): TPointArray; //StdCall;
var i:Integer;
begin
  SetLength(Result, Amount);
  for i:=0 to Amount-1 do
    Result[i] := Point(RandomRange(MinX, MaxX), RandomRange(MinY, MaxY));
end;


var
  TPA:TPointArray;
  PTree: PTreeData;
  Tree: T2DTree;
  t,i:Integer;
begin
  TPA := RandomTPA(5000,0,0,500,500);
  PTree := PointTree(Tree, TPA);

  RecurseTree(PTree);
end.