| Copyright | (C) Frank Staals |
|---|---|
| License | see the LICENSE file |
| Maintainer | Frank Staals |
| Safe Haskell | None |
| Language | Haskell2010 |
Algorithms.Geometry.SoS
Description
Implementation of Simulation of Simplicity: A Technique to Cope with Degenerate Cases in Geometric Algorithms
By Herbert Edelsbrunner and Ernst Peter Mucke
Synopsis
- data Sign
- flipSign :: Sign -> Sign
- signFromTerms :: (Num r, Eq r) => [r] -> Sign
- type SoS d = (Arity d, HasDeterminant (d + 1))
- sideTest :: (SoS d, Num r, Ord r, Ord i) => (Point d r :+ i) -> Vector d (Point d r :+ i) -> Sign
- sideTest' :: (Num r, Ord r, Ord i, HasDeterminant (d + 1), Arity d, Arity (d + 1)) => Point d (Symbolic i r) -> Vector d (Point d (Symbolic i r)) -> Sign
- toSymbolic :: (Ord i, Arity d) => (Point d r :+ i) -> Point d (Symbolic (i, Int) r)
- signDet :: (HasDeterminant d, Ord i, Num r, Ord r) => Matrix d d (Symbolic i r) -> Sign
Documentation
The sign of an expression
signFromTerms :: (Num r, Eq r) => [r] -> Sign Source #
Given the terms, in decreasing order of significance, computes the sign
i.e. expects a list of terms, we base the sign on the sign of the first non-zero term.
pre: the list contains at least one such a term.
type SoS d = (Arity d, HasDeterminant (d + 1)) Source #
A dimension d has support for SoS when we can: compute a dterminant of a d+1 by d+1 dimensional matrix.
sideTest :: (SoS d, Num r, Ord r, Ord i) => (Point d r :+ i) -> Vector d (Point d r :+ i) -> Sign Source #
Given a query point q, and a vector of d points defining a hyperplane test if q lies above or below the hyperplane. Each point is assumed to have an unique index of type i that can be used to disambiguate it in case of degeneracies.
some 1D examples:
>>>sideTest (Point1 0 :+ 0) (Vector1 $ Point1 2 :+ 1)Negative>>>sideTest (Point1 10 :+ 0) (Vector1 $ Point1 2 :+ 1)Positive>>>sideTest (Point1 2 :+ 0) (Vector1 $ Point1 2 :+ 1)Positive>>>sideTest (Point1 2 :+ 3) (Vector1 $ Point1 2 :+ 1)Negative
some 2D examples:
>>>sideTest (Point2 1 2 :+ 0) $ Vector2 (Point2 0 0 :+ 1) (Point2 2 2 :+ 3)Positive>>>sideTest (Point2 1 (-2) :+ 0) $ Vector2 (Point2 0 0 :+ 1) (Point2 2 2 :+ 3)Negative>>>sideTest (Point2 1 1 :+ 0) $ Vector2 (Point2 0 0 :+ 1) (Point2 2 2 :+ 3)Positive>>>sideTest (Point2 1 1 :+ 10) $ Vector2 (Point2 0 0 :+ 1) (Point2 2 2 :+ 3)Negative>>>sideTest (Point2 1 1 :+ 10) $ Vector2 (Point2 0 0 :+ 3) (Point2 2 2 :+ 1)Negative
sideTest' :: (Num r, Ord r, Ord i, HasDeterminant (d + 1), Arity d, Arity (d + 1)) => Point d (Symbolic i r) -> Vector d (Point d (Symbolic i r)) -> Sign Source #
Given a point q and a vector of d points defining a hyperplane, test on which side of the hyperplane q lies.
TODO: Specify what the sign means