Low-level routines to place a mesh of templates on an 2-dimensional parameter space. More...
Prototypes | |
void | LALTwoDMesh (LALStatus *stat, TwoDMeshNode **tail, TwoDMeshParamStruc *params) |
void | LALTwoDColumn (LALStatus *stat, TwoDMeshNode **tail, TwoDColumnParamStruc *column, TwoDMeshParamStruc *params) |
void | LALTwoDNodeCopy (LALStatus *stat, TwoDMeshNode **new, TwoDMeshNode *old) |
Low-level routines to place a mesh of templates on an 2-dimensional parameter space.
These are low-level `‘internal’' routines called by LALCreateTwoDMesh() to lay out an unevenly-spaced mesh on a 2-dimensional parameter space, according to the method discussed in Header TwoDMesh.h. They are made globally available to allow greater control to users attempting to tile complicated parameter spaces.
LALTwoDMesh() places a mesh on the parameter space specified by *params
. On successful completion, the linked list of mesh points is attached to (*tail)->next
(which must previously have been NULL
), updates *tail
to point to the new tail of the list, and increases params->nOut
by the number of mesh points added. (This is useful for tiling several parameter regions independently with successive calls to LALTwoDMesh().) On an error, **tail
is left unchanged, and params->nOut
indicates where the error occurred.
LALTwoDColumn() places a single column of such a mesh, according to the additional column restrictions in *column
. Again, on success, the mesh points are attached to (*tail)->next
, *tail
is updated, and params->nOut
increased. If the column specified by *column
is deemed to be too wide for a single column of templates, then column->tooWide
is set to 1, *tail
and params->nOut
are not updated, and the function returns normally (i.e. not with an error code set). Other more fatal errors are treated as for LALTwoDMesh(), above.
LALTwoDNodeCopy() creates a copy of the node *old
and points *new
to the copy. If old->subMesh
exists, each node in the submesh is copied into its corresponding place by recursive calls to LALTwoDNodeCopy(). On an error, the copy is destroyed and *new
left unchanged.
params->getRange()
to get the bottom and top of the left edge of the first column. It also calls params->getMetric
at these two corners, estimates the optimum width for the first column, and uses params->getRange()
again to get the two corners of the right edge of the column. It then calls the subroutine LALTwoDColumn() (below) to place the mesh points in this column.If LALTwoDColumn() reports that the estimated column width was too large, LALCreateTwoDMesh() tries again with the width reduced by the factor params->widthRetryFac
. This continues until the estimated number of columns exceeds params->maxColumns
; i.e. until the current column width is less than \( (x_\mathrm{max}-x_\mathrm{min})/ \) params->maxColumns
. If this occurs, the linked list is destroyed using LALDestroyTwoDMesh(), and an error is returned.
Otherwise, if LALTwoDColumn() returns success (and does not complain about the column width), LALCreateTwoDMesh() gets the width and heights of the next column, and calls LALTwoDColumn() again. This continues until eventually the right edge of a column lies beyond \( x_\mathrm{max} \) . This last column is squeezed so that its right edge lies exactly at \( x_\mathrm{max} \) ; once it is filled, the mesh is deemed complete, and no further columns are generated.
params->getRange()
to see how much of this centreline is taken up by the requested parameter region, restricted by any clipping area specified in *column
. If any region of this centreline remains uncovered, LALTwoDColumn() places a tile at the bottom of the uncovered portion, and stacks more tiles upward until it reaches the top of the uncovered line. The sizes and orientations of each tile are determined from calls to params->getMetric
.While it is doing this, LALTwoDColumn() keeps track of the bottom and top corners of the newly-covered region. If it finds that the top corners are not increasing monotonically, this is usually an indication that the metric is changing too rapidly, or that the tiles are getting too thin and tilted. Often this can be corrected by using narrower (and taller) tiles, so LALTwoDColumn() reports this as a `‘column too wide’' result: it sets column->tooWide
, frees everythin attached to **tail
and reduced params->nOut
accordingly, then returns. This is also done if LALTwoDColumn() ever determines that the maximum width of a mismatch ellipse is less than params->widthMaxFac
times the current column width.
Having successfully stacked up the centreline of the current column, LALTwoDColumn() then checks to see whether corners of the parameter region extend above or below the top and bottom of the newly-tiled region on either side of the centreline, by looking at the values in column->leftRange
and column->rightRange
. If a corner remains uncovered, LALTwoDColumn() calls itself recursively on a half-width column on the appropriate side, setting the clipping area of the subroutine call to exclude the region already covered. In principle it could call itself up to four times (once for each column), and each recursive call could in turn call itself recursively in order to cover a particularly steep or complicated boundary. However, in most cases at most two additional tiles need to be placed (one on a top corner, one on a bottom corner). If you're concerned about a runaway process, set params->nIn
to stop generation after a given number of tiles. If a recursive call reports the column is too wide, this information is passed up the calling chain.
Once the centreline and any corners have been successfully covered, LALTwoDColumn() updates *tail
to the new tail of the list, and returns.
new->subMesh
exists, LALTwoDNodeCopy() navigates its way along the list, calling itself recursively on each node, and attaching copies of each node to a corresponding list in (*new)->subMesh
. If any errors are detected, *new
is destroyed via LALDestroyTwoDMesh(), restoring it to NULL
.\[ m_\mathrm{thresh} = g_{xx}(\Delta x)^2 + g_{yy}(\Delta y)^2 + 2g_{xy}\Delta x\Delta y \; . \]
Thus for a tile of some half-width \( \Delta x \) , the heights of the two right-hand corners of the tile relative to its centre are:\[ \Delta y = \frac{-g_{xy}\Delta x \pm\sqrt{g_{yy}m_\mathrm{thresh} - ( g_{xx}g_{yy} - g_{xy}^2 )(\Delta x)^2}}{g_{yy}} \; , \]
and the maximum half-width of a tile is:\[ \Delta x_\mathrm{max} = \sqrt{\frac{g_{yy}m_\mathrm{thresh}} {g_{xx}g_{yy} - g_{xy}^2}} \; . \]
The positive-definiteness of the metric ensures that \( g_{xx}>0 \) , \( g_{yy}>0 \) , and \( g_{xx}g_{yy}>g_{xy}^2 \) . Furthermore, if one maximizes the proper area of a tile with respect to \( \Delta x \) , one finds that the optimal tile half-width is:\[ \Delta x_\mathrm{opt} = \frac{\Delta x_\mathrm{max}}{\sqrt{2}} \; . \]
When estimating the width for the next column, LALTwoDMesh() computes \( \Delta x_\mathrm{opt} \) at both the bottom and the top of the column and uses the smaller value (it is almost always better to underestimate \( \Delta x \) than to overestimate it). In LALTwoDColumn(), tile heights are computed using the column half-width \( \Delta x \) and the value of the metric components at its particular location.
We also note that the width of a column is computed using the metric evaluated at the edge joining it to the previous column, and the height of a tile is computed using the metric evaluated at the edge joining it to the previous tile. In principle it might be more accurate to refine our estimate of the column width or tile height by re-evaluating the metric at their centres, but this may be a significant excess computational burden. Furthermore, if the metric varies enough that the estimated width or height changes significantly over that distance, then the quadratic approximation to the match function is breaking down, and we shouldn't be treating the constant-mismatch contour as an ellipse. The routines here do not do any sophisticated sanity-checking, though.
Definition in file TwoDMeshInternal.c.