 Orientation predicate

An orientation predicate determines on which side of an oriented geometric object a point lies. For planar points $p,q,r$, compute the determinantIn coordinates with $x$ rightward and $y$ upward, $D>0$ means a counterclockwise turn from $p$ through $q$ to $r$, $D<0$ a clockwise turn, and $D=0$ collinearity. Its magnitude is twice the area of the triangle.

For $p=(0,0)$ and $q=(2,0)$, $r=(1,3)$ gives $D=6$, while $(1,-3)$ gives $D=-6$. Convex hull and segment-intersection algorithms use these signs to make discrete decisions. A tiny round-off error can reverse a nearly zero sign and make those decisions inconsistent. Jonathan Richard Shewchuk's adaptive arithmetic computes extra precision only when needed to certify the sign for the supplied coordinates.^[ref]