Class TLazQuadTree

Unit

Declaration

type TLazQuadTree = class(TObject)

Description

TLazQuadTree A QuadTree for Lazarus. Organizes arbitrary Items who are ordered on a plane by X and Y coordinates for a fast access for a given Rect. The TLazQuadTree could be used to store tenthousands of items and access them very fast, because items that are not within the desired Rect are sorted out quickly. To allow the processing of any kind of objects or data, an event is used where the user has to provide the location or Rect of a specific item in the tree. The tree could be used for a flat world with borders on all four edges or a cylindric world, where the right and left edge are connected. Additionally the orientation of the Y-Axis could be adjusted, to cover cartesian-coordinate-systems (like Maps or mathematical function diagrams, where the Y value increases when going upwards) or computer-coordinate-system (like Bitmaps or Editors, where the Y increases when going downwards). To aggregate data on smaller magnification (e.g. showing bigger parts of the plane) a sum of TotalItems in the (Sub-)Nodes is maintained. This allowes, instead of a search of a bunch of unusefull Items, the display of a Placeholder/Sum of the items which are hidden.

Hierarchy

Overview

Methods

Protected function GetWorldRect: TLQTRect; virtual;
Protected function InternalCreateNode(const AParentNode : TLQTNode; const ALQTRect : TLQTRect; const ANodeToken : Cardinal = 0) : TLQTNode; virtual;
Protected function InternalEnumerateNodesInRect( const ANode : TLQTNode; const AUnwrappedRect : TLQTRect; const AEnumCallBackFunc : TLQTNodeEnumerationCallBack; const AUserData : Pointer) : Boolean; virtual;
Protected function InternalEnumerateItemsInRect( const ANode : TLQTNode; const AUnwrappedRect : TLQTRect; const AEnumCallBackFunc : TLQTItemEnumerationCallBack; const AUserData : Pointer) : Boolean; virtual;
Protected function InternalEnumerateItemsInParentNodes( const ANode : TLQTNode; const AUnwrappedRect : TLQTRect; const AEnumCallBackFunc : TLQTItemEnumerationCallBack; const AUserData : Pointer) : Boolean; virtual;
Protected function InternalCountNodesInRect(const ANode : TLQTNode; const AUnwrappedRect : TLQTRect) : Integer; virtual;
Protected function InternalCountAssignedNodeItemsInRect(const ANode : TLQTNode; const AUnwrappedRect : TLQTRect) : Integer; virtual;
Protected function InternalEstimatedCountOfAssignedItemsInRect(const ANode : TLQTNode; const AUnwrappedRect : TLQTRect; const AItemThreshold : Integer) : Double; virtual;
Protected function DoGetItemCoord(AItem : TObject; var AX, AY : Double) : Boolean; virtual;
Protected function DoGetItemRect(AItem : TObject; var AItemRect : TLQTRect) : Boolean; virtual;
Protected function DoGetItemCaption(AItem : TObject; var AItemCaption : String) : Boolean; virtual;
Protected function TreeItemToListEnumerationCallBack(Sender : TObject; ANode : TLQTNode; ANodeItem : TObject; ANodeItemIndex : Integer; AUserData : Pointer) : Boolean; virtual;
Protected function TreeNodeToListEnumerationCallBack(Sender : TObject; ANode : TLQTNode; AUserData : Pointer) : Boolean; virtual;
Protected procedure WriteFileStreamStart(const AStream : TStream); virtual;
Protected procedure WriteStreamTreeHeader(const AStream : TStream; const AQuadTreeStreamDataVersion : Cardinal); virtual;
Protected procedure WriteStreamTreeProperties(const AStream : TStream; const AQuadTreeStreamDataVersion : Cardinal); virtual;
Protected procedure WriteStreamTreeRootNode(const AStream : TStream; const AQuadTreeStreamDataVersion : Cardinal); virtual;
Protected procedure ReadFileStreamStart(const AStream : TStream); virtual;
Protected procedure ReadStreamTreeHeader(const AStream : TStream; out AQuadTreeStreamDataVersion : Cardinal); virtual;
Protected procedure ReadStreamTreeProperties(const AStream : TStream; const AQuadTreeStreamDataVersion : Cardinal); virtual;
Protected procedure ReadStreamTreeRootNode(const AStream : TStream; const AQuadTreeStreamDataVersion : Cardinal); virtual;
Protected function GetOccupiedRect: TLQTRect; virtual;
Protected function GetActualNodeRect(const ANode : TLQTNode) : TLQTRect; virtual;
Protected function GetActualNodeRectAsTetragonCorners(ANode : TLQTNode; Index : Integer) : TLQTPoint; virtual;
Protected function GetActualOccupiedRect(const ANode : TLQTNode) : TLQTRect; virtual;
Protected function GetActualOccupiedRectAsTetragonCorners(ANode : TLQTNode; Index : Integer) : TLQTPoint; virtual;
Public function InsertItem(const AItem : TObject; const APointValid : Boolean = False; const ARectValid : Boolean = False; const APointX : Double = 0.0; const APointY : Double = 0.0; const ARectLeft : Double = 0.0; const ARectTop : Double = 0.0; const ARectRight : Double = 0.0; const ARectBottom : Double = 0.0 ) : TLQTNode; virtual;
Public function ExtractItem(const AItem : TObject) : TObject; virtual;
Public function MoveItemAfterCoordChange(const AItem : TObject) : TLQTNode; virtual;
Public procedure GetActualNodeTetragon(const ANode : TLQTNode; out AActualBoundingtTetragon : TLQTPointArr);
Public function FindRectNode(const ALQTRect : TLQTRect) : TLQTNode; virtual;
Public function FindCoordNode(const AX, AY : Double) : TLQTNode; virtual;
Public function FindItemNode(const AItem : TObject) : TLQTNode; virtual;
Public function EnumerateNodesInRect(const ALQTRect : TLQTRect; const AEnumCallBackFunc : TLQTNodeEnumerationCallBack; const AUserData : Pointer = Nil) : Boolean; virtual;
Public procedure ListNodesInRect(const ALQTRect : TLQTRect; const AList : TList); virtual;
Public function CountNodesInRect(const ALQTRect : TLQTRect) : Integer; virtual;
Public function EnumerateItemsInRect(const ALQTRect : TLQTRect; const AEnumCallBackFunc : TLQTItemEnumerationCallBack; const AUserData : Pointer = Nil) : Boolean; virtual;
Public procedure ListItemsInRect(const ALQTRect : TLQTRect; const AList : TList); virtual;
Public function CountAssignedItemsInRect(const ALQTRect : TLQTRect) : Integer; virtual;
Public function EstimatedCountOfAssignedItemsInRect(const ALQTRect : TLQTRect; const AItemThreshold : Integer) : Double; virtual;
Public function AgglomerateNodeAsEnumeration( const ANode : TLQTNode; const AAgglomerationDepth : Integer; const AMinimumItemNumberInAgglomeration : Integer; const AItemEnumFunc : TLQTItemEnumerationCallBack; const AItemUserData : Pointer; const AAgglomerationEnumFunc : TLQTAgglomerationEnumerationCallBack; const AAgglomerationUserData : Pointer) : Boolean; virtual;
Public procedure AgglomerateNodeAsList(const ANode : TLQTNode; const AAgglomerationDepth: Integer; const AMinimumItemNumberInAgglomeration: Integer; var AAgglomerationArray: TLQTAgglomerationArray; const AItemList: TList);
Public procedure TreeAsStrings(const AStrings : TStrings); virtual;
Public procedure ListTreeNodes(const AList : TList); virtual;
Public procedure ListSubNodes(const ANode : TLQTNode; const AList : TList); virtual;
Public function CountTreeNodes: Integer;
Public function CountNodes(const ANode : TLQTNode) : Integer; virtual;
Public function EnumerateItemsInSubNodes(const ANode : TLQTNode; const AEnumCallBackFunc : TLQTItemEnumerationCallBack; const AUserData : Pointer = Nil) : Boolean; virtual;
Public procedure ListItemsInSubNodes(const ANode : TLQTNode; const AList : TList); virtual;
Public function EnumerateItemsInParentNodes(const ANode : TLQTNode; const AEnumCallBackFunc : TLQTItemEnumerationCallBack; const AUserData : Pointer = Nil) : Boolean; virtual;
Public procedure ListItemsInParentNodes(const ANode : TLQTNode; const AItemList : TList); virtual;
Public function NextNode(const AStartNode : TLQTNode = Nil) : TLQTNode;
Public function NextItem(out ANextItem : TObject; out ANextItemNode : TLQTNode; const AStartItem : TObject = Nil; const AStartItemNode : TLQTNode = Nil) : Boolean;
Public procedure RecountTotalNodeItems; virtual;
Public procedure RebuildOccupiedRect; virtual;
Public procedure Clear; virtual;
Public procedure BeginUpdate;
Public procedure EndUpdate;
Public procedure WriteTreeToStream(const AStream : TStream); virtual;
Public procedure ReadTreeFromStream(const AStream : TStream; const AStreamReadOptions : Cardinal = 0); virtual;
Public procedure WriteTreeToFile(const AFileName : String); virtual;
Public procedure ReadTreeFromFile(const AFileName : String; const AStreamReadOptions : Cardinal = 0); virtual;
Public constructor Create(const AWorldRect : TLQTRect; const AWorldModel : TLQTWorldModel; const AFreeObjects: Boolean = False; const AQuadTreeCreateQuadNodeEvent : TLQTCreateNodeEvent = Nil);
Public destructor Destroy; override;

