next up previous contents
Next: Function: plot_list Up: GRASP Routines: Template Bank Previous: Structure: struct tile   Contents

Function: tiling_2d

int tiling\_2d(double *x_bound, double *y_bound, int npts,
	      int (*metric)(double , double , double *),
	      struct tile **tail, int *n_tiles);

This is a generic routine for laying out a mesh of overlapping rectangular tiles in a (relatively) arbitrary two-dimensional parameter space. The tiles are sized such that no point on the tile is more than one unit of proper distance from its centre, where the proper distance is computed with a metric function which can vary arbitrarily over the parameter space. Thus the size and shape of the tiles can and will vary over the space. The tiles are rectangular, aligned with the coordinate axes, and are laid out in columns, with extra overlapping tiles on the edges to ensure complete coverage of the space. The lattice of tile positions is stored as a linked list.

Note that the routine can be easily modified to lay out tiles with non-unit proper radius. To scale the tiles by a factor $d$, simply multiply the metric function by a factor $d^{-2}$.

Upon successful execution, tiling_2d() attaches the new linked list to (**tail).next, updates *tail to point to the new tail of the list, and returns a value of 0. It returns an error code of 1 if it suspects that some of the columns may not be properly filled. It returns 2 if at any point the width of the parameter space was more than N_COLS times the computed column width. It returns 3 if the routine terminated prematurely for any other reason (usually because the algorithm accidentally stepped out of the parameter space, due to imprecise interpolation of the boundary). In the case of error codes 2 and 3, tiling_2d() still attaches the generated list onto (**tail).next (up to the point where the error occurred), but does not update the position of *tail. tiling_2d() will also write appropriate error messages indicating where any errors took place, and the flag field of the tile on the list (at the time of the error) is set to the error code. A flag value of $-1$ on any tile is a warning flag; the tile was placed correctly, but not all of the fields were calculated.

The arguments are:

x_bound: Input. An array [0..npts] storing the $x$-coordinates of npts points along the boundary of the parameter space. The array has length npts+1, but the index [npts] should refer to the same point as [0].

y_bound: Input. As above, but the $y$-coordinates.

npts: Input. The number of points used to specify the boundary.

metric(): Input. This function computes the three independent components of the distance metric matrix at a given point in parameter space. The first two arguments are the $x$ and $y$ coordinates of the requested point, the third passes back the metric components in a three-element array. The [0], [1], and [2] metric components are defined in terms of the proper interval as follows:

ds^2 = \hbox{\tt [0]}dx^2 + \hbox{\tt [1]}dxdy
+ \hbox{\tt [2]}dy^2 .

metric() itself should return 0, or 1 if the metric is undefined or not computable at the specified location.

tail: Input/Output. Initially points to the ``tail'' of a pre-existing list; the generated list is attached to (**tail).next. Upon successful completion, **tail is updated to the new tail of the list.

n_tiles: Input/Output. A running tally of the number of tiles in the mesh; it is incremented each time a tile is added (and decremented whenever a tile is removed).

The tiling_2d() routine makes very few assumptions about the parameter space. The most stringent is the assumption that the parameter space boundary can be expressed as bivalued functions of both $x$ and $y$; that is, both vertical and horizontal lines intersect the boundary at no more than two points. If a vertical line intersects at more than two points, the routine may come to a point where it cannot determine the location or width of a column of tiles, and will terminate. If a horizontal line intersects at more than two points, the routine may not completely cover the edges of the parameter space. Appropriate warning or error messages are generated in these cases.

Author: Teviet Creighton,

next up previous contents
Next: Function: plot_list Up: GRASP Routines: Template Bank Previous: Structure: struct tile   Contents
Bruce Allen 2000-11-19