test_qhull.py

import os
import copy

import numpy as np
from numpy.testing import (assert_equal, assert_almost_equal,
                           assert_, assert_allclose, assert_array_equal)
import pytest
from pytest import raises as assert_raises

import scipy.spatial._qhull as qhull
from scipy.spatial import cKDTree as KDTree
from scipy.spatial import Voronoi

import itertools

def sorted_tuple(x):
    return tuple(sorted(x))


def assert_unordered_tuple_list_equal(a, b, tpl=tuple):
    if isinstance(a, np.ndarray):
        a = a.tolist()
    if isinstance(b, np.ndarray):
        b = b.tolist()
    a = list(map(tpl, a))
    a.sort()
    b = list(map(tpl, b))
    b.sort()
    assert_equal(a, b)


np.random.seed(1234)

points = [(0,0), (0,1), (1,0), (1,1), (0.5, 0.5), (0.5, 1.5)]

pathological_data_1 = np.array([
    [-3.14,-3.14], [-3.14,-2.36], [-3.14,-1.57], [-3.14,-0.79],
    [-3.14,0.0], [-3.14,0.79], [-3.14,1.57], [-3.14,2.36],
    [-3.14,3.14], [-2.36,-3.14], [-2.36,-2.36], [-2.36,-1.57],
    [-2.36,-0.79], [-2.36,0.0], [-2.36,0.79], [-2.36,1.57],
    [-2.36,2.36], [-2.36,3.14], [-1.57,-0.79], [-1.57,0.79],
    [-1.57,-1.57], [-1.57,0.0], [-1.57,1.57], [-1.57,-3.14],
    [-1.57,-2.36], [-1.57,2.36], [-1.57,3.14], [-0.79,-1.57],
    [-0.79,1.57], [-0.79,-3.14], [-0.79,-2.36], [-0.79,-0.79],
    [-0.79,0.0], [-0.79,0.79], [-0.79,2.36], [-0.79,3.14],
    [0.0,-3.14], [0.0,-2.36], [0.0,-1.57], [0.0,-0.79], [0.0,0.0],
    [0.0,0.79], [0.0,1.57], [0.0,2.36], [0.0,3.14], [0.79,-3.14],
    [0.79,-2.36], [0.79,-0.79], [0.79,0.0], [0.79,0.79],
    [0.79,2.36], [0.79,3.14], [0.79,-1.57], [0.79,1.57],
    [1.57,-3.14], [1.57,-2.36], [1.57,2.36], [1.57,3.14],
    [1.57,-1.57], [1.57,0.0], [1.57,1.57], [1.57,-0.79],
    [1.57,0.79], [2.36,-3.14], [2.36,-2.36], [2.36,-1.57],
    [2.36,-0.79], [2.36,0.0], [2.36,0.79], [2.36,1.57],
    [2.36,2.36], [2.36,3.14], [3.14,-3.14], [3.14,-2.36],
    [3.14,-1.57], [3.14,-0.79], [3.14,0.0], [3.14,0.79],
    [3.14,1.57], [3.14,2.36], [3.14,3.14],
])

pathological_data_2 = np.array([
    [-1, -1], [-1, 0], [-1, 1],
    [0, -1], [0, 0], [0, 1],
    [1, -1 - np.finfo(np.float64).eps], [1, 0], [1, 1],
])

bug_2850_chunks = [np.random.rand(10, 2),
                   np.array([[0,0], [0,1], [1,0], [1,1]])  # add corners
                   ]

# same with some additional chunks
bug_2850_chunks_2 = (bug_2850_chunks +
                     [np.random.rand(10, 2),
                      0.25 + np.array([[0,0], [0,1], [1,0], [1,1]])])

DATASETS = {
    'some-points': np.asarray(points),
    'random-2d': np.random.rand(30, 2),
    'random-3d': np.random.rand(30, 3),
    'random-4d': np.random.rand(30, 4),
    'random-5d': np.random.rand(30, 5),
    'random-6d': np.random.rand(10, 6),
    'random-7d': np.random.rand(10, 7),
    'random-8d': np.random.rand(10, 8),
    'pathological-1': pathological_data_1,
    'pathological-2': pathological_data_2
}

INCREMENTAL_DATASETS = {
    'bug-2850': (bug_2850_chunks, None),
    'bug-2850-2': (bug_2850_chunks_2, None),
}


def _add_inc_data(name, chunksize):
    """
    Generate incremental datasets from basic data sets
    """
    points = DATASETS[name]
    ndim = points.shape[1]

    opts = None
    nmin = ndim + 2

    if name == 'some-points':
        # since Qz is not allowed, use QJ
        opts = 'QJ Pp'
    elif name == 'pathological-1':
        # include enough points so that we get different x-coordinates
        nmin = 12

    chunks = [points[:nmin]]
    for j in range(nmin, len(points), chunksize):
        chunks.append(points[j:j+chunksize])

    new_name = "%s-chunk-%d" % (name, chunksize)
    assert new_name not in INCREMENTAL_DATASETS
    INCREMENTAL_DATASETS[new_name] = (chunks, opts)


for name in DATASETS:
    for chunksize in 1, 4, 16:
        _add_inc_data(name, chunksize)


class Test_Qhull:
    def test_swapping(self):
        # Check that Qhull state swapping works

        x = qhull._Qhull(b'v',
                         np.array([[0,0],[0,1],[1,0],[1,1.],[0.5,0.5]]),
                         b'Qz')
        xd = copy.deepcopy(x.get_voronoi_diagram())

        y = qhull._Qhull(b'v',
                         np.array([[0,0],[0,1],[1,0],[1,2.]]),
                         b'Qz')
        yd = copy.deepcopy(y.get_voronoi_diagram())

        xd2 = copy.deepcopy(x.get_voronoi_diagram())
        x.close()
        yd2 = copy.deepcopy(y.get_voronoi_diagram())
        y.close()

        assert_raises(RuntimeError, x.get_voronoi_diagram)
        assert_raises(RuntimeError, y.get_voronoi_diagram)

        assert_allclose(xd[0], xd2[0])
        assert_unordered_tuple_list_equal(xd[1], xd2[1], tpl=sorted_tuple)
        assert_unordered_tuple_list_equal(xd[2], xd2[2], tpl=sorted_tuple)
        assert_unordered_tuple_list_equal(xd[3], xd2[3], tpl=sorted_tuple)
        assert_array_equal(xd[4], xd2[4])

        assert_allclose(yd[0], yd2[0])
        assert_unordered_tuple_list_equal(yd[1], yd2[1], tpl=sorted_tuple)
        assert_unordered_tuple_list_equal(yd[2], yd2[2], tpl=sorted_tuple)
        assert_unordered_tuple_list_equal(yd[3], yd2[3], tpl=sorted_tuple)
        assert_array_equal(yd[4], yd2[4])

        x.close()
        assert_raises(RuntimeError, x.get_voronoi_diagram)
        y.close()
        assert_raises(RuntimeError, y.get_voronoi_diagram)

    def test_issue_8051(self):
        points = np.array(
            [[0, 0], [0, 1], [0, 2], [1, 0], [1, 1], [1, 2],[2, 0], [2, 1], [2, 2]]
        )
        Voronoi(points)


class TestUtilities:
    """
    Check that utility functions work.

    """

    def test_find_simplex(self):
        # Simple check that simplex finding works
        points = np.array([(0,0), (0,1), (1,1), (1,0)], dtype=np.float64)
        tri = qhull.Delaunay(points)

        # +---+
        # |\ 0|
        # | \ |
        # |1 \|
        # +---+

        assert_equal(tri.simplices, [[1, 3, 2], [3, 1, 0]])

        for p in [(0.25, 0.25, 1),
                  (0.75, 0.75, 0),
                  (0.3, 0.2, 1)]:
            i = tri.find_simplex(p[:2])
            assert_equal(i, p[2], err_msg=f'{p!r}')
            j = qhull.tsearch(tri, p[:2])
            assert_equal(i, j)

    def test_plane_distance(self):
        # Compare plane distance from hyperplane equations obtained from Qhull
        # to manually computed plane equations
        x = np.array([(0,0), (1, 1), (1, 0), (0.99189033, 0.37674127),
                      (0.99440079, 0.45182168)], dtype=np.float64)
        p = np.array([0.99966555, 0.15685619], dtype=np.float64)

        tri = qhull.Delaunay(x)

        z = tri.lift_points(x)
        pz = tri.lift_points(p)

        dist = tri.plane_distance(p)

        for j, v in enumerate(tri.simplices):
            x1 = z[v[0]]
            x2 = z[v[1]]
            x3 = z[v[2]]

            n = np.cross(x1 - x3, x2 - x3)
            n /= np.sqrt(np.dot(n, n))
            n *= -np.sign(n[2])

            d = np.dot(n, pz - x3)

            assert_almost_equal(dist[j], d)

    def test_convex_hull(self):
        # Simple check that the convex hull seems to works
        points = np.array([(0,0), (0,1), (1,1), (1,0)], dtype=np.float64)
        tri = qhull.Delaunay(points)

        # +---+
        # |\ 0|
        # | \ |
        # |1 \|
        # +---+

        assert_equal(tri.convex_hull, [[3, 2], [1, 2], [1, 0], [3, 0]])

    def test_volume_area(self):
        #Basic check that we get back the correct volume and area for a cube
        points = np.array([(0, 0, 0), (0, 1, 0), (1, 0, 0), (1, 1, 0),
                           (0, 0, 1), (0, 1, 1), (1, 0, 1), (1, 1, 1)])
        hull = qhull.ConvexHull(points)

        assert_allclose(hull.volume, 1., rtol=1e-14,
                        err_msg="Volume of cube is incorrect")
        assert_allclose(hull.area, 6., rtol=1e-14,
                        err_msg="Area of cube is incorrect")

    def test_random_volume_area(self):
        #Test that the results for a random 10-point convex are
        #coherent with the output of qconvex Qt s FA
        points = np.array([(0.362568364506, 0.472712355305, 0.347003084477),
                           (0.733731893414, 0.634480295684, 0.950513180209),
                           (0.511239955611, 0.876839441267, 0.418047827863),
                           (0.0765906233393, 0.527373281342, 0.6509863541),
                           (0.146694972056, 0.596725793348, 0.894860986685),
                           (0.513808585741, 0.069576205858, 0.530890338876),
                           (0.512343805118, 0.663537132612, 0.037689295973),
                           (0.47282965018, 0.462176697655, 0.14061843691),
                           (0.240584597123, 0.778660020591, 0.722913476339),
                           (0.951271745935, 0.967000673944, 0.890661319684)])

        hull = qhull.ConvexHull(points)
        assert_allclose(hull.volume, 0.14562013, rtol=1e-07,
                        err_msg="Volume of random polyhedron is incorrect")
        assert_allclose(hull.area, 1.6670425, rtol=1e-07,
                        err_msg="Area of random polyhedron is incorrect")

    def test_incremental_volume_area_random_input(self):
        """Test that incremental mode gives the same volume/area as
        non-incremental mode and incremental mode with restart"""
        nr_points = 20
        dim = 3
        points = np.random.random((nr_points, dim))
        inc_hull = qhull.ConvexHull(points[:dim+1, :], incremental=True)
        inc_restart_hull = qhull.ConvexHull(points[:dim+1, :], incremental=True)
        for i in range(dim+1, nr_points):
            hull = qhull.ConvexHull(points[:i+1, :])
            inc_hull.add_points(points[i:i+1, :])
            inc_restart_hull.add_points(points[i:i+1, :], restart=True)
            assert_allclose(hull.volume, inc_hull.volume, rtol=1e-7)
            assert_allclose(hull.volume, inc_restart_hull.volume, rtol=1e-7)
            assert_allclose(hull.area, inc_hull.area, rtol=1e-7)
            assert_allclose(hull.area, inc_restart_hull.area, rtol=1e-7)

    def _check_barycentric_transforms(self, tri, err_msg="",
                                      unit_cube=False,
                                      unit_cube_tol=0):
        """Check that a triangulation has reasonable barycentric transforms"""
        vertices = tri.points[tri.simplices]
        sc = 1/(tri.ndim + 1.0)
        centroids = vertices.sum(axis=1) * sc

        # Either: (i) the simplex has a `nan` barycentric transform,
        # or, (ii) the centroid is in the simplex

        def barycentric_transform(tr, x):
            r = tr[:,-1,:]
            Tinv = tr[:,:-1,:]
            return np.einsum('ijk,ik->ij', Tinv, x - r)

        eps = np.finfo(float).eps

        c = barycentric_transform(tri.transform, centroids)
        with np.errstate(invalid="ignore"):
            ok = np.isnan(c).all(axis=1) | (abs(c - sc)/sc < 0.1).all(axis=1)

        assert_(ok.all(), f"{err_msg} {np.nonzero(~ok)}")

        # Invalid simplices must be (nearly) zero volume
        q = vertices[:,:-1,:] - vertices[:,-1,None,:]
        volume = np.array([np.linalg.det(q[k,:,:])
                           for k in range(tri.nsimplex)])
        ok = np.isfinite(tri.transform[:,0,0]) | (volume < np.sqrt(eps))
        assert_(ok.all(), f"{err_msg} {np.nonzero(~ok)}")

        # Also, find_simplex for the centroid should end up in some
        # simplex for the non-degenerate cases
        j = tri.find_simplex(centroids)
        ok = (j != -1) | np.isnan(tri.transform[:,0,0])
        assert_(ok.all(), f"{err_msg} {np.nonzero(~ok)}")

        if unit_cube:
            # If in unit cube, no interior point should be marked out of hull
            at_boundary = (centroids <= unit_cube_tol).any(axis=1)
            at_boundary |= (centroids >= 1 - unit_cube_tol).any(axis=1)

            ok = (j != -1) | at_boundary
            assert_(ok.all(), f"{err_msg} {np.nonzero(~ok)}")

    def test_degenerate_barycentric_transforms(self):
        # The triangulation should not produce invalid barycentric
        # transforms that stump the simplex finding
        data = np.load(os.path.join(os.path.dirname(__file__), 'data',
                                    'degenerate_pointset.npz'))
        points = data['c']
        data.close()

        tri = qhull.Delaunay(points)

        # Check that there are not too many invalid simplices
        bad_count = np.isnan(tri.transform[:,0,0]).sum()
        assert_(bad_count < 23, bad_count)

        # Check the transforms
        self._check_barycentric_transforms(tri)

    @pytest.mark.xslow
    def test_more_barycentric_transforms(self):
        # Triangulate some "nasty" grids

        eps = np.finfo(float).eps

        npoints = {2: 70, 3: 11, 4: 5, 5: 3}

        for ndim in range(2, 6):
            # Generate an uniform grid in n-d unit cube
            x = np.linspace(0, 1, npoints[ndim])
            grid = np.c_[
                list(map(np.ravel, np.broadcast_arrays(*np.ix_(*([x]*ndim)))))
            ].T

            err_msg = "ndim=%d" % ndim

            # Check using regular grid
            tri = qhull.Delaunay(grid)
            self._check_barycentric_transforms(tri, err_msg=err_msg,
                                               unit_cube=True)

            # Check with eps-perturbations
            np.random.seed(1234)
            m = (np.random.rand(grid.shape[0]) < 0.2)
            grid[m,:] += 2*eps*(np.random.rand(*grid[m,:].shape) - 0.5)

            tri = qhull.Delaunay(grid)
            self._check_barycentric_transforms(tri, err_msg=err_msg,
                                               unit_cube=True,
                                               unit_cube_tol=2*eps)

            # Check with duplicated data
            tri = qhull.Delaunay(np.r_[grid, grid])
            self._check_barycentric_transforms(tri, err_msg=err_msg,
                                               unit_cube=True,
                                               unit_cube_tol=2*eps)


class TestVertexNeighborVertices:
    def _check(self, tri):
        expected = [set() for j in range(tri.points.shape[0])]
        for s in tri.simplices:
            for a in s:
                for b in s:
                    if a != b:
                        expected[a].add(b)

        indptr, indices = tri.vertex_neighbor_vertices

        got = [set(map(int, indices[indptr[j]:indptr[j+1]]))
               for j in range(tri.points.shape[0])]

        assert_equal(got, expected, err_msg=f"{got!r} != {expected!r}")

    def test_triangle(self):
        points = np.array([(0,0), (0,1), (1,0)], dtype=np.float64)
        tri = qhull.Delaunay(points)
        self._check(tri)

    def test_rectangle(self):
        points = np.array([(0,0), (0,1), (1,1), (1,0)], dtype=np.float64)
        tri = qhull.Delaunay(points)
        self._check(tri)

    def test_complicated(self):
        points = np.array([(0,0), (0,1), (1,1), (1,0),
                           (0.5, 0.5), (0.9, 0.5)], dtype=np.float64)
        tri = qhull.Delaunay(points)
        self._check(tri)


