gpp_geometry

Contents:

gpp_geometry.hpp

This file contains classes and utilities to help with (planar) geometry operations.

  • Functions:

    • CheckPointInHypercube: checks whether a point is in the domain \(\, [x_{1,min}, x_{1,max}] X ... X [x_{dim,min}, x_{dim,max}]\)
    • CheckPointInUnitSimplex: checks whether a point is in the unit simplex
  • Structs:

    • ClosedInterval: represents the closed interval \(\, [a, b]\) with utilities for length, in/out test etc.
    • Plane: represents a dim-dimensional plane as its “outward” unit normal and the signed distance from the origin. Contains functions for distance, projection, etc.

namespace optimal_learning

Macro to allow restrict as a keyword for C++ compilation and CUDA/nvcc compilation. See related entry in gpp_common.hpp for more details.

Functions

OL_WARN_UNUSED_RESULT OL_NONNULL_POINTERS bool CheckPointInHypercube(ClosedInterval const *restrict domain, double const *restrict point, int dim)

Simple auxilliary function that checks if a point is within the given hypercube.

Parameters:
domain[dim]:array of ClosedInterval specifying the boundaries of a dim-dimensional tensor-product domain.
point[dim]:the point to check
dim:the number of spatial dimensions
Returns:
true if the point is inside the specified tensor-product domain

OL_NONNULL_POINTERS OL_WARN_UNUSED_RESULT bool CheckPointInUnitSimplex(double const *restrict point, int dim)

Checks if a point is inside/on the unit d-simplex. A point \(\, x_i\) lies inside the unit d-simplex if:

  1. \(\, x_i \geq 0 \ \forall i\) (i ranging over dimension)
  2. \(\, \sum_i x_i \leq 1\)

Implying that \(\, x_i \leq 1 \ \forall i\).

Parameters:
point[dim]:point to check
dim:number of dimensions
Returns:
true if the point lies inside/on the unit d-simplex

class ClosedInterval

Container to represent the mathematical notion of a closed interval, commonly written \(\, [a,b]\). The closed interval \(\, [a,b]\) is the set of all numbers \(\, x \in \mathbb{R}\) such that \(\, a \leq x \leq b\). Note that “closed” here indicates the interval includes both endpoints. An interval with \(\, a > b\) is considered empty.

This struct is “trivial” and “standard layout” and thus “POD” (in the C++11 sense).

This struct is not an aggregate; list (aka brace) initialization and a 2-argument constructor are both available:

ClosedInterval tmp(1.0, 2.0);  // this ctor makes it non-aggregate
ClosedInterval tmp{1.0, 2.0};  // and brace-style (aka initializer list) inits also work

Public Functions

ClosedInterval()

Explicitly defaulted default constructor. Defining a custom ctor (below) disables the default ctor, so we explicitly default it. This is needed to maintain POD-ness.

ClosedInterval(double min_in, double max_in)

Constructs a ClosedInterval object with specified min, max.

The presence of this ctor makes this object a non-aggregate, so brace-initialization follow list initialization rules (not aggregate initialization):

Parameters:
min_in:left bound of the interval
max_in:right bound of the interval

bool IsInside(double value)

Check if a value is inside this ClosedInterval.

Parameters:
value:the value to check
Returns:
true if min \(\,\leq\) value \(\,\leq\) max

double Length()

Compute the length of this ClosedInterval; result can be negative (i.e., an empty interval).

Returns:
length of the interval

bool IsEmpty()

Checks whether the interval is \(\,\emptyset\) (i.e., max < min).

Equivalent to Length() \(\,\geq\) 0.0.

Returns:
true if the interval is non-empty: max \(\,\geq\) min

Public Members

double min

left and right boundaries, [min, max], of this ClosedInterval

double max

class Plane

We specify a plane in dim-space using the Hesse (or Hessian) Normal Form:

The equation of plane requires dim + 1 real numbers:

\(\, a_0 + \sum_{i=0}^{dim} n_i x_i = 0\)

Hence we can describe any plane as a vector, \(\, [n_0, n_2, ..., n_{dim-1}]\), and a real number, \(\, a_0\).

Let \(\, n_{vec} = [n_0, ..., n_{dim-1}]\) be the (outward) unit normal vector. By convention, \(\, \|n_{vec}\|_2 = 1\). \(\, a_0\) is the signed distance to the origin. This is the distance from the plane to the origin in the direction of \(\, n_{vec}\). Put another way, \(\, a_0\) is positive if the origin is in the same half-space “pointed to” by \(\, n_{vec}\) and negative otherwise.

