predicates
You are reading the documentation of an outdated version, whose text may no longer be accurate. Go to the latest version.
Status: planned (wave 2). There is no repository and no code yet, and predicates is a working name. These pages describe the plan, not a release.
Exact geometric predicates at near floating-point cost.
What it will provide
| 2D | Orient2D, InCircle |
| 3D | Orient3D, InSphere |
| method | adaptive precision: a floating-point filter first, exact expansion arithmetic only when the filter cannot decide the sign |
References
The algorithms and the theory the package will start from, as the roadmap’s bibliography lists them:
| Reference | Cite |
|---|---|
| Shewchuk, Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates, Discrete Comput. Geom. 18:305-363, 1997 | doi:10.1007/PL00009321 |
Reference implementations and licences
What exists, under which licence, and what that allows:
| Implementation | Licence and use |
|---|---|
| Shewchuk’s predicates.c | public domain; may be ported (https://www.cs.cmu.edu/~quake/robust.html) |
GPL, LGPL, AGPL and non-free code is never ported: it is only run as an oracle, as an external program.
How it will be validated
- The sign of each predicate equals the sign computed with
big.Ratarithmetic on random and near-degenerate input; zero mismatches. - Degenerate families (cocircular grids, collinear sets) are generated in the repository.
Depends on
nothing. Every other package of the organization depends on it.
Where the plan lives
PLAN.md, STATUS.md and the bibliography in the go-scikit roadmap.
Created on by tannevaled
Modified on by tannevaled