= 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 <determinant>
$$
D=(q_x-p_x)(r_y-p_y)-(q_y-p_y)(r_x-p_x).
$$
In 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.<Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates by Jonathan Richard Shewchuk>[orientation tests, determinant signs and adaptive exact arithmetic]{ref}
Back to article page
