Skip to content

adaptive.learner.triangulation module

Triangulation

Triangulation(coords)

A triangulation object.

Parameters:

Name Type Description Default
coords 2d array-like of floats

Coordinates of vertices.

required

Attributes:

Name Type Description
vertices list of float tuples

Coordinates of the triangulation vertices.

simplices set of integer tuples

List with indices of vertices forming individual simplices

vertex_to_simplices list of sets

Set of simplices connected to a vertex, the index of the vertex is the index of the list.

hull set of int

Exterior vertices

Raises:

Type Description
ValueError

if the list of coordinates is incorrect or the points do not form one or more simplices in the

Source code in adaptive/learner/triangulation.py
def __init__(self, coords):
    if not is_iterable_and_sized(coords):
        raise TypeError("Please provide a 2-dimensional list of points")
    coords = list(coords)
    if not all(is_iterable_and_sized(coord) for coord in coords):
        raise TypeError("Please provide a 2-dimensional list of points")
    if len(coords) == 0:
        raise ValueError("Please provide at least one simplex")
        # raise now because otherwise the next line will raise a less

    dim = len(coords[0])
    if any(len(coord) != dim for coord in coords):
        raise ValueError("Coordinates dimension mismatch")

    if dim == 1:
        raise ValueError("Triangulation class only supports dim >= 2")

    if len(coords) < dim + 1:
        raise ValueError("Please provide at least one simplex")

    coords = list(map(tuple, coords))
    vectors = subtract(coords[1:], coords[0])
    if matrix_rank(vectors) < dim:
        raise ValueError(
            "Initial simplex has zero volumes (the points are linearly dependent)"
        )

    self.vertices = list(coords)
    self.simplices = set()
    # initialise empty set for each vertex
    self.vertex_to_simplices = [set() for _ in coords]

    # find a Delaunay triangulation to start with, then we will throw it
    # away and continue with our own algorithm
    initial_tri = scipy.spatial.Delaunay(coords)
    for simplex in initial_tri.simplices:
        self.add_simplex(simplex)

vertices instance-attribute

vertices = list(coords)

simplices instance-attribute

simplices = set()

vertex_to_simplices instance-attribute

vertex_to_simplices = [set() for _ in coords]

dim property

dim

default_transform property

default_transform

hull property

hull

Compute hull from triangulation.

Parameters:

Name Type Description Default
check bool

Whether to raise an error if the computed hull is different from stored.

True

Returns:

Name Type Description
hull set of int

Vertices in the hull.

delete_simplex

delete_simplex(simplex)
Source code in adaptive/learner/triangulation.py
def delete_simplex(self, simplex):
    simplex = tuple(sorted(simplex))
    self.simplices.remove(simplex)
    for vertex in simplex:
        self.vertex_to_simplices[vertex].remove(simplex)

add_simplex

add_simplex(simplex)
Source code in adaptive/learner/triangulation.py
def add_simplex(self, simplex):
    simplex = tuple(sorted(simplex))
    self.simplices.add(simplex)
    for vertex in simplex:
        self.vertex_to_simplices[vertex].add(simplex)

get_vertices

get_vertices(indices)
Source code in adaptive/learner/triangulation.py
def get_vertices(self, indices):
    return [self.get_vertex(i) for i in indices]

get_vertex

get_vertex(index)
Source code in adaptive/learner/triangulation.py
def get_vertex(self, index):
    if index is None:
        return None
    return self.vertices[index]

get_reduced_simplex

get_reduced_simplex(point, simplex, eps=1e-08) -> list

Check whether vertex lies within a simplex.

Returns:

Name Type Description
vertices list of ints

Indices of vertices of the simplex to which the vertex belongs. An empty list indicates that the vertex is outside the simplex.

Source code in adaptive/learner/triangulation.py
def get_reduced_simplex(self, point, simplex, eps=1e-8) -> list:
    """Check whether vertex lies within a simplex.

    Returns
    -------
    vertices : list of ints
        Indices of vertices of the simplex to which the vertex belongs.
        An empty list indicates that the vertex is outside the simplex.
    """
    # XXX: in the end we want to lose this method
    if len(simplex) != self.dim + 1:
        # We are checking whether point belongs to a face.
        simplex = self.containing(simplex).pop()
    x0 = array(self.vertices[simplex[0]])
    vectors = array(self.get_vertices(simplex[1:])) - x0
    alpha = solve(vectors.T, point - x0)
    if any(alpha < -eps) or sum(alpha) > 1 + eps:
        return []

    result = [i for i, a in enumerate(alpha, 1) if a > eps]
    if sum(alpha) < 1 - eps:
        result.insert(0, 0)

    return [simplex[i] for i in result]

