Class TQtreeNode

DescriptionHierarchyFieldsMethodsProperties

Unit

QuadTreeClass

Declaration

type TQtreeNode = class(TObject)

Description

TQtreeNode does the most of the real work of a TRbwQuadTree.

Hierarchy

Overview

Fields

Private FNumPts: Integer;
Protected FChildren: array[TNorthOrSouth, TEastOrWest] of TQtreeNode;
Protected FParent: TQtreeNode;
Protected FPts: array of TQPoint;
Protected FTree: TRbwQuadTree;
Protected FXmax: double;
Protected FXmin: double;
Protected FYmax: double;
Protected FYmin: double;

Methods

Private procedure FindNearestPoints(const CenterX, CenterY: double; const Count: Integer; const List: TObjectList);
Private function GetPoints(Index: Integer): TQPoint;
Private procedure ResetCount;
Private procedure SetNumPts(const Value: Integer);
Protected procedure AddPoint(X, Y: double; Data: pointer);
Protected procedure CheckNearbyLeaves(const exclude: TQtreeNode; var best_leaf: TQtreeNode; const X, Y: double; var best_i: integer; var best_dist2, best_dist: double);
Protected procedure Clear;
Protected constructor Create(ATree: TRbwQuadTree); overload;
Protected constructor Create(const x_min, x_max, y_min, y_max: double; const ParentNode: TQtreeNode; ATree: TRbwQuadTree); overload;
Protected procedure ExpandBounds(XY: double; ExpandDirection: TExpandDirection);
Protected function FindClosestPoint(const X, Y: double): TQPoint;
Protected procedure FindClosestPointsData(var X, Y: double; var Data: TPointerArray);
Protected procedure FindPoint(var X, Y: double; var Data: pointer);
Protected procedure FindPointsInBlock(const Block: T2DBlock; const List: TList);
Protected procedure FindPointsInCircle(const CenterX, CenterY, Radius, RadiusSquared: double; const List: TList);
Protected function LocateLeaf(const X, Y: double; const Siblings: TStack): TQtreeNode;
Protected procedure NearPointInLeaf(const X, Y: double; out best_i: integer; out best_dist2: double);
Protected function RemovePoint(const X, Y: double; const Data: pointer): boolean;
Protected function Xmid: double;
Protected function Ymid: double;
Public destructor Destroy; override;

Properties

Protected property NumPts: Integer read FNumPts write SetNumPts;
Protected property Points[Index:Integer]: TQPoint read GetPoints;

Description

Fields

Private FNumPts: Integer; 

FNumPts: Integer;

FNumPts is the number of locations stored by this TQtreeNode or its children. See NumPts.

Protected FChildren: array[TNorthOrSouth, TEastOrWest] of TQtreeNode;

FChildren: array [TNorthOrSouth, TEastOrWest] of TQtreeNode; If NumPts <= FTree.MaxPoints, then FChildren will normally contain all nil values and the data in the TQtreeNode will be stored in FPts. Otherwise, FChildren will have all instances of TQtreeNode and they will hold the data.

Protected FParent: TQtreeNode; 

FParent : TQtreeNode;

FParent is the TQtreeNode (if one exists) that has the current instance in FChildren.

Protected FPts: array of TQPoint;