class TestDelaunay:
    """
    Check that triangulation works.

    """
    def test_masked_array_fails(self):
        masked_array = np.ma.masked_all(1)
        assert_raises(ValueError, qhull.Delaunay, masked_array)

    def test_array_with_nans_fails(self):
        points_with_nan = np.array([(0,0), (0,1), (1,1), (1,np.nan)], dtype=np.float64)
        assert_raises(ValueError, qhull.Delaunay, points_with_nan)

    def test_nd_simplex(self):
        # simple smoke test: triangulate a n-dimensional simplex
        for nd in range(2, 8):
            points = np.zeros((nd+1, nd))
            for j in range(nd):
                points[j,j] = 1.0
            points[-1,:] = 1.0

            tri = qhull.Delaunay(points)

            tri.simplices.sort()

            assert_equal(tri.simplices, np.arange(nd+1, dtype=int)[None, :])
            assert_equal(tri.neighbors, -1 + np.zeros((nd+1), dtype=int)[None,:])

    def test_2d_square(self):
        # simple smoke test: 2d square
        points = np.array([(0,0), (0,1), (1,1), (1,0)], dtype=np.float64)
        tri = qhull.Delaunay(points)

        assert_equal(tri.simplices, [[1, 3, 2], [3, 1, 0]])
        assert_equal(tri.neighbors, [[-1, -1, 1], [-1, -1, 0]])

    def test_duplicate_points(self):
        x = np.array([0, 1, 0, 1], dtype=np.float64)
        y = np.array([0, 0, 1, 1], dtype=np.float64)

        xp = np.r_[x, x]
        yp = np.r_[y, y]

        # shouldn't fail on duplicate points
        qhull.Delaunay(np.c_[x, y])
        qhull.Delaunay(np.c_[xp, yp])

    def test_pathological(self):
        # both should succeed
        points = DATASETS['pathological-1']
        tri = qhull.Delaunay(points)
        assert_equal(tri.points[tri.simplices].max(), points.max())
        assert_equal(tri.points[tri.simplices].min(), points.min())

        points = DATASETS['pathological-2']
        tri = qhull.Delaunay(points)
        assert_equal(tri.points[tri.simplices].max(), points.max())
        assert_equal(tri.points[tri.simplices].min(), points.min())

    def test_joggle(self):
        # Check that the option QJ indeed guarantees that all input points
        # occur as vertices of the triangulation

        points = np.random.rand(10, 2)
        points = np.r_[points, points]  # duplicate input data

        tri = qhull.Delaunay(points, qhull_options="QJ Qbb Pp")
        assert_array_equal(np.unique(tri.simplices.ravel()),
                           np.arange(len(points)))

    def test_coplanar(self):
        # Check that the coplanar point output option indeed works
        points = np.random.rand(10, 2)
        points = np.r_[points, points]  # duplicate input data

        tri = qhull.Delaunay(points)

        assert_(len(np.unique(tri.simplices.ravel())) == len(points)//2)
        assert_(len(tri.coplanar) == len(points)//2)

        assert_(len(np.unique(tri.coplanar[:,2])) == len(points)//2)

        assert_(np.all(tri.vertex_to_simplex >= 0))

    def test_furthest_site(self):
        points = [(0, 0), (0, 1), (1, 0), (0.5, 0.5), (1.1, 1.1)]
        tri = qhull.Delaunay(points, furthest_site=True)

        expected = np.array([(1, 4, 0), (4, 2, 0)])  # from Qhull
        assert_array_equal(tri.simplices, expected)

    @pytest.mark.parametrize("name", sorted(INCREMENTAL_DATASETS))
    def test_incremental(self, name):
        # Test incremental construction of the triangulation

        chunks, opts = INCREMENTAL_DATASETS[name]
        points = np.concatenate(chunks, axis=0)

        obj = qhull.Delaunay(chunks[0], incremental=True,
                             qhull_options=opts)
        for chunk in chunks[1:]:
            obj.add_points(chunk)

        obj2 = qhull.Delaunay(points)

        obj3 = qhull.Delaunay(chunks[0], incremental=True,
                              qhull_options=opts)
        if len(chunks) > 1:
            obj3.add_points(np.concatenate(chunks[1:], axis=0),
                            restart=True)

        # Check that the incremental mode agrees with upfront mode
        if name.startswith('pathological'):
            # XXX: These produce valid but different triangulations.
            #      They look OK when plotted, but how to check them?

            assert_array_equal(np.unique(obj.simplices.ravel()),
                               np.arange(points.shape[0]))
            assert_array_equal(np.unique(obj2.simplices.ravel()),
                               np.arange(points.shape[0]))
        else:
            assert_unordered_tuple_list_equal(obj.simplices, obj2.simplices,
                                              tpl=sorted_tuple)

        assert_unordered_tuple_list_equal(obj2.simplices, obj3.simplices,
                                          tpl=sorted_tuple)


def assert_hulls_equal(points, facets_1, facets_2):
    # Check that two convex hulls constructed from the same point set
    # are equal

    facets_1 = set(map(sorted_tuple, facets_1))
    facets_2 = set(map(sorted_tuple, facets_2))

    if facets_1 != facets_2 and points.shape[1] == 2:
        # The direct check fails for the pathological cases
        # --- then the convex hull from Delaunay differs (due
        # to rounding error etc.) from the hull computed
        # otherwise, by the question whether (tricoplanar)
        # points that lie almost exactly on the hull are
        # included as vertices of the hull or not.
        #
        # So we check the result, and accept it if the Delaunay
        # hull line segments are a subset of the usual hull.

        eps = 1000 * np.finfo(float).eps

        for a, b in facets_1:
            for ap, bp in facets_2:
                t = points[bp] - points[ap]
                t /= np.linalg.norm(t)       # tangent
                n = np.array([-t[1], t[0]])  # normal

                # check that the two line segments are parallel
                # to the same line
                c1 = np.dot(n, points[b] - points[ap])
                c2 = np.dot(n, points[a] - points[ap])
                if not np.allclose(np.dot(c1, n), 0):
                    continue
                if not np.allclose(np.dot(c2, n), 0):
                    continue

                # Check that the segment (a, b) is contained in (ap, bp)
                c1 = np.dot(t, points[a] - points[ap])
                c2 = np.dot(t, points[b] - points[ap])
                c3 = np.dot(t, points[bp] - points[ap])
                if c1 < -eps or c1 > c3 + eps:
                    continue
                if c2 < -eps or c2 > c3 + eps:
                    continue

                # OK:
                break
            else:
                raise AssertionError("comparison fails")

        # it was OK
        return

    assert_equal(facets_1, facets_2)


class TestConvexHull:
    def test_masked_array_fails(self):
        masked_array = np.ma.masked_all(1)
        assert_raises(ValueError, qhull.ConvexHull, masked_array)

    def test_array_with_nans_fails(self):
        points_with_nan = np.array([(0,0), (1,1), (2,np.nan)], dtype=np.float64)
        assert_raises(ValueError, qhull.ConvexHull, points_with_nan)

    @pytest.mark.parametrize("name", sorted(DATASETS))
    def test_hull_consistency_tri(self, name):
        # Check that a convex hull returned by qhull in ndim
        # and the hull constructed from ndim delaunay agree
        points = DATASETS[name]

        tri = qhull.Delaunay(points)
        hull = qhull.ConvexHull(points)

        assert_hulls_equal(points, tri.convex_hull, hull.simplices)

        # Check that the hull extremes are as expected
        if points.shape[1] == 2:
            assert_equal(np.unique(hull.simplices), np.sort(hull.vertices))
        else:
            assert_equal(np.unique(hull.simplices), hull.vertices)

    @pytest.mark.parametrize("name", sorted(INCREMENTAL_DATASETS))
    def test_incremental(self, name):
        # Test incremental construction of the convex hull
        chunks, _ = INCREMENTAL_DATASETS[name]
        points = np.concatenate(chunks, axis=0)

        obj = qhull.ConvexHull(chunks[0], incremental=True)
        for chunk in chunks[1:]:
            obj.add_points(chunk)

        obj2 = qhull.ConvexHull(points)

        obj3 = qhull.ConvexHull(chunks[0], incremental=True)
        if len(chunks) > 1:
            obj3.add_points(np.concatenate(chunks[1:], axis=0),
                            restart=True)

        # Check that the incremental mode agrees with upfront mode
        assert_hulls_equal(points, obj.simplices, obj2.simplices)
        assert_hulls_equal(points, obj.simplices, obj3.simplices)

    def test_vertices_2d(self):
        # The vertices should be in counterclockwise order in 2-D
        np.random.seed(1234)
        points = np.random.rand(30, 2)

        hull = qhull.ConvexHull(points)
        assert_equal(np.unique(hull.simplices), np.sort(hull.vertices))

        # Check counterclockwiseness
        x, y = hull.points[hull.vertices].T
        angle = np.arctan2(y - y.mean(), x - x.mean())
        assert_(np.all(np.diff(np.unwrap(angle)) > 0))

    def test_volume_area(self):
        # Basic check that we get back the correct volume and area for a cube
        points = np.array([(0, 0, 0), (0, 1, 0), (1, 0, 0), (1, 1, 0),
                           (0, 0, 1), (0, 1, 1), (1, 0, 1), (1, 1, 1)])
        tri = qhull.ConvexHull(points)

        assert_allclose(tri.volume, 1., rtol=1e-14)
        assert_allclose(tri.area, 6., rtol=1e-14)

    @pytest.mark.parametrize("incremental", [False, True])
    def test_good2d(self, incremental):
        # Make sure the QGn option gives the correct value of "good".
        points = np.array([[0.2, 0.2],
                           [0.2, 0.4],
                           [0.4, 0.4],
                           [0.4, 0.2],
                           [0.3, 0.6]])
        hull = qhull.ConvexHull(points=points,
                                incremental=incremental,
                                qhull_options='QG4')
        expected = np.array([False, True, False, False], dtype=bool)
        actual = hull.good
        assert_equal(actual, expected)

    @pytest.mark.parametrize("visibility", [
                              "QG4",  # visible=True
                              "QG-4",  # visible=False
                              ])
    @pytest.mark.parametrize("new_gen, expected", [
        # add generator that places QG4 inside hull
        # so all facets are invisible
        (np.array([[0.3, 0.7]]),
         np.array([False, False, False, False, False], dtype=bool)),
        # adding a generator on the opposite side of the square
        # should preserve the single visible facet & add one invisible
        # facet
        (np.array([[0.3, -0.7]]),
         np.array([False, True, False, False, False], dtype=bool)),
        # split the visible facet on top of the square into two
        # visible facets, with visibility at the end of the array
        # because add_points concatenates
        (np.array([[0.3, 0.41]]),
         np.array([False, False, False, True, True], dtype=bool)),
        # with our current Qhull options, coplanarity will not count
        # for visibility; this case shifts one visible & one invisible
        # facet & adds a coplanar facet
        # simplex at index position 2 is the shifted visible facet
        # the final simplex is the coplanar facet
        (np.array([[0.5, 0.6], [0.6, 0.6]]),
         np.array([False, False, True, False, False], dtype=bool)),
        # place the new generator such that it envelops the query
        # point within the convex hull, but only just barely within
        # the double precision limit
        # NOTE: testing exact degeneracy is less predictable than this
        # scenario, perhaps because of the default Qt option we have
        # enabled for Qhull to handle precision matters
        (np.array([[0.3, 0.6 + 1e-16]]),
         np.array([False, False, False, False, False], dtype=bool)),
        ])
    def test_good2d_incremental_changes(self, new_gen, expected,
                                        visibility):
        # use the usual square convex hull
        # generators from test_good2d
        points = np.array([[0.2, 0.2],
                           [0.2, 0.4],
                           [0.4, 0.4],
                           [0.4, 0.2],
                           [0.3, 0.6]])
        hull = qhull.ConvexHull(points=points,
                                incremental=True,
                                qhull_options=visibility)
        hull.add_points(new_gen)
        actual = hull.good
        if '-' in visibility:
            expected = np.invert(expected)
        assert_equal(actual, expected)

    @pytest.mark.parametrize("incremental", [False, True])
    def test_good2d_no_option(self, incremental):
        # handle case where good attribute doesn't exist
        # because Qgn or Qg-n wasn't specified
        points = np.array([[0.2, 0.2],
                           [0.2, 0.4],
                           [0.4, 0.4],
                           [0.4, 0.2],
                           [0.3, 0.6]])
        hull = qhull.ConvexHull(points=points,
                                incremental=incremental)
        actual = hull.good
        assert actual is None
        # preserve None after incremental addition
        if incremental:
            hull.add_points(np.zeros((1, 2)))
            actual = hull.good
            assert actual is None

    @pytest.mark.parametrize("incremental", [False, True])
    def test_good2d_inside(self, incremental):
        # Make sure the QGn option gives the correct value of "good".
        # When point n is inside the convex hull of the rest, good is
        # all False.
        points = np.array([[0.2, 0.2],
                           [0.2, 0.4],
                           [0.4, 0.4],
                           [0.4, 0.2],
                           [0.3, 0.3]])
        hull = qhull.ConvexHull(points=points,
                                incremental=incremental,
                                qhull_options='QG4')
        expected = np.array([False, False, False, False], dtype=bool)
        actual = hull.good
        assert_equal(actual, expected)

    @pytest.mark.parametrize("incremental", [False, True])
    def test_good3d(self, incremental):
        # Make sure the QGn option gives the correct value of "good"
        # for a 3d figure
        points = np.array([[0.0, 0.0, 0.0],
                           [0.90029516, -0.39187448, 0.18948093],
                           [0.48676420, -0.72627633, 0.48536925],
                           [0.57651530, -0.81179274, -0.09285832],
                           [0.67846893, -0.71119562, 0.18406710]])
        hull = qhull.ConvexHull(points=points,
                                incremental=incremental,
                                qhull_options='QG0')
        expected = np.array([True, False, False, False], dtype=bool)
        assert_equal(hull.good, expected)

class TestVoronoi:

    @pytest.mark.parametrize("qhull_opts, extra_pts", [
        # option Qz (default for SciPy) will add
        # an extra point at infinity
        ("Qbb Qc Qz", 1),
        ("Qbb Qc", 0),
    ])
    @pytest.mark.parametrize("n_pts", [50, 100])
    @pytest.mark.parametrize("ndim", [2, 3])
    def test_point_region_structure(self,
                                    qhull_opts,
                                    n_pts,
                                    extra_pts,
                                    ndim):
        # see gh-16773
        rng = np.random.default_rng(7790)
        points = rng.random((n_pts, ndim))
        vor = Voronoi(points, qhull_options=qhull_opts)
        pt_region = vor.point_region
        assert pt_region.max() == n_pts - 1 + extra_pts
        assert pt_region.size == len(vor.regions) - extra_pts
        assert len(vor.regions) == n_pts + extra_pts
        assert vor.points.shape[0] == n_pts
        # if there is an empty sublist in the Voronoi
        # regions data structure, it should never be
        # indexed because it corresponds to an internally
        # added point at infinity and is not a member of the
        # generators (input points)
        if extra_pts:
            sublens = [len(x) for x in vor.regions]
            # only one point at infinity (empty region)
            # is allowed
            assert sublens.count(0) == 1
            assert sublens.index(0) not in pt_region

    def test_masked_array_fails(self):
        masked_array = np.ma.masked_all(1)
        assert_raises(ValueError, qhull.Voronoi, masked_array)

    def test_simple(self):
        # Simple case with known Voronoi diagram
        points = [(0, 0), (0, 1), (0, 2),
                  (1, 0), (1, 1), (1, 2),
                  (2, 0), (2, 1), (2, 2)]

        # qhull v o Fv Qbb Qc Qz < dat
        output = """
        2
        5 10 1
        -10.101 -10.101
           0.5    0.5
           0.5    1.5
           1.5    0.5
           1.5    1.5
        2 0 1
        3 2 0 1
        2 0 2
        3 3 0 1
        4 1 2 4 3
        3 4 0 2
        2 0 3
        3 4 0 3
        2 0 4
        0
        12
        4 0 3 0 1
        4 0 1 0 1
        4 1 4 1 2
        4 1 2 0 2
        4 2 5 0 2
        4 3 4 1 3
        4 3 6 0 3
        4 4 5 2 4
        4 4 7 3 4
        4 5 8 0 4
        4 6 7 0 3
        4 7 8 0 4
        """
        self._compare_qvoronoi(points, output)

    def _compare_qvoronoi(self, points, output, **kw):
        """Compare to output from 'qvoronoi o Fv < data' to Voronoi()"""

        # Parse output
        output = [list(map(float, x.split())) for x in output.strip().splitlines()]
        nvertex = int(output[1][0])
        vertices = list(map(tuple, output[3:2+nvertex]))  # exclude inf
        nregion = int(output[1][1])
        regions = [[int(y)-1 for y in x[1:]]
                   for x in output[2+nvertex:2+nvertex+nregion]]
        ridge_points = [[int(y) for y in x[1:3]]
                        for x in output[3+nvertex+nregion:]]
        ridge_vertices = [[int(y)-1 for y in x[3:]]
                          for x in output[3+nvertex+nregion:]]

        # Compare results
        vor = qhull.Voronoi(points, **kw)

        def sorttuple(x):
            return tuple(sorted(x))

        assert_allclose(vor.vertices, vertices)
        assert_equal(set(map(tuple, vor.regions)),
                     set(map(tuple, regions)))

        p1 = list(zip(list(map(sorttuple, ridge_points)),
                      list(map(sorttuple, ridge_vertices))))
        p2 = list(zip(list(map(sorttuple, vor.ridge_points.tolist())),
                      list(map(sorttuple, vor.ridge_vertices))))
        p1.sort()
        p2.sort()

        assert_equal(p1, p2)

    @pytest.mark.parametrize("name", sorted(DATASETS))
    def test_ridges(self, name):
        # Check that the ridges computed by Voronoi indeed separate
        # the regions of nearest neighborhood, by comparing the result
        # to KDTree.

        points = DATASETS[name]

        tree = KDTree(points)
        vor = qhull.Voronoi(points)

        for p, v in vor.ridge_dict.items():
            # consider only finite ridges
            if not np.all(np.asarray(v) >= 0):
                continue

            ridge_midpoint = vor.vertices[v].mean(axis=0)
            d = 1e-6 * (points[p[0]] - ridge_midpoint)

            dist, k = tree.query(ridge_midpoint + d, k=1)
            assert_equal(k, p[0])

            dist, k = tree.query(ridge_midpoint - d, k=1)
            assert_equal(k, p[1])

    def test_furthest_site(self):
        points = [(0, 0), (0, 1), (1, 0), (0.5, 0.5), (1.1, 1.1)]

        # qhull v o Fv Qbb Qc Qu < dat
        output = """
        2
        3 5 1
        -10.101 -10.101
        0.6000000000000001    0.5
           0.5 0.6000000000000001
        3 0 2 1
        2 0 1
        2 0 2
        0
        3 0 2 1
        5
        4 0 2 0 2
        4 0 4 1 2
        4 0 1 0 1
        4 1 4 0 1
        4 2 4 0 2
        """
        self._compare_qvoronoi(points, output, furthest_site=True)

    def test_furthest_site_flag(self):
        points = [(0, 0), (0, 1), (1, 0), (0.5, 0.5), (1.1, 1.1)]

        vor = Voronoi(points)
        assert_equal(vor.furthest_site,False)
        vor = Voronoi(points,furthest_site=True)
        assert_equal(vor.furthest_site,True)

    @pytest.mark.parametrize("name", sorted(INCREMENTAL_DATASETS))
    def test_incremental(self, name):
        # Test incremental construction of the triangulation

        if INCREMENTAL_DATASETS[name][0][0].shape[1] > 3:
            # too slow (testing of the result --- qhull is still fast)
            return

        chunks, opts = INCREMENTAL_DATASETS[name]
        points = np.concatenate(chunks, axis=0)

        obj = qhull.Voronoi(chunks[0], incremental=True,
                             qhull_options=opts)
        for chunk in chunks[1:]:
            obj.add_points(chunk)

        obj2 = qhull.Voronoi(points)

        obj3 = qhull.Voronoi(chunks[0], incremental=True,
                             qhull_options=opts)
        if len(chunks) > 1:
            obj3.add_points(np.concatenate(chunks[1:], axis=0),
                            restart=True)

        # -- Check that the incremental mode agrees with upfront mode
        assert_equal(len(obj.point_region), len(obj2.point_region))
        assert_equal(len(obj.point_region), len(obj3.point_region))

        # The vertices may be in different order or duplicated in
        # the incremental map
        for objx in obj, obj3:
            vertex_map = {-1: -1}
            for i, v in enumerate(objx.vertices):
                for j, v2 in enumerate(obj2.vertices):
                    if np.allclose(v, v2):
                        vertex_map[i] = j

            def remap(x):
                if hasattr(x, '__len__'):
                    return tuple({remap(y) for y in x})
                try:
                    return vertex_map[x]
                except KeyError as e:
                    message = (f"incremental result has spurious vertex "
                               f"at {objx.vertices[x]!r}")
                    raise AssertionError(message) from e

            def simplified(x):
                items = set(map(sorted_tuple, x))
                if () in items:
                    items.remove(())
                items = [x for x in items if len(x) > 1]
                items.sort()
                return items

            assert_equal(
                simplified(remap(objx.regions)),
                simplified(obj2.regions)
                )
            assert_equal(
                simplified(remap(objx.ridge_vertices)),
                simplified(obj2.ridge_vertices)
                )

            # XXX: compare ridge_points --- not clear exactly how to do this


class Test_HalfspaceIntersection:
    def assert_unordered_allclose(self, arr1, arr2, rtol=1e-7):
        """Check that every line in arr1 is only once in arr2"""
        assert_equal(arr1.shape, arr2.shape)

        truths = np.zeros((arr1.shape[0],), dtype=bool)
        for l1 in arr1:
            indexes = np.nonzero((abs(arr2 - l1) < rtol).all(axis=1))[0]
            assert_equal(indexes.shape, (1,))
            truths[indexes[0]] = True
        assert_(truths.all())

    @pytest.mark.parametrize("dt", [np.float64, int])
    def test_cube_halfspace_intersection(self, dt):
        halfspaces = np.array([[-1, 0, 0],
                               [0, -1, 0],
                               [1, 0, -2],
                               [0, 1, -2]], dtype=dt)
        feasible_point = np.array([1, 1], dtype=dt)

        points = np.array([[0.0, 0.0], [2.0, 0.0], [0.0, 2.0], [2.0, 2.0]])

        hull = qhull.HalfspaceIntersection(halfspaces, feasible_point)

        assert_allclose(hull.intersections, points)

    def test_self_dual_polytope_intersection(self):
        fname = os.path.join(os.path.dirname(__file__), 'data',
                             'selfdual-4d-polytope.txt')
        ineqs = np.genfromtxt(fname)
        halfspaces = -np.hstack((ineqs[:, 1:], ineqs[:, :1]))

        feas_point = np.array([0., 0., 0., 0.])
        hs = qhull.HalfspaceIntersection(halfspaces, feas_point)

        assert_equal(hs.intersections.shape, (24, 4))

        assert_almost_equal(hs.dual_volume, 32.0)
        assert_equal(len(hs.dual_facets), 24)
        for facet in hs.dual_facets:
            assert_equal(len(facet), 6)

        dists = halfspaces[:, -1] + halfspaces[:, :-1].dot(feas_point)
        self.assert_unordered_allclose((halfspaces[:, :-1].T/dists).T, hs.dual_points)

        points = itertools.permutations([0., 0., 0.5, -0.5])
        for point in points:
            assert_equal(np.sum((hs.intersections == point).all(axis=1)), 1)

    def test_wrong_feasible_point(self):
        halfspaces = np.array([[-1.0, 0.0, 0.0],
                               [0.0, -1.0, 0.0],
                               [1.0, 0.0, -1.0],
                               [0.0, 1.0, -1.0]])
        feasible_point = np.array([0.5, 0.5, 0.5])
        #Feasible point is (ndim,) instead of (ndim-1,)
        assert_raises(ValueError,
                      qhull.HalfspaceIntersection, halfspaces, feasible_point)
        feasible_point = np.array([[0.5], [0.5]])
        #Feasible point is (ndim-1, 1) instead of (ndim-1,)
        assert_raises(ValueError,
                      qhull.HalfspaceIntersection, halfspaces, feasible_point)
        feasible_point = np.array([[0.5, 0.5]])
        #Feasible point is (1, ndim-1) instead of (ndim-1,)
        assert_raises(ValueError,
                      qhull.HalfspaceIntersection, halfspaces, feasible_point)

        feasible_point = np.array([-0.5, -0.5])
        #Feasible point is outside feasible region
        assert_raises(qhull.QhullError,
                      qhull.HalfspaceIntersection, halfspaces, feasible_point)

    def test_incremental(self):
        #Cube
        halfspaces = np.array([[0., 0., -1., -0.5],
                               [0., -1., 0., -0.5],
                               [-1., 0., 0., -0.5],
                               [1., 0., 0., -0.5],
                               [0., 1., 0., -0.5],
                               [0., 0., 1., -0.5]])
        #Cut each summit
        extra_normals = np.array([[1., 1., 1.],
                                  [1., 1., -1.],
                                  [1., -1., 1.],
                                  [1, -1., -1.]])
        offsets = np.array([[-1.]]*8)
        extra_halfspaces = np.hstack((np.vstack((extra_normals, -extra_normals)),
                                      offsets))

        feas_point = np.array([0., 0., 0.])

        inc_hs = qhull.HalfspaceIntersection(halfspaces, feas_point, incremental=True)

        inc_res_hs = qhull.HalfspaceIntersection(halfspaces, feas_point,
                                                 incremental=True)

        for i, ehs in enumerate(extra_halfspaces):
            inc_hs.add_halfspaces(ehs[np.newaxis, :])

            inc_res_hs.add_halfspaces(ehs[np.newaxis, :], restart=True)

            total = np.vstack((halfspaces, extra_halfspaces[:i+1, :]))

            hs = qhull.HalfspaceIntersection(total, feas_point)

            assert_allclose(inc_hs.halfspaces, inc_res_hs.halfspaces)
            assert_allclose(inc_hs.halfspaces, hs.halfspaces)

            #Direct computation and restart should have points in same order
            assert_allclose(hs.intersections, inc_res_hs.intersections)
            #Incremental will have points in different order than direct computation
            self.assert_unordered_allclose(inc_hs.intersections, hs.intersections)

        inc_hs.close()

    def test_cube(self):
        # Halfspaces of the cube:
        halfspaces = np.array([[-1., 0., 0., 0.],  # x >= 0
                               [1., 0., 0., -1.],  # x <= 1
                               [0., -1., 0., 0.],  # y >= 0
                               [0., 1., 0., -1.],  # y <= 1
                               [0., 0., -1., 0.],  # z >= 0
                               [0., 0., 1., -1.]])  # z <= 1
        point = np.array([0.5, 0.5, 0.5])

        hs = qhull.HalfspaceIntersection(halfspaces, point)

        # qhalf H0.5,0.5,0.5 o < input.txt
        qhalf_points = np.array([
            [-2, 0, 0],
            [2, 0, 0],
            [0, -2, 0],
            [0, 2, 0],
            [0, 0, -2],
            [0, 0, 2]])
        qhalf_facets = [
            [2, 4, 0],
            [4, 2, 1],
            [5, 2, 0],
            [2, 5, 1],
            [3, 4, 1],
            [4, 3, 0],
            [5, 3, 1],
            [3, 5, 0]]

        assert len(qhalf_facets) == len(hs.dual_facets)
        for a, b in zip(qhalf_facets, hs.dual_facets):
            assert set(a) == set(b)  # facet orientation can differ

        assert_allclose(hs.dual_points, qhalf_points)