## Documentation ¶

### Overview ¶

Package rquad proposes various implementations of region quadtrees. The region quadtree is a special kind of quadtree that recursively subdivides a 2D dimensional space into 4, smaller and generally equal rectangular regions, until the wanted quadtree resolution has been reached, or no further subdivisions can be performed.

Region quadtree may be used for image processing, in this case a node represents a rectangular region of an image in which all pixels have the same color.

A region quadtree may also be used as a variable resolution representation of a data field. For example, the temperatures in an area may be stored as a quadtree, with each leaf node storing the average temperature over the subregion it represents.

Quadtree implementations in this package use the binimg.Scanner interface to represent the complete area, and provide us with a way to know if a particular sub-area is to be considered uniform, in which case further subdivision is not necessary, or not.

### Index ¶

### Constants ¶

This section is empty.

### Variables ¶

This section is empty.

### Functions ¶

#### func ForEachNeighbour ¶

ForEachNeighbour calls the given function for each neighbour of the node n.

The generic method to search for the neighbours of node n is the "bottom-up neighbour finding technique", first described by Hanan Samet in 1981 in his article "Neighbour FInding in Quadtrees". If n implements the NeighbourNode interface, (i.e it implements a specific and generalyl more efficient method), then the call is forwarded to n.ForEachNeighbour.

### Types ¶

#### type BasicNode ¶

```
type BasicNode struct {
// contains filtered or unexported fields
}
```

BasicNode represents a standard quadtree node.

It is a basic implementation of the Node interface, the one used in the BasicTree implementation of the Quadtree interface.

#### func (*BasicNode) Bounds ¶

Bounds returns the bounds of the rectangular area represented by this quadtree node.

#### type BasicTree ¶

```
type BasicTree struct {
// contains filtered or unexported fields
}
```

BasicTree is a standard implementation of a region quadtree.

It performs a standard quadtree subdivision of the rectangular area represented by an binimg.Scanner.

#### func NewBasicTree ¶

NewBasicTree creates a basic region quadtree from a scannable rectangular area and populates it with basic node instances.

resolution is the smallest size in pixels that can have a leaf node, no further subdivisions will be performed on a node if its width or height is equal to this value.

#### func (*BasicTree) ForEachLeaf ¶

ForEachLeaf calls the given function for each leaf node of the quadtree.

Successive calls to the provided function are performed in no particular order. The color parameter allows to loop on the leaves of a particular color, Black or White. NOTE: As by definition, Gray leaves do not exist, passing Gray to ForEachLeaf should return all leaves, independently of their color.

#### type CNNode ¶

type CNNode struct { BasicNode // contains filtered or unexported fields }

CNNode is a node of a Cardinal Neighbour Quadtree.

It is an implementation of the Node interface, with additional fields and methods required to obtain the node neighbours in constant time. The time complexity reduction is obtained through the addition of only four pointers per leaf node in the quadtree.

The Western cardinal neighbor is the top-most neighbor node among the western neighbors, noted cn0.

The Northern cardinal neighbor is the left-most neighbor node among the northern neighbors, noted cn1.

The Eastern cardinal neighbor is the bottom-most neighbor node among the eastern neighbors, noted cn2.

The Southern cardinal neighbor is the right-most neighbor node among the southern neighbors, noted cn3.

#### type CNTree ¶

type CNTree struct { BasicTree // contains filtered or unexported fields }

CNTree implements a Cardinal Neighbour Quadtree, a quadtree structure that allows finding neighbor quadrants in constant time O(1) regardless of their sizes.

The time complexity reduction is obtained through the addition of four pointers per node in the quadtree, those pointers are the cardinal neighbour of the node.

This quadtree structure has been proposed by Safwan W. Qasem, King Saud University, Kingdom of Saudi Arabia, in his paper "Cardinal Neighbor Quadtree: a New Quadtree-based Structure for Constant-Time Neighbor Finding"

#### func NewCNTree ¶

NewCNTree creates a cardinal neighbour quadtree and populates it.

The quadtree is populated according to the content of the scanned image. It works only on square and power of 2 sized images, NewCNTree will return a non-nil error if that's not the case.

resolution is the minimal dimension of a leaf node, no further subdivisions will be performed on a leaf if its dimension is equal to the resolution.

#### type Node ¶

type Node interface { // Parent returns the quadtree node that is the parent of current one. Parent() Node // Child returns current node child at specified quadrant. Child(Quadrant) Node // Bounds returns the bounds of the rectangular area represented by this // quadtree node. Bounds() image.Rectangle // Color returns the node Color. Color() Color // Location returns the node inside its parent quadrant Location() Quadrant }

Node defines the interface for a quadtree node.

#### func Locate ¶

Locate returns the leaf node containing the given point.

The generic method to search for the leaf Node that contains a given point is a recursive search from the root node, it returns the leaf node containing the point. If q implements the PointLocator interface, (i.e it implements a specific and generally more efficient method), then the call is forwarded to q.Locate.

#### type Quadrant ¶

type Quadrant int

Quadrant indicates the position of a child Node inside its parent.

Possible values for the Quadrant type.

#### type Quadtree ¶

type Quadtree interface { // ForEachLeaf calls the given function for each leaf node of the quadtree. // // Successive calls to the provided function are performed in no particular // order. The color parameter allows to loop on the leaves of a particular // color, Black or White. // NOTE: As by definition, Gray leaves do not exist, passing Gray to // ForEachLeaf should return all leaves, independently of their color. ForEachLeaf(Color, func(Node)) // Root returns the quadtree root node. Root() Node }

Quadtree defines the interface for a quadtree type.