The quadtree Reference Manual

This is the quadtree Reference Manual, version 0.1, generated automatically by Declt version 4.0 beta 2 "William Riker" on Wed May 15 06:39:16 2024 GMT+0.

Table of Contents


1 Introduction


2 Systems

The main system appears first, followed by any subsystem dependency.


2.1 quadtree

Quadtree data structure in Common Lisp

Author

Masayuki Takagi

License

MIT

Long Description

# Quadtree

[![Build Status](https://travis-ci.org/takagi/quadtree.svg?branch=master)](https://travis-ci.org/takagi/quadtree)
[![Coverage Status](https://coveralls.io/repos/takagi/quadtree/badge.svg?branch=master)](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.

Version

0.1

Source

quadtree.asd.

Child Component

src (module).


3 Modules

Modules are listed depth-first from the system components tree.


3.1 quadtree/src

Source

quadtree.asd.

Parent Component

quadtree (system).

Child Component

quadtree.lisp (file).


4 Files

Files are sorted by type and then listed depth-first from the systems components trees.


4.1 Lisp


4.1.1 quadtree/quadtree.asd

Source

quadtree.asd.

Parent Component

quadtree (system).

ASDF Systems

quadtree.

Packages

quadtree-asd.


4.1.2 quadtree/src/quadtree.lisp

Source

quadtree.asd.

Parent Component

src (module).

Packages

quadtree.

Public Interface
Internals

5 Packages

Packages are listed by definition order.


5.1 quadtree-asd

Source

quadtree.asd.

Use List
  • asdf/interface.
  • common-lisp.

5.2 quadtree

Source

quadtree.lisp.

Use List

common-lisp.

Public Interface
Internals

6 Definitions

Definitions are sorted by export status, category, package, and then by lexicographic order.


6.1 Public Interface


6.1.1 Special variables

Special Variable: *max-capacity*
Package

quadtree.

Source

quadtree.lisp.

Special Variable: *max-depth*
Package

quadtree.

Source

quadtree.lisp.


6.1.2 Ordinary functions

Function: boundary (quadtree)
Package

quadtree.

Source

quadtree.lisp.

Function: clear (quadtree)
Package

quadtree.

Source

quadtree.lisp.

Function: insert (quadtree object)
Package

quadtree.

Source

quadtree.lisp.

Function: make (x0 y0 x1 y1 &key max-depth max-capacity)
Package

quadtree.

Source

quadtree.lisp.

Function: query (quadtree x y &optional neighbor-p)
Package

quadtree.

Source

quadtree.lisp.


6.1.3 Generic functions

Generic Function: intersect-p (quadtree object)

Returns if the object intersects the quadtree

Package

quadtree.

Source

quadtree.lisp.


6.2 Internals


6.2.1 Ordinary functions

Function: %make (x0 y0 x1 y1 depth max-depth max-capacity)
Package

quadtree.

Source

quadtree.lisp.

Function: %make-quadtree (&key objects nw ne sw se boundary depth max-depth max-capacity)
Package

quadtree.

Source

quadtree.lisp.

Function: copy-quadtree (instance)
Package

quadtree.

Source

quadtree.lisp.

Function: full-p (quadtree)
Package

quadtree.

Source

quadtree.lisp.

Function: leaf-p (quadtree)
Package

quadtree.

Source

quadtree.lisp.

Function: max-depth-p (quadtree)
Package

quadtree.

Source

quadtree.lisp.

Function: node-p (quadtree)
Package

quadtree.

Source

quadtree.lisp.

Function: point-intersect-p (quadtree x y)
Package

quadtree.

Source

quadtree.lisp.

Reader: quadtree-boundary (instance)
Writer: (setf quadtree-boundary) (instance)
Package

quadtree.

Source

quadtree.lisp.

Target Slot

boundary.

Reader: quadtree-depth (instance)
Writer: (setf quadtree-depth) (instance)
Package

quadtree.

Source

quadtree.lisp.

Target Slot

depth.

Reader: quadtree-max-capacity (instance)
Writer: (setf quadtree-max-capacity) (instance)
Package

quadtree.

Source

quadtree.lisp.

Target Slot

max-capacity.

Reader: quadtree-max-depth (instance)
Writer: (setf quadtree-max-depth) (instance)
Package

quadtree.

Source

quadtree.lisp.

Target Slot

max-depth.

Reader: quadtree-ne (instance)
Writer: (setf quadtree-ne) (instance)
Package

quadtree.

Source

quadtree.lisp.

Target Slot

ne.

Reader: quadtree-nw (instance)
Writer: (setf quadtree-nw) (instance)
Package

quadtree.

Source

quadtree.lisp.

Target Slot

nw.

Reader: quadtree-objects (instance)
Writer: (setf quadtree-objects) (instance)
Package

quadtree.

Source

quadtree.lisp.

Target Slot

objects.

Function: quadtree-p (object)
Package

quadtree.

Source

quadtree.lisp.

Reader: quadtree-se (instance)
Writer: (setf quadtree-se) (instance)
Package

quadtree.

Source

quadtree.lisp.

Target Slot

se.

Reader: quadtree-sw (instance)
Writer: (setf quadtree-sw) (instance)
Package

quadtree.

Source

quadtree.lisp.

Target Slot

sw.

Function: root-p (quadtree)
Package

quadtree.

Source

quadtree.lisp.

Function: subdevide (quadtree)
Package

quadtree.

Source

quadtree.lisp.


6.2.2 Structures

Structure: quadtree
Package

quadtree.

Source

quadtree.lisp.

Direct superclasses

structure-object.

Direct slots
Slot: objects
Readers

quadtree-objects.

Writers

(setf quadtree-objects).

Slot: nw
Readers

quadtree-nw.

Writers

(setf quadtree-nw).

Slot: ne
Readers

quadtree-ne.

Writers

(setf quadtree-ne).

Slot: sw
Readers

quadtree-sw.

Writers

(setf quadtree-sw).

Slot: se
Readers

quadtree-se.

Writers

(setf quadtree-se).

Slot: boundary
Readers

quadtree-boundary.

Writers

(setf quadtree-boundary).

Slot: depth
Readers

quadtree-depth.

Writers

(setf quadtree-depth).

Slot: max-depth
Readers

quadtree-max-depth.

Writers

(setf quadtree-max-depth).

Slot: max-capacity
Readers

quadtree-max-capacity.

Writers

(setf quadtree-max-capacity).


Appendix A Indexes


A.1 Concepts


A.2 Functions

Jump to:   %   (  
B   C   F   G   I   L   M   N   P   Q   R   S  
Index Entry  Section

%
%make: Private ordinary functions
%make-quadtree: Private ordinary functions

(
(setf quadtree-boundary): Private ordinary functions
(setf quadtree-depth): Private ordinary functions
(setf quadtree-max-capacity): Private ordinary functions
(setf quadtree-max-depth): Private ordinary functions
(setf quadtree-ne): Private ordinary functions
(setf quadtree-nw): Private ordinary functions
(setf quadtree-objects): Private ordinary functions
(setf quadtree-se): Private ordinary functions
(setf quadtree-sw): Private ordinary functions

B
boundary: Public ordinary functions

C
clear: Public ordinary functions
copy-quadtree: Private ordinary functions

F
full-p: Private ordinary functions
Function, %make: Private ordinary functions
Function, %make-quadtree: Private ordinary functions
Function, (setf quadtree-boundary): Private ordinary functions
Function, (setf quadtree-depth): Private ordinary functions
Function, (setf quadtree-max-capacity): Private ordinary functions
Function, (setf quadtree-max-depth): Private ordinary functions
Function, (setf quadtree-ne): Private ordinary functions
Function, (setf quadtree-nw): Private ordinary functions
Function, (setf quadtree-objects): Private ordinary functions
Function, (setf quadtree-se): Private ordinary functions
Function, (setf quadtree-sw): Private ordinary functions
Function, boundary: Public ordinary functions
Function, clear: Public ordinary functions
Function, copy-quadtree: Private ordinary functions
Function, full-p: Private ordinary functions
Function, insert: Public ordinary functions
Function, leaf-p: Private ordinary functions
Function, make: Public ordinary functions
Function, max-depth-p: Private ordinary functions
Function, node-p: Private ordinary functions
Function, point-intersect-p: Private ordinary functions
Function, quadtree-boundary: Private ordinary functions
Function, quadtree-depth: Private ordinary functions
Function, quadtree-max-capacity: Private ordinary functions
Function, quadtree-max-depth: Private ordinary functions
Function, quadtree-ne: Private ordinary functions
Function, quadtree-nw: Private ordinary functions
Function, quadtree-objects: Private ordinary functions
Function, quadtree-p: Private ordinary functions
Function, quadtree-se: Private ordinary functions
Function, quadtree-sw: Private ordinary functions
Function, query: Public ordinary functions
Function, root-p: Private ordinary functions
Function, subdevide: Private ordinary functions

G
Generic Function, intersect-p: Public generic functions

I
insert: Public ordinary functions
intersect-p: Public generic functions

L
leaf-p: Private ordinary functions

M
make: Public ordinary functions
max-depth-p: Private ordinary functions

N
node-p: Private ordinary functions

P
point-intersect-p: Private ordinary functions

Q
quadtree-boundary: Private ordinary functions
quadtree-depth: Private ordinary functions
quadtree-max-capacity: Private ordinary functions
quadtree-max-depth: Private ordinary functions
quadtree-ne: Private ordinary functions
quadtree-nw: Private ordinary functions
quadtree-objects: Private ordinary functions
quadtree-p: Private ordinary functions
quadtree-se: Private ordinary functions
quadtree-sw: Private ordinary functions
query: Public ordinary functions

R
root-p: Private ordinary functions

S
subdevide: Private ordinary functions