SMS:Quadtree Module

The Quadtree module contains tools used to construct and edit Quadtrees. A quadtree is a tree data structure in which each internal node has exactly four children. Quadtrees are most often used to partition a two-dimensional space by recursively subdividing it into four quadrants or regions.

In SMS, quadtrees are synonymous with telescoping grids because currently only the CMS-Flow model can utilize them and they are referred to as telescoping grids by that model and its developers. Beginning with SMS 12.1, a quadtree grid system was implemented allowing for CMS-Flow grid telescoping and refinement while replacing the previous cartesian grid.

It is strongly recommended that quadtrees be created through the Map Module. The quadtree module currently includes interfaces for:

• CMS-Flow – hydrodynamic circulation specifically adapted for coastal zone

Creating and Editing Quadtrees

Creating Quadtrees

A quadtree is generated using a Quadtree Generator coverage and uses a technique from previous versions of SMS to generate telescoping grids. The rules for generating such a grid are described in the Telescoping Grid article.

Quadtree Generator Coverage

Quadtree generator coverage Polygon Attributes dialog

A generic coverage that can be used for creating feature objects to be converted to a quadtree. The Create 2D-Grid Frame tool and Select 2D-Grid Frame tool are available with this coverage. A grid frame is required before converting the coverage to a quadtree.

Polygon attributes can be assigned by double-clicking on a polygon or right-clicking on the polygon then selecting the Attributes command. The Polygon Attributes dialog allows setting the Maximum grid cell size.

The quadtree generator coverage has a right-click menu. This menu has the standard coverage menu commands and access to the Map → Quadtree Grid command.

Map → Quadtree

The Map → Quadtree command is used to construct a quadtree grid using a grid frame feature object in a the current quadtree generator coverage. When the Map → Quadtree command is selected, the Map → Quadtree dialog appears.

Parameters specified to create the grid include:

• Grid Geometry – This section specifies the origin, orientation and size of the grid. The fields of these quantities are populated with default values based on the three points. The orientation is measured as an angle from the positive X axis.

• Cell Options – This section specifies the number of cells in each direction in the grid. Several options are available. Specify sizes in the I (Delta U) and J (Delta V) directions or a number of columns and rows. If the Use Grid Frame Size toggle is checked, the grid will exactly match the dimensions specified in the Grid Geometry section. If that option is not checked, the last row and column may extend beyond the specified lengths. This allows specifying exact grid size or exact cell size.

• Depth Options – The elevations or depths assigned to each cell or node can be specified as a single value, or select a dataset to interpolate from.

SMS will generate a quadtree on the input parameters.

Editing Quadtrees

Each of the cells in a quadtree can be subdivided into four subcells by selecting the cell, right-clicking, and selecting the Split command. Multiple cells may be selected and split in a single command.

Four sub cells can be merged by selecting them, right-clicking, and selecting the Merge command.

Smoothing Quadtrees

Example of the Quadtree Smoothing Options dialog.

It may be useful to smooth the spatial data stored on a quadtree for a number of reasons. These reasons include:

• In order to conserve the amount of disk spaced required to store a DEM, many DEM formats store elevations rounded to the nearest integer value. This causes elevation changes to occur in discrete steps rather than smoothly, as would be the case in nature. In regions of low relief, rounded elevations can cause an area to be artificially "flat."
• Surveys may include anomalies. Smoothing algorithms blend these bad data points into the surrounding values.
• Datasets may include spurious noise either from physical conditions such as waves or numerical filtering. Smoothing can dampen these variations.

When right-clicking on quadtree data in the Project Explorer, operations for the quadtree appear in a pop up window. One of these is the smooth operation.

Quadtree Smoothing Options

This dialog is accessed by right-clicking on the quadtree data in the Project Explorer and selecting the Smooth command. The Quadtree Smoothing Options dialog contains the following options:

• Filter size – This determines how many neighbors are included when smoothing the grid. Options are 3x3 and 5x5.
• Number of iterations – This specifies how many passes should be made with the smoothing algorithm.
• Max. elevation change – This value specifies the maximum allowable elevation change per iteration for each cell.
• Filter ratio – The new cell elevation is computed using the original elevation (at the beginning of the iteration not the whole process) and the "blurred" elevation. The filter ratio defines how far the elevation is changed between the original elevation and the "blurred" elevation. A filter ratio of 1.0 would replace the existing elevation with the "blurred" elevation. A filter ratio of 0.0 would be pointless as it wouldn't change the elevations. A filter ratio of 0.5 would give a new elevation that is the average of the original elevation and the blurred elevation.
• Only modify selected cells – If this option is selected, only the cells that are selected are smoothed. Cells not selected may be used to compute "blurred" elevations but their elevations are never modified.

Converting Quadtrees

Quadtrees may be converted to other types of data used in SMS, such as a scattered dataset of 2D mesh. Quadtrees can be converted by right-clicking on the grid in the Project Explorer.

Project Explorer

Project Explorer mouse right-click menus are available when the mouse right-click is performed on a quadtree item. See Quadtree Menus for more information.

Quadtree Module Tools

See Quadtree Module Tools for more information.

Quadtree Module Menus

See Quadtree Module Menus for more information.

How do I?

To learn more about how to use the Quadtree module go to the Tutorials section of the Aquaveo website.

Tutorials currently demonstrating the Quadtree module include:

• CMS-Flow

Related Coverages

The Quadtree module currently includes interfaces for:

• CMS-Flow – hydrodynamic circulation specifically adapted for coastal zone

Related Topics

• SMS Modules