helpers module

This is a collection of generic utility procedures that help with various geometric computations.

Procedures

void bbox(int *num_nodes, double *nodes, double *left, double *right, double *bottom, double *top)

Computes a rectangular bounding box \(\left[m_x, M_x\right] \times \left[m_y, M_y\right]\) for a set of points in \(\mathbf{R}^2\).

Parameters

• num_nodes (int*) – [Input] The number of nodes \(N\) we are bounding.

• nodes (double*) – [Input] The actual nodes as a \(2 \times N\) array. This should be laid out in Fortran order, with \(2 N\) total values.

• left (double*) – [Output] The minimal \(x\)-value \(m_x\).

• right (double*) – [Output] The maximal \(x\)-value \(M_x\).

• bottom (double*) – [Output] The minimal \(y\)-value \(m_y\).

• top (double*) – [Output] The maximal \(y\)-value \(M_y\).

Signature:

void
bbox(int *num_nodes,
     double *nodes,
     double *left,
     double *right,
     double *bottom,
     double *top);

void contains_nd(int *num_nodes, int *dimension, double *nodes, double *point, bool *predicate)

Checks if a point \(p\) is contained in the bounding box for a set of points.

Parameters

• num_nodes (int*) – [Input] The number of nodes \(N\) define the bounding box.

• dimension (int*) – [Input] The dimension \(D\) such that the nodes and point lie in \(\mathbf{R}^D\).

• nodes (double*) – [Input] The actual nodes as a \(D \times N\) array. This should be laid out in Fortran order, with \(D N\) total values.

• point (double*) – [Input] The point \(p\) as an array containing \(D\) values.

• predicate (bool*) – [Output] Flag indicating if the point lies inside the box.

Signature:

void
contains_nd(int *num_nodes,
            int *dimension,
            double *nodes,
            double *point,
            bool *predicate);

void cross_product(double *vec0, double *vec1, double *result)

Computes the cross-product of two vectors \(v_1, v_2\) in \(\mathbf{R}^2\). This is done as if they were embedded in \(\mathbf{R}^3\) and the result is the resulting \(z\)-component \(x_1 y_2 - x_2 y_1\).

Parameters

• vec0 (double*) – [Input] The first vector \(v_1\) in \(\mathbf{R}^2\).

• vec1 (double*) – [Input] The second vector \(v_2\) in \(\mathbf{R}^2\).

• result (double*) – [Output] The cross-product.

Signature:

void
cross_product(double *vec0,
              double *vec1,
              double *result);

bool in_interval(double *value, double *start, double *end)

Checks if a value \(v\) is in an interval \(\left[s, e\right]\).

Parameters

• value (double*) – [Input] The value \(v\).

• start (double*) – [Input] The start \(s\) of the interval \(\left[s, e\right]\).

• end (double*) – [Input] The end \(e\) of the interval \(\left[s, e\right]\).

Returns

Flag indicating if \(v \in \left[s, e\right]\).

Return type

bool

Signature:

bool
in_interval(double *value,
            double *start,
            double *end);

void polygon_collide(int *polygon_size1, double *polygon1, int *polygon_size2, double *polygon2, bool *collision)

Determines if two polygons collide.

Parameters

• polygon_size1 (int*) – [Input] The number of sides \(N_1\) in the first polygon.

• polygon1 (double*) – [Input] The nodes of the first polygon as a \(2 \times N_1\) array. This should be laid out in Fortran order.

• polygon_size2 (int*) – [Input] The number of sides \(N_2\) in the second polygon.

• polygon2 (double*) – [Input] The nodes of the second polygon as a \(2 \times N_2\) array. This should be laid out in Fortran order.

• collision (bool*) – [Output] Flag indicating if the polygons collide.

Signature:

void
polygon_collide(int *polygon_size1,
                double *polygon1,
                int *polygon_size2,
                double *polygon2,
                bool *collision);

void simple_convex_hull(int *num_points, double *points, int *polygon_size, double *polygon)

Computes the convex hull of a set of points.

Parameters

• num_points (int*) – [Input] The number of points \(N\).

• points (double*) – [Input] The points being considered, as a \(2 \times N\) array. This should be laid out in Fortran order.

• polygon_size (int*) – [Output] The number of sides \(M\) in the convex hull. This will be at most \(N\).

• polygon (double*) – [Output] The nodes in the convex hull, as a \(2 \times N\) array laid out in Fortran order. This must be allocated by the caller and must be size \(N\) to account for the extreme case.

Signature:

void
simple_convex_hull(int *num_points,
                   double *points,
                   int *polygon_size,
                   double *polygon);

bool vector_close(int *num_values, double *vec1, double *vec2, double *eps)

Determines if two vectors are close to machine precision.

Parameters

• num_values (int*) – [Input] The dimension \(D\) such that the vectors lie in \(\mathbf{R}^D\).

• vec1 (double*) – [Input] The first vector \(v_1\), as an array of \(D\) values.

• vec2 (double*) – [Input] The second vector \(v_2\), as an array of \(D\) values.

• eps (double*) – [Input] The tolerance \(\varepsilon\) used when comparing \(\left\lVert v_1 - v_2 \right\rVert\) to \(\left\lVert v_1 \right\rVert\) and \(\left\lVert v_2 \right\rVert\).

Returns

Flag indicating if \(v_1\) and \(v_2\) are close to the desired precision.

Return type

bool

Signature:

bool
vector_close(int *num_values,
             double *vec1,
             double *vec2,
             double *eps);

void wiggle_interval(double *value, double *result, bool *success)

Round a value \(v\) into the unit interval if it is sufficiently close. The real line will be broken into five intervals and handled differently on each interval:

• \(v \in \left(-\infty, -2^{-44}\right]\) will not be rounded and will set success to FALSE.

• \(v \in \left(-2^{-44}, 2^{-44}\right)\) will be rounded to 0.0.

• \(v \in \left[2^{-44}, 1 - 2^{-44}\right]\) will be left untouched (i.e. they are safely in the unit interval).

• \(v \in \left(1 - 2^{-44}, 1 + 2^{-44}\right)\) will be rounded to 1.0.

• \(v \in \left[1 + 2^{-44}, \infty\right)\) will not be rounded and will set success to FALSE.

Parameters

• value (double*) – [Input] The value \(v\) to be rounded.

• result (double*) – [Output] The rounded version of \(v\). If success is FALSE this is undefined.

• success (bool*) – [Output] Flag indicating if \(v\) was in the unit interval or sufficiently close to it.

Signature:

void
wiggle_interval(double *value,
                double *result,
                bool *success);