point_in_simplex

point_in_simplex(point, simplex, eps=1e-08)
Source code in adaptive/learner/triangulation.py
def point_in_simplex(self, point, simplex, eps=1e-8):
    vertices = self.get_vertices(simplex)
    return point_in_simplex(point, vertices, eps)

locate_point

locate_point(point)

Find to which simplex the point belongs.

Return indices of the simplex containing the point. Empty tuple means the point is outside the triangulation

Source code in adaptive/learner/triangulation.py
def locate_point(self, point):
    """Find to which simplex the point belongs.

    Return indices of the simplex containing the point.
    Empty tuple means the point is outside the triangulation
    """
    for simplex in self.simplices:
        if self.point_in_simplex(point, simplex):
            return simplex
    return ()

faces

faces(dim=None, simplices=None, vertices=None)

Iterator over faces of a simplex or vertex sequence.

Source code in adaptive/learner/triangulation.py
def faces(self, dim=None, simplices=None, vertices=None):
    """Iterator over faces of a simplex or vertex sequence."""
    if dim is None:
        dim = self.dim

    if simplices is not None and vertices is not None:
        raise ValueError("Only one of simplices and vertices is allowed.")
    if vertices is not None:
        vertices = set(vertices)
        simplices = chain(*(self.vertex_to_simplices[i] for i in vertices))
        simplices = set(simplices)
    elif simplices is None:
        simplices = self.simplices

    faces = (face for tri in simplices for face in combinations(tri, dim))

    if vertices is not None:
        return (face for face in faces if all(i in vertices for i in face))
    else:
        return faces

containing

containing(face)

Simplices containing a face.

Source code in adaptive/learner/triangulation.py
def containing(self, face):
    """Simplices containing a face."""
    return set.intersection(*(self.vertex_to_simplices[i] for i in face))

circumscribed_circle

circumscribed_circle(simplex, transform)

Compute the center and radius of the circumscribed circle of a simplex.

Parameters:

Name Type Description Default
simplex tuple of ints

the simplex to investigate

required

Returns:

Type Description
tuple (center point, radius)

The center and radius of the circumscribed circle

Source code in adaptive/learner/triangulation.py
def circumscribed_circle(self, simplex, transform):
    """Compute the center and radius of the circumscribed circle of a simplex.

    Parameters
    ----------
    simplex : tuple of ints
        the simplex to investigate

    Returns
    -------
    tuple (center point, radius)
        The center and radius of the circumscribed circle
    """
    pts = dot(self.get_vertices(simplex), transform)
    return circumsphere(pts)

point_in_cicumcircle

point_in_cicumcircle(pt_index, simplex, transform)
Source code in adaptive/learner/triangulation.py
def point_in_cicumcircle(self, pt_index, simplex, transform):
    # return self.fast_point_in_circumcircle(pt_index, simplex, transform)
    eps = 1e-8

    center, radius = self.circumscribed_circle(simplex, transform)
    pt = dot(self.get_vertices([pt_index]), transform)[0]

    return norm(center - pt) < (radius * (1 + eps))

bowyer_watson

bowyer_watson(pt_index, containing_simplex=None, transform=None)

Modified Bowyer-Watson point adding algorithm.

Create a hole in the triangulation around the new point, then retriangulate this hole.

Parameters:

Name Type Description Default
pt_index

the index of the point to inspect

required

Returns:

Name Type Description
deleted_simplices set of tuples

Simplices that have been deleted

new_simplices set of tuples

Simplices that have been added

