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

This is the quadtree Reference Manual, version 0.1, generated automatically by Declt version 2.3 "Robert April" on Wed Mar 14 04:29:07 2018 GMT+0.

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

## Usage

Here shows how to store points into a quadtree.

First, define point structure.

(defstruct (point (:constructor make-point (x y)))

Then, implement an intersection test method for the point structure, which is called when inserting points to a 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)))
(loop for point in points
(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

After approved, you can install via Quicklisp.

## 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

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

Clears the contents of quadtree. The return value is always t.

### [Function] 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

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 (c) 2015 Masayuki Takagi (kamonama@gmail.com)

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

## 2 Systems

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

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

Author

Masayuki Takagi

MIT

Description

Quadtree data structure in Common Lisp

Long Description

## Usage

Here shows how to store points into a quadtree.

First, define point structure.

(defstruct (point (:constructor make-point (x y)))

Then, implement an intersection test method for the point structure, which is called when inserting points to a 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)))
(loop for point in points
(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

After approved, you can install via Quicklisp.

## 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

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

Clears the contents of ‘quadtree‘. The return value is always ‘t‘.

### [Function] 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

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 (c) 2015 Masayuki Takagi (kamonama@gmail.com)

Version

0.1

Source

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]

Parent

Location

src/

Component

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]

Location

Systems

Packages

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

Parent

src (module)

Location

Packages
Exported Definitions
Internal Definitions

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

## 5 Packages

Packages are listed by definition order.

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

Source

Use List
• asdf/interface
• common-lisp

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

Source

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
Source

Special Variable: *max-depth*
Package
Source

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

#### 6.1.2 Functions

Package
Source

Package
Source

Package
Source

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

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

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

#### 6.1.3 Generic functions

Returns if the object intersects the quadtree

Package
Source

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
Source

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
Source

Package
Source

Package
Source

Package
Source

Package
Source

Package
Source

Package
Source

Package
Source

Package
Source

Package
Source

Package
Source

Package
Source

Package
Source

Package
Source

Package
Source

Package
Source

Package
Source

Package
Source

Package
Source

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

#### 6.2.2 Structures

Package
Source

Direct superclasses

structure-object (structure)

Direct slots
Slot: objects

Writers

Slot: nw

Writers

Slot: ne

Writers

Slot: sw

Writers

Slot: se

Writers

Slot: boundary

Writers

Slot: depth

Writers

Slot: max-depth

Writers

Slot: max-capacity

Writers

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

## Appendix A Indexes

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

### A.1 Concepts

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

### A.2 Functions

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: , Previous: , Up: Indexes   [Contents][Index]