rquad

package module
v0.0.1 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Apr 19, 2020 License: MIT Imports: 8 Imported by: 0

README

Region quadtrees in Go

Build Status Coverage Go Report Card GoDoc

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

Quadtree creation benchmark

Neighbour finding benchmark

Point location benchmark

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

func ForEachNeighbour(n Node, fn func(Node))

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

func (n *BasicNode) Bounds() image.Rectangle

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

func (*BasicNode) Child

func (n *BasicNode) Child(q Quadrant) Node

Child returns current node child at specified quadrant.

func (*BasicNode) Color

func (n *BasicNode) Color() Color

Color returns the node Color.

func (*BasicNode) Location

func (n *BasicNode) Location() Quadrant

Location returns the node inside its parent quadrant

func (*BasicNode) Parent

func (n *BasicNode) Parent() Node

Parent returns the quadtree node that is the parent of current one.

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

func NewBasicTree(scanner imgscan.Scanner, resolution int) (*BasicTree, error)

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

func (q *BasicTree) ForEachLeaf(color Color, fn func(Node))

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.

func (*BasicTree) Root

func (q *BasicTree) Root() Node

Root returns the quadtree root node.

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

func NewCNTree(scanner imgscan.Scanner, resolution int) (*CNTree, error)

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 Color

type Color byte

Color is the set of colors that can take a Node.

const (
	// Black is the color of leaf nodes
	// that are considered as obstructed.
	Black Color = 0 + iota

	// White is the color of leaf nodes
	// that are considered as free.
	White

	// Gray is the color of non-leaf nodes
	// that contain both black and white children.
	Gray
)

func (Color) String

func (i Color) String() string

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

func Locate(q Quadtree, pt image.Point) Node

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 NodeList

type NodeList []Node

NodeList is a slice of Node instances.

type Quadrant

type Quadrant int

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

const (
	Northwest Quadrant = iota
	Northeast
	Southwest
	Southeast
)

Possible values for the Quadrant type.

func (Quadrant) String

func (i Quadrant) String() string

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.

type Side

type Side int

Side is used to represent a direction according to a quadtree Node.

const (
	West Side = iota
	North
	East
	South
)

Possible values for the Side type.

func (Side) String

func (i Side) String() string

Directories

Path Synopsis

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL