Fast Robust Predicates for Computational Geometry
Many computational geometry applications use numerical tests known as the orientation and incircle tests. The orientation test determines whether a point lies to the left of, to the right of, or on a line or plane defined by other points. The incircle test determines whether a point lies inside, outside, or on a circle defined by other points.Each of these tests is performed by evaluating the sign of a determinant (see the figure below). The determinant is expressed in terms of the coordinates of the points. If these coordinates are expressed as single or double precision floating-point numbers, roundoff error may lead to an incorrect result when the true determinant is near zero. In turn, this misinformation can lead an application to fail or produce incorrect results.
Download Files (local site)Offical Site
Problem Links
This page last modified on 2008-07-10
.
www.algorist.com
