# Path: pyhull/halfspace.py
# class Halfspace(object):
#     """
#     A halfspace defined by dot(normal, coords) + offset <= 0
#     """
#     def __init__(self, normal, offset):
#         """
#         Initializes a Halfspace.
# 
#         Args:
#             normal: vector normal to hyperplane
#             offset: offset of hyperplane from origin
#         """
#         self.normal = normal
#         self.offset = offset
# 
#     def __str__(self):
#         return "Halfspace, normal: {}, offset: {}".format(self.normal, self.offset)
# 
#     @staticmethod
#     def from_hyperplane(basis, origin, point, internal = True):
#         """
#         Returns a Halfspace defined by a list of vectors parallel to the
#         bounding hyperplane.
# 
#         Args:
#             basis: basis for the hyperplane (array with vector rows)
#             origin: point on the hyperplane
#             point: point not on the hyperplane
#             internal: whether point is inside the halfspace
#         """
#         basis = np.array(basis)
#         assert basis.shape[0] + 1 == basis.shape[1]
# 
#         big_basis = np.zeros((basis.shape[1], basis.shape[1]))
#         big_basis[:basis.shape[0],:basis.shape[1]] = basis
# 
#         u, s, vh = np.linalg.svd(big_basis)
#         null_mask = (s <= 1e-8)
#         normal = np.compress(null_mask, vh, axis=0)[0]
# 
#         if np.inner(np.array(point)-np.array(origin), normal) > 0:
#             if internal:
#                 normal *= -1
#         else:
#             if not internal:
#                 normal *= -1
#         offset = -np.dot(origin, normal)
#         return Halfspace(normal, offset)
# 
# class HalfspaceIntersection(object):
#     """
#     Uses qhalf to calculate the vertex representation of the intersection
#     of a set of halfspaces
#     """
#     def __init__(self, halfspaces, interior_point):
#         self.halfspaces = halfspaces
#         self.interior_point = interior_point
#         self._v_out = None
#         self._fbv_out = None
#         self._fbh_out = None
# 
#     @property
#     def vertices(self):
#         """
#         Returns the vertices of the halfspace intersection
#         """
#         if self._v_out is None:
#             output = qhalf('Fp', self.halfspaces, self.interior_point)
#             pts = []
#             for l in output[2:]:
#                 pt = []
#                 for c in l.split():
#                     c = float(c)
#                     if c != 10.101 and c != -10.101:
#                         pt.append(c)
#                     else:
#                         pt.append(np.inf)
#                 pts.append(pt)
#             self._v_out = np.array(pts)
#         return self._v_out
# 
#     @property
#     def facets_by_vertex(self):
#         """
#         Returns a list of non-redundant halfspace indices for each vertex
#         e.g: facets_by_vertex[0] is the list of indices of halfspaces
#         incident to vertex 0
#         """
#         if self._fbv_out is None:
#             output = qhalf('Fv', self.halfspaces, self.interior_point)
#             facets = []
#             for l in output[1:]:
#                 facets.append([int(i) for i in l.split()[1:]])
#             self._fbv_out = facets
#         return self._fbv_out
# 
#     @property
#     def facets_by_halfspace(self):
#         """
#         Returns a list of vertex indices for each halfspace
#         e.g: facets_by_halfspace[0] is the list of indices ov vertices
#         incident to halfspace 0
#         """
#         if self._fbh_out is None:
#             output = qhalf('FN', self.halfspaces, self.interior_point)
#             facets = []
#             for l in output[1:]:
#                 facets.append([int(i) for i in l.split()[1:]])
#             self._fbh_out = facets
#         return self._fbh_out


