unit QtreeF;
//*******************************************************
// Example program demonstrating quadtrees.
//*******************************************************
// Copyright (C) 1998 John Wiley & Sons, Inc.
// All rights reserved. See additional copyright
// information in Readme.txt.
//*******************************************************

interface

uses
  Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
  QtreeC, Menus, StdCtrls, ExtCtrls;

type
  TPointArray = array[1..100000000] of TPoint;
  PPointArray = ^TPointArray;

  TQtreeForm = class(TForm)
    MainMenu1: TMainMenu;
    mnuExit: TMenuItem;
    Help1: TMenuItem;
    mnuAbout: TMenuItem;
    Exit1: TMenuItem;
    Quadtree1: TMenuItem;
    mnuUseQuadtree: TMenuItem;
    Label1: TLabel;
    ComparisonsLabel: TLabel;
    QtreeImage: TImage;
    procedure FormCreate(Sender: TObject);
    procedure DrawPoints;
    procedure Exit1Click(Sender: TObject);
    procedure mnuAboutClick(Sender: TObject);
    procedure mnuUseQuadtreeClick(Sender: TObject);
    procedure FormMouseUp(Sender: TObject; Button: TMouseButton;
      Shift: TShiftState; X, Y: Integer);
    procedure FindPoint(var X, Y : Integer; var comp : Longint);
    procedure HighlightPoint(X, Y: Integer);
  private
    { Private declarations }
  public
    { Public declarations }
    qtree_root : TQtreeNode;
    hi_x, hi_y : Integer;
  end;

var
  QtreeForm: TQtreeForm;

implementation

{$R *.DFM}

var
    num_points : Longint;
    points     : PPointArray;

// Initialize the quadtree.
procedure TQtreeForm.FormCreate(Sender: TObject);
const
    a = 2.24;
    b = 0.43;
    c = -0.65;
    d = -2.43;
    e = 1;
    X_MAX = 2;
    X_MIN = -2;
    Y_MAX = 2;
    Y_MIN = -2;
var
    txt                         : String;
    i                           : Longint;
    Dx, Dy, xtmp, ytmp, X, Y, Z : Single;
begin
    // See how many points we should create.
    txt := '10000';
    if (not InputQuery('Number of Items',
        'Number of points to create', txt)) then
    begin
        Application.Terminate;
        exit;
    end;

    // Create an array of points. Create the quadtree and
    // fill it with the points.
    num_points := StrToInt(txt);
    GetMem(Points, num_points * SizeOf(TPoint));
    qtree_root := TQtreeNode.Create(
        0, QtreeImage.ClientWidth - 1,
        0, QtreeImage.ClientHeight - 1);

    Dx := QtreeImage.ClientWidth / (X_MAX - X_MIN);
    Dy := QtreeImage.ClientHeight / (Y_MAX - Y_MIN);

    X := 0;
    Y := 0;
    Z := 0;
    for i := 1 to num_points do
    begin
        xtmp := Sin(a * Y) - Z * Cos(b * X);
        ytmp := Z * Sin(c * X) - Cos(d * Y);
        Z := e * Sin(X);
        X := xtmp;
        Y := ytmp;

        points^[i].X := Round((X - X_MIN) * Dx);
        points^[i].Y := Round((Y - Y_MIN) * Dy);

        qtree_root.AddPoint(points^[i].X, points^[i].Y);
    end; // End for i := 1 to num_points do...

    // Start with no point selected.
    hi_x := -1;

    // Display the points.
    DrawPoints;
end;

// Draw the quadtree.
procedure TQtreeForm.DrawPoints;
var
    i    : Longint;
    rect : TRect;