Source code in adaptive/learner/triangulation.py
def bowyer_watson(self, pt_index, containing_simplex=None, transform=None):
    """Modified Bowyer-Watson point adding algorithm.

    Create a hole in the triangulation around the new point,
    then retriangulate this hole.

    Parameters
    ----------
    pt_index: number
        the index of the point to inspect

    Returns
    -------
    deleted_simplices : set of tuples
        Simplices that have been deleted
    new_simplices : set of tuples
        Simplices that have been added
    """
    queue = set()
    done_simplices = set()

    transform = self.default_transform if transform is None else transform

    if containing_simplex is None:
        queue.update(self.vertex_to_simplices[pt_index])
    else:
        queue.add(containing_simplex)

    bad_triangles = set()

    while len(queue):
        simplex = queue.pop()
        done_simplices.add(simplex)

        if self.point_in_cicumcircle(pt_index, simplex, transform):
            self.delete_simplex(simplex)
            todo_points = set(simplex)
            bad_triangles.add(simplex)

            # Get all simplices that share at least a point with the simplex
            neighbors = self.get_neighbors_from_vertices(todo_points)
            # Filter out the already evaluated simplices
            neighbors = neighbors - done_simplices
            neighbors = self.get_face_sharing_neighbors(neighbors, simplex)
            queue.update(neighbors)

    faces = list(self.faces(simplices=bad_triangles))

    multiplicities = Counter(face for face in faces)
    hole_faces = [face for face in faces if multiplicities[face] < 2]

    for face in hole_faces:
        if pt_index not in face:
            simplex = (*face, pt_index)
            if not self._simplex_is_almost_flat(simplex):
                self.add_simplex(simplex)

    new_triangles = self.vertex_to_simplices[pt_index]
    deleted_simplices = bad_triangles - new_triangles
    new_simplices = new_triangles - bad_triangles

    old_vol = sum([self.volume(simplex) for simplex in deleted_simplices])
    new_vol = sum([self.volume(simplex) for simplex in new_simplices])
    assert np.isclose(old_vol, new_vol), f"{old_vol} !== {new_vol}"

    return deleted_simplices, new_simplices

add_point

add_point(point, simplex=None, transform=None)

Add a new vertex and create simplices as appropriate.

Parameters:

Name Type Description Default
point float vector

Coordinates of the point to be added.

required
transform N*N matrix of floats

Multiplication matrix to apply to the point (and neighbouring simplices) when running the Bowyer Watson method.

None
simplex tuple of ints

Simplex containing the point. Empty tuple indicates points outside the hull. If not provided, the algorithm costs O(N), so this should be used whenever possible.

None
Source code in adaptive/learner/triangulation.py
def add_point(self, point, simplex=None, transform=None):
    """Add a new vertex and create simplices as appropriate.

    Parameters
    ----------
    point : float vector
        Coordinates of the point to be added.
    transform : N*N matrix of floats
        Multiplication matrix to apply to the point (and neighbouring
        simplices) when running the Bowyer Watson method.
    simplex : tuple of ints, optional
        Simplex containing the point. Empty tuple indicates points outside
        the hull. If not provided, the algorithm costs O(N), so this should
        be used whenever possible.
    """
    point = tuple(point)
    if simplex is None:
        simplex = self.locate_point(point)

    actual_simplex = simplex
    self.vertex_to_simplices.append(set())

    if not simplex:
        temporary_simplices = self._extend_hull(point)

        pt_index = len(self.vertices) - 1
        deleted_simplices, added_simplices = self.bowyer_watson(
            pt_index, transform=transform
        )

        deleted = deleted_simplices - temporary_simplices
        added = added_simplices | (temporary_simplices - deleted_simplices)
        return deleted, added
    else:
        reduced_simplex = self.get_reduced_simplex(point, simplex)
        if not reduced_simplex:
            self.vertex_to_simplices.pop()  # revert adding vertex
            raise ValueError("Point lies outside of the specified simplex.")
        else:
            simplex = reduced_simplex

    if len(simplex) == 1:
        self.vertex_to_simplices.pop()  # revert adding vertex
        raise ValueError("Point already in triangulation.")
    else:
        pt_index = len(self.vertices)
        self.vertices.append(point)
        return self.bowyer_watson(pt_index, actual_simplex, transform)

volume

volume(simplex)
Source code in adaptive/learner/triangulation.py
def volume(self, simplex):
    prefactor = factorial(self.dim)
    vertices = array(self.get_vertices(simplex))
    vectors = vertices[1:] - vertices[0]
    return float(abs(fast_det(vectors)) / prefactor)

volumes

volumes()
Source code in adaptive/learner/triangulation.py
def volumes(self):
    return [self.volume(sim) for sim in self.simplices]

reference_invariant

reference_invariant()

vertex_to_simplices and simplices are compatible.

