KDPointTree¶

A 2D version of a KDTree for TPoint datatype

Note: For more dimensions, and/or floating point values, along with category or index reference see TKDTree.

TKDPointTree.Create¶

function TKDPointTree.Create(TPA: TPointArray): TKDPointTree; static;

Builds the KDTree. Time complexity average is O(n log n)

TKDPointTree.IndexOf¶

function TKDPointTree.IndexOf(P: TPoint): Integer;

Search and find the index for use in TKDPointTree.Data for a given point p

Time complexity average is O(log n)

TKDPointTree.Find¶

function TKDPointTree.Find(P: TPoint): PSlackNode;

Search and find the given point p, returns a node, a pointer to the tree node.

Time complexity average is O(log n)

TKDPointTree.Hide¶

procedure TKDPointTree.Hide(idx:Integer);

Hide the node (by index) so that queries will not return it.

Time complexity average is O(1)

TKDPointTree.Hide¶

function TKDPointTree.Hide(P: TPoint): Boolean; overload;

Hide the node (by TPoint) so that queries will not return it.

Time complexity average is O(log n)

TKDPointTree.RawNearest¶

function TKDPointTree.RawNearest(P: TPoint; NotEqual: Boolean = False): PSlackNode;

Returns the closest node to the point given.

Time complexity average is O(log n)

TKDPointTree.Nearest¶

function TKDPointTree.Nearest(P: TPoint; NotEqual :Boolean = False): TPoint;

Returns the closest point to the point given.

Time complexity average is O(log n)

TKDPointTree.RawKNearest¶

function TKDPointTree.RawKNearest(P: TPoint; k:Integer; NotEqual: Boolean = False): TSlackRefArray;

Returns the k closest node to the point given.

Time complexity average is O(k * log n)

TKDPointTree.KNearest¶

function TKDPointTree.KNearest(P: TPoint; k:Integer; NotEqual: Boolean = False): TPointArray;

Returns the k closest points to the point given.

Time complexity average is O(k * log n)

TKDPointTree.RangeQuery¶

function TKDPointTree.RangeQuery(B:TBox; hide:Boolean = False): TPointArray;

Returns all the points that are within the given box.

Time complexity average is O(k * log n) where k is the number of points returned

TKDPointTree.RangeQueryEx¶

function TKDPointTree.RangeQueryEx(query:TPoint; xRad,yRad:Double; hide: Boolean = False): TPointArray;

Returns all the points that are within the given range xRad and yRad.

Time complexity average is O(k * log n) where k is the number of points returned

TKDPointTree.RangeQueryEx¶

function TKDPointTree.RangeQueryEx(query:TPoint; xmin,ymin,xmax,ymax: Double; hide: Boolean = False): TPointArray;

Returns all the points that are further away than xmin, and ymin, but closer than xmax, and ymax from the query.

Time complexity average is O(k * log n) where k is the number of points returned

TKDPointTree.Clusters¶

function TKDPointTree.Clusters(xRad,yRad: Single): T2DPointArray;

Like TPA.Cluster, but acts on the points in the tree, and allows you to use floats for xRad, and yRad. This methods also exists in TKDTree and works in n dimensions.

Time complexity average is between O(n) and O(n log n)

Speedwise, once the tree is built this method is on pair with ClusterTPA.