begin
    // Erase the canvas.
    rect.Left := 0;
    rect.Right := QtreeImage.ClientWidth;
    rect.Top := 0;
    rect.Bottom := QtreeImage.ClientHeight;
    QtreeImage.Canvas.Brush.Color := clLtGray;
    QtreeImage.Canvas.FillRect(rect);

    // Draw the points.
    for i := 1 to num_points do
    begin
        QtreeImage.Canvas.Pixels[points[i].X, points[i].Y] := clBlack;
    end;

    // If the quadtree is enabled, draw it.
    if (mnuUseQuadtree.Checked) then
        qtree_root.Draw(QtreeImage.Canvas);

    // Rehighlight the selected point.
    HighlightPoint(hi_x, hi_y);
end;

// End the program.
procedure TQtreeForm.Exit1Click(Sender: TObject);
begin
    Close;
end;

procedure TQtreeForm.mnuAboutClick(Sender: TObject);
const
    CRCR = #13#10#13#10;
begin
    MessageDlg(
        'This program demonstrates a quadtree.' + CRCR +
        'Click on the form and the program will locate the closest point.' + CRCR +
        'Use the Quadtree menu to enable and disable the quadtree.'
        , mtInformation, [mbOK], 0);
end;

// Toggle quadtree use and redraw.
procedure TQtreeForm.mnuUseQuadtreeClick(Sender: TObject);
begin
    mnuUseQuadtree.Checked := (not mnuUseQuadtree.Checked);
    hi_x := -1; // Unselect the highlighted point.
    DrawPoints;
end;

procedure TQtreeForm.FormMouseUp(Sender: TObject; Button: TMouseButton;
  Shift: TShiftState; X, Y: Integer);
var
    comp : Longint;
begin
    if (mnuUseQuadtree.Checked) then
        qtree_root.FindPoint(X, Y, comp)
    else
        FindPoint(X, Y, comp);

    // Highlight the point.
    HighlightPoint(X, Y);
    ComparisonsLabel.Caption := IntToStr(comp);
end;

// Find the closest point exhaustively.
procedure TQtreeForm.FindPoint(var X, Y : Integer; var comp : Longint);
var
    i, best_i                 : Longint;
    dist2, best_dist2, dx, dy : Integer;
begin
    dx := X - points^[1].X;
    dy := Y - points^[1].Y;
    best_dist2 := dx * dx + dy * dy;
    best_i := 1;

    for i := 2 to num_points do
    begin
        dx := X - points^[i].X;
        dy := Y - points^[i].Y;
        dist2 := dx * dx + dy * dy;
        if (best_dist2 > dist2) then
        begin
            best_i := i;
            best_dist2 := dist2;
        end;
    end;
    X := points^[best_i].X;
    Y := points^[best_i].Y;

    comp := num_points;
end;

// Highlight the point.
procedure TQtreeForm.HighlightPoint(X, Y: Integer);
begin
    QtreeImage.Canvas.Pen.Mode := pmNot;

    // Unhighlight the old point.
    if (hi_x >= 0) then
    begin
        QtreeImage.Canvas.MoveTo(hi_x - 2, hi_y - 2);
        QtreeImage.Canvas.LineTo(hi_x + 2, hi_y - 2);
        QtreeImage.Canvas.LineTo(hi_x + 2, hi_y + 2);
        QtreeImage.Canvas.LineTo(hi_x - 2, hi_y + 2);
        QtreeImage.Canvas.LineTo(hi_x - 2, hi_y - 2);
    end;

    // Highlight the new point.
    hi_x := X;
    hi_y := Y;
    if (hi_x >= 0) then
    begin
        QtreeImage.Canvas.MoveTo(hi_x - 2, hi_y - 2);
        QtreeImage.Canvas.LineTo(hi_x + 2, hi_y - 2);
        QtreeImage.Canvas.LineTo(hi_x + 2, hi_y + 2);
        QtreeImage.Canvas.LineTo(hi_x - 2, hi_y + 2);
        QtreeImage.Canvas.LineTo(hi_x - 2, hi_y - 2);
    end;

    QtreeImage.Canvas.Pen.Mode := pmCopy;
end;

end.
