README
¶
Region quadtrees in Go
Region quadtrees and efficient neighbour finding techniques in Go
Go-rquad proposes various implementations of region quadtrees.
A region quadtree is a special kind of quadtree that recursively subdivides a 2 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 quadtrees can be used for image processing; in this case a leaf node represents a rectangular region of an image in which all colors are equal or the color difference is under a given threshold.
Region quadtrees may also be used to represent data fields with variable resolution. For example, the temperatures in an area may be stored as a quadtree where each leaf node stores the average temperature over the subregion it represents.
In this package, quadtrees implement the imgscan.Scanner interface,
this provides a way to scan (i.e extract) the pixels in order to perform the subdivisions.
API Overview
Node interface
type Node interface {
Parent() Node
Child(Quadrant) Node
Bounds() image.Rectangle
Color() Color
Location() Quadrant
}
Quadtree interface
A Quadtree represents a hierarchical collection of Nodes, its API is
simple: access to the root Node and a way to iterate over all the leaves.
type Quadtree interface {
ForEachLeaf(Color, func(Node))
Root() Node
}
Functions
Locate returns the leaf node of q that contains pt, or nil if q doesn't contain pt.
func Locate(q Quadtree, pt image.Point) Node
ForEachNeighbour calls fn for each neighbour of n.
func ForEachNeighbour(n Node, fn func(Node))
Basic implementation: BasicTree and basicNode
BasicTree is in many ways the standard implementation of Quadtree, it just does the job.
State of the art implementation: CNTree and CNNode
CNTree or Cardinal Neighbour Quadtree implements state of the art techniques:
- from any given leaf node, its neighbours (of any size) are accessed in constant time 0(1) as they implement the Cardinal Neighbour Quadtree technique (cf Safwan Qasem 2015). The time complexity reduction is obtained through the addition of only four pointers per leaf node in the quadtree.
- fast point location queries (locating which leaf node contains a specific point), thanks to the binary branching method (cf Frisken Perry 2002). This simple and efficient method is nonrecursive, table free, and reduces the number of comparisons with poor predictive behavior, that are otherwise required with the standard method.
Benchmarks
Research papers
-
Bottom-up neighour finding technique. cf Hanan Samet 1981,
Neighbor Finding Techniques for Images Represented by Quadtrees, paper -
Cardinal Neighbor Quadtree. cf Safwan Qasem 2015,
Cardinal Neighbor Quadtree: a New Quadtree-based Structure for Constant-Time Neighbor Finding, paper -
Fast point location using binary branching method. cf Frisken, Perry 2002
Simple and Efficient Traversal Methods for Quadtrees and Octrees, paper
License
go-rquad is open source software distributed in accordance with the MIT License, which says:
Copyright (c) 2016 Aurélien Rainone
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
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.
Source Files
Directories