The quadtree Reference Manual

Table of Contents

Next: , Previous: , Up: (dir)   [Contents][Index]

The quadtree Reference Manual

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.


Next: , Previous: , Up: Top   [Contents][Index]

1 Introduction

Quadtree

Build Status Coverage Status

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

Copyright

Copyright (c) 2015 Masayuki Takagi (kamonama@gmail.com)

License

Licensed under the MIT License.


Next: , Previous: , Up: Top   [Contents][Index]

2 Systems

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


Previous: , Up: Systems   [Contents][Index]

2.1 quadtree

Author

Masayuki Takagi

License

MIT

Description

Quadtree data structure in Common Lisp

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 (file)

Component

src (module)


Next: , Previous: , Up: Top   [Contents][Index]

3 Modules

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


Previous: , Up: Modules   [Contents][Index]

3.1 quadtree/src

Parent

quadtree (system)

Location

src/

Component

quadtree.lisp (file)


Next: , Previous: , Up: Top   [Contents][Index]

4 Files

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


Previous: , Up: Files   [Contents][Index]

4.1 Lisp


Next: , Previous: , Up: Lisp files   [Contents][Index]

4.1.1 quadtree.asd

Location

quadtree.asd

Systems

quadtree (system)

Packages

quadtree-asd


Previous: , Up: Lisp files   [Contents][Index]

4.1.2 quadtree/src/quadtree.lisp

Parent

src (module)

Location

src/quadtree.lisp

Packages

quadtree

Exported Definitions
Internal Definitions

Next: , Previous: , Up: Top   [Contents][Index]

5 Packages

Packages are listed by definition order.


Next: , Previous: , Up: Packages   [Contents][Index]

5.1 quadtree-asd

Source

quadtree.asd

Use List

Previous: , Up: Packages   [Contents][Index]

5.2 quadtree

Source

quadtree.lisp (file)

Use List

common-lisp

Exported Definitions
Internal Definitions

Next: , Previous: , Up: Top   [Contents][Index]

6 Definitions

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


Next: , Previous: , Up: Definitions   [Contents][Index]

6.1 Exported definitions


Next: , Previous: , Up: Exported definitions   [Contents][Index]

6.1.1 Special variables

Special Variable: *max-capacity*
Package

quadtree

Source

quadtree.lisp (file)

Special Variable: *max-depth*
Package

quadtree

Source

quadtree.lisp (file)


Next: , Previous: , Up: Exported definitions   [Contents][Index]

6.1.2 Functions

Function: boundary QUADTREE
Package

quadtree

Source

quadtree.lisp (file)

Function: clear QUADTREE
Package

quadtree

Source

quadtree.lisp (file)

Function: insert QUADTREE OBJECT
Package

quadtree

Source

quadtree.lisp (file)

Function: make X0 Y0 X1 Y1 &key MAX-DEPTH MAX-CAPACITY
Package

quadtree

Source

quadtree.lisp (file)

Function: query QUADTREE X Y &optional NEIGHBOR-P
Package

quadtree

Source

quadtree.lisp (file)


Previous: , Up: Exported definitions   [Contents][Index]

6.1.3 Generic functions

Generic Function: intersect-p QUADTREE OBJECT

Returns if the object intersects the quadtree

Package

quadtree

Source

quadtree.lisp (file)


Previous: , Up: Definitions   [Contents][Index]

6.2 Internal definitions


Next: , Previous: , Up: Internal definitions   [Contents][Index]

6.2.1 Functions

Function: %make X0 Y0 X1 Y1 DEPTH MAX-DEPTH MAX-CAPACITY
Package

quadtree

Source

quadtree.lisp (file)

Function: %make-quadtree &key (OBJECTS OBJECTS) (NW NW) (NE NE) (SW SW) (SE SE) (BOUNDARY BOUNDARY) (DEPTH DEPTH) (MAX-DEPTH MAX-DEPTH) (MAX-CAPACITY MAX-CAPACITY)
Package

quadtree

Source

quadtree.lisp (file)

Function: copy-quadtree INSTANCE
Package

quadtree

Source

quadtree.lisp (file)

Function: full-p QUADTREE
Package

quadtree

Source

quadtree.lisp (file)

Function: leaf-p QUADTREE
Package

quadtree

Source

quadtree.lisp (file)

Function: max-depth-p QUADTREE
Package

quadtree

Source

quadtree.lisp (file)

Function: node-p QUADTREE
Package

quadtree

Source

quadtree.lisp (file)

Function: point-intersect-p QUADTREE X Y
Package

quadtree

Source

quadtree.lisp (file)

Function: quadtree-boundary INSTANCE
Function: (setf quadtree-boundary) VALUE INSTANCE
Package

quadtree

Source

quadtree.lisp (file)

Function: quadtree-depth INSTANCE
Function: (setf quadtree-depth) VALUE INSTANCE
Package

quadtree

Source

quadtree.lisp (file)

Function: quadtree-max-capacity INSTANCE
Function: (setf quadtree-max-capacity) VALUE INSTANCE
Package

quadtree

Source

quadtree.lisp (file)

Function: quadtree-max-depth INSTANCE
Function: (setf quadtree-max-depth) VALUE INSTANCE
Package

quadtree

Source

quadtree.lisp (file)

Function: quadtree-ne INSTANCE
Function: (setf quadtree-ne) VALUE INSTANCE
Package

quadtree

Source

quadtree.lisp (file)