Source code in adaptive/learner/triangulation.py
def reference_invariant(self):
    """vertex_to_simplices and simplices are compatible."""
    for vertex in range(len(self.vertices)):
        if any(vertex not in tri for tri in self.vertex_to_simplices[vertex]):
            return False
    for simplex in self.simplices:
        if any(simplex not in self.vertex_to_simplices[pt] for pt in simplex):
            return False
    return True

vertex_invariant

vertex_invariant(vertex)

Simplices originating from a vertex don't overlap.

Source code in adaptive/learner/triangulation.py
def vertex_invariant(self, vertex):
    """Simplices originating from a vertex don't overlap."""
    raise NotImplementedError

get_neighbors_from_vertices

get_neighbors_from_vertices(simplex)
Source code in adaptive/learner/triangulation.py
def get_neighbors_from_vertices(self, simplex):
    return set.union(*[self.vertex_to_simplices[p] for p in simplex])

get_face_sharing_neighbors

get_face_sharing_neighbors(neighbors, simplex)

Keep only the simplices sharing a whole face with simplex.

Source code in adaptive/learner/triangulation.py
def get_face_sharing_neighbors(self, neighbors, simplex):
    """Keep only the simplices sharing a whole face with simplex."""
    return {
        simpl for simpl in neighbors if len(set(simpl) & set(simplex)) == self.dim
    }  # they share a face

get_simplices_attached_to_points

get_simplices_attached_to_points(indices)
Source code in adaptive/learner/triangulation.py
def get_simplices_attached_to_points(self, indices):
    # Get all simplices that share at least a point with the simplex
    neighbors = self.get_neighbors_from_vertices(indices)
    return self.get_face_sharing_neighbors(neighbors, indices)

get_opposing_vertices

get_opposing_vertices(simplex)
Source code in adaptive/learner/triangulation.py
def get_opposing_vertices(self, simplex):
    if simplex not in self.simplices:
        raise ValueError("Provided simplex is not part of the triangulation")
    neighbors = self.get_simplices_attached_to_points(simplex)

    def find_opposing_vertex(vertex):
        # find the simplex:
        simp = next((x for x in neighbors if vertex not in x), None)
        if simp is None:
            return None
        opposing = set(simp) - set(simplex)
        assert len(opposing) == 1
        return opposing.pop()

    result = tuple(find_opposing_vertex(v) for v in simplex)
    return result

convex_invariant

convex_invariant(vertex)

Hull is convex.

Source code in adaptive/learner/triangulation.py
def convex_invariant(self, vertex):
    """Hull is convex."""
    raise NotImplementedError

FakeDelaunay

FakeDelaunay(vertices, simplices)

Bases: Delaunay

Throw in a Triangulation object, and receive a brandnew scipy.spatial.Delaunay

Parameters:

Name Type Description Default
vertices 2d arraylike of floats
required
simplices 2d arraylike of integers
required
Source code in adaptive/learner/triangulation.py
def __init__(self, vertices, simplices):
    """
    Throw in a Triangulation object, and receive a brandnew
    scipy.spatial.Delaunay

    Parameters
    ----------
    vertices : 2d arraylike of floats

    simplices : 2d arraylike of integers
    """

    # just create some Delaunay triangulation object, any would do.
    super().__init__([[0, 1], [1, 0], [0, 0]])

    self.ndim = len(vertices[0])
    self._points = np.array(vertices, dtype="float64")
    self.simplices = np.array(list(simplices), dtype="int32")
    # self.neighbors = np.zero # () todo
    self.nsimplex = len(simplices)
    self.npoints = len(vertices)
    self.min_bound = self._points.min(axis=0)
    self.max_bound = self._points.max(axis=0)
    self._transform = None  # Set it to None to recompute it when needed

    # now the hard part: finding the neighbours
    self.neighbors = -np.ones_like(self.simplices)  # set all to -1

    faces_dict = {}
    for n, simplex in enumerate(self.simplices):
        simplex = tuple(simplex)
        for i, _point in enumerate(simplex):
            face = tuple(sorted(simplex[:i] + simplex[i + 1 :]))
            if face in faces_dict:
                other_simpl_index, other_point_index = faces_dict[face]
                self.neighbors[other_simpl_index, other_point_index] = n
                self.neighbors[n, i] = other_simpl_index
            else:
                faces_dict[face] = (n, i)

ndim instance-attribute

ndim = len(vertices[0])

