quadtree

Documentation

Overview

Package quadtree is a compact implementation of a static 2D quadtree.

This implementation supports a Barnes Hut algorithm with more that one million bodies. It is a compact (and fun!) implementation because node coordinates are encoded into a 4 bytes stucture

type Coord uint32

This quatree is a hierarchical set of nodes that divide the 2D space at different levels (1 node at level 0, 4 nodes at level 1, 16 nodes at level 2, etc...). Each node holds sub nodes except the leaf nodes that contains all bodies that are located in the area of the node.

Bodies's X,Y coordinates are float64 between 0 & 1

A quadtree is usualy a dynmic structure. In this package implementation, the architecture is static with a depth of nodes limited to 8 (256 * 256 cells at the level 8)

Index

• Constants
• Variables
• func Init(traceHandle io.Writer, infoHandle io.Writer, warningHandle io.Writer, ...)
• func InitBodiesUniform(bodies *[]Body, nbBodies int)
• type Body
  • func (b *Body) Coord() Coord
  • func (b *Body) Next() *Body
• type BodyXY
• type Coord
  • func GetCoord(level, i, j int) Coord
  • func NodesBelow(c Coord) (coordNW, coordNE, coordSW, coordSE Coord)
  • func (c Coord) Level() int
  • func (c *Coord) SetLevel(level int)
  • func (c *Coord) String() string
  • func (c Coord) X() int
  • func (c Coord) Y() int
• type Node
  • func (n *Node) Coord() Coord
  • func (n *Node) First() *Body
• type Quadtree
  • func (q *Quadtree) CheckIntegrity(t *testing.T)
  • func (q *Quadtree) ComputeNbBodiesPerNode()
  • func (q *Quadtree) ComputeQuadtreeGini()
  • func (q *Quadtree) Init(bodies *[]Body)
  • func (q *Quadtree) UpdateNodesListsAndCOM()
• type QuadtreeGini

Constants

const (
	NW = 0x0000
	NE = 0x0100
	SW = 0x0001
	SE = 0x0101
)

constants used to navigate from one node to the other

Variables

var (
	Trace   *log.Logger
	Info    *log.Logger
	Warning *log.Logger
	Error   *log.Logger
)

Functions

func Init

func Init(
	traceHandle io.Writer,
	infoHandle io.Writer,
	warningHandle io.Writer,
	errorHandle io.Writer)

func InitBodiesUniform

func InitBodiesUniform(bodies *[]Body, nbBodies int)

init a quadtree with random position

Types

type Body

type Body struct {
	BodyXY
	M float64
	// contains filtered or unexported fields
}

a body is a position & a mass

func (*Body) Coord

func (b *Body) Coord() Coord

func (*Body) Next

func (b *Body) Next() *Body

bodies of a node are linked together Some quadtree use an alternative choice : store bodies of a node in a slice attached to the node. This alternative implies memory allocation which one tries to avoid. number of memory allocation are benchmaked with

go test -bench=BenchmarkUpdateNodesList_10M -benchmem

type BodyXY

type BodyXY struct {
	X float64
	Y float64
}

type Coord

type Coord uint32

Coordinate system of a node

Situation : most quadtree implementation are dynamic (the nodes can be created and deleted after the quadtree initialisation). This is an optimal solution if bodies are sparesely located (as in cosmology). Access to node is in (log(n))

Current case is different because bodies are uniformly spread on a 2D square.

Problem : the dynamic implementation is not necessary for uniformly spread bodies

Solution : a static quadtree with the following requirements

Node coordinates are their rank in a direct access table.
Node coordinates of a body are computed directly from body's X,Y position

Coordinates of a node are coded as follow

byte 0 : 0x00 (unused)
byte 1 : level (root = 0, max depth = 7)
byte 2 : X coordinate
byte 3 : Y coordinate : coded on

the X coordinate code depends on the level

level 0: there is no coordinate
level 1: west if 0, east is 128 (0x80)
level 2: node coordinates are 0, 64 (0x40), 128 (0x80), 192 (0x84)
...
level 8: node coordinates are encoded on the full 8 bits, from 0 to 0xFF (255)

func GetCoord

func GetCoord(level, i, j int) Coord

func NodesBelow

func NodesBelow(c Coord) (coordNW, coordNE, coordSW, coordSE Coord)

get nodes coords below

func (Coord) Level

func (c Coord) Level() int

node level of a node coord c is between 0 and 8 and coded on 2nd byte of the Coord c

func (*Coord) SetLevel

func (c *Coord) SetLevel(level int)

func (*Coord) String

func (c *Coord) String() string

print a coord

func (Coord) X

func (c Coord) X() int

x coord

func (Coord) Y

func (c Coord) Y() int

y coord

type Node

type Node struct {

	// Barycenter with mass of all the bodies of the node
	// this body is linked with the bodies at his level in the node
	Body
	// contains filtered or unexported fields
}

a node is a body

func (*Node) Coord

func (n *Node) Coord() Coord

func (*Node) First

func (n *Node) First() *Body

link to the first body of the bodies chain belonging to the node

type Quadtree

type Quadtree struct {
	Nodes [1 << 20]Node

	BodyCountGini QuadtreeGini // for each of the 9 levels, tencentile of bodies
	// contains filtered or unexported fields
}

a Quadtree store Nodes. It is a an array with direct access to the Nodes with the Nodes coordinate see Coord

func (*Quadtree) CheckIntegrity

func (q *Quadtree) CheckIntegrity(t *testing.T)

check integrity of the quadtree by performing all kinds of test

func (*Quadtree) ComputeNbBodiesPerNode

func (q *Quadtree) ComputeNbBodiesPerNode()

compute number of bodies per node update the counting of bodies per node for all levels

func (*Quadtree) ComputeQuadtreeGini

func (q *Quadtree) ComputeQuadtreeGini()

compute the gini of body density par node at level 8

func (*Quadtree) Init

func (q *Quadtree) Init(bodies *[]Body)

init quadtree

func (*Quadtree) UpdateNodesListsAndCOM

func (q *Quadtree) UpdateNodesListsAndCOM()

updates nodes according to bodies locations this function should be called when bodies have been moved

type QuadtreeGini

type QuadtreeGini [9][10]float64