![]() Other quadrants have to be split further. 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. Therefore, a quadtree provides a nested tessellation: quadrants are only split if they have two or more different values. ![]() 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. An interior angle of a square is 90 and the sum of four interior angles is 360. There are four squares meeting at a vertex. ![]() In Figure 10.78, the tessellation is made up of squares. It shows a small 8×8 raster with three possible field values: white, green and blue. For a tessellation of regular congruent polygons, the sum of the measures of the interior angles that meet at a vertex equals. 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 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |