Coordinate and Vector Algorithms

The Central Idea

A geometric object can often be represented by coordinates, and a geometric relationship can often be tested by a short numerical procedure.

For example, two points in the plane may be stored as

and

The displacement from \(P\) to \(Q\) is the vector

This single subtraction operation converts a geometric relation into data that can be used for distance, direction, projection, orientation, motion, collision checks, and many other algorithms.

What Makes a Geometric Procedure an Algorithm?

An algorithm is a finite, repeatable procedure for transforming inputs into outputs.

In computational geometry, the inputs may be:

• point coordinates;
• vectors;
• line or segment endpoints;
• polygons or meshes;
• distances, angles, or tolerances.

The output may be a number, a new geometric object, or a logical decision such as left of, inside, parallel, or overlapping.

Coordinates as Data

A point in two-dimensional Cartesian space is usually represented as an ordered pair

In three dimensions, the point is represented as

Computationally, these coordinates can be stored in an array, tuple, record, or object. The mathematical representation and the software representation serve the same purpose: they identify the components needed for later operations.

Points and Vectors Use Similar Data but Different Meanings

A point describes a location. A vector describes a displacement, direction, or change.

The point

identifies a location. The vector

describes a movement of \(3\) units in the \(x\)-direction and \(5\) units in the \(y\)-direction.

Their numerical components may be identical, but their geometric roles are different.

Subtracting Points Produces a Vector

Let

The displacement from \(P\) to \(Q\) is

Therefore,

Point subtraction is one of the most frequently used operations in computational geometry.

Adding a Vector to a Point Produces a New Point

Suppose

and

Translating \(P\) by \(\mathbf{v}\) gives

Thus,

This is the computational form of translation.

Vector Addition

If

and

then

Vector addition combines displacements.

For example,

Vector Subtraction

Vector subtraction is performed component by component:

For example,

Subtraction is especially useful when constructing relative directions between points.

Scalar Multiplication

Multiplying a vector by a scalar changes its magnitude and may reverse its direction.

If

then

For example,

When \(k=-1\), the vector reverses direction.

Vector Magnitude

The magnitude of

is

For

we obtain

Magnitude converts a vector displacement into a scalar length.

Distance between Two Points

The distance between two points is the magnitude of their displacement.

For

form

Then

Squared Distance Is Often Enough

Many algorithms only need to compare distances rather than report the distance itself.

Since square roots preserve the order of nonnegative numbers,

Midpoint Algorithm

The midpoint of

and

is found by averaging corresponding coordinates:

This can also be written in vector form as

Linear Interpolation between Points

The midpoint formula is one case of a more general construction called linear interpolation.

A point moving from \(P\) to \(Q\) can be written

When

the point lies on the segment from \(P\) to \(Q\).

• \(t=0\) gives \(P\);
• \(t=\frac12\) gives the midpoint;
• \(t=1\) gives \(Q\).

Example: Interpolating along a Segment

Let

Then

At \(t=\frac14\),

Therefore,

Normalizing a Vector

A unit vector has magnitude \(1\).

For a nonzero vector \(\mathbf{v}\), its normalized form is

For

we have \(\|\mathbf{v}\|=5\), so

Normalization separates direction from magnitude.

Zero Vectors Need Special Handling

The vector

has magnitude \(0\).

Attempting to normalize it would require division by zero:

Therefore, a robust normalization algorithm must first test whether the magnitude is zero, or sufficiently close to zero in approximate arithmetic.

The Dot Product

For

and

the dot product is

It is a scalar rather than a vector.

The Dot Product as an Angular Test

The dot product also satisfies

Therefore, for nonzero vectors:

• if \(\mathbf{u}\cdot\mathbf{v}>0\), the angle is acute;
• if \(\mathbf{u}\cdot\mathbf{v}=0\), the vectors are perpendicular;
• if \(\mathbf{u}\cdot\mathbf{v}<0\), the angle is obtuse.

