Contents

Radial OrderEdit

Radial order is a concept in planar geometry and computational geometry that describes the cyclic arrangement of points around a chosen center. Rather than organizing points by how far away they are from the center, radial order orders them by their direction from that center. This directional perspective is foundational for many algorithms that manipulate or reason about 2D spatial data, from constructing polygons to guiding robots along a plane.

In practice, the radial order around a center p0 is the circular sequence of the remaining points ordered by their polar angle relative to p0. If multiple points lie on the same ray from p0, the definition may specify a tie-breaking rule, such as ordering first by distance from p0, or by some other deterministic criterion. The concept generalizes to different centers and to higher-dimensional spaces, where analogous notions describe how objects are arranged around a pivot or axis.

Definition and formalism

Given a finite set P of points in the Euclidean plane and a chosen center p0 ∈ P, the radial order around p0 is the cyclic order of the points in P \ {p0} determined by their polar angle with respect to p0. The polar angle is typically computed as the angle from a reference direction (often the positive x-axis) to the vector from p0 to a point p ∈ P, commonly via the atan2 function atan2.

  • If no three points are collinear with p0, the radial order is well-defined and unique up to rotation of the cycle (i.e., there is no distinguished starting point).
  • If some points lie on the same ray from p0, the order among those co-radial points depends on the chosen tie-breaking rule.
  • The concept is sometimes referred to as the angular order or circular order around p0.

Radial order is closely tied to the notion of polar coordinates polar coordinates and to the idea of sorting elements by angle, rather than by distance alone. It also connects to the notion of cyclic or circular order, a fundamental idea in many geometric algorithms.

Computation and algorithms

Computing the radial order around a center p0 typically involves two steps:

  • Compute the polar angle for each point p ∈ P \ {p0} using a function like atan2(y − p0.y, x − p0.x).
  • Sort the points by the computed angle, applying a deterministic tie-breaker if necessary.

The overall complexity for sorting n − 1 points around a single center is O(n log n). In algorithms that need radial orders for many centers, such as certain triangulation and visibility problems, practitioners may reuse data structures or employ sweep-line approaches to maintain orders efficiently as the center changes. The Graham scan algorithm for convex hull construction, for example, relies on sorting points by their polar angle around a chosen pivot Graham scan.

In three-dimensional settings, analogous procedures sort directions around a center on a plane or around a reference normal, giving rise to a spherical or angular ordering concept that extends the same core ideas.

Applications

Radial order serves as a practical tool in a range of disciplines and tasks:

  • Polygon construction and convex hulls: Sorting by polar angle around a pivot is a common step in methods like the Graham scan to build convex hulls efficiently.
  • Planar graph algorithms: Radial ordering around vertices informs how edges are connected and how faces are traversed, which is important for mesh generation and planar embedding.
  • Robotics and computer graphics: Determining how nearby features are arranged around a robot or camera helps in visibility, path planning, and rendering.
  • Geographic information systems (GIS): Sorting features by angle around facilities or landmarks supports services such as range analysis and service area design.
  • Data visualization: Star plots and angular histograms rely on radial ordering to present multivariate data in a compact, interpretable form.

Properties and variations

  • Degenerate cases: When several points lie on the same ray from p0, the radial order is not unique without a rule to resolve ties (e.g., distance from p0 or a predefined secondary criterion).
  • Center choice: The radial order depends on the selected center. Different centers yield different angular sequences, which is why the notion is often used with a specified pivot in algorithmic contexts.
  • Relationship to cyclic order: Radial order is a form of cyclic order on the set P \ {p0}, where the cycle reflects the angular progression around p0.

Examples

  • Suppose p0 is at the origin, and the other points are at (1,0), (0,1), (−1,0), and (0,−1). Their polar angles around p0 are 0, π/2, π, and −π/2 (or 3π/2). The radial order in counterclockwise direction starting at angle 0 is: (1,0) → (0,1) → (−1,0) → (0,−1).
  • If a fifth point lies at (2,0) on the same ray as (1,0), tie-breaking by distance might place (1,0) before (2,0) in the radial order around p0.

See also