next up previous contents
Next: 4.2.2 Offset Iterator Up: 4.2 Sequential Data Access Previous: 4.2 Sequential Data Access

4.2.1 Basic Iterator

The basic iterator traverses the H-RLE data structure in sequential order and stops at every segment, thus at every defined grid point and at every undefined run. The iterator can be moved either forward or backward. Each step requires constant time on average. Since the number of segments is proportional to the number of defined grid points (see Section 3.5.4), a traversal of the entire data structure is possible in linear time.

The iterator allows access to all stored information of the current segment:

Figure 4.3b shows a two-dimensional example of a H-RLE data structure with sequentially numbered segments. The numbering corresponds to the traversal sequence of the iterator. The second position refers to the positive undefined run which contains the grid points $ \left(0,2\right)$ , $ \left(1,2\right)$ , and $ \left(2,2\right)$ . Hence, in this case the minimum and maximum index vectors are $ \left(0,2\right)$ and $ \left(2,2\right)$ , respectively.

Aside from stepping forward and backward the basic iterator can also be moved to any segment, specified by an index vector belonging to that segment. However, this corresponds to a random access operation with a logarithmic complexity in the worst case.

Figure 4.3: (a) A surface embedded in a domain with extensions $ 4\times 5$ . However, due to the different boundary conditions in $ {x}_1$ -direction (reflective) and $ {x}_2$ -direction (periodic) $ 5\times 5$ grid points are used for the discretization of the level set function. (b) Basic iterators traverse the segments of the H-RLE data structure according to their numbering. (c) The segmentation as seen by an iterator with offset $ \left (-1,-1\right )$ . (d) The same for an iterator with offset $ \left (2,1\right )$ .
Image fig_4_3


next up previous contents
Next: 4.2.2 Offset Iterator Up: 4.2 Sequential Data Access Previous: 4.2 Sequential Data Access

Otmar Ertl: Numerical Methods for Topography Simulation