unit QtreeC;
//*******************************************************
// Quadtree class.
//*******************************************************
// Copyright (C) 1998 John Wiley & Sons, Inc.
// All rights reserved. See additional copyright
// information in Readme.txt.
//*******************************************************

interface

uses
    Windows, Graphics, Classes;

const MAX_QTREE_NODES = 100;

type
    NorthOrSouth = (North, South);
    EastOrWest = (East, West);
    TPointArray = array[1..MAX_QTREE_NODES] of TPoint;
    PPointArray = ^TPointArray;
    TQtreeNode = class(TObject)
        private
        public
            Children               : array [NorthOrSouth, EastOrWest] of TQtreeNode;
            Xmin, Xmax, Ymin, Ymax : Integer;
            Pts                    : PPointArray;
            NumPts                 : Integer;

            constructor Create(x_min, x_max, y_min, y_max : Integer);
            destructor Destroy; override;
            procedure AddPoint(X, Y : Integer);
            procedure Draw(cvs : TCanvas);
            procedure FindPoint(var X, Y : Integer; var comp : Longint);
            function LocateLeaf(X, Y : Integer) : TQtreeNode;
            procedure NearPointInLeaf(X, Y : Integer; var best_i, best_dist2 : Integer; var comp : Longint);
            procedure CheckNearbyLeaves(exclude : TQtreeNode; var best_leaf : TQtreeNode; X, Y : Integer; var best_i, best_dist2 : Integer; var comp : Longint);
    end;

implementation

// Create and initialize the node.
constructor TQtreeNode.Create(x_min, x_max, y_min, y_max : Integer);
begin
    inherited Create;
    Xmin := x_min;
    Xmax := x_max;
    Ymin := y_min;
    Ymax := y_max;

    // Allocate space for the points.
    GetMem(Pts, MAX_QTREE_NODES * SizeOf(TPoint));
end;

// Free all children.
destructor TQtreeNode.Destroy;
var
    ns : NorthOrSouth;
    ew : EastOrWest;
begin
    // If we have no children, free the point memory.
    if (Children[North, West] = nil) then
        FreeMem(Pts)
    else begin
        // Otherwise free the children.
        for ns := North to South do
            for ew := East to West do
                Children[ns, ew].Free;
    end;

    inherited Destroy;
end;

procedure TQtreeNode.AddPoint(X, Y : Integer);
var
    xmid, ymid, i : Integer;
    ns            : NorthOrSouth;
    ew            : EastOrWest;
begin
    // See if the node belongs in a child.
    if (NumPts >= MAX_QTREE_NODES) then
    begin
        xmid := (xmin + xmax) div 2;
        ymid := (ymin + ymax) div 2;

        // See if we need to create new children.
        if (Children[North, West] = nil) then
        begin
            // Split the node into four children.
            Children[North, West] := TQtreeNode.Create(Xmin, xmid, Ymin, ymid);
            Children[North, East] := TQtreeNode.Create(xmid, Xmax, Ymin, ymid);
            Children[South, West] := TQtreeNode.Create(Xmin, xmid, ymid, Ymax);
            Children[South, East] := TQtreeNode.Create(xmid, Xmax, ymid, Ymax);

            // Move the old points into the new children.
            for i := 1 to NumPts do
            begin
                if (Pts^[i].Y <= ymid) then
                    ns := North
                else
                    ns := South;
                if (Pts^[i].X <= xmid) then
                    ew := West
                else
                    ew := East;
                Children[ns, ew].AddPoint(
                    Pts^[i].X, Pts^[i].Y);
            end; // End moving points to the new children.
            // Note that we do not reset NumPts so later
            // points are also placed in the children.

            // Free point memory.
            FreeMem(Pts);
        end; // End creating new children.

        // Add the point to the correct child.
        if (Y <= ymid) then
            ns := North
        else
            ns := South;
        if (X <= xmid) then
            ew := West
        else
            ew := East;
        Children[ns, ew].AddPoint(X, Y);

        // We are done.
        exit;
    end;

    // Place the point in this node.
    NumPts := NumPts + 1;
    Pts^[NumPts].X := X;
    Pts^[NumPts].Y := Y;
end;

// Draw the node's outline.
procedure TQtreeNode.Draw(cvs : TCanvas);
begin
    cvs.MoveTo(Xmin, Ymin);
    cvs.LineTo(Xmax, Ymin);
    cvs.LineTo(Xmax, Ymax);
    cvs.LineTo(Xmin, Ymax);
    cvs.LineTo(Xmin, Ymin);
    if (Children[North, West] <> nil) then
    begin
        Children[North, West].Draw(cvs);
        Children[North, East].Draw(cvs);
        Children[South, West].Draw(cvs);
        Children[South, East].Draw(cvs);
    end;
end;

// Find the point closest to the given coordinates.
procedure TQtreeNode.FindPoint(var X, Y : Integer; var comp : Longint);
var
    best_dist2, best_i     : Integer;
    leaf                   : TQtreeNode;
begin
    // See which leaf contains the point.
    leaf := LocateLeaf(X, Y);

    // Find the closest point within the leaf.
    comp := 0;
    leaf.NearPointInLeaf(X, Y, best_i, best_dist2, comp);

    // Check nearby leaves for closer points.
    CheckNearbyLeaves(leaf, leaf, X, Y, best_i, best_dist2, comp);

    X := leaf.Pts^[best_i].X;
    Y := leaf.Pts^[best_i].Y;
end;

// See what leaf contains the point.
function TQtreeNode.LocateLeaf(X, Y : Integer) : TQtreeNode;
var
    xmid, ymid : Integer;
    ns         : NorthOrSouth;
    ew         : EastOrWest;
begin
    if (Children[North, West] = nil) then
    begin
        // This node has no children. It must be the node.
        Result := Self;
        exit;
    end;

    // Search the appropriate child.
    xmid := (Xmax + Xmin) div 2;
    ymid := (Ymax + Ymin) div 2;
    if (Y <= ymid) then
        ns := North
    else
        ns := South;
    if (X <= xmid) then
        ew := West
    else
        ew := East;

    Result := Children[ns, ew].LocateLeaf(X, Y);
end;

// Return the index of the point closest to the given
// coordinates in this leaf.
procedure TQtreeNode.NearPointInLeaf(X, Y : Integer; var best_i, best_dist2 : Integer; var comp : Longint);
var
    i             : Longint;
    dist2, dx, dy : Integer;
begin
    // If there are no points in the node, do nothing.
    best_dist2 := 32767;
    best_i := 0;

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

// Check nearby leaves to see if there is a better point.
procedure TQtreeNode.CheckNearbyLeaves(exclude : TQtreeNode; var best_leaf : TQtreeNode; X, Y : Integer; var best_i, best_dist2 : Integer; var comp : Longint);
var
    xmid, ymid, i, dist2, best_dist : Integer;
begin
    // If we are excluding this leaf, do nothing.
    if (exclude = Self) then exit;

    // If this is a leaf node, look for close nodes.
    if (Children[North, West] = nil) then
    begin
        NearPointInLeaf(X, Y, i, dist2, comp);
        if (best_dist2 > dist2) then
        begin
            best_dist2 := dist2;
            best_leaf := Self;
            best_i := i;
        end;
    end else begin
        // Examine children that lie within best_dist
        // of the point.
        xmid := (Xmax + Xmin) div 2;
        ymid := (Ymax + Ymin) div 2;
        best_dist := Round(Sqrt(best_dist2) + 0.5);
        if (X - best_dist <= xmid) then
        begin
            // The West children may be close enough.
            // See if the NorthWest child is close enough.
            if (Y - best_dist <= ymid) Then
                Children[North, West].CheckNearbyLeaves(
                    exclude, best_leaf, X, Y, best_i,
                    best_dist2, comp);

            // See if the SouthWest child is close enough.
            if (Y + best_dist > ymid) Then
                Children[South, West].CheckNearbyLeaves(
                    exclude, best_leaf, X, Y, best_i,
                    best_dist2, comp);
        end; // End the West children may be close enough.

        if (X + best_dist > xmid) then
        begin
            // The East children may be close enough.
            // See if the NorthEast child is close enough.
            if (Y - best_dist <= ymid) Then
                Children[North, East].CheckNearbyLeaves(
                    exclude, best_leaf, X, Y, best_i,
                    best_dist2, comp);

            // See if the SouthEast child is close enough.
            if (Y + best_dist > ymid) Then
                Children[South, East].CheckNearbyLeaves(
                    exclude, best_leaf, X, Y, best_i,
                    best_dist2, comp);
        end; // End the East children may be close enough.
    end; // End if a leaf ... else check children ...
end;

end.