import unittest
import numpy as np
from pyhull.halfspace import Halfspace, HalfspaceIntersection
        self.assertEqual(h1.offset, -100)
        h2 = Halfspace.from_hyperplane([[0,1,0], [1,0,0]], [1,1,-100], [2,2,2], False)
        self.assertEqual(h2.offset, 100)

    def test_intersection(self):
        h1 = Halfspace.from_hyperplane([[1,0,0], [0,1,0]], [1,1,1], [0.9, 0.9, 0.9], True)
        h2 = Halfspace.from_hyperplane([[0,1,0], [0,0,1]], [1,1,1], [0.9, 0.9, 0.9], True)
        h3 = Halfspace.from_hyperplane([[0,0,1], [1,0,0]], [1,1,1], [0.9, 0.9, 0.9], True)
        h4 = Halfspace.from_hyperplane([[-1,0,1], [0,-1,1]], [1,1,0], [0.9, 0.9, 0.9], True)

        hi = HalfspaceIntersection([h1, h2, h3, h4], [0.9, 0.9, 0.9])
        self.assertTrue(np.allclose(np.sum(hi.vertices, axis = 0), [3,3,3]))

        h5 = Halfspace.from_hyperplane([[1,0,0], [0,1,0]], [1,2,2], [0.9, 0.9, 0.9], True)
        hi = HalfspaceIntersection([h5, h2, h3, h4], [0.9, 0.9, 0.9])
        self.assertTrue(np.allclose(np.sum(hi.vertices, axis = 0), [2,2,6]))

        for h, vs in zip(hi.halfspaces, hi.facets_by_halfspace):
            for v in vs:
                self.assertAlmostEqual(np.dot(h.normal, hi.vertices[v]) + h.offset, 0)
        for v, hss in zip(hi.vertices, hi.facets_by_vertex):
            for i in hss:
                hs = hi.halfspaces[i]
                self.assertAlmostEqual(np.dot(hs.normal, v) + hs.offset, 0)

    def test_intersection2d(self):
        h1 = Halfspace([1,0], -1)
        h2 = Halfspace([0,1], 1)
        h3 = Halfspace([-2,-1], 0)
        h_redundant = Halfspace([1,0], -2)

# Path: pyhull/halfspace.py
# class Halfspace(object):
#     """
#     A halfspace defined by dot(normal, coords) + offset <= 0
#     """
#     def __init__(self, normal, offset):
#         """
#         Initializes a Halfspace.
# 
#         Args:
#             normal: vector normal to hyperplane
#             offset: offset of hyperplane from origin
#         """
#         self.normal = normal
#         self.offset = offset
# 
#     def __str__(self):
#         return "Halfspace, normal: {}, offset: {}".format(self.normal, self.offset)
# 
#     @staticmethod
#     def from_hyperplane(basis, origin, point, internal = True):
#         """
#         Returns a Halfspace defined by a list of vectors parallel to the
#         bounding hyperplane.
# 
#         Args:
#             basis: basis for the hyperplane (array with vector rows)
#             origin: point on the hyperplane
#             point: point not on the hyperplane
#             internal: whether point is inside the halfspace
#         """
#         basis = np.array(basis)
#         assert basis.shape[0] + 1 == basis.shape[1]
# 
#         big_basis = np.zeros((basis.shape[1], basis.shape[1]))
#         big_basis[:basis.shape[0],:basis.shape[1]] = basis
# 
#         u, s, vh = np.linalg.svd(big_basis)
#         null_mask = (s <= 1e-8)
#         normal = np.compress(null_mask, vh, axis=0)[0]
# 
#         if np.inner(np.array(point)-np.array(origin), normal) > 0:
#             if internal:
#                 normal *= -1
#         else:
#             if not internal:
#                 normal *= -1
#         offset = -np.dot(origin, normal)
#         return Halfspace(normal, offset)
# 
# class HalfspaceIntersection(object):
#     """
#     Uses qhalf to calculate the vertex representation of the intersection
#     of a set of halfspaces
#     """
#     def __init__(self, halfspaces, interior_point):
#         self.halfspaces = halfspaces
#         self.interior_point = interior_point
#         self._v_out = None
#         self._fbv_out = None
#         self._fbh_out = None
# 
#     @property
#     def vertices(self):
#         """
#         Returns the vertices of the halfspace intersection
#         """
#         if self._v_out is None:
#             output = qhalf('Fp', self.halfspaces, self.interior_point)
#             pts = []
#             for l in output[2:]:
#                 pt = []
#                 for c in l.split():
#                     c = float(c)
#                     if c != 10.101 and c != -10.101:
#                         pt.append(c)
#                     else:
#                         pt.append(np.inf)
#                 pts.append(pt)
#             self._v_out = np.array(pts)
#         return self._v_out
# 
#     @property
#     def facets_by_vertex(self):
#         """
#         Returns a list of non-redundant halfspace indices for each vertex
#         e.g: facets_by_vertex[0] is the list of indices of halfspaces
#         incident to vertex 0
#         """
#         if self._fbv_out is None:
#             output = qhalf('Fv', self.halfspaces, self.interior_point)
#             facets = []
#             for l in output[1:]:
#                 facets.append([int(i) for i in l.split()[1:]])
#             self._fbv_out = facets
#         return self._fbv_out
# 
#     @property
#     def facets_by_halfspace(self):
#         """
#         Returns a list of vertex indices for each halfspace
#         e.g: facets_by_halfspace[0] is the list of indices ov vertices
#         incident to halfspace 0
#         """
#         if self._fbh_out is None:
#             output = qhalf('FN', self.halfspaces, self.interior_point)
#             facets = []
#             for l in output[1:]:
#                 facets.append([int(i) for i in l.split()[1:]])
#             self._fbh_out = facets
#         return self._fbh_out