simplices instance-attribute

simplices = np.array(list(simplices), dtype='int32')

nsimplex instance-attribute

nsimplex = len(simplices)

npoints instance-attribute

npoints = len(vertices)

min_bound instance-attribute

min_bound = self._points.min(axis=0)

max_bound instance-attribute

max_bound = self._points.max(axis=0)

neighbors instance-attribute

neighbors = -np.ones_like(self.simplices)

fast_norm

fast_norm(v)

Take the vector norm for len 2, 3 vectors. Defaults to a square root of the dot product for larger vectors.

Note that for large vectors, it is possible for integer overflow to occur. For instance: vec = [49024, 59454, 12599, -63721, 18517, 27961] dot(vec, vec) = -1602973744

Source code in adaptive/learner/triangulation.py
def fast_norm(v):
    """Take the vector norm for len 2, 3 vectors.
    Defaults to a square root of the dot product for larger vectors.

    Note that for large vectors, it is possible for integer overflow to occur.
    For instance:
    vec = [49024, 59454, 12599, -63721, 18517, 27961]
    dot(vec, vec) = -1602973744

    """
    len_v = len(v)
    if len_v == 2:
        return sqrt(v[0] * v[0] + v[1] * v[1])
    if len_v == 3:
        return sqrt(v[0] * v[0] + v[1] * v[1] + v[2] * v[2])
    return sqrt(dot(v, v))

fast_2d_point_in_simplex

fast_2d_point_in_simplex(point, simplex, eps=1e-08)
Source code in adaptive/learner/triangulation.py
def fast_2d_point_in_simplex(point, simplex, eps=1e-8):
    (p0x, p0y), (p1x, p1y), (p2x, p2y) = simplex
    px, py = point

    area = 0.5 * (-p1y * p2x + p0y * (p2x - p1x) + p1x * p2y + p0x * (p1y - p2y))

    s = 1 / (2 * area) * (+p0y * p2x + (p2y - p0y) * px - p0x * p2y + (p0x - p2x) * py)
    if s < -eps or s > 1 + eps:
        return False
    t = 1 / (2 * area) * (+p0x * p1y + (p0y - p1y) * px - p0y * p1x + (p1x - p0x) * py)

    return (t >= -eps) and (s + t <= 1 + eps)

point_in_simplex

point_in_simplex(point, simplex, eps=1e-08)
Source code in adaptive/learner/triangulation.py
def point_in_simplex(point, simplex, eps=1e-8):
    if len(point) == 2:
        return fast_2d_point_in_simplex(point, simplex, eps)

    x0 = array(simplex[0], dtype=float)
    vectors = array(simplex[1:], dtype=float) - x0
    alpha = solve(vectors.T, point - x0)

    return all(alpha > -eps) and sum(alpha) < 1 + eps

fast_2d_circumcircle

fast_2d_circumcircle(points)

Compute the center and radius of the circumscribed circle of a triangle

Parameters:

Name Type Description Default
points

the points of the triangle to investigate

required

Returns:

Type Description
tuple

(center point : tuple(float), radius: float)

Source code in adaptive/learner/triangulation.py
def fast_2d_circumcircle(points):
    """Compute the center and radius of the circumscribed circle of a triangle

    Parameters
    ----------
    points: 2D array-like
        the points of the triangle to investigate

    Returns
    -------
    tuple
        (center point : tuple(float), radius: float)
    """
    points = array(points)
    # transform to relative coordinates
    pts = points[1:] - points[0]

    (x1, y1), (x2, y2) = pts
    # compute the length squared
    l1 = x1 * x1 + y1 * y1
    l2 = x2 * x2 + y2 * y2

    # compute some determinants
    dx = +l1 * y2 - l2 * y1
    dy = -l1 * x2 + l2 * x1
    aa = +x1 * y2 - x2 * y1
    a = 2 * aa

    # compute center
    x = dx / a
    y = dy / a
    radius = sqrt(x * x + y * y)  # radius = norm([x, y])

    return (x + points[0][0], y + points[0][1]), radius

fast_3d_circumcircle

fast_3d_circumcircle(points)

Compute the center and radius of the circumscribed sphere of a simplex.

Parameters:

Name Type Description Default
points

the points of the triangle to investigate

required

Returns:

Type Description
tuple

(center point : tuple(float), radius: float)

