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
- TObject
- TLazQuadTree
Overview
Methods
![]() |
function GetWorldRect: TLQTRect; virtual; |
![]() |
function InternalCreateNode(const AParentNode : TLQTNode; const ALQTRect : TLQTRect; const ANodeToken : Cardinal = 0) : TLQTNode; virtual; |
![]() |
function InternalEnumerateNodesInRect( const ANode : TLQTNode; const AUnwrappedRect : TLQTRect; const AEnumCallBackFunc : TLQTNodeEnumerationCallBack; const AUserData : Pointer) : Boolean; virtual; |
![]() |
function InternalEnumerateItemsInRect( const ANode : TLQTNode; const AUnwrappedRect : TLQTRect; const AEnumCallBackFunc : TLQTItemEnumerationCallBack; const AUserData : Pointer) : Boolean; virtual; |
![]() |
function InternalEnumerateItemsInParentNodes( const ANode : TLQTNode; const AUnwrappedRect : TLQTRect; const AEnumCallBackFunc : TLQTItemEnumerationCallBack; const AUserData : Pointer) : Boolean; virtual; |
![]() |
function InternalCountNodesInRect(const ANode : TLQTNode; const AUnwrappedRect : TLQTRect) : Integer; virtual; |
![]() |
function InternalCountAssignedNodeItemsInRect(const ANode : TLQTNode; const AUnwrappedRect : TLQTRect) : Integer; virtual; |
![]() |
function InternalEstimatedCountOfAssignedItemsInRect(const ANode : TLQTNode; const AUnwrappedRect : TLQTRect; const AItemThreshold : Integer) : Double; virtual; |
![]() |
function DoGetItemCoord(AItem : TObject; var AX, AY : Double) : Boolean; virtual; |
![]() |
function DoGetItemRect(AItem : TObject; var AItemRect : TLQTRect) : Boolean; virtual; |
![]() |
function DoGetItemCaption(AItem : TObject; var AItemCaption : String) : Boolean; virtual; |
![]() |
function TreeItemToListEnumerationCallBack(Sender : TObject; ANode : TLQTNode; ANodeItem : TObject; ANodeItemIndex : Integer; AUserData : Pointer) : Boolean; virtual; |
![]() |
function TreeNodeToListEnumerationCallBack(Sender : TObject; ANode : TLQTNode; AUserData : Pointer) : Boolean; virtual; |
![]() |
procedure WriteFileStreamStart(const AStream : TStream); virtual; |
![]() |
procedure WriteStreamTreeHeader(const AStream : TStream; const AQuadTreeStreamDataVersion : Cardinal); virtual; |
![]() |
procedure WriteStreamTreeProperties(const AStream : TStream; const AQuadTreeStreamDataVersion : Cardinal); virtual; |
![]() |
procedure WriteStreamTreeRootNode(const AStream : TStream; const AQuadTreeStreamDataVersion : Cardinal); virtual; |
![]() |
procedure ReadFileStreamStart(const AStream : TStream); virtual; |
![]() |
procedure ReadStreamTreeHeader(const AStream : TStream; out AQuadTreeStreamDataVersion : Cardinal); virtual; |
![]() |
procedure ReadStreamTreeProperties(const AStream : TStream; const AQuadTreeStreamDataVersion : Cardinal); virtual; |
![]() |
procedure ReadStreamTreeRootNode(const AStream : TStream; const AQuadTreeStreamDataVersion : Cardinal); virtual; |
![]() |
function GetOccupiedRect: TLQTRect; virtual; |
![]() |
function GetActualNodeRect(const ANode : TLQTNode) : TLQTRect; virtual; |
![]() |
function GetActualNodeRectAsTetragonCorners(ANode : TLQTNode; Index : Integer) : TLQTPoint; virtual; |
![]() |
function GetActualOccupiedRect(const ANode : TLQTNode) : TLQTRect; virtual; |
![]() |
function GetActualOccupiedRectAsTetragonCorners(ANode : TLQTNode; Index : Integer) : TLQTPoint; virtual; |
![]() |
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; |
![]() |
function ExtractItem(const AItem : TObject) : TObject; virtual; |
![]() |
function MoveItemAfterCoordChange(const AItem : TObject) : TLQTNode; virtual; |
![]() |
procedure GetActualNodeTetragon(const ANode : TLQTNode; out AActualBoundingtTetragon : TLQTPointArr); |
![]() |
function FindRectNode(const ALQTRect : TLQTRect) : TLQTNode; virtual; |
![]() |
function FindCoordNode(const AX, AY : Double) : TLQTNode; virtual; |
![]() |
function FindItemNode(const AItem : TObject) : TLQTNode; virtual; |
![]() |
function EnumerateNodesInRect(const ALQTRect : TLQTRect; const AEnumCallBackFunc : TLQTNodeEnumerationCallBack; const AUserData : Pointer = Nil) : Boolean; virtual; |
![]() |
procedure ListNodesInRect(const ALQTRect : TLQTRect; const AList : TList); virtual; |
![]() |
function CountNodesInRect(const ALQTRect : TLQTRect) : Integer; virtual; |
![]() |
function EnumerateItemsInRect(const ALQTRect : TLQTRect; const AEnumCallBackFunc : TLQTItemEnumerationCallBack; const AUserData : Pointer = Nil) : Boolean; virtual; |
![]() |
procedure ListItemsInRect(const ALQTRect : TLQTRect; const AList : TList); virtual; |
![]() |
function CountAssignedItemsInRect(const ALQTRect : TLQTRect) : Integer; virtual; |
![]() |
function EstimatedCountOfAssignedItemsInRect(const ALQTRect : TLQTRect; const AItemThreshold : Integer) : Double; virtual; |
![]() |
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; |
![]() |
procedure AgglomerateNodeAsList(const ANode : TLQTNode; const AAgglomerationDepth: Integer; const AMinimumItemNumberInAgglomeration: Integer; var AAgglomerationArray: TLQTAgglomerationArray; const AItemList: TList); |
![]() |
procedure TreeAsStrings(const AStrings : TStrings); virtual; |
![]() |
procedure ListTreeNodes(const AList : TList); virtual; |
![]() |
procedure ListSubNodes(const ANode : TLQTNode; const AList : TList); virtual; |
![]() |
function CountTreeNodes: Integer; |
![]() |
function CountNodes(const ANode : TLQTNode) : Integer; virtual; |
![]() |
function EnumerateItemsInSubNodes(const ANode : TLQTNode; const AEnumCallBackFunc : TLQTItemEnumerationCallBack; const AUserData : Pointer = Nil) : Boolean; virtual; |
![]() |
procedure ListItemsInSubNodes(const ANode : TLQTNode; const AList : TList); virtual; |
![]() |
function EnumerateItemsInParentNodes(const ANode : TLQTNode; const AEnumCallBackFunc : TLQTItemEnumerationCallBack; const AUserData : Pointer = Nil) : Boolean; virtual; |
![]() |
procedure ListItemsInParentNodes(const ANode : TLQTNode; const AItemList : TList); virtual; |
![]() |
function NextNode(const AStartNode : TLQTNode = Nil) : TLQTNode; |
![]() |
function NextItem(out ANextItem : TObject; out ANextItemNode : TLQTNode; const AStartItem : TObject = Nil; const AStartItemNode : TLQTNode = Nil) : Boolean; |
![]() |
procedure RecountTotalNodeItems; virtual; |
![]() |
procedure RebuildOccupiedRect; virtual; |
![]() |
procedure Clear; virtual; |
![]() |
procedure BeginUpdate; |
![]() |
procedure EndUpdate; |
![]() |
procedure WriteTreeToStream(const AStream : TStream); virtual; |
![]() |
procedure ReadTreeFromStream(const AStream : TStream; const AStreamReadOptions : Cardinal = 0); virtual; |
![]() |
procedure WriteTreeToFile(const AFileName : String); virtual; |
![]() |
procedure ReadTreeFromFile(const AFileName : String; const AStreamReadOptions : Cardinal = 0); virtual; |
![]() |
constructor Create(const AWorldRect : TLQTRect; const AWorldModel : TLQTWorldModel; const AFreeObjects: Boolean = False; const AQuadTreeCreateQuadNodeEvent : TLQTCreateNodeEvent = Nil); |
![]() |
destructor Destroy; override; |
Properties
![]() |
property WorldModel : TLQTWorldModel read FWorldModel; |
![]() |
property WorldRect : TLQTRect read GetWorldRect; |
![]() |
property WorldXAxisLeftPlus : Boolean read GetWorldXAxisLeftPlus; |
![]() |
property WorldYAxisUpPlus : Boolean read GetWorldYAxisUpPlus; |
![]() |
property OwnsObjects: Boolean read FOwnsObjects write FOwnsObjects; |
![]() |
property RootNode : TLQTNode read FRootNode; |
![]() |
property MaxNodeItemCount : Integer read FMaxNodeItemCount write FMaxNodeItemCount; |
![]() |
property MaxTreeLevel : Integer read FMaxTreeLevel write FMaxTreeLevel default DefaultMaxTreeLevel; |
![]() |
property TreeToken : Cardinal read FTreeToken; |
![]() |
property OccupiedRect : TLQTRect read GetOccupiedRect; |
![]() |
property ActualNodeRect[Index:TLQTNode]: TLQTRect read GetActualNodeRect; |
![]() |
property ActualNodeRectAsTetragonCorners[ANode:TLQTNode;Index:Integer]: TLQTPoint read GetActualNodeRectAsTetragonCorners; |
![]() |
property ActualOccupiedRect[Index:TLQTNode]: TLQTRect read GetActualOccupiedRect; |
![]() |
property ActualOccupiedRectAsTetragonCorners[ANode:TLQTNode;Index:Integer]: TLQTPoint read GetActualOccupiedRectAsTetragonCorners; |
![]() |
property OnGetItemCoord : TLQTGetItemCoordEvent read FGetItemCoordEvent write FGetItemCoordEvent; |
![]() |
property OnGetItemRect : TLQTGetItemRectEvent read FGetItemRectEvent write FGetItemRectEvent; |
![]() |
property OnGetItemCaption : TLQTGetItemCaptionEvent read FGetItemCaptionEvent write FGetItemCaptionEvent; |
![]() |
property OnCreateNode : TLQTCreateNodeEvent read FCreateNodeEvent write FCreateNodeEvent; |
![]() |
property OnReadStreamItem : TLQTReadStreamItemEvent read FReadStreamItemEvent write FReadStreamItemEvent; |
![]() |
property OnWriteStreamItem : TLQTWriteStreamItemEvent read FWriteStreamItemEvent write FWriteStreamItemEvent; |
Description
Methods
![]() |
function GetWorldRect: TLQTRect; virtual; |
![]() |
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. |
![]() |
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 |
![]() |
function InternalEnumerateItemsInRect( const ANode : TLQTNode; const AUnwrappedRect : TLQTRect; const AEnumCallBackFunc : TLQTItemEnumerationCallBack; const AUserData : Pointer) : Boolean; virtual; |
![]() |
function InternalEnumerateItemsInParentNodes( const ANode : TLQTNode; const AUnwrappedRect : TLQTRect; const AEnumCallBackFunc : TLQTItemEnumerationCallBack; const AUserData : Pointer) : Boolean; virtual; |
![]() |
function InternalCountNodesInRect(const ANode : TLQTNode; const AUnwrappedRect : TLQTRect) : Integer; virtual; |
![]() |
function InternalCountAssignedNodeItemsInRect(const ANode : TLQTNode; const AUnwrappedRect : TLQTRect) : Integer; virtual; |
![]() |
function InternalEstimatedCountOfAssignedItemsInRect(const ANode : TLQTNode; const AUnwrappedRect : TLQTRect; const AItemThreshold : Integer) : Double; virtual; |
![]() |
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. |
![]() |
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 |
![]() |
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 |
![]() |
procedure WriteFileStreamStart(const AStream : TStream); virtual; |
WriteFileStreamStart will write the QuadTreeFileStartCode to the passed Stream |
![]() |
procedure WriteStreamTreeProperties(const AStream : TStream; const AQuadTreeStreamDataVersion : Cardinal); virtual; |
WriteTreeProperties writes the property fields to the stream |
![]() |
procedure WriteStreamTreeRootNode(const AStream : TStream; const AQuadTreeStreamDataVersion : Cardinal); virtual; |
WriteRootNode write the RootNode |
![]() |
procedure ReadStreamTreeProperties(const AStream : TStream; const AQuadTreeStreamDataVersion : Cardinal); virtual; |
ReadStreamTreeProperties reads the property fields from the stream |
![]() |
procedure ReadStreamTreeRootNode(const AStream : TStream; const AQuadTreeStreamDataVersion : Cardinal); virtual; |
ReadRootNode calls the StreamRed method of the root node |
![]() |
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 |
![]() |
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. |
![]() |
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) |
![]() |
function GetActualOccupiedRect(const ANode : TLQTNode) : TLQTRect; virtual; |
GetActualOccupiedRect does the same as GetActualNodeRect does, but using the FOccupiedRect |
![]() |
function GetActualOccupiedRectAsTetragonCorners(ANode : TLQTNode; Index : Integer) : TLQTPoint; virtual; |
GetActualOccupiedRectAsTetragonCorners does the same as GetActualNodeRectAsTetragonCorners does, but using the FOccupiedRect |
![]() |
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. |
![]() |
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. |
![]() |
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 |
![]() |
function FindRectNode(const ALQTRect : TLQTRect) : TLQTNode; virtual; |
FindRectNode returns the deepest (leaf)node which contains (or is equal to) the ALQTRect. |
![]() |
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. |
![]() |
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. |
![]() |
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. |
![]() |
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. |
![]() |
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. |
![]() |
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. |
![]() |
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. |
![]() |
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. |
![]() |
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%. |
![]() |
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. |
![]() |
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. |
![]() |
procedure TreeAsStrings(const AStrings : TStrings); virtual; |
TreeAsStrings returns the content of the Tree in a readable form for debugging purpose. |
![]() |
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. |
![]() |
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 |
![]() |
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. |
![]() |
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. |
![]() |
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. |
![]() |
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. |
![]() |
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. |
![]() |
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. |
![]() |
procedure Clear; virtual; |
Clear, empties the QuadTree, frees all Nodes and if OwnsObjects is true Items are freed too |
![]() |
procedure WriteTreeToStream(const AStream : TStream); virtual; |
WriteQuadTreeToStream writes the Tree including all Nodes to the stream |
![]() |
procedure ReadTreeFromStream(const AStream : TStream; const AStreamReadOptions : Cardinal = 0); virtual; |
ReadNodeFromStream read the content of the Tree including all Nodes from the stream |
![]() |
procedure WriteTreeToFile(const AFileName : String); virtual; |
WriteQuadTreeToFile writes the Tree including all Nodes to the stream |
![]() |
procedure ReadTreeFromFile(const AFileName : String; const AStreamReadOptions : Cardinal = 0); virtual; |
ReadQuadTreeFromFile read the content of the Tree including all Nodes from the stream |
![]() |
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) |
![]() |
destructor Destroy; override; |
Destroy frees the Tree. It frees the RootNode and subsequently all data in the tree. |
Properties
![]() |
property WorldModel : TLQTWorldModel read FWorldModel; |
WorldModel contains the extent of the Worls covered by this tree |
![]() |
property WorldRect : TLQTRect read GetWorldRect; |
![]() |
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 |
![]() |
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 |
![]() |
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. |
![]() |
property RootNode : TLQTNode read FRootNode; |
RootNode: The RootNode where the tree is build below |
![]() |
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. |
![]() |
property TreeToken : Cardinal read FTreeToken; |
DefaultQuadTreeToken is used to identify the Tree class in the Stream read and write methods |
![]() |
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) |
![]() |
property ActualNodeRect[Index:TLQTNode]: TLQTRect read GetActualNodeRect; |
ActualNodeRect in this implementation the same value as WorldRect. See GetActualNodeRect for more details. |
![]() |
property ActualNodeRectAsTetragonCorners[ANode:TLQTNode;Index:Integer]: TLQTPoint read GetActualNodeRectAsTetragonCorners; |
ActualNodeRectAsTetragonCorners in this implementation the four corners of the ActualNodeRect, see GetActualNodeRectAsTetragonCorners for more details. |
![]() |
property ActualOccupiedRect[Index:TLQTNode]: TLQTRect read GetActualOccupiedRect; |
ActualOccupiedRect in this implementation the same value as WorldRect. See GetActualOccupiedRect for more details. |
![]() |
property ActualOccupiedRectAsTetragonCorners[ANode:TLQTNode;Index:Integer]: TLQTPoint read GetActualOccupiedRectAsTetragonCorners; |
ActualOccupiedRectAsTetragonCorners in this implementation the four corners of the ActualOccupiedRect, see GetActualOccupiedRectAsTetragonCorners for more details. |
![]() |
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. |
![]() |
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. |
![]() |
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. |
![]() |
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. |
![]() |
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. |
![]() |
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.