longcode(#FPts: array of TQPoint;#) If NumPts <= FTree.MaxPoints, then the data in the TQtreeNode will be stored in FPts. See FChildren.

Protected FTree: TRbwQuadTree; 

FTree: TRbwQuadTree;

FTree is the TRbwQuadTree that is the ultimate root for the current TQtreeNode.

Protected FXmax: double; 

FXmax : double;

FXmax is the largest X coordinate that should be stored in this TQtreeNode. However, see ExpandBounds.

Protected FXmin: double; 

FXmin : double;

FXmin is the smallest X coordinate that should be stored in this TQtreeNode. However, see ExpandBounds.

Protected FYmax: double; 

FYmax : double;

FYmax is the largest Y coordinate that should be stored in this TQtreeNode. However, see ExpandBounds.

Protected FYmin: double; 

FYmin : double;

FYmin is the smallest Y coordinate that should be stored in this TQtreeNode. However, see ExpandBounds.

Methods

Private procedure FindNearestPoints(const CenterX, CenterY: double; const Count: Integer; const List: TObjectList);

FindNearestPoints finds the Count nearest locations to the location (CenterX, CenterY) and store TSelectNodes representing those locations in List. (TSelectNode is defined in the implementation section.) The number of objects in List may be greater then Count because several points may be the same distance from (CenterX, CenterY).

Private function GetPoints(Index: Integer): TQPoint;

See Points.

Private procedure ResetCount;

If a TQtreeNode has children, ResetCount sets NumPts to the sum of its childrens' NumPts.

Private procedure SetNumPts(const Value: Integer);

See NumPts. SetNumPts may free child nodes if Value < FTree.MaxPoints

Protected procedure AddPoint(X, Y: double; Data: pointer);

AddPoint adds the location (X,Y) and it associated data to the data stored by this TQtreeNode.

Protected procedure CheckNearbyLeaves(const exclude: TQtreeNode; var best_leaf: TQtreeNode; const X, Y: double; var best_i: integer; var best_dist2, best_dist: double);

CheckNearbyLeaves is used when searching for the closest points to X, Y. If exclude is self, the procedure immediately exits. This prevents infinite recursion. Best_leaf is changed to the TQtreeNode that contains the closest point to X, Y. Best_i is changed to the index of the data point in best_leaf that contains the closest point to X, Y. Best_dist is the distance from X, Y to the closest point in best_leaf. Best_dist2 is best_dist squared.

Protected procedure Clear;

Clear removes all the data stored by this TQtreeNode. Members of FChildren, if any, will be freed.

Protected constructor Create(ATree: TRbwQuadTree); overload;

Create creates an instance of TQtreeNode

Protected constructor Create(const x_min, x_max, y_min, y_max: double; const ParentNode: TQtreeNode; ATree: TRbwQuadTree); overload;

Create creates an instance of TQtreeNode and sets FXmax, FXmin, FYmax, and FYmin.

Protected procedure ExpandBounds(XY: double; ExpandDirection: TExpandDirection);

ExpandBounds is used to expand the range of X and Y coordinates that can be stored in this TQtreeNode and its children. See FXmax, FXmin, FYmax, and FYmin.

Protected function FindClosestPoint(const X, Y: double): TQPoint;

FindClosestPoint returns a TQPoint that has the X,Y, locations and data in the point closest to the value specified for X and Y. the TQPoint is owned by a TQtreeNode.

Protected procedure FindClosestPointsData(var X, Y: double; var Data: TPointerArray);

FindClosestPointsData, sets X and Y to the closest location to the original X, Y and sets Data to hold the data at that location.

Protected procedure FindPoint(var X, Y: double; var Data: pointer);

FindPoint sets X and Y to the closest location in the TQtreeNode to the original (X, Y) and sets Data to the first data at that location.

Protected procedure FindPointsInBlock(const Block: T2DBlock; const List: TList);

FindPointsInBlock, fills List with PQPoint that point to locations within Block.

Protected procedure FindPointsInCircle(const CenterX, CenterY, Radius, RadiusSquared: double; const List: TList);

FindPointsInCircle, fills List with PQPoints that point to locations within the circle defined by CenterX, CenterY, and Radius.

Protected function LocateLeaf(const X, Y: double; const Siblings: TStack): TQtreeNode;

LocateLeaf returns the TQtreeNode that contains the location (X,Y). Siblings is filled with other TQtreeNode that are siblings of the one found or its ancestors.

Protected procedure NearPointInLeaf(const X, Y: double; out best_i: integer; out best_dist2: double);

NearPointInLeaf sets best_i to indicate the point closest to (X,Y) in this leaf. best_dist2 is set to the square of the distance to that point.

Protected function RemovePoint(const X, Y: double; const Data: pointer): boolean;

RemovePoint removes Data at location (X,Y). If this is the only data at that point, it also removes the point.

Protected function Xmid: double;

Xmid is the location in the X coordinate direction at which the where eastern children meet the western children. If no children exist, it is the middle of the node in the X direction.

Protected function Ymid: double;

Ymid is the location in the Y coordinate direction at which the where northern children meet the southern children. If no children exist, it is the middle of the node in the Y direction.

Public destructor Destroy; override;

Destroy destroys the current instance of TQtreeNode and its children. Do not call Destroy directly. Call Free instead.

Properties

Protected property NumPts: Integer read FNumPts write SetNumPts;

NumPts is the number of locations stored by this TQtreeNode.

Protected property Points[Index:Integer]: TQPoint read GetPoints;

Points returns the TQPoint designated by Index. The TQPoint may be stored either in this TQtreeNode or its children.

Generated by PasDoc 0.12.1 on 2013-05-13 15:41:58