next up previous contents
Next: 4.2 Sequential Data Access Up: 4.1 Initialization Previous: 4.1.1 Closest Point Transformation

4.1.2 H-RLE Data Structure Setup

The H-RLE data structure can be set up by inserting all defined grid points in lexicographical order along with their LS values. In this way only the ends of the dynamic arrays must be modified, which can be performed with constant complexity using, for instance, vectors from the standard template library (STL) [124].

The LS framework provides two functions for setting up the H-RLE data structure. The first function allows the insertion of a single defined grid point, while the other one adds a new run of undefined grid points (undefined run) together with a specific run code, indicating the sign of their LS values. Both functions take two parameters. The first parameter is the index vector of the first grid point of the segment. (See Section 3.5.4 for the definition of a segment regarding the H-RLE data structure.) The second parameter takes the LS value for the defined grid point, or the run code for the new run, respectively. By appending successive new defined grid points and new undefined runs in lexicographical order, the H-RLE data structure can be set up in linear time.

For example, the following is done to set up the H-RLE data structure as given in Figure 3.6, for which the corresponding segmentation is shown in Figure 3.7: For each segment, one of the two setup functions must be called. The first segment is the positive undefined run starting at $ \left(0,0\right)$ . Then, the same function must be called with start indices $ \left(0,2\right)$ . Next, the second function for inserting defined grid points must be called multiple times with indices $ \left(2,2\right),\left(3,2\right),\ldots,\left(9,2\right)$ along with the corresponding LS values. Afterwards, another positive undefined run is inserted which starts at $ \left(10,2\right)$ , and so on. Runs are automatically finished, if another new run with a different run code is started or a defined grid point is inserted.

The previously described closest point transform algorithm does not deliver information about the start indices of undefined runs. The output is only a sorted list of all grid points which have at least one neighbor with opposite LS sign. However, from this list and the grid boundaries all starting indices can be derived.


next up previous contents
Next: 4.2 Sequential Data Access Up: 4.1 Initialization Previous: 4.1.1 Closest Point Transformation

Otmar Ertl: Numerical Methods for Topography Simulation