# Path: pyhull/tests/test_halfspace.py
import unittest
import numpy as np
from pyhull.halfspace import Halfspace, HalfspaceIntersection

        self.assertEqual(h1.offset, -100)
        h2 = Halfspace.from_hyperplane([[0,1,0], [1,0,0]], [1,1,-100], [2,2,2], False)
        self.assertEqual(h2.offset, 100)

    def test_intersection(self):
        h1 = Halfspace.from_hyperplane([[1,0,0], [0,1,0]], [1,1,1], [0.9, 0.9, 0.9], True)
        h2 = Halfspace.from_hyperplane([[0,1,0], [0,0,1]], [1,1,1], [0.9, 0.9, 0.9], True)
        h3 = Halfspace.from_hyperplane([[0,0,1], [1,0,0]], [1,1,1], [0.9, 0.9, 0.9], True)
        h4 = Halfspace.from_hyperplane([[-1,0,1], [0,-1,1]], [1,1,0], [0.9, 0.9, 0.9], True)

        hi = HalfspaceIntersection([h1, h2, h3, h4], [0.9, 0.9, 0.9])
        self.assertTrue(np.allclose(np.sum(hi.vertices, axis = 0), [3,3,3]))

        h5 = Halfspace.from_hyperplane([[1,0,0], [0,1,0]], [1,2,2], [0.9, 0.9, 0.9], True)
        hi = HalfspaceIntersection([h5, h2, h3, h4], [0.9, 0.9, 0.9])
        self.assertTrue(np.allclose(np.sum(hi.vertices, axis = 0), [2,2,6]))

        for h, vs in zip(hi.halfspaces, hi.facets_by_halfspace):
            for v in vs:
                self.assertAlmostEqual(np.dot(h.normal, hi.vertices[v]) + h.offset, 0)
        for v, hss in zip(hi.vertices, hi.facets_by_vertex):
            for i in hss:
                hs = hi.halfspaces[i]
                self.assertAlmostEqual(np.dot(hs.normal, v) + hs.offset, 0)

    def test_intersection2d(self):
        h1 = Halfspace([1,0], -1)
        h2 = Halfspace([0,1], 1)
        h3 = Halfspace([-2,-1], 0)
        h_redundant = Halfspace([1,0], -2)

        hi = HalfspaceIntersection([h1, h2, h_redundant, h3], [0.9,-1.1])