After the first split, the southeast quadrant is entirely green, and this is indicated by a green square at level two of the tree. To construct a quadtree, the field is successively split into four quadrants until all parts have only a single value. Figure: An 8 x8, three value raster (here, three colours) and its representation as a region quadtree. Regular tessellations provide simple structures with straightforward algorithms that are, however, not adaptive to the phenomena they represent. Therefore, a quadtree provides a nested tessellation: quadrants are only split if they have two or more different values. Irregular tessellations are more complex than regular ones, but they are also more adaptive, which typically leads to a reduction in the amount of computer memory needed to store the data. When a conglomerate of cells has the same value, they are represented together in the quadtree, provided their boundaries coincide with the predefined quadrant boundaries. Quadtrees are adaptive because they apply Tobler’s law. The links between them are pointers, i.e. a programming technique to address (or to point to) other records. In the computer’s main memory, the nodes of a quadtree (both circles and squares in the Figure) are represented as records. The procedure produces an upside-down, tree-like structure, hence the name “quadtree”. This procedure stops when all the cells in a quadrant have the same field value. The quadtree that represents this raster is constructed by repeatedly splitting up the area into four quadrants, which are called NW, NE, SE, SW for obvious reasons. It shows a small 8×8 raster with three possible field values: white, green and blue. A simple illustration is provided in the Figure above. It is based on a regular tessellation of square cells, but takes advantage of cases where neighbouring cells have the same field value, so that they can be represented together as one bigger cell. A well-known data structure in this family - upon which many more variations have been based - is the region quadtree.
0 kommentar(er)