An algorithm can often determine a directional relationship without explicitly computing the angle.

Avoiding Unnecessary Angle Calculations

Suppose an algorithm only needs to know whether two directions are perpendicular.

It does not need to compute

It can test the simpler condition

Computational geometry frequently replaces an expensive geometric quantity with a simpler equivalent predicate.

Projection onto a Vector

The projection of \(\mathbf{u}\) onto a nonzero vector \(\mathbf{v}\) is

This formula is computationally useful because

Projection is used in closest-point calculations, collision response, decomposition of motion, and many geometric constructions.

Perpendicular Vectors in Two Dimensions

If

then two perpendicular vectors are

and

For example, if

then

is perpendicular because

The Two-Dimensional Cross-Product Scalar

In the plane, two vectors

can be combined using the determinant-like quantity

Although the three-dimensional cross product produces a vector, this two-dimensional form produces a scalar. Its sign is extremely useful for orientation tests.

Orientation of Three Points

Let

Form the two vectors

and

Then compute

Reading the Orientation Test

Under the usual Cartesian orientation:

• a positive result means \(A,B,C\) make a counterclockwise turn;
• a negative result means they make a clockwise turn;
• zero means the three points are collinear.

This one test is a foundational geometric predicate used in convex hulls, polygon algorithms, triangulation, segment tests, and many other computational procedures.

Example: Orientation

Let

Then

and

Therefore,

Since \(12>0\), the turn from \(A\) to \(B\) to \(C\) is counterclockwise.

Signed Area of a Triangle

The same determinant used for orientation also measures twice the signed area of triangle \(ABC\):

Therefore, the ordinary area is

One computation can therefore answer two different geometric questions: orientation and area.

Collinearity as a Determinant Test

Three points are collinear exactly when

This is often more useful computationally than comparing slopes, because slope calculations can require division and become problematic for vertical lines.

Why Determinants Often Beat Slopes

The slope between two points is

If \(x_2=x_1\), this expression requires division by zero.

By contrast, the orientation determinant uses only multiplication, subtraction, and addition. It handles vertical, horizontal, and oblique configurations in one uniform procedure.

Axis-Aligned Bounding Boxes

A simple way to enclose a collection of planar points is with an axis-aligned bounding box, often abbreviated AABB.

For points

compute

These four values define the smallest axis-aligned rectangle containing all the points.

Point-in-Bounding-Box Test

A point

lies inside or on the boundary of an axis-aligned box when

and

Bounding-box tests are inexpensive and are often used to reject impossible cases before more detailed geometry is computed.

Componentwise Minimum and Maximum

Given two points

their componentwise minimum is

while their componentwise maximum is

These operations are useful when building bounding regions from endpoints or expanding a box as new points are processed.

Coordinate Clamping

To clamp a scalar \(x\) to an interval \([a,b]\), define

If \(xb\), the result is \(b\). Otherwise, the result is \(x\).

Clamping is a small but useful algorithmic tool in geometry, graphics, and nearest-point calculations.

Coordinate Transformations as Algorithms

A two-dimensional affine transformation can be written

where \(A\) is a \(2\times2\) matrix and \(\mathbf{t}\) is a translation vector.

If

then

Translation Algorithm

Translation by

sends

to

To translate an entire polygon or mesh, apply the same operation to every vertex.

Scaling Algorithm

Scaling about the origin by factors \(s_x\) and \(s_y\) sends

to

Uniform scaling uses the same factor in both directions:

Nonuniform scaling allows the two factors to differ.

Rotation Algorithm

Rotating a point about the origin through angle \(\theta\) gives

This is equivalent to multiplying by the rotation matrix

Transforming about a Chosen Center

To rotate or scale about a point \(C\) rather than the origin:

1. translate so that \(C\) moves to the origin;
2. apply the desired rotation or scaling;
3. translate back.

In vector notation,