Properties

Public property WorldModel : TLQTWorldModel read FWorldModel;
Public property WorldRect : TLQTRect read GetWorldRect;
Public property WorldXAxisLeftPlus : Boolean read GetWorldXAxisLeftPlus;
Public property WorldYAxisUpPlus : Boolean read GetWorldYAxisUpPlus;
Public property OwnsObjects: Boolean read FOwnsObjects write FOwnsObjects;
Public property RootNode : TLQTNode read FRootNode;
Public property MaxNodeItemCount : Integer read FMaxNodeItemCount write FMaxNodeItemCount;
Public property MaxTreeLevel : Integer read FMaxTreeLevel write FMaxTreeLevel default DefaultMaxTreeLevel;
Public property TreeToken : Cardinal read FTreeToken;
Public property OccupiedRect : TLQTRect read GetOccupiedRect;
Public property ActualNodeRect[Index:TLQTNode]: TLQTRect read GetActualNodeRect;
Public property ActualNodeRectAsTetragonCorners[ANode:TLQTNode;Index:Integer]: TLQTPoint read GetActualNodeRectAsTetragonCorners;
Public property ActualOccupiedRect[Index:TLQTNode]: TLQTRect read GetActualOccupiedRect;
Public property ActualOccupiedRectAsTetragonCorners[ANode:TLQTNode;Index:Integer]: TLQTPoint read GetActualOccupiedRectAsTetragonCorners;
Public property OnGetItemCoord : TLQTGetItemCoordEvent read FGetItemCoordEvent write FGetItemCoordEvent;
Public property OnGetItemRect : TLQTGetItemRectEvent read FGetItemRectEvent write FGetItemRectEvent;
Public property OnGetItemCaption : TLQTGetItemCaptionEvent read FGetItemCaptionEvent write FGetItemCaptionEvent;
Public property OnCreateNode : TLQTCreateNodeEvent read FCreateNodeEvent write FCreateNodeEvent;
Public property OnReadStreamItem : TLQTReadStreamItemEvent read FReadStreamItemEvent write FReadStreamItemEvent;
Public property OnWriteStreamItem : TLQTWriteStreamItemEvent read FWriteStreamItemEvent write FWriteStreamItemEvent;

