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:

• The iterator provides a function that returns the minimum and maximum index vectors of the current segment. If the segment contains only a single grid point, as is the case for defined grid points, both index vectors are identical.
• The LS sign can be queried for the current segment. This is also possible for segments which are undefined runs. In this case the sign can be retrieved from the run code.
• If the current segment is a defined grid point, its LS value can be accessed using the iterator. For undefined runs $+\infty$ or $-\infty$ is returned instead. Floating-point data types fulfilling the IEEE standard for binary floating-point arithmetic [49] provide numerical representations for $+\infty$ and $-\infty$ . Alternatively, the maximum and minimum representable value can be used instead.

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 )$ .