This pattern appears repeatedly in graphics, CAD, and geometric modeling.

Three-Dimensional Vectors

The same componentwise ideas extend naturally to

Its magnitude is

The dot product becomes

The Three-Dimensional Cross Product

For

and

the cross product is

The result is perpendicular to both input vectors.

Surface Normals from Cross Products

Given three noncollinear points \(A\), \(B\), and \(C\) in three-dimensional space, form

and

Then

is normal to the plane of the triangle.

Normal vectors are fundamental in rendering, lighting, surface orientation, and mesh processing.

Degenerate Geometric Cases

A geometric configuration is often called degenerate when it collapses into a lower-dimensional or otherwise exceptional case.

Examples include:

• a segment whose endpoints are identical;
• three points that are collinear instead of forming a triangle;
• a vector with zero magnitude;
• a triangle with zero area;
• two nominally distinct coordinates that are numerically indistinguishable.

Robust algorithms check for these cases rather than assuming that every input is generic.

Exact Arithmetic and Approximate Arithmetic

Mathematical formulas are often written as though arithmetic were exact. Computers, however, commonly represent real-number approximations using floating-point numbers.

As a result, a theoretically exact equality such as

may appear computationally as two values that differ by a tiny amount.

This distinction matters when algorithms test collinearity, perpendicularity, coincidence, or other boundary conditions.

Using a Tolerance

Instead of testing whether an approximate quantity \(r\) equals zero exactly, an algorithm may test

for a suitably chosen tolerance \(\varepsilon>0\).

For example, an approximate perpendicularity test might examine whether

The appropriate tolerance depends on the scale and numerical requirements of the problem. There is no universal tolerance that is correct for every computation.

Scale Matters in Numerical Tests

A fixed tolerance such as

may be reasonable for one coordinate scale and inappropriate for another.

Coordinates measured near \(1\) behave differently from coordinates near \(10^{12}\). For this reason, robust computational systems often use scale-aware comparisons, higher-precision arithmetic, or exact geometric predicates when correctness near boundaries is critical.

Geometric Predicates and Geometric Constructions

Computational geometry often separates operations into two broad types.

A predicate answers a question:

• Are these points collinear?
• Is this turn clockwise or counterclockwise?
• Is this point inside a bounding box?

A construction creates a new geometric object:

• construct a midpoint;
• construct a translated point;
• construct a projection;
• construct a normal vector.

Many larger algorithms alternate between predicates and constructions.

A Small Geometry Toolkit

A reusable coordinate-and-vector toolkit commonly includes procedures for:

• adding, subtracting, and scaling vectors;
• computing magnitudes and squared magnitudes;
• computing distances and squared distances;
• normalizing nonzero vectors;
• computing dot products;
• computing two-dimensional orientation values;
• computing three-dimensional cross products;
• interpolating between points;
• forming and testing bounding boxes;
• applying affine transformations.

More advanced computational geometry can then be built from these small, tested pieces.

Example: A Combined Coordinate Workflow

Let

First compute the displacement:

Its squared length is

Its length is

The midpoint is

Therefore,

Several geometric quantities were produced from one basic displacement vector.

Example: Classifying a Turn

Suppose a path passes through

Form

and

The orientation value is

Since the value is positive,

Example: Testing Perpendicularity

Let

and

Their dot product is

Therefore,

Common Error: Confusing a Point with a Vector

The notation

does not by itself explain whether the object is a location or a displacement.

Algorithms become clearer when the roles are explicit:

for a point, and

for a vector.

Common Error: Reversing a Displacement

The vector from \(P\) to \(Q\) is

not \(P-Q\).

Reversing the subtraction reverses the vector:

The two vectors have the same magnitude but opposite directions.

Common Error: Normalizing the Zero Vector

The formula

applies only when

A zero vector must be handled as a separate case.

Common Error: Computing an Angle When Only a Sign Is Needed