Description

Methods

Protected function GetWorldRect: TLQTRect; virtual;
 
Protected function InternalCreateNode(const AParentNode : TLQTNode; const ALQTRect : TLQTRect; const ANodeToken : Cardinal = 0) : TLQTNode; virtual;

InternalCreateQuadNode creates a new node. If FCreateNodeEvent is assigned, it is called to allow Users to create Nodes of a derived class. If this failed, a Node of the type TLQTNode is created and returned.

Protected function InternalEnumerateNodesInRect( const ANode : TLQTNode; const AUnwrappedRect : TLQTRect; const AEnumCallBackFunc : TLQTNodeEnumerationCallBack; const AUserData : Pointer) : Boolean; virtual;

The following "Internal" methods, implements the recursive variants of the non-"Internal" methods in the public section. They expect nonwrapped rectangles as ALQTRect E.g. the public EnumerateNodesInRect will call the private InternalEnumerateNodesInRect with the RootNode as the parameter Caution: All functions expect an unwrapped rectangle

Protected function InternalEnumerateItemsInRect( const ANode : TLQTNode; const AUnwrappedRect : TLQTRect; const AEnumCallBackFunc : TLQTItemEnumerationCallBack; const AUserData : Pointer) : Boolean; virtual;
 
Protected function InternalEnumerateItemsInParentNodes( const ANode : TLQTNode; const AUnwrappedRect : TLQTRect; const AEnumCallBackFunc : TLQTItemEnumerationCallBack; const AUserData : Pointer) : Boolean; virtual;
 
Protected function InternalCountNodesInRect(const ANode : TLQTNode; const AUnwrappedRect : TLQTRect) : Integer; virtual;
 
Protected function InternalCountAssignedNodeItemsInRect(const ANode : TLQTNode; const AUnwrappedRect : TLQTRect) : Integer; virtual;
 
Protected function InternalEstimatedCountOfAssignedItemsInRect(const ANode : TLQTNode; const AUnwrappedRect : TLQTRect; const AItemThreshold : Integer) : Double; virtual;
 
Protected function DoGetItemCoord(AItem : TObject; var AX, AY : Double) : Boolean; virtual;

DoGetItemCoord: Fetches the coordinates for the given AItem. The coordinates (AX, AY) are valid if the return value is true. The function calls the assigned GetItemCoordEvent. Derived class may overwrite the method and implement a different approach to get the coordinates.

Protected function DoGetItemRect(AItem : TObject; var AItemRect : TLQTRect) : Boolean; virtual;

DoGetItemRect: Fetches the covered Rect for the given AItem. The AItemRect are valid if the return value is true. The function calls the assigned GetItemRectEvent. Derived class may overwrite the method and implement a different approach to get the Rect.

Protected function DoGetItemCaption(AItem : TObject; var AItemCaption : String) : Boolean; virtual;

DoGetItemCaption: Fetches the Caption of the given AItem. If the AItemCaption is valid, the result is True. The function call the assigned GetItemCaptionEvent.

Protected function TreeItemToListEnumerationCallBack(Sender : TObject; ANode : TLQTNode; ANodeItem : TObject; ANodeItemIndex : Integer; AUserData : Pointer) : Boolean; virtual;

TreeItemToListEnumerationCallBack is used by the several ListItems methods to accumlate the found items into a list. Caution: The function assumes that the parameter UserData is a pointer to a TList Descendand! The method is used only internal but is declared protected and virtual for future expansions. If the parameter ANodeItem is Nil, nothing is inserted into the list The result true if the AUserData is assigned, else false

