-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Geometric predicates (Intel SSE)
--   
--   Exact, hardware based computation of geometric predicates using an SSE
--   based interval filter and the ESSA algorithm. See "Exact computation
--   of Voronoi diagram and Delaunay triangulation" by Marina Gavrilova,
--   Helmut Ratschek and Jon Rokne. This package is a specialization of the
--   <tt>GeomPredicates</tt> package and uses it's primitives defined under
--   <tt>Numeric.Geometric.Primitives</tt>. This package requires a CPU
--   with <tt>Streaming SIMD Extensions 2</tt>.
@package GeomPredicates-SSE
@version 0.2


-- | Hardware based, exact computation using the ESSA algorithm in double
--   precision (1)
--   
--   <ul>
--   <li>We're using Float inputs on Double precision ESSA at the moment.
--   Hopefully later we can add support for Double inputs on Quadruple
--   ESSA</li>
--   <li>Line intersection is based on the algorithm presented in (4)</li>
--   <li>ccw and incircle based on (5)</li>
--   <li>See (2) and (3) for more information on the splitDouble
--   operation</li>
--   <li>We assume realToFrac is broken and that CFloat == Float and
--   CDouble == Double</li>
--   </ul>
--   
--   <ol>
--   <li>Helmut Ratschek, Jon Rokne. "Exact computation of the sign of a
--   finite sum". Applied Mathematics and Computation, Volume 99, Issue
--   2-3, Pages: 99-127, ISSN:0096-3003, 1999.</li>
--   <li>Siegfried M. Rump. "High precision evaluation of nonlinear
--   functions"</li>
--   <li>T.J. Dekker. "A Floating-Point Technique for Extending the
--   Available Precision". Numerische Mathematik, 18:224-242, 1971.</li>
--   <li>Marina Gavrilova, Jon Rokne. "Reliable line segment intersection
--   testing"</li>
--   <li>Marina Gavrilova, Helmut Ratschek and Jon Rokne. "Exact
--   computation of Voronoi diagram and Delaunay triangulation"</li>
--   </ol>
module Numeric.Geometric.Predicates.ESSA

-- | Test if p3 is within the closed interval specified by [p1,p2]
cinttESSA :: Float -> Float -> Float -> Bool

-- | Intersect two line segments
intersectESSA_SS2D :: LineSegment (Vector2 Float) -> LineSegment (Vector2 Float) -> LineIntersection

-- | Counter-clockwise orientation test. Classifies p3 in relation to the
--   line formed by p1 and p2.
--   
--   Result: LT=Right, GT=Left, EQ=Coincident
ccwESSA :: Vector2 Float -> Vector2 Float -> Vector2 Float -> Ordering

-- | Test the relation of a point to the circle formed by (p1..p3).
--   (p1..p3) must be in counterclockwise order.
--   
--   Result: GT=inside, EQ=border, LT=outside.
--   
--   Note: this is the sum of 192 multiplications.
incircleESSA :: (Vector2 Float, Vector2 Float, Vector2 Float) -> Vector2 Float -> Ordering

-- | Compute the exact sign of the sum of the input sequence. It is the
--   caller's responsibility to ensure that the inputs have not suffered a
--   loss of precision.
essa :: (Functor t, Foldable t) => t Double -> Ordering

-- | Split a 53 bit double into two 26 bit halves so that: <tt> let (lo,hi)
--   = splitDouble x in x == lo + hi </tt>
--   
--   The trick is that the sign is used as the additional bit.
--   
--   Note that the multiplication of two 26-bit floating point numbers is
--   exact in double precision.
--   
--   If you're new to this function you may want to read paper (5), as
--   using this function properly may be trickier than it seems.
splitDouble :: Double -> (Double, Double)


-- | These predicates use hardware (SSE) based interval arithmetic based on
--   the algorithms presented in (1). They are intended to be used as a
--   filter before resorting to slower exact computation.
--   
--   <ul>
--   <li>These routines return Nothing if the result could not be
--   determined exactly from the calculated interval.</li>
--   <li>Each call toggles the SSE rounding mode to -infinity and
--   back.</li>
--   <li>All computations are done in Double precision.</li>
--   <li>Rewrite specializations are in place for Float and Double that
--   greatly reduce allocations compared to Real. Using anything but Float
--   or Double is probably absurdly slow thanks to realToFrac.</li>
--   <li>For performance reasons we assume CDouble == Double.</li>
--   </ul>
--   
--   <ol>
--   <li>BRANIMIR LAMBOV. "INTERVAL ARITHMETIC USING SSE-2"</li>
--   </ol>
module Numeric.Geometric.Predicates.Interval

-- | Test if p3 is within the closed interval specified by [p1,p2]
cinttSSE :: (Real a) => a -> a -> a -> Maybe Bool

-- | Test the relation of a point to the circle formed by (p1..p3).
--   (p1..p3) must be in counterclockwise order. Result: GT=inside,
--   EQ=border, LT=outside
incircleSSE :: (Real a) => (Vector2 a, Vector2 a, Vector2 a) -> Vector2 a -> Maybe Ordering

-- | Counter-clockwise orientation test. Classifies p3 in relation to the
--   line formed by p1 and p2. Result: LT=Right, GT=Left, EQ=Coincident
ccwSSE :: (Real a) => Vector2 a -> Vector2 a -> Vector2 a -> Maybe Ordering