If the task is only to decide whether two vectors form an acute or obtuse angle, computing an inverse trigonometric function is unnecessary.

The sign of

already answers the question.

Good algorithm design often means identifying the smallest computation that produces the required information.

Common Error: Comparing Slopes for Vertical Geometry

Slope comparisons can fail when a denominator becomes zero.

For collinearity and orientation, determinant-based formulas are usually more uniform:

No division is required.

Common Error: Treating Floating-Point Equality as Exact Geometry

A computed value that should theoretically be zero may instead appear as

Whether that should be treated as zero depends on the numerical scale and requirements of the problem.

Robust computational geometry distinguishes mathematical equality from the practical comparison of approximate numerical values.

A Reliable Procedure for Coordinate Computation

1. Identify which quantities are points and which are vectors.
2. Write the needed coordinates explicitly.
3. Construct displacement vectors by subtracting points in the correct order.
4. Use componentwise arithmetic for vector operations.
5. Avoid square roots or angle calculations when a simpler equivalent test is enough.
6. Check for zero vectors and other degenerate inputs before division.
7. Use determinant-based predicates for orientation and collinearity.
8. Account for numerical tolerance when approximate arithmetic is involved.
9. Verify the geometric meaning of the numerical output.

A Reliable Procedure for Building Geometric Algorithms

1. Represent the geometric objects with coordinates or vectors.
2. Reduce the geometric question to one or more basic predicates or constructions.
3. Choose formulas that avoid unnecessary operations.
4. Handle special and degenerate cases explicitly.
5. Separate reusable operations into small functions or procedures.
6. Test ordinary cases, boundary cases, and extreme coordinate scales.
7. Confirm that the output matches the intended geometric interpretation.

Practice 1: Displacement Vector

Let

Find \(\overrightarrow{PQ}\).

Practice 2: Squared Distance

Find the squared distance between

and

Practice 3: Midpoint

Find the midpoint of

and

Practice 4: Linear Interpolation

Let

Find the point

when \(t=\frac13\).

Practice 5: Dot Product

Compute

and determine whether the angle between the vectors is acute, right, or obtuse.

Practice 6: Perpendicular Vector

Give one vector perpendicular to

Practice 7: Orientation

Determine whether the ordered points

make a clockwise turn, a counterclockwise turn, or are collinear.

Practice 8: Triangle Area

Find the area of the triangle with vertices

Practice 9: Bounding Box

Find the axis-aligned bounding box of the points

Practice 10: Three-Dimensional Normal

Let

Compute

Practice Answers

Practice 1

Practice 2

Practice 3

Practice 4

Practice 5

Because the dot product is positive, the angle is acute.

Practice 6

For \((a,b)=(7,-3)\), one perpendicular vector is

Check:

Practice 7

Since \(10>0\),

Practice 8

Practice 9

The coordinate extremes are

Therefore, the bounding box is

Practice 10

What to Remember

Coordinate and vector algorithms convert geometric relationships into arithmetic operations.

• subtract points to form displacement vectors;
• use vector magnitude for length and distance;
• use squared distance when only comparison is needed;
• use the dot product for angular relationships and projection;
• use the two-dimensional cross-product scalar for orientation;
• use cross products in three dimensions to construct perpendicular directions;
• use interpolation to construct points along segments;
• use coordinate minima and maxima to construct bounding boxes;
• check zero, collinear, coincident, and other degenerate cases;
• treat floating-point comparisons carefully near geometric boundaries.

The larger lesson is that geometry does not need to be abandoned when a problem becomes computational. Instead, geometric structure is encoded in coordinates, vectors, determinants, and carefully chosen numerical tests.

Where We Go Next

Coordinate and vector algorithms provide the basic operations needed to represent directions, compare orientations, and construct points.

The next lesson, Line and Curve Intersection, uses these tools to determine where geometric paths meet, how to distinguish intersections from nonintersections, and how special cases such as parallelism, tangency, and overlapping geometry affect the computation.