Note: \(\, a_0\) is measured in units of \(\, \|n_{vec}\|\), so if it is not an unit vector, that is analogous to scaling :math:`, a_0nme.

As an example, let’s consider 4 planes with dim = 2:

  • \(\, a_0\) = -1, and \(\, n_{vec}\) = { 1.0, 0.0}: the plane x = 1 with rightward pointing normal.
  • \(\, a_0\) = -1, and \(\, n_{vec}\) = {-1.0, 0.0}: the plane x = -1 with leftward pointing normal.
  • \(\, a_0\) = 1, and \(\, n_{vec}\) = { 1.0, 0.0}: the plane x = -1 with rightward pointing normal.
  • \(\, a_0\) = 1, and \(\, n_{vec}\) = {-1.0, 0.0}: the plane x = 1 with leftward pointing normal.

Be careful with the signs.

Another common way of specifying a plane is via a point \(\, x_0\) and an unit normal, \(\, n_{vec}\). A point x is in the plane if and only if \(\, (x-x_0) \cdot n_{vec} = 0\). Since \(\, x_0\) is constant, we can precompute and store \(\, ms x_0 \cdot n_{vec} = -a_0\), yielding: \(\, x \cdot n_{vec} - x_0 \cdot n_{vec} = x \cdot n_{vec} + a_0\), which is our original equation of a plane.

Public Functions

Plane()

Plane(int dim_in)

Creates a zero-initialized plane object with enough space for dim-dimensions.

Note

This plane is invalid (unit_normal := zero is not a unit vector) and needs to have its members initialized. That said, no member functions will fail even without complete initialization.

Parameters:
dim:the number of spatial dimensions

Plane(double const *restrict unit_normal_in, double offset_in, int dim_in)

Creates a plane in dim-dimensions with the specified unit normal (\(\, n_i\)) and offset (\(\, a_0\)):

\(\, a_0 + \sum_{i=0}^{dim} n_i * x_i = 0\)

Note

Failure to specify a unit normal will result in surprising behavior. \(\, a_0\) is really in units of \(\,\|n_{vec}\|\), so if \(\,\|n_{vec}\| = 3.5\), then the actual distance to the origin is \(\, 3.5 a_0\).

Parameters:
dim:the number of spatial dimensions
unit_normal[dim]:
 the unit normal vector. VectorNorm(unit_normal, dim) must be 1.0
offset:a_0, the signed distance to the origin (see class docs)

Plane(double const *restrict unit_normal_in, double const *restrict point, int dim_in)

Creates a plane in dim-dimensions that contains “point,” with the specified unit normal.

Parameters:
dim:the number of spatial dimensions
unit_normal[dim]:
 the unit normal vector. VectorNorm(unit_normal, dim) must be 1.0
point[dim]:a point contained in the plane

int dim()

Returns:
the number of spatial dimensions (that this plane lives in)

double OrthogonalDistanceToPoint(double const *restrict point)

Computes the signed, shortest distance from this plane to point: positive means the point is in the half-space determined by the direction of unit_normal.

Note

if point is the origin, this yields precisely \(\, a_0\) (offset).

Parameters:
point[dim]:point to compute distance to
Returns:
signed, shortest distance from this plane to point, where positive means the point and normal are in the same half-space

void OrthogonalProjectionOntoPlane(double *restrict point)

Projects a point (orthogonally) onto a plane; i.e., finds the point on the plane that is closest to the input point.

Parameters:
point[dim]:point to project onto plane
Outputs:
point[dim]:point projected onto plane

double DistanceToPlaneAlongVector(double const *restrict point, double const *restrict vector)

Computes the signed distance from the specified point to this plane along the specified vector. This result is computed in units of \(\,\|vector\|_2\). That is, a distance of 3.14 means if we compute:

new_point = 3.14*vector + point,

then new_point will be on this plane.

A negative distance means the plane is “behind” the ray.

Parameters:
point[dim]:point to compute distance from
vector[dim]:vector to compute distance along
Returns:
Signed distance along the given vector; positive means the intersection is in the same direction as the vector. This result is in units of \(\,\|vector\|_2\); normalize vector if you want an actual distance.

Public Members

double offset

the scalar a_0: the distance from the plane to the origin

std::vector< double > unit_normal

the vector n_i: the “outward” unit normal vector