Fundamental Geometric Primitives

Why This Matters

Every algorithm in computational geometry—from collision detection to mesh generation to spatial indexing—builds on a small set of fundamental primitives. When you're implementing a convex hull algorithm, designing a ray tracer, or solving intersection problems, you're really manipulating points, lines, and polygons in precise mathematical ways. Understanding these primitives isn't just about definitions; it's about knowing how they're represented, what operations they support, and when to use each one.

You're being tested on your ability to choose the right primitive for a given problem, convert between representations efficiently, and understand the mathematical properties that make certain algorithms work. Don't just memorize that a line segment has two endpoints—know why parametric representation makes intersection tests elegant, why convex polygons simplify so many algorithms, and how vectors enable the transformations that power computer graphics. Master the primitives, and the algorithms will follow.

---

Zero-Dimensional and Directional Primitives

These primitives represent positions and directions—the atomic units from which all other geometric objects are constructed. Points define "where," while vectors define "which way" and "how far."

Points

• Represented as coordinate tuples $P = (x, y)$ in 2D or $P = (x, y, z)$ in 3D—the foundation for every other primitive
• Dimensionless by definition—no area, volume, or extent; purely a location in space
• Homogeneous coordinates $(x, y, w)$ allow unified treatment of transformations including translation

Vectors

• Encode magnitude and direction as $\vec{v} = (v_x, v_y)$, distinct from points because they represent displacement, not position
• Support critical operations—dot product $\vec{a} \cdot \vec{b}$ tests perpendicularity; cross product $\vec{a} \times \vec{b}$ computes area and orientation
• Essential for transformations—rotation, scaling, and translation all operate through vector arithmetic

---

One-Dimensional Linear Primitives

Lines and their bounded variants form the backbone of intersection algorithms, visibility computations, and geometric queries. The key distinction is extent: infinite, semi-infinite, or finite.

Lines

• Multiple representations—implicit form $ax + by + c = 0$, parametric form $P(t) = P_0 + t\vec{d}$, or slope-intercept $y = mx + b$
• Extend infinitely in both directions—useful for theoretical constructs but rarely stored directly in practical applications
• Signed distance from point to line enables half-plane classification, critical for convex hull and polygon algorithms

Rays

• Semi-infinite—defined by origin point $O$ and direction $\vec{d}$, extending as $R(t) = O + t\vec{d}$ for $t \geq 0$
• Fundamental to ray casting and ray tracing—every visibility query, shadow test, and intersection computation uses rays
• Parameterized queries return $t$ values, making it easy to find closest intersections or sort hit points

Line Segments

• Bounded by two endpoints $P_0$ and $P_1$, with parametric form $S(t) = P_0 + t(P_1 - P_0)$ for $t \in [0, 1]$
• Length computed via Euclidean distance—$\|P_1 - P_0\| = \sqrt{(x_1-x_0)^2 + (y_1-y_0)^2}$
• Intersection testing requires checking both collinearity and parameter bounds—a common source of implementation bugs

---

Two-Dimensional Surface Primitives

Planes define the 2D surfaces embedded in 3D space that partition regions and enable surface computations. In 2D problems, lines play the analogous role.

Planes

• Defined by normal vector and offset—implicit form $\vec{n} \cdot P + d = 0$ or equivalently $ax + by + cz + d = 0$
• Three non-collinear points determine a unique plane—compute normal via cross product $\vec{n} = (P_1 - P_0) \times (P_2 - P_0)$
• Half-space classification uses sign of $\vec{n} \cdot P + d$ to determine which side of the plane a point lies on

---

Polygonal Primitives

Polygons are the workhorses of computational geometry—they approximate curves, define regions, and form the basis of mesh representations. Convexity is the key property that determines algorithmic complexity.

Triangles

• Simplest polygon—three vertices, three edges, always planar and always convex
• Barycentric coordinates $(u, v, w)$ with $u + v + w = 1$ enable point-in-triangle tests and smooth interpolation
• Universally used in rendering—GPUs are optimized for triangles; any surface can be triangulated

Polygons

• Ordered sequence of vertices $\{P_0, P_1, \ldots, P_{n-1}\}$ with edges connecting consecutive points
• Convex vs. concave—convex polygons have all interior angles $< 180°$; concave polygons require more complex algorithms
• Area via shoelace formula—$A = \frac{1}{2}|\sum_{i=0}^{n-1}(x_i y_{i+1} - x_{i+1} y_i)|$, a signed value indicating winding order

Convex Hulls

• Smallest convex polygon containing all input points—like stretching a rubber band around the point set
• Computed by algorithms like Graham scan $O(n \log n)$, Jarvis march $O(nh)$, or QuickHull $O(n \log n)$ expected
• Preprocessing step for many algorithms—simplifies collision detection, diameter computation, and spatial queries

---

Curved Primitives

Circles represent the fundamental curved primitive, enabling smooth boundaries and distance-based queries. Most curved geometry in computational applications is approximated by polygons, but circles have special-case algorithms.

Circles

• Defined by center $C$ and radius $r$—implicit form $(x - c_x)^2 + (y - c_y)^2 = r^2$
• Point containment is a simple distance check: $\|P - C\| \leq r$ for interior points
• Circle-circle intersection determines collision detection; smallest enclosing circle solves facility location problems in $O(n)$ expected time

---

Quick Reference Table

---

Self-Check Questions

1. Representation choice: You need to test whether a point lies to the left or right of a directed line. Which representation of a line makes this easiest, and what mathematical operation do you use?

2. Compare and contrast: Both rays and line segments are bounded versions of lines. Explain how their parametric representations differ and give one algorithm that specifically requires rays rather than segments.

3. Convexity matters: Why do convex hull algorithms produce useful output even when the input is already a polygon? What property of the output guarantees simpler subsequent computations?

4. Primitive selection: You're implementing a 2D physics engine and need to detect collisions between rotating objects. Compare the tradeoffs between using circles versus convex polygons as bounding shapes.

5. Cross-primitive operations: Given three points $A$, $B$, and $C$, describe how you would use vector operations to determine (a) whether they are collinear, and (b) if not, whether $C$ lies to the left or right of the directed line from $A$ to $B$.