A small function for accessing a cell in a quad-tree matrix.
The quad-tree is a tree data structure with (guess what) 4 children. They are used for various applications (Wikipedia-page), for example, storing an image. The picture is decomposed in a series of squares of size 2ⁿx2ⁿ, which are a matrix stored as a quad-tree. This tree can be a leaf with one color or an internal node with four children.
If you want a generic and visual explanation of quad-tree: An interactive explanation of quad-trees.
The code is in Haskell, and the data structures are parametrized for allowing the use of different types of data: the a can be any type like an RGB color.
data QT a = C a | Q (QT a) (QT a) (QT a) (QT a) deriving (Eq, Show)data Matrix a = Mat{
nexp :: Int,
mat :: QT a
} deriving (Eq, Show)
If you’re unfamiliar with Haskell, don’t worry about the details and try to get a general sense of it.
An example of a quad-tree matrix 4x4 is:
quadtree = Q (C 5) (Q (C 1) (C 3) (C 6) (C 8) ) (Q (C 32) (C 27) (C 45) (C 11) ) (C 7)matrix = Mat 4 quadtree
The code for the access is recursive, where the base case is when the input is a leaf, and the other case determines which child of the node the cell we’re looking for. This is done by making the comparison with nexp/2 and calling the recursion with new indices.
The div is the integer division, the recursion case use the guard syntax of Haskell, nexp is here called n for brevity. I call the quadrants: tl, tr, bl, br; the names are build combining t: top, b: bottom, l: left, r: right. (There is an other convention of called them with: north, south, est, west).
access:: Matrix a -> Int -> Int -> a
access (Mat _ (C value)) _ _ = value
access (Mat n (Q tl tr bl br ) ) i j
| i > n`div`2 && j > n`div`2 =
access (Mat (n `div` 2) br) (i- n`div`2) (j- n`div`2)
| i > n`div`2 && j <= n`div`2 =
access (Mat (n `div` 2) bl) (i- n`div`2) j
| i <= n`div`2 && j > n`div`2 =
access (Mat (n `div` 2) tr) i (j- n`div`2)
| i <= n`div`2 && j <= n`div`2 =
access (Mat (n `div` 2) tl) i jYou should also make some input validation and check if the indices are inside the admitted range.
accessWrapper:: Matrix a -> Int -> Int -> a
accessWrapper matrix@(Mat n _) i j
| i > n || j > n || i <= 0 || j <= 0 = error “indexes out of bound”
| otherwise = access matrix i j
