Next: Introduction, Previous: (dir), Up: (dir) [Contents][Index]
This is the quadtree Reference Manual, version 0.1, generated automatically by Declt version 2.4 "Will Decker" on Wed Jun 20 12:28:16 2018 GMT+0.
| • Introduction: | What quadtree is all about | |
| • Systems: | The systems documentation | |
| • Modules: | The modules documentation | |
| • Files: | The files documentation | |
| • Packages: | The packages documentation | |
| • Definitions: | The symbols documentation | |
| • Indexes: | Concepts, functions, variables and data types |
Quadtree is quadtree data structure in Common Lisp.
Here shows how to store points into a quadtree.
First, define point structure.
(defstruct (point (:constructor make-point (x y)))
(x 0d0 :read-only t)
(y 0d0 :read-only t))
Then, implement an intersection test method for the point structure, which is called when inserting points to a quadtree.
(defmethod quadtree:intersect-p (quadtree (point point))
(destructuring-bind (x0 y0 x1 y1) (quadtree:boundary quadtree)
(let ((x (point-x point))
(y (point-y point)))
(and (<= x0 x x1) (<= y0 y y1)))))
Now, make and bulid a quadtree with its boundary, query it to get points stored in the leaf that contains specified x and y.
(let ((points (list (make-point 0.0d0 0.0d0)
(make-point 1.0d0 1.0d0)
(make-point 0.1d0 0.1d0)
(make-point 0.1d0 0.2d0)
(make-point 0.2d0 0.1d0)
(make-point 0.2d0 0.2d0)
(make-point 0.2d0 0.3d0)
(make-point 0.2d0 0.4d0)
(make-point 0.3d0 0.2d0)
(make-point 0.3d0 0.3d0))))
;; make a quadtree with its boundary
(let ((qt (quadtree:make 0.0d0 0.0d0 1.0d0 1.0d0)))
;; build the quadtree
(loop for point in points
do (quadtree:insert qt point))
;; query the quadtree
(is (length (quadtree:query qt 0.1 0.1)) 5)))
Since quadtree is just requesting to Quicklisp, plese use its local-projects feature for now.
$ cd quicklisp/local-projects
$ git clone git://github.com/takagi/quadtree.git
After approved, you can install via Quicklisp.
(ql:quickload :quadtree)
Specifies the maximum depth of a newly created quadtree.
Specifies the maximum capacity of leaves of a newly created quadtree.
MAKE x0 y0 x1 y1 &key max-depth max-capacity => quadtree
Creates an empty quadtree with the boundary of x0, y0, x1 and y1. max-depth specifies the maxinum depth of a quadtree and its default value is provided by *max-depth* special variable. max-capacity is the maxinum capacity of a quadtree leaf, subdevided if the value is exceeded, and its default value is provided by *max-capacity* special variable. However, leaves at the maximum depth contain all inserted objects regardless of the capacity.
INSERT quadtree object => boolean
Inserts object to quadtree. If suceeded, returns t. Otherwise, returns nil. The case it fails to inserted an object to a quadtree is that it is out of boundary of the quadtree. If the number of objects in a leaf is exceeded, the leaf is subdevided into four subtrees and its objects are distributed to them.
QUERY quadtree x y &optional neighbor-p => object-list
Queries objects at the point (x, y) to quadtree. If neighbor-p is nil, returns objects stored in the leaf that contains the point. Otherwise, additionally returns objects stored in leaves neighboring top, bottom, left and right to the leaf that contains the point. The default value of neighbor-p is nil.
CLEAR quadtree => boolean
Clears the contents of quadtree. The return value is always t.
BOUNDARY quadtree => boundary
Returns the boundary of quadtree, represented by a list of x0, y0, x1 and y1. It is intended to be used in following intersect-p function to determine if an object intersects a quadtree.
INTERSECT-P quadtree object => boolean
Called when object is being inserted to quadtree which stores objects and returns if object intersects quadtree. Library users should implement this generic function as the object's structure or class they are storing into a quadtree.
Copyright (c) 2015 Masayuki Takagi (kamonama@gmail.com)
Licensed under the MIT License.
Next: Modules, Previous: Introduction, Up: Top [Contents][Index]
The main system appears first, followed by any subsystem dependency.
| • The quadtree system: |
Masayuki Takagi
MIT
Quadtree data structure in Common Lisp
# Quadtree
[](https://travis-ci.org/takagi/quadtree)
[](https://coveralls.io/r/takagi/quadtree?branch=master)
Quadtree is quadtree data structure in Common Lisp.
## Usage
Here shows how to store points into a quadtree.
First, define point structure.
(defstruct (point (:constructor make-point (x y)))
(x 0d0 :read-only t)
(y 0d0 :read-only t))
Then, implement an intersection test method for the point structure, which is called when inserting points to a quadtree.
(defmethod quadtree:intersect-p (quadtree (point point))
(destructuring-bind (x0 y0 x1 y1) (quadtree:boundary quadtree)
(let ((x (point-x point))
(y (point-y point)))
(and (<= x0 x x1) (<= y0 y y1)))))
Now, make and bulid a quadtree with its boundary, query it to get points stored in the leaf that contains specified ‘x‘ and ‘y‘.
(let ((points (list (make-point 0.0d0 0.0d0)
(make-point 1.0d0 1.0d0)
(make-point 0.1d0 0.1d0)
(make-point 0.1d0 0.2d0)
(make-point 0.2d0 0.1d0)
(make-point 0.2d0 0.2d0)
(make-point 0.2d0 0.3d0)
(make-point 0.2d0 0.4d0)
(make-point 0.3d0 0.2d0)
(make-point 0.3d0 0.3d0))))
;; make a quadtree with its boundary
(let ((qt (quadtree:make 0.0d0 0.0d0 1.0d0 1.0d0)))
;; build the quadtree
(loop for point in points
do (quadtree:insert qt point))
;; query the quadtree
(is (length (quadtree:query qt 0.1 0.1)) 5)))
## Installation
Since quadtree is just requesting to Quicklisp, plese use its local-projects feature for now.
$ cd quicklisp/local-projects
$ git clone git://github.com/takagi/quadtree.git
After approved, you can install via Quicklisp.
(ql:quickload :quadtree)
## API
### [Special Variable] \*max-depth\*
Specifies the maximum depth of a newly created quadtree.
### [Special Variable] \*max-capacity\*
Specifies the maximum capacity of leaves of a newly created quadtree.
### [Function] make
MAKE x0 y0 x1 y1 &key max-depth max-capacity => quadtree
Creates an empty quadtree with the boundary of ‘x0‘, ‘y0‘, ‘x1‘ and ‘y1‘. ‘max-depth‘ specifies the maxinum depth of a quadtree and its default value is provided by ‘*max-depth*‘ special variable. ‘max-capacity‘ is the maxinum capacity of a quadtree leaf, subdevided if the value is exceeded, and its default value is provided by ‘*max-capacity*‘ special variable. However, leaves at the maximum depth contain all inserted objects regardless of the capacity.
### [Function] insert
INSERT quadtree object => boolean
Inserts ‘object‘ to ‘quadtree‘. If suceeded, returns ‘t‘. Otherwise, returns ‘nil‘. The case it fails to inserted an object to a quadtree is that it is out of boundary of the quadtree. If the number of objects in a leaf is exceeded, the leaf is subdevided into four subtrees and its objects are distributed to them.
### [Function] query
QUERY quadtree x y &optional neighbor-p => object-list
Queries objects at the point ‘(x, y)‘ to ‘quadtree‘. If ‘neighbor-p‘ is ‘nil‘, returns objects stored in the leaf that contains the point. Otherwise, additionally returns objects stored in leaves neighboring top, bottom, left and right to the leaf that contains the point. The default value of ‘neighbor-p‘ is ‘nil‘.
### [Function] clear
CLEAR quadtree => boolean
Clears the contents of ‘quadtree‘. The return value is always ‘t‘.
### [Function] boundary
BOUNDARY quadtree => boundary
Returns the boundary of ‘quadtree‘, represented by a list of ‘x0‘, ‘y0‘, ‘x1‘ and ‘y1‘. It is intended to be used in following ‘intersect-p‘ function to determine if an object intersects a quadtree.
### [Generic Function] intersect-p
INTERSECT-P quadtree object => boolean
Called when ‘object‘ is being inserted to ‘quadtree‘ which stores objects and returns if ‘object‘ intersects ‘quadtree‘. Library users should implement this generic function as the object’s structure or class they are storing into a quadtree.
## Author
* Masayuki Takagi (kamonama@gmail.com)
## Copyright
Copyright (c) 2015 Masayuki Takagi (kamonama@gmail.com)
## License
Licensed under the MIT License.
0.1
quadtree.asd (file)
src (module)
Modules are listed depth-first from the system components tree.
| • The quadtree/src module: |
quadtree (system)
src/
quadtree.lisp (file)
Files are sorted by type and then listed depth-first from the systems components trees.
| • Lisp files: |
| • The quadtree.asd file: | ||
| • The quadtree/src/quadtree.lisp file: |
Next: The quadtree/src/quadtree<dot>lisp file, Previous: Lisp files, Up: Lisp files [Contents][Index]
quadtree.asd
quadtree (system)
Previous: The quadtree<dot>asd file, Up: Lisp files [Contents][Index]
src (module)
src/quadtree.lisp
Next: Definitions, Previous: Files, Up: Top [Contents][Index]
Packages are listed by definition order.
| • The quadtree-asd package: | ||
| • The quadtree package: |
Next: The quadtree package, Previous: Packages, Up: Packages [Contents][Index]
quadtree.asd
Previous: The quadtree-asd package, Up: Packages [Contents][Index]
quadtree.lisp (file)
common-lisp
Definitions are sorted by export status, category, package, and then by lexicographic order.
| • Exported definitions: | ||
| • Internal definitions: |
Next: Internal definitions, Previous: Definitions, Up: Definitions [Contents][Index]
| • Exported special variables: | ||
| • Exported functions: | ||
| • Exported generic functions: |
Next: Exported functions, Previous: Exported definitions, Up: Exported definitions [Contents][Index]
quadtree.lisp (file)
quadtree.lisp (file)
Next: Exported generic functions, Previous: Exported special variables, Up: Exported definitions [Contents][Index]
quadtree.lisp (file)
quadtree.lisp (file)
quadtree.lisp (file)
quadtree.lisp (file)
quadtree.lisp (file)
Previous: Exported functions, Up: Exported definitions [Contents][Index]
Returns if the object intersects the quadtree
quadtree.lisp (file)
Previous: Exported definitions, Up: Definitions [Contents][Index]
| • Internal functions: | ||
| • Internal structures: |
Next: Internal structures, Previous: Internal definitions, Up: Internal definitions [Contents][Index]
quadtree.lisp (file)
quadtree.lisp (file)
quadtree.lisp (file)
quadtree.lisp (file)
quadtree.lisp (file)
quadtree.lisp (file)
quadtree.lisp (file)
quadtree.lisp (file)
quadtree.lisp (file)
quadtree.lisp (file)
quadtree.lisp (file)
quadtree.lisp (file)
quadtree.lisp (file)
quadtree.lisp (file)
quadtree.lisp (file)
quadtree.lisp (file)
quadtree.lisp (file)
quadtree.lisp (file)
quadtree.lisp (file)
quadtree.lisp (file)
Previous: Internal functions, Up: Internal definitions [Contents][Index]
quadtree.lisp (file)
structure-object (structure)
quadtree-objects (function)
(setf quadtree-objects) (function)
quadtree-nw (function)
(setf quadtree-nw) (function)
quadtree-ne (function)
(setf quadtree-ne) (function)
quadtree-sw (function)
(setf quadtree-sw) (function)
quadtree-se (function)
(setf quadtree-se) (function)
quadtree-boundary (function)
(setf quadtree-boundary) (function)
quadtree-depth (function)
(setf quadtree-depth) (function)
quadtree-max-depth (function)
(setf quadtree-max-depth) (function)
quadtree-max-capacity (function)
(setf quadtree-max-capacity) (function)
Previous: Definitions, Up: Top [Contents][Index]
| • Concept index: | ||
| • Function index: | ||
| • Variable index: | ||
| • Data type index: |
Next: Function index, Previous: Indexes, Up: Indexes [Contents][Index]
| Jump to: | F L M Q |
|---|
| Jump to: | F L M Q |
|---|
Next: Variable index, Previous: Concept index, Up: Indexes [Contents][Index]
| Jump to: | %
(
B C F G I L M N P Q R S |
|---|
| Jump to: | %
(
B C F G I L M N P Q R S |
|---|
Next: Data type index, Previous: Function index, Up: Indexes [Contents][Index]
| Jump to: | *
B D M N O S |
|---|
| Jump to: | *
B D M N O S |
|---|
Previous: Variable index, Up: Indexes [Contents][Index]
| Jump to: | P Q S |
|---|
| Jump to: | P Q S |
|---|