Unit uLazQuadTree
Description
A general Quad-Tree for Objects (and arbitrary data) Copyright (C) 2023,2024 Ekkehard Domning (www.domis.de)
License: modified LGPL with linking exception (like RTL, FCL and LCL)
See the file COPYING.modifiedLGPL.txt, included in the Lazarus distribution, for details about the license.
Version Date Change 0.0.1 2023-04-27 First release 0.0.2 2024-05-25 Bugfixes, changes in visibility of virtual methods 0.0.3 2024-05-29 Caching for NodeItem-Positions and Area 0.0.4 2024-08-05 Using new ulazQuadTreeGeometry.pas for all rectangles 0.0.5 2024-08-24 Bugfixes for area items and cleanups, removing code duplicity 0.0.6 2024-08-30 Write and Read from Stream 0.0.7 2024-08-31 Speedup CoordIsInNodeRect 0.0.8 2024-09-14 OccupiedRect contains all items in one node. 0.0.9 2024-09-24 Renaming Declarations for streamlining
Overview
Classes, Interfaces, Objects and Records
Functions and Procedures
Types
Constants
Description
Functions and Procedures
function ReadIntegerFromStream(const AStream : TStream) : Integer; |
|
procedure WriteIntegerToStream(const AStream : TStream; const AInteger : Integer); |
|
function ReadDoubleFromStream(const AStream : TStream) : Double; |
|
procedure WriteDoubleToStream(const AStream : TStream; const ADouble : Double); |
|
procedure WriteStringToStream(const AStream : TStream; const AString : String); |
|
function ReadStringFromStream(const AStream : TStream) : String; |
|
Types
TLQTNodeChildLocation = (...); |
TLQTNodeChildLocation the Index of the four ChildNodes
Values
|
TLQTNodeEnumerationCallBack = function (Sender : TObject; ANode : TLQTNode; AUserData : Pointer) : Boolean of object; |
TLQTNodeEnumerationCallBack This event/callback is used in the enumeration functions. It will be called for each found Node. Parameters Sender is the tree to which the node belongs ANode contains the found node. AUserData is passed unchanged from the function call and may be used by the callback-function to identify data, avoiding the usage of global variable.
|
TLQTItemEnumerationCallBack = function (Sender : TObject; ANode : TLQTNode; ANodeItem : TObject; ANodeItemIndex : Integer; AUserData : Pointer) : Boolean of object; |
TLQTItemEnumerationCallBack This event is used in the enumeration function. It will be called for each found Item. Parameters Sender is the tree to which the node belongs ANode contains the found node. ANodeItem contains the Item. ANodeItemIndex contains the index of the ANodeItem in the NodeItems-Array. AUserData is passed unchanged from the function call and may be used by the callback-function to identify data, avoiding the usage of global variable.
|
PLQTAgglomerationArray = ˆTLQTAgglomerationArray; |
PLQTAgglomerationArray, an pointer to an array of TLazQuadTreeAgglomerationRec
|
TLQTAgglomerationArray = array of TLQTAgglomerationRec; |
TLQTAgglomerationArray an array of TLazQuadTreeAgglomerationRec
|
TLQTAgglomerationEnumerationCallBack = function (ANode : TLQTNode; const ATreeAgglomerationRec : TLQTAgglomerationRec; AUserData : Pointer) : Boolean of object; |
TLQTAgglomerationEnumerationCallBack is used in the Agglomeration Enumeration and is called for every build agglomeration Parameters ANode contains the operated node. ATreeAgglomerationRec contains the agglomerated data for this node AUserData is passed unchanged from the function call and may be used by the callback-function to identify data, avoiding the usage of global variable.
|
TLQTGetItemCoordEvent = function (Sender : TObject; AItem : TObject; var AX, AY : Double) : Boolean of object; |
TLQTGetItemCoordEvent An event which has to return an X and a Y Coordinate for the given ItemIndex. Return True if the return values AX and AY are valid, False if not.
|
TLQTGetItemRectEvent = function (Sender : TObject; AItem : TObject; var AItemRect : TLQTRect) : Boolean of object; |
TLQTGetItemRectEvent An event which may return an Rect which contains the entire item. If the item has no Rect, the Event should return false. Return True if the return value AItemRect is valid, False if not.
|
TLQTGetItemCaptionEvent = function (Sender : TObject; AItem : TObject; var ACaption : String) : Boolean of object; |
TLQTGetItemCaptionEvent An event which can return a Caption (title, descriptive string) of the item. If the item has not such a Caption than the result shlould return false Return True if the Caption is valid, False if not.
|
TLQTReadStreamItemEvent = function (AOwner : TLazQuadTree; ANode : TLQTNode; AItemIndex : Integer; AStream : TStream) : TObject of object; |
TLQTReadStreamItemEvent The event is used within the tree stream reading method. An event which has to read an Object from the given Stream. Depending from the Tree.OwnsObjects property the returned object has to be a real created object (True) or arbitrary data (False). The first DWord of the Stream contains a UserValue <> 0 that describes the following data. Most common is this an UserID where the User code knows what Object to create. The second DWord of the Stream contains the length of the remaining data. If this value is 0, no bytes are following.
|
TLQTWriteStreamItemEvent = procedure(AOwner : TLazQuadTree; ANode : TLQTNode; AItem : TObject; AItemIndex : Integer; AStream : TStream) of object; |
TLQTWriteStreamItemEvent The event is used within the tree stream reading method. An event which has to write an Object to the given Stream. The data is user dependend, but has to follow the general rule of writing data into the .lqtf-File. The first DWord that is written to the Stream mus be an UserID which allows the User code to reconstruct the data on the read procedure. The second DWord will contain the dta length of the remaining data. To ease the write process this value is calculated by the caller, but the space must reserved, by writing an DWord value 0
|
TLQTCreateNodeEvent = function (AOwner : TLazQuadTree; AParentNode : TLQTNode; ALQTRect : TLQTRect; ANodeToken : Cardinal = 0) : TLQTNode of object; |
TLQTCreateNodeEvent An Event which has to return a new created QuadNode. This event could be used to insert derived nodes into the QuadTree. Parameter AOwner the tree where the node belongs to. AParentNode the parent node (if Assigned, otherwise RootNode) ALQTRect the NodeRectangle (see ANodeToken) for an important remark. ANodeToken if the parameter is 0 then the function has to create an node by the provided information in the passed Owner and ParentNode. The function may decide to return Nil, in this case the caller will create a default Node. If the parameter is not 0 then the value is derived from DefaultLQTNodeToken = $81780000, with a different value at the lower two bytes. In this case the passed value comes from a Stream which is about to be read and the value identify the class which has to be created. In this case the function has to create a class, which is able to read the data from the stream. If this is not possible return Nil Result the creeated class. If the ANodeToken is 0 then Nil will be fine, else the stream reading process ends with an Exception.
|
TLQTGetNodeChildRectEvent = procedure (AOwner : TLazQuadTree; AParentNode : TLQTNode; AChildLocation : TLQTNodeChildLocation; AChangeAllowedTop, AChangeAllowedRight, AChangeAllowedBottom, AChangeAllowedLeft : Boolean; var AChildRect : TLQTRect) of object; |
TLQTGetNodeChildRectEvent This event is called whenever a queried ChildRect Size is variable, e.g. not fixed by other childrens positions. It allows to modify the suggested ChildRect. The purpose is to shift the borders between the newly created children so that a uniform distribution of the items between the nodes are possible. If using non point items (e.g. Shapes of countries, tracks) a good selection of borders, help to avoid inefficent long list of Items at a high level. On a globe, the 0°-Longitude crosses a long list of countries, which by default all will be placed on the root node. By moving the division to -25° this could be reduced to one country. Caution: Asking the AParentNode for other ChildRects may cause a recursive call of this event! Asking the ParentNode for its NodeRect is always possible since this Rect is fixed. The parameters AChangeAllowedTop, ... , ...Left indicates, which of the field of the AChildRect could be modified. Modification of the not allowed fields are ignored.
|
Constants
DefaultMaxTreeLevel = 25; |
DefaultMaxTreeLevel: Each level quaters the area of the level above. Subsequently the one Node in Level 25 contains, if used as an earth map, roughly one squaremeter (at the equator). Keep in mind that the amount of Items that *could* be stored increases very fast. The default is about 1280 TerraItems, far beyond what can be actually processed. Used as initial value of the MaxQuadTreeLevel property of the QuadTree.
|
DefaultMaxNodeItemCount = 4; |
DefaultMaxNodeItemCount: If a node contains more items, it will be split in subnodes. Used as initial value of the MaxQuadNodeItemCount property of the QuadTree. if the items are close together, this will be continued until MaxLazQuadTreeLevels is reached
|
QuadTreeFileExtension = '.lqtf'; |
QuadTreeFileExtension defines the default file extension of a QuadTree-File
|
QuadTreeFileStartCode = $ED6C5154; |
QuadTreeFileStartCode the first few bytes in the File(!) indicating a QuadTree following
|
DefaultQuadTreeToken = $51540000; |
DefaultQuadTreeToken indicates the trunk with a QuadTree definition the last two bytes could be used to identify different QuadTree-Class-Descendants
|
DefaultLQTNodeToken = $514E0000; |
DefaultLQTNodeToken indicates the trunk with a QuadNode definition the last two bytes could be used to identify different QuadNode-Class-Descendants
|
DefaultQuadTreeStreamDataVersion = $00000000; |
DefaultQuadTreeStreamDataVersion a const that allows modification within the data of a QuadTree and the backward compatibilty of writen Streams The 4 bytes are used as follow AABBCCDD ˆ ˆ ˆ ˆ—— User Tree Minor changes | | +———User Tree Major changes | +———–Unit Tree Minor changes +————-Unit Tree Major changes The code in this unit will raise an exception on read from stream if the two Unit Bytes are not reflected in the code. The two UserBytes are user implementation dependend and ignored.
|
DefaultLQTNodeStreamDataVersion = $00000000; |
DefaultLQTNodeStreamDataVersion a const that allows modification within the data of a QuadNode and the backward compatibilty of writen Streams The 4 bytes are used as follow AABBCCDD ˆ ˆ ˆ ˆ—— User Node Minor changes | | +———User Node Major changes | +———–Unit Node Minor changes +————-Unit Node Major changes The code in this unit will raise an exception on read from stream if the two Unit Bytes are not reflected in the code. The two UserBytes are user implementation dependend and ignored.
|
lqtStreamDataVersionUnitMajorMask = $FF000000; |
lqtStreamDataVersionXXXMasks can be used to "and" with the received Mask Value
|
lqtStreamDataVersionUnitMinorMask = $00FF0000; |
|
lqtStreamDataVersionUserMajorMask = $0000FF00; |
|
lqtStreamDataVersionUserMinorMask = $000000FF; |
|
lqtStreamDataVersionUnitMajorShr = 24; |
lqtStreamDataVersionXXXShr can be used to shift the "anded" Value to the right
|
lqtStreamDataVersionUnitMinorShr = 16; |
|
lqtStreamDataVersionUserMajorShr = 8; |
|
lqtStreamDataVersionUserMinorShr = 0; |
|
srofLazyLengthProcessing = $00000001; |
srofLazyLengthProcessing If the length of a Trunk is longer than read, the remainder is skipped without error
|
LQTNodeChildLocationStrings : array[TLQTNodeChildLocation] of String = (
'NorthEast','SouthEast', 'SouthWest', 'NorthWest'); |
|
Generated by PasDoc 0.16.0.