Geometric Modeling, Predicates, and Robustness

What Is Computational Geometry?

Computational geometry is the study of algorithms that solve problems about shapes and locations. It combines familiar geometry (points, lines, and polygons) with step-by-step instructions a computer can carry out quickly and consistently.

For example, a map application may need to decide whether a road crosses a river, which region contains your location, or what route avoids a blocked area. These are geometric questions. Computational geometry turns them into precise operations on coordinates so software can answer them for thousands or millions of objects.

Why Does It Matter?

Whenever software works with a map, a drawing, a 3D scene, or a moving robot, it needs to answer questions about where things are and how they relate. The same core ideas appear in:

• Maps and GIS: Which neighbourhood contains this address? Do two roads cross?
• Games and animation: Did two objects collide? Is a character inside a platform?
• Robotics: Can the robot reach its goal without hitting an obstacle?
• Design and manufacturing: Can two parts fit together? Does a tool path stay inside the workpiece?

These problems sound visual, but a computer does not reason from a picture. It stores numbers and applies rules to them. That is why we begin with a few simple shapes and questions.

The Basic Shapes: Points, Segments, Polygons, and Circles

Most two-dimensional geometry problems can be described using a small set of building blocks:

• Point: one location, written as a coordinate pair such as $A=(2,3)$.
• Line segment: the straight connection between two endpoints, such as $\overline{AB}$.
• Polygon: a closed shape made by joining line segments, such as a triangle or a map region.
• Circle: all points the same distance from a centre; useful for proximity and “within this radius?” questions.

The drawing is only a visual aid. An algorithm usually sees a point as two numbers, a segment as two points, and a polygon as an ordered list of points. The first step is to decide what question to ask about those numbers.

From Shapes to Geometric Questions

A geometry algorithm rarely needs to reconstruct the whole picture. It often needs one small answer: is this point left or right of that edge? Do these two segments cross? Is this point inside the circle? We call such a yes/no or three-way decision a geometric predicate.

Predicates are like reliable building blocks. A convex-hull algorithm, for example, repeatedly asks whether a new point turns left or right from the current boundary. A triangulation asks whether a point lies inside a circle. If these small answers are consistent, larger algorithms can build on them. If one answer is wrong near an edge or corner, the final shape can have gaps, overlaps, or the wrong boundary.

Points, Vectors, and Coordinates

A point $p=(x,y)$ is a location on a flat plane. A vector describes a direction and distance from one point to another: to go from $A$ to $B$, subtract their coordinates, giving $B-A$. For example, going from $(1,2)$ to $(4,6)$ means moving 3 units right and 4 units up.

When two vectors are compared, a compact calculation called the 2D cross product tells us whether the turn is left, right, or straight. You do not need to memorize that calculation yet; the next section works through it with an example. The SVG below shows vectors as arrows.

Slide a copy of each vector to complete the parallelogram. The cross product's magnitude is its area, while its sign records whether the turn from the first arrow to the second is counterclockwise or clockwise. Many algorithms need only the sign because it tells them which case to handle.

Coordinates may be whole numbers, such as grid positions, or decimals, such as GPS measurements. Computers store and calculate with these numbers differently; later, we will see why that matters when a point lies very close to a line.

The Orientation Test: Which Way Did We Turn?

Given three points $a$, $b$, and $c$, imagine walking from $a$ to $b$, then toward $c$. The orientation test answers one simple question: did you turn left, turn right, or continue in a straight line? In geometry and programming, a small yes/no or three-way calculation like this is often called a predicate.

The calculation below subtracts the coordinates to form two arrows, then compares the area on either side of them. For now, focus on the sign of the answer:

$$ \operatorname{orient}(a, b, c) \;=\; (b_x - a_x)(c_y - a_y) - (b_y - a_y)(c_x - a_x) $$

This is the cross product of the arrows $b-a$ and $c-a$. Its magnitude is twice the triangle's area; its sign tells us the turn:

• $\operatorname{orient}(a,b,c) > 0$: $c$ is to the left of ray $a \to b$ (counterclockwise turn).
• $\operatorname{orient}(a,b,c) < 0$: $c$ is to the right (clockwise turn).
• $\operatorname{orient}(a,b,c) = 0$: $a$, $b$, $c$ are collinear.