Protected function TreeNodeToListEnumerationCallBack(Sender : TObject; ANode : TLQTNode; AUserData : Pointer) : Boolean; virtual;

TreeNodeToListEnumerationCallBack is used by the ListNode methods to accumulate found Nodes into a list. Caution: The function assumes that the parameter UserData is a pointer to a TList Descendand! The method is used only internal but is declared protected and virtual for future expansions. If the parameter ANodeItem is Nil, nothing is inserted into the list The result true if the AUserData is assigned, else false

Protected procedure WriteFileStreamStart(const AStream : TStream); virtual;

WriteFileStreamStart will write the QuadTreeFileStartCode to the passed Stream

Protected procedure WriteStreamTreeHeader(const AStream : TStream; const AQuadTreeStreamDataVersion : Cardinal); virtual;

WriteStreamHeader writes the Header to the stream, containing the StartCode and the Version Code. Could be overwritten to write a modified StreamDataVersion

Protected procedure WriteStreamTreeProperties(const AStream : TStream; const AQuadTreeStreamDataVersion : Cardinal); virtual;

WriteTreeProperties writes the property fields to the stream

Protected procedure WriteStreamTreeRootNode(const AStream : TStream; const AQuadTreeStreamDataVersion : Cardinal); virtual;

WriteRootNode write the RootNode

Protected procedure ReadFileStreamStart(const AStream : TStream); virtual;

ReadFileStreamStart read the QuadTreeFileStartCode from passed Stream. if the value is different from the const, an exception is raised

Protected procedure ReadStreamTreeHeader(const AStream : TStream; out AQuadTreeStreamDataVersion : Cardinal); virtual;

ReadStreamHeader reads the header and the Version. raises an exception if the Header Code is wrong or the version incompatible

Protected procedure ReadStreamTreeProperties(const AStream : TStream; const AQuadTreeStreamDataVersion : Cardinal); virtual;

ReadStreamTreeProperties reads the property fields from the stream

Protected procedure ReadStreamTreeRootNode(const AStream : TStream; const AQuadTreeStreamDataVersion : Cardinal); virtual;

ReadRootNode calls the StreamRed method of the root node

Protected function GetOccupiedRect: TLQTRect; virtual;

GetOccupiedRect returns the OccupiedRect of the RootNode. The method could be overwritten to implement a differen way to obtain the occuopied area of the items in the tree

Protected function GetActualNodeRect(const ANode : TLQTNode) : TLQTRect; virtual;

GetActualNodeRect returns the NodeRect from the passed ANode. If the ANode is not assigned the RootNode is used This Method is prepared to provide forward compatibility for derived trees. The method could be overwritten to modify the returned value to an "actual" value. The reason for this subtle distinguish is, that QuadTrees could be used to implement polygon representation for fast collision detection. In this scenario the full tree needs to be translated and rotated, since the polygon (imagine a car / heavy cruizer in a complex polygon-world) is moving and turning. It is very ineffective to rebuild the full tree after such an (small) change. So it is much better to store the roation and translation value in the tree and calculate only the rotated and translated result of the several NodeRect, on request. The question if two of such complex polygon items collides could be very fast denied by comparing such "actual"-Bonding boxes. For example Tree with a world of (-1, -1, 1, 1) wich is rotated by 45° would return (-1.414..., -1.414..., 1.414..., 1.414...), This approach helps to deal with different capable trees.

Protected function GetActualNodeRectAsTetragonCorners(ANode : TLQTNode; Index : Integer) : TLQTPoint; virtual;

GetActualNodeRectAsTetragonCorners calls the GetActualNodeRect (definition below) procedure and return the indexed corner from the Tetragon. This function could be overwritten return the rotated rectangle, instead of the bounding box of the rotated rectangle. Following the example from GetActualNodeRect above, the four corners would be (0,-1.414...), (1.414...,0), (0, 1.414...),(-1.414...,0)

Protected function GetActualOccupiedRect(const ANode : TLQTNode) : TLQTRect; virtual;

GetActualOccupiedRect does the same as GetActualNodeRect does, but using the FOccupiedRect

Protected function GetActualOccupiedRectAsTetragonCorners(ANode : TLQTNode; Index : Integer) : TLQTPoint; virtual;

GetActualOccupiedRectAsTetragonCorners does the same as GetActualNodeRectAsTetragonCorners does, but using the FOccupiedRect

Public function InsertItem(const AItem : TObject; const APointValid : Boolean = False; const ARectValid : Boolean = False; const APointX : Double = 0.0; const APointY : Double = 0.0; const ARectLeft : Double = 0.0; const ARectTop : Double = 0.0; const ARectRight : Double = 0.0; const ARectBottom : Double = 0.0 ) : TLQTNode; virtual;

InsertItem insert the Item into the tree. The optional parameters could be used to speed up the processing APointValid, ARectValid, APointX, APointY ARectLeft, ARectTop, ARectRight, ARectBottom The function returns the node where the item was inserted. If the item is already in the tree, the containing node is returned. If the node could not be inserted, the result is Nil! The tree might be reorganized if necesarry and possible, thus some or all Items in the tree may be moved in different nodes or indices than before this call.

Public function ExtractItem(const AItem : TObject) : TObject; virtual;

ExtractItem removes an Item from the Tree. The function returns the removed Item. On any other case the result is Nil! The tree might be reorganized if necesarry and possible, thus Items may be moved to different nodes than they located before this call.

Public function MoveItemAfterCoordChange(const AItem : TObject) : TLQTNode; virtual;

MoveItemAfterCoordChange moves the given Item to a new Node, reflecting an updated internal position. This may cause the relocation of the Item and a restructure of the tree.

Public procedure GetActualNodeTetragon(const ANode : TLQTNode; out AActualBoundingtTetragon : TLQTPointArr);

GetActualNodeTetragon returns the same values as the ActualBoundingTetragonEdges but effective in one call. If ANode is Nil, the FRootNode will be used to obtain the world's actual BoundingBox

Public function FindRectNode(const ALQTRect : TLQTRect) : TLQTNode; virtual;

FindRectNode returns the deepest (leaf)node which contains (or is equal to) the ALQTRect.

Public function FindCoordNode(const AX, AY : Double) : TLQTNode; virtual;

FindCoordNode returns the deepest (leaf)node which contains the coordinate. As long as the coordinate is within the world, the result will be assigned.

Public function FindItemNode(const AItem : TObject) : TLQTNode; virtual;

FindItemNode returns the Node where the Item is located. The Tree tries to locate the Item by its coords, if this fails, the full tree is searched. So it is very time consuming looking for Items that are not in the tree. If the item is not found the result is Nil.

Public function EnumerateNodesInRect(const ALQTRect : TLQTRect; const AEnumCallBackFunc : TLQTNodeEnumerationCallBack; const AUserData : Pointer = Nil) : Boolean; virtual;

EnumerateNodesInNodeRect enumerates all Nodes in the Tree who are at least partly covered by the passed ALQTRect. For each found node, the passed callback function is called. Since the RootNode contains the whole world, the callback is called always at least once. See the TLQTNodeEnumerationCallBack defintion for more details. AUserData is a generic Pointer, containing any data what the caler likes. The value is unchanged passed to the callback. This allows the usage of local variables as a context to be used in the callback, avoiding the usage ob global variables.

Public procedure ListNodesInRect(const ALQTRect : TLQTRect; const AList : TList); virtual;

ListNodesInNodeRect lists all Nodes in the Tree who are at least partly covered by the passed ALQTRect. Since the RootNode contains the whole world, the List will contain always at least one Node. The AList must be created prior and freed after the call by the using code.

Public function CountNodesInRect(const ALQTRect : TLQTRect) : Integer; virtual;

CountNodesInRect returns the number of Nodes in the passed Rect. The function will return the precise count of nodes in the given Rect. This function has to traverse the covered parts of the tree, while nodes outside the ALQTRect are completely ignored.

Public function EnumerateItemsInRect(const ALQTRect : TLQTRect; const AEnumCallBackFunc : TLQTItemEnumerationCallBack; const AUserData : Pointer = Nil) : Boolean; virtual;

EnumerateItemsInRect enumerates all Nodes in the Tree, who are at least partly covered by the passed ALQTRect. For each found node, the passed callback function is called. Since the RootNode contains the whole world, the callback is called always at least once. See the definition of TLQTItemEnumerationCallBack for more details. AUserData is a generic Pointer, containing any data what the caler likes. The value is unchanged passed to the callback. This allows the usage of local variables as a context to be used in the callback, avoiding the usage ob global variables.

Public procedure ListItemsInRect(const ALQTRect : TLQTRect; const AList : TList); virtual;

ListItemsInRect lists all Items in the Tree who are inside the passed ALQTRect. The AList must be created prior and freed after the call by the using code.

Public function CountAssignedItemsInRect(const ALQTRect : TLQTRect) : Integer; virtual;

CountAssignedItemsInRect returns the exact number of (assigned) items in the passed Rect. This method returns the exact number of items in the Rect. It's still a fast method, since for all fully covered rectangles the TotalNodeItemsCount is taken. For all partly covered rectangles all items in the nodes are queried for their exact position. Thus, the method may takes her time. If only an estimation is wanted use the faster EstimatedCountOfAssignedItemsInRect instead.

Public function EstimatedCountOfAssignedItemsInRect(const ALQTRect : TLQTRect; const AItemThreshold : Integer) : Double; virtual;

EstimatedCountOfAssignedItemsInRect returns the estimated amount of Items in the passed Rect. This estimation is faster than counting, since no items are queried for there positions. Only the TotalNodeItemsCount is used for the estimation and the fraction of the passed Rect. Parameters ALQTRect, the rectangle i which the item count should be estimated AItemThreshold, if TotalNodeItemsCount is equal or less then the estimation is terminated for this node and a part of the value is returned. Remarks The main use of this method is to decide quickly, whether too many items in an Rect exists, so that only a placeholder should be displayed, instead of an bunch of overlapping items. A result greater than 0 will not guaranty that items are really exists in the passed Rect. If a node is covering a large Rect, but all items sit in a small region, than a mismatch between the reality and the estimation occour. A larger AItemThreshold will increase the execution speed, by reducing the accuracy. Depending of the data values between 100 and 500 gives an accuracy between 10%-20%.