Source code in adaptive/learner/triangulation.py
def fast_3d_circumcircle(points):
    """Compute the center and radius of the circumscribed sphere of a simplex.

    Parameters
    ----------
    points: 2D array-like
        the points of the triangle to investigate

    Returns
    -------
    tuple
        (center point : tuple(float), radius: float)
    """
    points = array(points)
    pts = points[1:] - points[0]

    (x1, y1, z1), (x2, y2, z2), (x3, y3, z3) = pts

    l1 = x1 * x1 + y1 * y1 + z1 * z1
    l2 = x2 * x2 + y2 * y2 + z2 * z2
    l3 = x3 * x3 + y3 * y3 + z3 * z3

    # Compute some determinants:
    dx = +l1 * (y2 * z3 - z2 * y3) - l2 * (y1 * z3 - z1 * y3) + l3 * (y1 * z2 - z1 * y2)
    dy = +l1 * (x2 * z3 - z2 * x3) - l2 * (x1 * z3 - z1 * x3) + l3 * (x1 * z2 - z1 * x2)
    dz = +l1 * (x2 * y3 - y2 * x3) - l2 * (x1 * y3 - y1 * x3) + l3 * (x1 * y2 - y1 * x2)
    aa = +x1 * (y2 * z3 - z2 * y3) - x2 * (y1 * z3 - z1 * y3) + x3 * (y1 * z2 - z1 * y2)
    a = 2 * aa

    center = (dx / a, -dy / a, dz / a)
    radius = fast_norm(center)
    center = (
        center[0] + points[0][0],
        center[1] + points[0][1],
        center[2] + points[0][2],
    )

    return center, radius

fast_det

fast_det(matrix)
Source code in adaptive/learner/triangulation.py
def fast_det(matrix):
    matrix = asarray(matrix, dtype=float)
    if matrix.shape == (2, 2):
        return matrix[0][0] * matrix[1][1] - matrix[1][0] * matrix[0][1]
    elif matrix.shape == (3, 3):
        a, b, c, d, e, f, g, h, i = matrix.ravel()
        return a * (e * i - f * h) - b * (d * i - f * g) + c * (d * h - e * g)
    else:
        return ndet(matrix)

circumsphere

circumsphere(pts)

Compute the center and radius of a N dimension sphere which touches each point in pts.

Parameters:

Name Type Description Default
pts array-like, of shape (N-dim + 1, N-dim)

The points for which we would like to compute a circumsphere.

required

Returns:

Name Type Description
center tuple of floats of size N-dim
radius a positive float
A valid center and radius, if a circumsphere is possible, and no points are repeated.
If points are repeated, or a circumsphere is not possible, will return nans, and a
ZeroDivisionError may occur.
Will fail for matrices which are not (N-dim + 1, N-dim) in size due to non-square determinants:
will raise numpy.linalg.LinAlgError.
May fail for points that are integers (due to 32bit integer overflow).
Source code in adaptive/learner/triangulation.py
def circumsphere(pts):
    """Compute the center and radius of a N dimension sphere which touches each point in pts.

    Parameters
    ----------
    pts : array-like, of shape (N-dim + 1, N-dim)
        The points for which we would like to compute a circumsphere.

    Returns
    -------
    center : tuple of floats of size N-dim
    radius : a positive float
    A valid center and radius, if a circumsphere is possible, and no points are repeated.
    If points are repeated, or a circumsphere is not possible, will return nans, and a
    ZeroDivisionError may occur.
    Will fail for matrices which are not (N-dim + 1, N-dim) in size due to non-square determinants:
    will raise numpy.linalg.LinAlgError.
    May fail for points that are integers (due to 32bit integer overflow).
    """

    dim = len(pts) - 1
    if dim == 2:
        return fast_2d_circumcircle(pts)
    if dim == 3:
        return fast_3d_circumcircle(pts)

    # Modified method from http://mathworld.wolfram.com/Circumsphere.html
    mat = array([[np_sum(square(pt)), *pt, 1] for pt in pts])
    center = zeros(dim)
    a = 1 / (2 * ndet(mat[:, 1:]))
    factor = a
    # Use ind to index into the matrix columns
    ind = ones((dim + 2,), bool)
    for i in range(1, len(pts)):
        ind[i - 1] = True
        ind[i] = False
        center[i - 1] = factor * ndet(mat[:, ind])
        factor *= -1

    # Use subtract as we don't know the type of x0.
    x0 = pts[0]
    vec = subtract(center, x0)
    # Vector norm.
    radius = sqrt(dot(vec, vec))

    return tuple(center), radius

orientation

orientation(face, origin)

Compute the orientation of the face with respect to a point, origin.

Parameters:

Name Type Description Default
face array-like, of shape (N-dim, N-dim)

The hyperplane we want to know the orientation of Do notice that the order in which you provide the points is critical

required
origin array-like, point of shape (N-dim)

The point to compute the orientation from

required

Returns:

Type Description
0 if the origin lies in the same hyperplane as face,
-1 or 1 to indicate left or right orientation
If two points lie on the same side of the face, the orientation will
be equal, if they lie on the other side of the face, it will be negated.
Source code in adaptive/learner/triangulation.py
def orientation(face, origin):
    """Compute the orientation of the face with respect to a point, origin.

    Parameters
    ----------
    face : array-like, of shape (N-dim, N-dim)
        The hyperplane we want to know the orientation of
        Do notice that the order in which you provide the points is critical
    origin : array-like, point of shape (N-dim)
        The point to compute the orientation from

    Returns
    -------
    0 if the origin lies in the same hyperplane as face,
    -1 or 1 to indicate left or right orientation

    If two points lie on the same side of the face, the orientation will
    be equal, if they lie on the other side of the face, it will be negated.
    """
    vectors = array(face)
    sign, logdet = slogdet(vectors - origin)
    if logdet < -50:  # assume it to be zero when it's close to zero
        return 0
    return sign

is_iterable_and_sized

is_iterable_and_sized(obj)
Source code in adaptive/learner/triangulation.py
def is_iterable_and_sized(obj):
    return isinstance(obj, Iterable) and isinstance(obj, Sized)

simplex_volume_in_embedding

simplex_volume_in_embedding(vertices) -> float

Calculate the volume of a simplex in a higher dimensional embedding. That is: dim > len(vertices) - 1. For example if you would like to know the surface area of a triangle in a 3d space.

This algorithm has not been tested for numerical stability.

Parameters:

Name Type Description Default
vertices 2D arraylike of floats
required

Returns:

Name Type Description
volume float

the volume of the simplex with given vertices.

Raises:

Type Description
ValueError

if the vertices do not form a simplex (for example, because they are coplanar, colinear or coincident).

Warning: this algorithm has not been tested for numerical stability.
Source code in adaptive/learner/triangulation.py
def simplex_volume_in_embedding(vertices) -> float:
    """Calculate the volume of a simplex in a higher dimensional embedding.
    That is: dim > len(vertices) - 1. For example if you would like to know the
    surface area of a triangle in a 3d space.

    This algorithm has not been tested for numerical stability.

    Parameters
    ----------
    vertices : 2D arraylike of floats

    Returns
    -------
    volume : float
        the volume of the simplex with given vertices.

    Raises
    ------
    ValueError
        if the vertices do not form a simplex (for example,
        because they are coplanar, colinear or coincident).

    Warning: this algorithm has not been tested for numerical stability.
    """
    # Implements http://mathworld.wolfram.com/Cayley-MengerDeterminant.html
    # Modified from https://codereview.stackexchange.com/questions/77593/calculating-the-volume-of-a-tetrahedron

    vertices = asarray(vertices, dtype=float)
    dim = len(vertices[0])
    if dim == 2:
        # Heron's formula
        a, b, c = scipy.spatial.distance.pdist(vertices, metric="euclidean")
        s = 0.5 * (a + b + c)
        return sqrt(s * (s - a) * (s - b) * (s - c))

    # β_ij = |v_i - v_k|²
    sq_dists = scipy.spatial.distance.pdist(vertices, metric="sqeuclidean")

    # Add border while compressed
    num_verts = scipy.spatial.distance.num_obs_y(sq_dists)
    bordered = concatenate((ones(num_verts), sq_dists))

    # Make matrix and find volume
    sq_dists_mat = scipy.spatial.distance.squareform(bordered)

    coeff = -((-2) ** (num_verts - 1)) * factorial(num_verts - 1) ** 2
    vol_square = fast_det(sq_dists_mat) / coeff

    if vol_square < 0:
        if vol_square > -1e-15:
            return 0
        raise ValueError("Provided vertices do not form a simplex")

    return sqrt(vol_square)