Function: quadtree-nw INSTANCE
Function: (setf quadtree-nw) VALUE INSTANCE
Package

quadtree

Source

quadtree.lisp (file)

Function: quadtree-objects INSTANCE
Function: (setf quadtree-objects) VALUE INSTANCE
Package

quadtree

Source

quadtree.lisp (file)

Function: quadtree-p OBJECT
Package

quadtree

Source

quadtree.lisp (file)

Function: quadtree-se INSTANCE
Function: (setf quadtree-se) VALUE INSTANCE
Package

quadtree

Source

quadtree.lisp (file)

Function: quadtree-sw INSTANCE
Function: (setf quadtree-sw) VALUE INSTANCE
Package

quadtree

Source

quadtree.lisp (file)

Function: root-p QUADTREE
Package

quadtree

Source

quadtree.lisp (file)

Function: subdevide QUADTREE
Package

quadtree

Source

quadtree.lisp (file)


Previous: , Up: Internal definitions   [Contents][Index]

6.2.2 Structures

Structure: quadtree ()
Package

quadtree

Source

quadtree.lisp (file)

Direct superclasses

structure-object (structure)

Direct slots
Slot: objects
Readers

quadtree-objects (function)

Writers

(setf quadtree-objects) (function)

Slot: nw
Readers

quadtree-nw (function)

Writers

(setf quadtree-nw) (function)

Slot: ne
Readers

quadtree-ne (function)

Writers

(setf quadtree-ne) (function)

Slot: sw
Readers

quadtree-sw (function)

Writers

(setf quadtree-sw) (function)

Slot: se
Readers

quadtree-se (function)

Writers

(setf quadtree-se) (function)

Slot: boundary
Readers

quadtree-boundary (function)

Writers

(setf quadtree-boundary) (function)

Slot: depth
Readers

quadtree-depth (function)

Writers

(setf quadtree-depth) (function)

Slot: max-depth
Readers

quadtree-max-depth (function)

Writers

(setf quadtree-max-depth) (function)

Slot: max-capacity
Readers

quadtree-max-capacity (function)

Writers

(setf quadtree-max-capacity) (function)


Previous: , Up: Top   [Contents][Index]

Appendix A Indexes


Next: , Previous: , Up: Indexes   [Contents][Index]

A.1 Concepts

Jump to:   F   L   M   Q  
Index Entry  Section

F
File, Lisp, quadtree.asd: The quadtree<dot>asd file
File, Lisp, quadtree/src/quadtree.lisp: The quadtree/src/quadtree<dot>lisp file

L
Lisp File, quadtree.asd: The quadtree<dot>asd file
Lisp File, quadtree/src/quadtree.lisp: The quadtree/src/quadtree<dot>lisp file

M
Module, quadtree/src: The quadtree/src module

Q
quadtree.asd: The quadtree<dot>asd file
quadtree/src: The quadtree/src module
quadtree/src/quadtree.lisp: The quadtree/src/quadtree<dot>lisp file

Jump to:   F   L   M   Q  

Next: , Previous: , Up: Indexes   [Contents][Index]

A.2 Functions

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

%
%make: Internal functions
%make-quadtree: Internal functions

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

B
boundary: Exported functions

C
clear: Exported functions
copy-quadtree: Internal functions

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

G
Generic Function, intersect-p: Exported generic functions

I
insert: Exported functions
intersect-p: Exported generic functions

L
leaf-p: Internal functions

M
make: Exported functions
max-depth-p: Internal functions

N
node-p: Internal functions

P
point-intersect-p: Internal functions

Q
quadtree-boundary: Internal functions
quadtree-depth: Internal functions
quadtree-max-capacity: Internal functions
quadtree-max-depth: Internal functions
quadtree-ne: Internal functions
quadtree-nw: Internal functions
quadtree-objects: Internal functions
quadtree-p: Internal functions
quadtree-se: Internal functions
quadtree-sw: Internal functions
query: Exported functions

R
root-p: Internal functions

S
subdevide: Internal functions

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

Next: , Previous: , Up: Indexes   [Contents][Index]

A.3 Variables

Jump to:   *  
B   D   M   N   O   S  
Index Entry  Section

*
*max-capacity*: Exported special variables
*max-depth*: Exported special variables

B
boundary: Internal structures

D
depth: Internal structures

M
max-capacity: Internal structures
max-depth: Internal structures

N
ne: Internal structures
nw: Internal structures

O
objects: Internal structures

S
se: Internal structures
Slot, boundary: Internal structures
Slot, depth: Internal structures
Slot, max-capacity: Internal structures
Slot, max-depth: Internal structures
Slot, ne: Internal structures
Slot, nw: Internal structures
Slot, objects: Internal structures
Slot, se: Internal structures
Slot, sw: Internal structures
Special Variable, *max-capacity*: Exported special variables
Special Variable, *max-depth*: Exported special variables
sw: Internal structures

Jump to:   *  
B   D   M   N   O   S  

Previous: , Up: Indexes   [Contents][Index]

A.4 Data types

Jump to:   P   Q   S  
Index Entry  Section

P
Package, quadtree: The quadtree package
Package, quadtree-asd: The quadtree-asd package

Q
quadtree: The quadtree system
quadtree: The quadtree package
quadtree: Internal structures
quadtree-asd: The quadtree-asd package

S
Structure, quadtree: Internal structures
System, quadtree: The quadtree system

Jump to:   P   Q   S