This is the kdtree-jk Reference Manual, generated automatically by Declt version 4.0 beta 2 "William Riker" on Mon Feb 26 16:50:10 2024 GMT+0.
The main system appears first, followed by any subsystem dependency.
kdtree-jkKD-TREE package for searching for nearest neighbors in N points in in M-dimensions in N log(N) time.
MIT
kdtree-jk-package.lisp (file).
kdtree-jk-structs.lisp (file).
kdtree-jk-utils.lisp (file).
kdtree-jk-balance.lisp (file).
kdtree-jk-insert.lisp (file).
kdtree-jk-search.lisp (file).
Files are sorted by type and then listed depth-first from the systems components trees.
kdtree-jk/kdtree-jk.asdkdtree-jk/kdtree-jk-package.lispkdtree-jk/kdtree-jk-structs.lispkdtree-jk/kdtree-jk-utils.lispkdtree-jk/kdtree-jk-balance.lispkdtree-jk/kdtree-jk-insert.lispkdtree-jk/kdtree-jk-search.lispkdtree-jk/kdtree-jk-structs.lispkdtree-jk-package.lisp (file).
kdtree-jk (system).
bbox (structure).
bbox-ndim (reader).
(setf bbox-ndim) (writer).
bbox-p (function).
bbox-rmax-vec (reader).
(setf bbox-rmax-vec) (writer).
bbox-rmin-vec (reader).
(setf bbox-rmin-vec) (writer).
build-kdtree (function).
describe-node (function).
dimnum (type).
index (type).
kd-float (type).
kdresult (structure).
kdresult-dist-vec (reader).
(setf kdresult-dist-vec) (writer).
kdresult-index-vec (reader).
(setf kdresult-index-vec) (writer).
kdresult-n (reader).
(setf kdresult-n) (writer).
kdresult-obj-vec (reader).
(setf kdresult-obj-vec) (writer).
kdresult-p (function).
kdtree (structure).
kdtree-avg-depth (reader).
(setf kdtree-avg-depth) (writer).
kdtree-bbox (reader).
(setf kdtree-bbox) (writer).
kdtree-idepth (reader).
(setf kdtree-idepth) (writer).
kdtree-ndim (reader).
(setf kdtree-ndim) (writer).
kdtree-npoints (reader).
(setf kdtree-npoints) (writer).
kdtree-obj-vec (reader).
(setf kdtree-obj-vec) (writer).
kdtree-p (function).
kdtree-r-vec (reader).
(setf kdtree-r-vec) (writer).
+empty+ (constant).
+end+ (constant).
+filled+ (constant).
+most-positive-float+ (constant).
copy-bbox (function).
copy-kdresult (function).
copy-kdtree (function).
dimvec (type).
flagvec (type).
indexvec (type).
kd-flag (type).
kdfltarr (type).
kdfltvec (type).
kdtree-flag-vec (reader).
(setf kdtree-flag-vec) (writer).
kdtree-index-left-vec (reader).
(setf kdtree-index-left-vec) (writer).
kdtree-index-right-vec (reader).
(setf kdtree-index-right-vec) (writer).
kdtree-ir-vec (reader).
(setf kdtree-ir-vec) (writer).
kdtree-needs-balancing (reader).
(setf kdtree-needs-balancing) (writer).
kdtree-npoints-total (reader).
(setf kdtree-npoints-total) (writer).
kdtree-sd-vec (reader).
(setf kdtree-sd-vec) (writer).
make-bbox (function).
make-dimvec (function).
make-flagvec (function).
make-indexvec (function).
make-kdfltarr (function).
make-kdfltvec (function).
make-kdresult (function).
make-kdtree (function).
make-objvec (function).
objvec (type).
kdtree-jk/kdtree-jk-utils.lispkdtree-jk-package.lisp (file).
kdtree-jk-structs.lisp (file).
kdtree-jk (system).
%remove-deleted-objects (function).
partition-ir-vec-around-median (function).
kdtree-jk/kdtree-jk-balance.lispkdtree-jk-structs.lisp (file).
kdtree-jk-utils.lisp (file).
kdtree-jk (system).
balance-kdtree (function).
kdtree-jk/kdtree-jk-insert.lispkdtree-jk-structs.lisp (file).
kdtree-jk-balance.lisp (file).
kdtree-jk (system).
insert-2d (function).
insert-3d (function).
insert-vector (function).
kdtree-minimize-size (function).
make-deletion-action (function).
make-search-action (function).
%expand-kdtree (function).
%insert-into-kd (function).
*kdtree-expansion-factor* (special variable).
kdtree-jk/kdtree-jk-search.lispkdtree-jk-structs.lisp (file).
kdtree-jk-balance.lisp (file).
kdtree-jk (system).
build-bbox (function).
build-kdresult (function).
kd-find-k-nearest (function).
kd-find-nearest-point (function).
kd-search-in-bbox (function).
kd-search-in-radius (function).
%expand-kdresult (function).
%insert-point-in-kdresult (function).
sort-kdresult-by-radius (function).
Packages are listed by definition order.
kdtree-jkcommon-lisp.
balance-kdtree (function).
bbox (structure).
bbox-ndim (reader).
(setf bbox-ndim) (writer).
bbox-p (function).
bbox-rmax-vec (reader).
(setf bbox-rmax-vec) (writer).
bbox-rmin-vec (reader).
(setf bbox-rmin-vec) (writer).
build-bbox (function).
build-kdresult (function).
build-kdtree (function).
describe-node (function).
dimnum (type).
index (type).
insert-2d (function).
insert-3d (function).
insert-vector (function).
kd-find-k-nearest (function).
kd-find-nearest-point (function).
kd-float (type).
kd-search-in-bbox (function).
kd-search-in-radius (function).
kdresult (structure).
kdresult-dist-vec (reader).
(setf kdresult-dist-vec) (writer).
kdresult-index-vec (reader).
(setf kdresult-index-vec) (writer).
kdresult-n (reader).
(setf kdresult-n) (writer).
kdresult-obj-vec (reader).
(setf kdresult-obj-vec) (writer).
kdresult-p (function).
kdtree (structure).
kdtree-avg-depth (reader).
(setf kdtree-avg-depth) (writer).
kdtree-bbox (reader).
(setf kdtree-bbox) (writer).
kdtree-idepth (reader).
(setf kdtree-idepth) (writer).
kdtree-minimize-size (function).
kdtree-ndim (reader).
(setf kdtree-ndim) (writer).
kdtree-npoints (reader).
(setf kdtree-npoints) (writer).
kdtree-obj-vec (reader).
(setf kdtree-obj-vec) (writer).
kdtree-p (function).
kdtree-r-vec (reader).
(setf kdtree-r-vec) (writer).
make-deletion-action (function).
make-search-action (function).
%expand-kdresult (function).
%expand-kdtree (function).
%insert-into-kd (function).
%insert-point-in-kdresult (function).
%remove-deleted-objects (function).
*kdtree-expansion-factor* (special variable).
+empty+ (constant).
+end+ (constant).
+filled+ (constant).
+most-positive-float+ (constant).
copy-bbox (function).
copy-kdresult (function).
copy-kdtree (function).
dimvec (type).
flagvec (type).
indexvec (type).
kd-flag (type).
kdfltarr (type).
kdfltvec (type).
kdtree-flag-vec (reader).
(setf kdtree-flag-vec) (writer).
kdtree-index-left-vec (reader).
(setf kdtree-index-left-vec) (writer).
kdtree-index-right-vec (reader).
(setf kdtree-index-right-vec) (writer).
kdtree-ir-vec (reader).
(setf kdtree-ir-vec) (writer).
kdtree-needs-balancing (reader).
(setf kdtree-needs-balancing) (writer).
kdtree-npoints-total (reader).
(setf kdtree-npoints-total) (writer).
kdtree-sd-vec (reader).
(setf kdtree-sd-vec) (writer).
make-bbox (function).
make-dimvec (function).
make-flagvec (function).
make-indexvec (function).
make-kdfltarr (function).
make-kdfltvec (function).
make-kdresult (function).
make-kdtree (function).
make-objvec (function).
objvec (type).
partition-ir-vec-around-median (function).
sort-kdresult-by-radius (function).
Definitions are sorted by export status, category, package, and then by lexicographic order.
Balances a KDTREE by ensuring that each node splits the remaining set in 2.
Also removes any deleted objects (objects with object-vec set to
’DELETED-OBJECT)
This seems to be a N [log(n)]^2 operation.
ndim.
Build a Bounding Box (BBOX). MIN-VEC and MAX-VEC are sequences representing the bounds.
Build a KDTREE with NDIM dimensions and NPOINTS of storage, initially.
Describe a node in the KDTREE, to STREAM.
Insert X,Y into 2d KDTREE.
Insert X,Y,Z into 3d KDTREE.
Insert a vector V corresponding to OBJECT into NDIM KDTREE,
returning the index where it ended up.
If DEFER keyword is set, then the tree-insertion is deferred to save time, but it will be necessary to run BALANCE-KDTREE before use. This is useful for creating a balanced tree from unbalanced or nonrandom data.
Find k-nearest objects in KDTREE, by doing increasing radial
searches. The returned KDRESULT will contain at least K-NEAREST points, sorted
by radius. It us up to the user to truncate the result to the first
K-NEAREST.
RSTART is an optional starting radius size. By default, it it set using
the volume fraction expected to be occupied by K-NEAREST points.
Returns the number of search iterations as the second value.
The ACTION keyword is not supported because the result is not know
before the end of the search.
Find the single nearest point to vector V in KDTREE.
A wrapper for:
(KD-SEARCH-IN-RADIUS KDTREE V HUGE-RADIUS :KDRESULT KDRESULT NEAREST-POINT T)
The ACTION keyword is not supported because the result is not known
before the end of the search.
Search KDTREE for points inside bounding box BBOX (of type BBOX). If keyword :KDRESULT
is NIL, then a KDRESULT will be created. Otherwise, given KDRESULT will be used to
return the result.
If ACTION is supplied, than it is applied to each matching point, and
KDRESULT is ignored and set to NIL.
It is called as (FUNCALL ACTION INODE) where INODE is the linear index of a node.
:ACTION (MAKE-DELETION-ACTION), for example, deletes an element by setting its value to a special symbol ’DELETED-OBJECT.
Search KDTREE for points within RADIUS of float vector V. If
keyword :KDRESULT is NIL, then a KDRESULT will be created. Otherwise,
given KDRESULT will be used to return the result.
If NEAREST-POINT is set, return just the nearest point. This is
especially efficient because the internal search radius keeps
shrinking.
If SORT is true, then the KDRESULT is sorted by increasing distance
from point given.
If ACTION is supplied, than it is applied to each matching point, and
KDRESULT is ignored and set to NIL.
It is called as (FUNCALL ACTION INODE) where INODE is the linear index of a node.
:ACTION (MAKE-DELETION-ACTION), for example, deletes any element returned by search by setting its value to a special symbol ’DELETED-OBJECT.
n.
bbox.
Make the arrays in KDTREE just large enough to hold the data.
ndim.
Function to generate a function to pass as an :ACTION, to delete
objects according to :TEST.
TEST is an optional function taking the OBJECT inside KDTREE-OBJ-VEC,
returning T if this object is to be deleted.
For example,
(MAKE-DELETION-ACTION (LAMBDA (OBJ) (EQ OBJ *MY-OBJ*)))
will return an action to delete objects EQ to *MY-OBJ*
that are picked up by the search.
and
(MAKE-DELETION-ACTION) will return an action to
delete all objects picked up by the KDTREE search.
Make a function that can be passed as an :ACTION to search functions, that will (FUNCALL OBJECT-FUNCTION OBJECT) to each object in KDTREE-OBJECT-VEC that falls inside the search.
structure-object.
(unsigned-byte 32)
0
kdtree-jk::kdfltvec
(kdtree-jk::make-kdfltvec 0)
kdtree-jk::kdfltvec
(kdtree-jk::make-kdfltvec 0)
structure-object.
(unsigned-byte 32)
0
kdtree-jk::objvec
(kdtree-jk::make-objvec 0)
kdtree-jk::indexvec
(kdtree-jk::make-indexvec 0)
kdtree-jk::kdfltvec
(kdtree-jk::make-kdfltvec 0)
structure-object.
(unsigned-byte 16)
0
(unsigned-byte 32)
0
(or null t)
(unsigned-byte 20)
0
double-float
0.0d0
(unsigned-byte 32)
0
kdtree-jk::flagvec
(kdtree-jk::make-flagvec 0 kdtree-jk::+empty+)
kdtree-jk::indexvec
(kdtree-jk::make-indexvec 0 kdtree-jk::+end+)
kdtree-jk::indexvec
(kdtree-jk::make-indexvec 0 kdtree-jk::+end+)
kdtree-jk::indexvec
(kdtree-jk::make-indexvec 0 kdtree-jk::+end+)
kdtree-jk::objvec
(make-array 0)
kdtree-jk::dimvec
(kdtree-jk::make-dimvec 0)
kdtree-jk::kdfltarr
(kdtree-jk::make-kdfltarr 0 0)
kdtree-jk:bbox
(kdtree-jk::make-bbox)
| Jump to: | %
(
B C D F I K M P S |
|---|
| Jump to: | %
(
B C D F I K M P S |
|---|
| Jump to: | *
+
A B C D F I N O R S |
|---|
| Jump to: | *
+
A B C D F I N O R S |
|---|
| Jump to: | B D F I K O P S T |
|---|
| Jump to: | B D F I K O P S T |
|---|