Public function AgglomerateNodeAsEnumeration( const ANode : TLQTNode; const AAgglomerationDepth : Integer; const AMinimumItemNumberInAgglomeration : Integer; const AItemEnumFunc : TLQTItemEnumerationCallBack; const AItemUserData : Pointer; const AAgglomerationEnumFunc : TLQTAgglomerationEnumerationCallBack; const AAgglomerationUserData : Pointer) : Boolean; virtual;

AgglomerateNodeAsEnumeration build a summary of the Items within this node and his children. The usage is e.g. to build clickable items on a map, which represents a bunch of items below, to prevent that thousands of items will be drawn, while a "10K"-sign would do the job. Another usage would be to colorize parts of an image recording to the "density" of the Agglomerations. Parameters ANode, the Node where the agglomeration starts. AAgglomerationDepth determines how many node-leves below should be taken into account. Due to the math (every level contains 4 times nodes than the parents level) a value of 1 will return up to 4 agglomeration records, 2 will return 16 and 3 = 64. If one Node cover an square of e.g. 256 pixel (as one OSM-Tile does), a level of 3 will place up to 64 ( = 16 * 16) agglomeration records on this tile. AMinimumItemNumberInAgglomeration will control the minimum ammount in one agglomeration. The value should not be less than MaxQuadNodeItemCount. A good value depends on the Data structure and the tile size. If one agglomeration contains a square of 16 x 16 pixel, the value could be 16 to place (in average) 4 x 4 items in this area. AItemEnumFunc, AAgglomerationEnumFunc both callback function must be provided to allow a sucessful operation. Each function will be called once for every item or build agglomeration. AItemUserData, AAgglomerationUserData are passed unmodified to the callback functions to allow the management of the passed data.

Public procedure AgglomerateNodeAsList(const ANode : TLQTNode; const AAgglomerationDepth: Integer; const AMinimumItemNumberInAgglomeration: Integer; var AAgglomerationArray: TLQTAgglomerationArray; const AItemList: TList);

AgglomerateNodeAsList (see the method with the same name of the TreeNode for a detailed explanation) The method build a summary of the Items related within the passed node. Parameters (see the method with the same name of the TreeNode for a detailed explanation) ANode, the Node where the agglomeration starts. Remarks: The method does exactly the same a the method of the node (actually it calls this method), but adds all related items of the parent and grand-parent nodes using the ListItemsInParentNodes method.

Public procedure TreeAsStrings(const AStrings : TStrings); virtual;

TreeAsStrings returns the content of the Tree in a readable form for debugging purpose.

Public procedure ListTreeNodes(const AList : TList); virtual;

ListTreeNodes recurses through the Nodes of the Tree and stores them in the passed list. The AList must be created prior and freed after the call by the using code.

Public procedure ListSubNodes(const ANode : TLQTNode; const AList : TList); virtual;

ListSubNodes recurses through the ANode and all SubNodes and stores them in the passed list. if ANode is Nil, the RootNode is used and the full tree listed. The AList must be created prior and freed after the call by the using code.

Public function CountTreeNodes: Integer;

NodesTreeCount recurses through all Nodes of the Tree return the sum of all nodes. The minimum result is one if the tree is empty, since the root node must always exists. If the result is zero, the tree is malformed

Public function CountNodes(const ANode : TLQTNode) : Integer; virtual;

CountNodes returns the number of SubNodes of the passed ANode (inclusive). If ANode is Nil, the result is 0, if ANode has no children, the result is 1

Public function EnumerateItemsInSubNodes(const ANode : TLQTNode; const AEnumCallBackFunc : TLQTItemEnumerationCallBack; const AUserData : Pointer = Nil) : Boolean; virtual;

EnumerateItemsInSubNodes recurses through the ANode and all SubNodes and calls the callback function once for every found Item. See the definition of TLQTItemEnumerationCallBack for details. AUserData is a generic Pointer, containing any data what the caller likes.

Public procedure ListItemsInSubNodes(const ANode : TLQTNode; const AList : TList); virtual;

ListItemsInSubNodes recurses through the ANode and all SubNodes and stores the found Items in the passed list. The AList must be created prior and freed after the call by the using code.

Public function EnumerateItemsInParentNodes(const ANode : TLQTNode; const AEnumCallBackFunc : TLQTItemEnumerationCallBack; const AUserData : Pointer = Nil) : Boolean; virtual;

EnumerateItemsInParentNodes recurses upwards through the Parent of ANode and Grandparents until the root node is reached and stores the Items located in the NodeArea in the passed list. This seems stupid, since all the items should reside in the smallest possible rectangle, and those will be collected with the Enumerate-/ListItemsInSubNodes method. But for items which covers an area the smallest rectangle might be a generations above. E.g. the shape of the USA-Mainland will reside much higher than the location of the Liberty-Statue in New York, but covers her fully. The AList must be created prior and freed after the call by the using code.

Public procedure ListItemsInParentNodes(const ANode : TLQTNode; const AItemList : TList); virtual;

