FoundationSource checked

Orientation Test

Determines whether three points make a left turn, right turn, or are collinear.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Geometry
Difficulty: Beginner
Family: Geometric Predicates
Tier: Foundation
Status: Verified
Review: Source Checked
Sources: 2
Formulas: 1
Relationships: 5
Code example: Ready
Visualization: Ready

Overview

The Orientation Test evaluates the sign of a 2D cross product or determinant. The sign tells whether the ordered triple turns counterclockwise, clockwise, or lies on one line.

Core Concepts

cross productdeterminant signcollinearityrobust predicate

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(1)

Average

O(1)

Worst

O(1)

Space

O(1)

When to Use

Use it whenever a planar algorithm needs left-turn or right-turn decisions.
Use it as a primitive for hulls, intersections, and polygon tests.
Use robust predicates when coordinates are floating-point or nearly collinear.

When Not to Use

Avoid naive floating-point comparisons for nearly collinear points.
Avoid it for 3D orientation without using the appropriate volume predicate.
Avoid assuming coordinate order does not matter.

What It Does

Classifies the turn direction of three points
Supports geometric predicates

Use Cases

Convex hull construction
Line-segment intersection
Point-in-polygon tests

Inputs

Points, segments, polygons, or geometric primitives
Query or construction parameters

Outputs

Geometric decision, measurement, or constructed structure

Key Formulas (1)

Signed area test

sign((bx−ax)·(cy−ay) − (by−ay)·(cx−ax))

sign((bx-ax)*(cy-ay) - (by-ay)*(cx-ax))

Determines whether three points make a left turn, right turn, or are collinear.

Pseudocode

1.Compute vector ab = b - a.
2.Compute vector ac = c - a.
3.Compute cross = ab.x * ac.y - ab.y * ac.x.
4.If cross is positive, return counterclockwise.
5.If cross is negative, return clockwise.
6.Otherwise return collinear.

Canonical Example

Input: a = (0, 0), b = (2, 0), c = (1, 1)
Output: counterclockwise
Explanation: The point c lies to the left of the directed segment from a to b.

Implementation Notes

Compute sign((b - a) x (c - a)) in 2D.
Use exact arithmetic or adaptive predicates for robust computational geometry.
Document whether positive means clockwise or counterclockwise in the chosen coordinate system.