Orientation Test

The fundamental predicate: given three points, do they turn left, right, or go straight?

int orient(P a, P b, P c) {
    long long v = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
    return (v > 0) - (v < 0);           // +1 CCW, 0 collinear, -1 CW
}

This is the sign of the cross product $\mathrm{cross}(b-a,c-a)$, and equivalently the sign of the determinant

$\left|\begin{array}{cc}{b}_x-a_x& c_x-a_x\\ b_y-a_y& c_y-a_y\end{array}\right|.$

Why it is the predicate

Nearly every 2D algorithm is built from it:

Algorithm	Use of orient
Convex hull	pop while the turn is not left
Segment intersection	four orientation tests
Point in convex polygon	same sign for every edge
Polygon orientation	sign of the signed area
Half-plane intersection	which side of each line
Sweep line	segment ordering
Is a polygon convex?	all turns the same direction
Triangulation	ear-clipping validity

Getting it exact is therefore worth more than optimising anything else.

Exactness

With integer coordinates up to $10^9$, differences reach $2\cdot 10^9$ and the products reach $4\cdot 10^{18}$ — the subtraction fits in long long (limit $9.22\cdot 10^{18}$). Beyond that, use __int128.

With floating point input, the naive formula can return the wrong sign when the points are nearly collinear — catastrophic cancellation. Three responses:

1. Scale to integers if the input has bounded precision (multiply by $10^k$ and round).
2. Use long double and an $\epsilon$ tuned to the coordinate magnitude.
3. Adaptive exact predicates (Shewchuk) — compute a fast estimate with an error bound, and fall back to exact arithmetic only when the estimate is inconclusive. This is what production geometry libraries do.

A wrong orientation is not a small error

An incorrect sign does not perturb the answer slightly — it makes a convex hull non-convex, a sweep-line status inconsistent, or a triangulation self-intersecting, and the algorithm then fails in ways that look nothing like a precision problem. This is the single biggest source of hard-to-debug geometry failures.

Derived predicates

// is p on segment ab?  (requires collinearity)
bool onSegment(P p, P a, P b) {
    return orient(a, b, p) == 0 && dot(p - a, p - b) <= 0;
}
 
// do segments ab and cd properly intersect?
bool properIntersect(P a, P b, P c, P d) {
    int o1 = orient(a, b, c), o2 = orient(a, b, d);
    int o3 = orient(c, d, a), o4 = orient(c, d, b);
    return o1 * o2 < 0 && o3 * o4 < 0;
}

dot(p-a, p-b) <= 0 is the elegant way to say ”$p$ lies between $a$ and $b$” — the vectors point in opposite directions.

The in-circle predicate

The other classical predicate, needed for Delaunay triangulation: is $d$ inside the circle through $a,b,c$ (taken CCW)?

$\mathrm{sign}\left|\begin{array}{ccc}{a}_x-d_x& a_y-d_y& (a_x-d_x{)}^2+(a_y-d_y{)}^2\\ b_x-d_x& b_y-d_y& (b_x-d_x{)}^2+(b_y-d_y{)}^2\\ c_x-d_x& c_y-d_y& (c_x-d_x{)}^2+(c_y-d_y{)}^2\end{array}\right|.$

Degree 4 in the coordinates, so with $10^9$ inputs the determinant reaches $10^{45}$ — far beyond both long long and double. This is why Delaunay implementations need exact predicates or heavily restricted coordinate ranges.

Convexity check

bool isConvex(const vector<P>& poly) {
    int n = poly.size(), sign = 0;
    for (int i = 0; i < n; i++) {
        int o = orient(poly[i], poly[(i+1)%n], poly[(i+2)%n]);
        if (o == 0) continue;                    // allow collinear points
        if (sign == 0) sign = o;
        else if (sign != o) return false;
    }
    return true;
}

Note this accepts polygons with collinear vertices; whether that counts as convex depends on the problem.

See also: Cross Product · Geometry Basics · Segment Intersection