ListItemsInParentNodes recurses upwards through the Parent of ANode and Grandparents until the root node is reached and stores the Items located in the NodeArea in the passed list. This seems stupid, since all the items should reside in the smallest possible rectangle, and those will be collected with the Enumerate-/ListItemsInSubNodes method. But for items which covers an area the smallest rectangle might be a generations above. E.g. the shape of the USA-Mainland will reside much higher than the location of the Liberty-Statue in New York, but covers her fully. The AList must be created prior and freed after the call by the using code.

Public function NextNode(const AStartNode : TLQTNode = Nil) : TLQTNode;

NextNode will return the next node in the tree, behind the given node. If the passed node is empty, the RootNode is returned. If StartNode is the last node, than Nil is returned.

Public function NextItem(out ANextItem : TObject; out ANextItemNode : TLQTNode; const AStartItem : TObject = Nil; const AStartItemNode : TLQTNode = Nil) : Boolean;

NextItem will return the next Item behind the given one. Parameters output ANextItem the next found item, nil if nothing found ANextItemNode the node where the next out item is found, nil if nothing input AStartItem the Item where the search starts. If Nil, the first*) Item is returned. AStartItemNode the Node where the AStartItem resides. If Nil, the RootNode is used. *) If AStartItem is Nil, but AStartItemNode assigned, then the first Item in this Node, or if no Item exists, the next item is returned. If AStartItem is assigned, but AStartNode is Nil, then the item is searched in the whole tree, which is very not efficent! Result true if something found, false if not. A loop: var item : TObject = Nil; node : TLQTNode = Nil; ... while NextItem(item, node, item, node) do begin // do something here end; ... will iterate through all items.

Public procedure RecountTotalNodeItems; virtual;

RecountTotalNodeItems iterate through all Nodes and Items and refreshes the Nodes TotalNodeItemsCount. This method might be useful after a manually reconfiguration of the Tree.

Public procedure RebuildOccupiedRect; virtual;

RebuildOccupiedRect iterate through all Nodes and Items and refreshes the Nodes FOccupiedRect. This method might be useful after a manually reconfiguration of the Tree.

Public procedure Clear; virtual;

Clear, empties the QuadTree, frees all Nodes and if OwnsObjects is true Items are freed too

Public procedure BeginUpdate;

BeginUpdate initiate a BeginUpdate..EndUpdate sequences. If inside this sequence splitting and packing nodes and packing node items are suppressed. BeginUpdate..EndUpdate calls could be nested. Caution: BeginUpdate..EndUpdate slows down the adding of many items to the tree, because all new Items are stored in the root node!

Public procedure EndUpdate;

EndUpdate finalize a BeginUpdate..EndUpdate sequences. If the last EndUpdate call from a BeginUpdate sequence is reached, the RootNode is "Splitted" and "Packed" (including cleaning up the Items) and this is recursed through the whole tree.

Public procedure WriteTreeToStream(const AStream : TStream); virtual;

WriteQuadTreeToStream writes the Tree including all Nodes to the stream

Public procedure ReadTreeFromStream(const AStream : TStream; const AStreamReadOptions : Cardinal = 0); virtual;

ReadNodeFromStream read the content of the Tree including all Nodes from the stream

Public procedure WriteTreeToFile(const AFileName : String); virtual;

WriteQuadTreeToFile writes the Tree including all Nodes to the stream

Public procedure ReadTreeFromFile(const AFileName : String; const AStreamReadOptions : Cardinal = 0); virtual;

ReadQuadTreeFromFile read the content of the Tree including all Nodes from the stream

Public constructor Create(const AWorldRect : TLQTRect; const AWorldModel : TLQTWorldModel; const AFreeObjects: Boolean = False; const AQuadTreeCreateQuadNodeEvent : TLQTCreateNodeEvent = Nil);

Create: Creates the Tree. AWorldSize defines the used world. if AXAxisIsCylindrical is True (this is the default), the Right-value should be the negative of the Left-value, to allow a seamless wrap around of the NodeItems. AFreeObjects defines whether the Tree owns the objects (and frees them, when needed) or if the NodeItems are held somewhere else and the NodeItems are only references. AXAxisIsCylindrical defines whether the World is flat, like a piece of paper (=False) or wraping around like a cylinder (=True, the default). AYAxisDirection defines whether Top is larger than Bottom (= qydUpPlus, the default) or Top is smaller than Bottom (=qydUpMinus). The first case is used for maps or cartesian projections, the second for Bitmaps or Editors AQuadTreeCreateQuadNodeEvent could be passed to allow the creation of derived classes of Nodes, which than extend or replace certain functionallities than the default Node-class. Usually this parameter is not used (=Nil)

Public destructor Destroy; override;

Destroy frees the Tree. It frees the RootNode and subsequently all data in the tree.

Properties

Public property WorldModel : TLQTWorldModel read FWorldModel;

WorldModel contains the extent of the Worls covered by this tree

Public property WorldRect : TLQTRect read GetWorldRect;
 
Public property WorldXAxisLeftPlus : Boolean read GetWorldXAxisLeftPlus;

WorldXAxisLeftPlus is true if the values on the X-Axis increment traveling to the left, false increment to the right

Public property WorldYAxisUpPlus : Boolean read GetWorldYAxisUpPlus;

WorldYAxisUpPlus is true if the values on the Y-Axis increment traveling to the top, false increment to the bottom

Public property OwnsObjects: Boolean read FOwnsObjects write FOwnsObjects;

OwnsObjects: True if the Tree is the owner of the added NodeItems, so that they will be freed on destroying the tree.

Public property RootNode : TLQTNode read FRootNode;

RootNode: The RootNode where the tree is build below

Public property MaxNodeItemCount : Integer read FMaxNodeItemCount write FMaxNodeItemCount;

MaxNodeItemCount: This is the amount of NodeItems one Node could hold. If the amount of NodeItems increases over this amount, the Node is split and the items are distributed to the new children. This value is ignored for Nodes at the deepest level, since this nodes are not allowed to split. A too small value will create a lot of nodes, with no Items in. A too big value will reduce the performance, since the items are processed like an unordered list. The value has a big performance impact depending of the desired functionality. The default value is 4

Public property MaxTreeLevel : Integer read FMaxTreeLevel write FMaxTreeLevel default DefaultMaxTreeLevel;

MaxTreeLevel: This is the maximum depth the tree could have. By default the value is 25. Keep in mind that the amount of Items that *could* be stored increases very fast. The default is about 1280 TerraItems, and a value of 32 exceeds the range of the used Integer variable. The value should be choosen, so that the median distance of the used items, will distribute them into different nodes. A too small value may lead into the situation, where to many items are collected in one node at the maximum depth, reducing the performance back to an unordered list. A too big value instead, creates a tree with only few, but very long branches, causing a lot of running around in empty nodes.

Public property TreeToken : Cardinal read FTreeToken;

DefaultQuadTreeToken is used to identify the Tree class in the Stream read and write methods

Public property OccupiedRect : TLQTRect read GetOccupiedRect;

OccupiedRect the rectangle which contains all items of the tree. If the tree is empty = (RootNode.TotalItemsCount = 0), the result is the NullRectangle. Caution: The rectangle might be empty or not an area, dependend of the extension(s) and location(s) of the item(s)

Public property ActualNodeRect[Index:TLQTNode]: TLQTRect read GetActualNodeRect;

ActualNodeRect in this implementation the same value as WorldRect. See GetActualNodeRect for more details.

Public property ActualNodeRectAsTetragonCorners[ANode:TLQTNode;Index:Integer]: TLQTPoint read GetActualNodeRectAsTetragonCorners;

ActualNodeRectAsTetragonCorners in this implementation the four corners of the ActualNodeRect, see GetActualNodeRectAsTetragonCorners for more details.

Public property ActualOccupiedRect[Index:TLQTNode]: TLQTRect read GetActualOccupiedRect;

ActualOccupiedRect in this implementation the same value as WorldRect. See GetActualOccupiedRect for more details.

Public property ActualOccupiedRectAsTetragonCorners[ANode:TLQTNode;Index:Integer]: TLQTPoint read GetActualOccupiedRectAsTetragonCorners;

ActualOccupiedRectAsTetragonCorners in this implementation the four corners of the ActualOccupiedRect, see GetActualOccupiedRectAsTetragonCorners for more details.

Public property OnGetItemCoord : TLQTGetItemCoordEvent read FGetItemCoordEvent write FGetItemCoordEvent;

OnGetItemCoord: The Event that is called to get the location of a specific NodeItem in the tree. If instantiate this class this Event *must* be assigned, since the Tree needs the get the coordinates of the Items to get the tree organized. A derived class of the tree may overwrite the DoGetItemCoord method to collect the coordinates of the items direct.

Public property OnGetItemRect : TLQTGetItemRectEvent read FGetItemRectEvent write FGetItemRectEvent;

OnGetItemRect: The Event that is called to get the covered Rect of a specific NodeItem in the tree. This Event may be not assigned, if only point-like NodeItems are used. If NodeItems are covering an Rect, this event must be assigned.

Public property OnGetItemCaption : TLQTGetItemCaptionEvent read FGetItemCaptionEvent write FGetItemCaptionEvent;

OnGetItemCaption: The Event is called to get a descriptive caption for a specific item in the tree. This event may be not assigned if items have no caption or the caption is not used.

Public property OnCreateNode : TLQTCreateNodeEvent read FCreateNodeEvent write FCreateNodeEvent;

OnCreateNode: This Event could be assigned to create descendants classes of the TLQTNode to be used by the tree. Under nomal circumstances it remains unassigned.

Public property OnReadStreamItem : TLQTReadStreamItemEvent read FReadStreamItemEvent write FReadStreamItemEvent;

OnReadStreamItem: This Event must be assigned, when the ReadStreamTree method is used. The event will be called for every Item that needs to be read from the stream.

Public property OnWriteStreamItem : TLQTWriteStreamItemEvent read FWriteStreamItemEvent write FWriteStreamItemEvent;

OnWriteStreamItem: This Event must be assigned, when the WriteStreamTree method is used. The event will be called for every Item that needs to be written to the stream.


Generated by PasDoc 0.16.0.