A Numerical Trace

For $a=(1,1)$, $b=(5,2)$, and $c=(3,4)$, the displacement vectors are $b-a=(4,1)$ and $c-a=(2,3)$, so

$$\operatorname{orient}(a,b,c)=4\cdot3-1\cdot2=10.$$

The positive sign says “left turn.” The magnitude also says the triangle's area is $10/2=5$. Translating all three points changes neither displacement vector, so orientation is translation invariant.

def orientation(a, b, c):
    """Return >0 if a->b->c turns left, <0 if right, 0 if collinear."""
    return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])


a, b, c = (0, 0), (4, 0), (2, 3)
print(orientation(a, b, c))  # 12 -> left turn (counterclockwise)

#include <iostream>

struct Point { double x, y; };

double orientation(const Point& a, const Point& b, const Point& c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

int main() {
    Point a{0, 0}, b{4, 0}, c{2, 3};
    std::cout << orientation(a, b, c) << "\n";  // 12 -> left turn
}

Nearly every algorithm in this series reduces to calling this one function: sorting points around a hull (Part 3), deciding which side of a sweep-line event a segment falls on (Part 6), testing whether a query point is inside a triangle (Part 9), and more.

The In-Circle Predicate

Here is another useful shape question: draw a circle through the three corners of a triangle. Is a fourth point $d$ inside that circle, exactly on it, or outside? The in-circle test answers this with a sign. It is a key building block for Delaunay triangulations, which we will meet later in the series.

For a counterclockwise triangle $a,b,c$, the following calculation is positive when $d$ is inside, zero when it is on the circle, and negative when it is outside. The formula uses $d$ as the origin, so each row describes one triangle corner relative to $d$:

$$ \operatorname{inCircle}(a,b,c,d) = \begin{vmatrix} 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{vmatrix} $$

The sign convention assumes $a,b,c$ are counterclockwise. Reverse their order and every determinant sign reverses. A robust implementation either normalizes the triangle orientation first or combines the in-circle sign with orientation(a, b, c).

Why Naive Floating-Point Predicates Fail

Computers store many decimal coordinates as nearby approximations rather than exact values. Usually the difference is tiny and harmless. But when points are almost on the same line, the orientation calculation combines close numbers; rounding can change the sign that tells an algorithm which side of the line a point lies on.

A common first attempt is to call every result smaller than a fixed threshold $|\operatorname{orient}(a,b,c)| < \varepsilon$ zero. But coordinates can be tiny or enormous, so one threshold cannot safely handle every scale. The deep dive on exact arithmetic and adaptive precision explains a stronger approach: estimate the possible rounding error, trust the quick answer when it is clearly larger than that error, and use more precise arithmetic when the sign is uncertain.

This is called filtered evaluation. Think of it as a confidence check: ordinary cases stay fast, and only borderline cases need extra precision.

Consistent Degeneracy Policies

A degenerate case is a special arrangement that makes a geometric test return exactly zero—for example, three points on one line. A robust algorithm decides in advance what to do in these cases, rather than letting the outcome depend on accident:

• Duplicate points — usually deduplicated before an algorithm runs, or explicitly defined to collapse to one point.
• Collinear points on a hull or triangulation boundary — does the middle point count as "on the hull" or is it dropped?
• Cocircular points in a Delaunay triangulation — the in-circle test returns exactly zero for four points on a common circle, and more than one valid triangulation exists.
• Shared endpoints / overlapping segments in a sweep-line algorithm — is a shared endpoint one event or two?

Later parts will introduce formal tie-breaking tools such as symbolic perturbation when they are useful. For now, the key habit is simple: identify special cases and state how the algorithm handles them.

A Brief History

Computational geometry grew as computers began solving practical shape problems in mapping, design, and graphics. Researchers found that tiny rounding errors could cause large failures in geometry software. Jonathan Shewchuk's work on adaptive-precision predicates showed how to keep these important decisions reliable without making every calculation slow; we explore that technique in the linked deep dive.

The next part builds directly on orientation(): segment intersection, point-to-segment distance, and point-in-polygon queries are all short compositions of the same sign test.