The Gold Standard of Computational Geometry

Computational Geometry develops algorithms for questions about spatial objects. Which segments meet? Which points form the outer convex boundary? Is a location inside a region? Which recorded point is nearest to a query? Each question needs an answer whose meaning is specified.

The gold standard is a complete connection between the geometric model, the decision tests, the algorithm and the evidence that the output satisfies the task. An attractive picture can help understanding, but the underlying coordinates and rules must also support the result.

Use a small original point set throughout this guide: A = (0,0), B = (4,0), C = (4,3), D = (0,3), E = (2,1) and F = (2,0). These are exact teaching coordinates in a Cartesian plane with the vertical axis increasing upwards.

The same set supports several tasks, but their answers differ. The convex hull uses A, B, C and D as extreme vertices. A nearest-point query can select E. A boundary-preserving application might retain F even though it is not an extreme vertex. Begin by naming the task rather than choosing an algorithm first.

Continue into: Geometry.

Contents · Next chapter

A pair of numbers becomes a location only within a coordinate convention. State the origin, axis directions, units and dimension. The guide’s calculations use ordinary planar Euclidean geometry; no map projection or physical measurement is implied.

If x is in metres and y in centimetres, directly adding squared coordinate differences produces a misleading distance. Convert to consistent units or specify a metric that deliberately weights the coordinates.

Likewise, longitude and latitude are not automatically Cartesian distances in metres. A geographic application needs an appropriate treatment of the Earth’s surface and the required scale. The Cartography branch provides a route into the surrounding representation choices.

Keep the mathematical input distinct from a measured object. Exact processing of rounded coordinates gives an exact answer about those represented coordinates. It does not establish that the represented boundary perfectly matches a surveyed or manufactured boundary.

Continue into: Cartography.

Contents · Previous chapter · Next chapter

A point set has no inherent boundary order. A polygon needs an ordered closed chain of edges. For the rectangle, A, B, C, D is the intended cyclic vertex order; rearranging the same four points as A, C, B, D creates a crossing chain.

Decide how repeated points are handled, whether a final vertex repeats the first, and whether zero-length edges are allowed. These choices affect counting, traversal and the preconditions of an algorithm.

Also state whether a polygon may contain holes or consist of several disconnected components. A single list of outer vertices cannot describe every such region without additional structure.

Boundary conventions are part of the result. A point on an edge can be reported separately from points strictly inside or outside. A Boolean flag called inside is incomplete until its treatment of the boundary is known.

Contents · Previous chapter · Next chapter

A predicate answers a discrete question: left turn, right turn or collinear; intersecting or disjoint; inside, outside or on the boundary. A construction produces a geometric object, such as an intersection point or a new polygon.

To test whether two segments cross, one can examine orientations before calculating the meeting coordinates. The crossing decision and the constructed coordinates are related, but they need different numerical handling.

If a small arithmetic error changes a predicate’s sign, the algorithm may choose a different branch and create inconsistent connectivity. A slightly rounded constructed point can instead create trouble when a later stage assumes exact agreement with another boundary.

CGAL’s kernel documentation distinguishes geometric objects and their operations, including numerical choices. Use that distinction when evaluating an implementation: ask which decisions are guaranteed and how newly constructed coordinates are represented.

Primary reference: CGAL’s linear geometry kernel manual.

Continue into: Numerical Analysis.

Contents · Previous chapter · Next chapter

For points P, Q and R, define orient(P,Q,R) = (Qx − Px)(Ry − Py) − (Qy − Py)(Rx − Px). In the stated upward-y convention, a positive result means a counterclockwise turn, a negative result a clockwise turn and zero collinearity.

For A = (0,0), B = (4,0) and C = (4,3), the result is 4 × 3 − 0 × 4 = 12. E = (2,1) gives orient(A,B,E) = 4. F = (2,0) gives zero.

The zero result says that A, B and F lie on one line. It does not by itself say whether F lies between A and B. Check the coordinate bounds as well; here F lies within the segment.

Swapping the first two arguments reverses the sign. Record the argument order in a calculation or test suite. A correct formula applied with inconsistent ordering can reverse the meaning of a turn.

Continue into: Linear Algebra · Graham Scan.

Contents · Previous chapter · Next chapter

Take the diagonals AC and DB of the rectangle. D and B lie on opposite sides of directed line AC: their orientation values are 12 and −12. A and C also lie on opposite sides of directed line DB, with values −12 and 12.

These strict opposite-side tests establish a proper crossing in this example. Solving the line equations gives the intersection (2,1.5), which lies within both segments.

Endpoint contact and collinear overlap need additional handling. Segments from (0,0) to (4,0) and from (2,0) to (6,0) overlap along the segment from (2,0) to (4,0). Their intersection is not a single isolated point.

Specify the result type accordingly: no intersection, one point or an overlapping segment. A routine that returns only true or false may be sufficient for a collision question but insufficient when the next stage must split the intersecting edges.

Continue into: Weiler–Atherton clipping.

Contents · Previous chapter · Next chapter

For the rectangle A, B, C, D, the query (2,1) lies strictly inside, (4,1) lies on the boundary and (5,1) lies outside. These conclusions follow directly from the coordinate inequalities.

For a general simple polygon, a ray-crossing method can count crossings under a consistent vertex convention. A ray through a vertex must not accidentally count the same passage twice. Testing for boundary membership first makes that case explicit.

A point inside an axis-aligned bounding box need not be inside the polygon enclosed by that box. For the concave polygon A, B, C, E, D, the point (2,2) is in the bounding box but outside the notched region.

Use the polygon’s actual representation and preconditions. The CGAL polygon reference provides the formal route into simplicity, orientation, area and bounded-side queries. A drawing is useful for checking an interpretation, while the predicate must settle the declared mathematical question.

Primary polygon reference: CGAL 2D Polygons user manual.

Contents · Previous chapter · Next chapter

The convex hull is the smallest convex set containing the input points. For the guide’s six points, the extreme vertices in counterclockwise order are A, B, C and D. E is inside, and F lies along the edge AB.

A hull representation that returns only extreme vertices omits F. A representation intended to retain every input point on the hull boundary might include it. Both need a documented output convention.

The hull also fills concavities. Replacing the concave polygon A, B, C, E, D with its hull produces the complete rectangle. That changes the region and increases its area from 8 to 12.

The connected Graham Scan and Jarvis March articles develop algorithmic routes to this task. Select a hull when enclosing all points convexly is the intended question. It does not automatically reproduce a property’s legal boundary, an obstacle’s outline or a route someone can walk.

Primary hull reference: CGAL 2D Convex Hulls and Extreme Points.

Continue into: Graham Scan · Jarvis March.

Contents · Previous chapter · Next chapter

For an ordered polygon, the shoelace sum adds xi times y at the next vertex minus yi times x at the next vertex, then divides by two. With A, B, C and D, the signed area is 12 in square coordinate units.

Reversing the order reverses the signed area to −12. The unsigned area remains 12. The sign therefore carries information about traversal orientation under the stated coordinate convention.

For A, B, C, E, D, the cross terms are 0, 12, −2, 6 and 0. Their sum is 16, so the simple concave polygon has area 8.

Do not treat a zero signed sum as proof of an empty region. A self-crossing chain can have cancelling signed contributions. Validate the geometry and decide which region semantics are intended before interpreting the arithmetic as a filled area.

Contents · Previous chapter · Next chapter

Use the simple counterclockwise polygon A, B, C, E, D. A convex corner is a candidate for ear clipping, but convexity alone is insufficient. The candidate triangle must also satisfy the ear conditions, including containing no other polygon vertex in the relevant interior.

At B, triangle ABC contains E. Therefore B is not an ear to remove under this test, even though the turn at B is convex. Removing it would cover space beyond the intended concave region.

At C, triangle BCE is a valid ear with area 3. Remove C, leaving A, B, E, D. Triangle EDA is then a valid ear with area 3, leaving triangle ABE with area 2.

The three triangle areas sum to 8, agreeing with the polygon area. This is a useful consistency check, though equal total area alone does not prove that triangles have no overlap or cover the correct boundary. Check those properties separately.

Continue into: Ear clipping.

Contents · Previous chapter · Next chapter

Clip the rectangle A, B, C, D to the half-plane x ≤ 2. The resulting vertices can be listed as (0,0), (2,0), (2,3), (0,3), giving area 6.

An edge traversal records whether its endpoints are inside or outside the clipping half-plane. Crossing edges contribute a constructed intersection; wholly outside edges contribute no retained segment for that half-plane.

For the example, AB crosses at (2,0) and CD crosses at (2,3). The edge at x = 0 remains, while the edge at x = 4 is discarded. The equality in x ≤ 2 includes the clipping boundary.

The Sutherland–Hodgman and Weiler–Atherton branches take clipping and intersection further. General polygon operations can yield holes or multiple components, so choose an output representation that can express the result rather than forcing every answer into one simple vertex cycle.

Primary region-operation reference: CGAL 2D Regularized Boolean Set-Operations. Its manual distinguishes regularized region operations from ordinary operations that retain all lower-dimensional boundary intersections. Match those semantics to the task.

Continue into: Sutherland–Hodgman clipping · Weiler–Atherton clipping.

Contents · Previous chapter · Next chapter

For Euclidean nearest-point queries, comparing squared distances avoids computing square roots when only the ordering matters. At query Q = (3,1), the squared distances to A, B, C, D, E and F are 10, 2, 5, 13, 1 and 2.

E is the unique nearest input point, at distance 1. B and F are tied for the next distance. If the query asks for the two nearest points, a tie convention determines whether to return exactly two or include all equally distant candidates at the cutoff.

Keep nearest point and nearest object distinct. The nearest point on a long segment may lie in its interior, not at either endpoint. An index of vertices alone does not answer every distance-to-boundary question.

Record the metric as well as the coordinates. Travel time, geodesic distance and weighted feature distance can order candidates differently from planar Euclidean distance. The correct search algorithm serves the declared metric.

Continue into: Closest-pair geometry.

Contents · Previous chapter · Next chapter

A Voronoi region groups locations that are nearest to a specified site under the chosen distance rule. With two sites U = (0,0) and V = (4,0), equal squared distance requires x² + y² = (x − 4)² + y².

Expanding and cancelling gives x = 2. Points to the left are closer to U, points to the right closer to V, and points on the bisector tie. Query (3,1) has squared distances 10 and 2, placing it on V’s side.

With more sites, the cell boundaries combine pairwise comparisons. Duplicate sites, ties and the distance model require explicit treatment. A nearest-site region in a map does not automatically represent an administrative boundary or a reachable service area.

The Fortune’s Sweep Line and Voronoi Regions articles provide the algorithm and geographic routes. Use this two-site derivation as a check that the representation still corresponds to the question being asked.

Continue into: Fortune’s sweep line · Voronoi Regions.

Contents · Previous chapter · Next chapter

A triangulation divides an appropriate region into triangles meeting along shared edges or vertices. For point sets, the region and any boundary constraints must be specified. Triangulating a concave polygon is not the same as triangulating the entire convex hull of its vertices.

A Delaunay triangulation of planar sites satisfies an empty-circumcircle condition: no input site lies strictly inside the circumcircle of a triangle. Boundary constraints and degenerate configurations need the relevant specialised treatment.

The four rectangle corners are cocircular: their common circle has centre (2,1.5). Either rectangle diagonal yields a Delaunay triangulation of those four sites, because the fourth corner is on, rather than strictly inside, the relevant circle.

This example shows why an exact geometric answer can still be non-unique. A documented tie rule can select one result without implying that the alternative violates the mathematical condition. The Bowyer–Watson branch develops the construction and its circle tests.

Primary triangulation reference: CGAL 2D Triangulations user manual.

Continue into: Bowyer–Watson.

Contents · Previous chapter · Next chapter

A direct nearest-point query can compare the query with every stored point. For many queries, a spatial index can preprocess the collection and use bounding regions to avoid examining every candidate in favourable cases.

A k-d tree partitions by coordinates. Its search must revisit another branch when that branch’s region could contain a better candidate. Choosing the side containing the query and stopping there is not a complete exact nearest-neighbour algorithm.

A range query asks for points in a specified region, such as a rectangle. State whether edges are included and whether results should be unique when the data contains duplicate coordinates with different records.

The k-d Tree and CGAL Spatial Searching routes explain the specialised structures. Separate preprocessing cost, query cost, storage and approximation guarantees. An exact geometric query and an approximate search result need different performance and correctness statements.

Primary search reference: CGAL Spatial Searching user manual.

Continue into: k-d trees.

Contents · Previous chapter · Next chapter

A sweep method processes geometric events in an ordered sequence while maintaining a summary of what is active. The summary must be defined precisely enough that each update preserves its meaning.

For intervals [0,3], [2,5] and [7,8] on a line, the union is [0,5] together with [7,8]. Its total length is 6, while adding the three input lengths gives 7 because the first two overlap for one unit.

A simple interval-union calculation sorts endpoints and accumulates distances between consecutive events whenever the active count is positive. At equal coordinates, the event convention should be consistent. Endpoints have zero length, but ordering can matter for other questions such as counting contacts.

The Klee Sweep Line article develops this example’s mechanism. Extending a sweep to planar intersections requires a more elaborate event queue and active structure. Do not assume the one-dimensional summary already supplies every invariant needed in two dimensions.

Continue into: Klee’s sweep line.

Contents · Previous chapter · Next chapter

Orientation and circle tests often branch on the sign of a computed quantity. When the exact value is close to zero, rounding can change that sign and cause inconsistent decisions. Shewchuk’s robust-predicate work explains adaptive arithmetic for these tests.

An arbitrary tolerance changes the decision policy. It may be appropriate to define a band of practically indistinguishable positions, but that model choice needs units, a rationale and consistent use. It is not a universal replacement for reliable predicates.

Exact arithmetic or robust predicates can establish a result for the represented input coordinates. If the original measurements were uncertain, the geometric conclusion about the physical object may still be uncertain.

Ask two separate questions: did the computation correctly process these coordinates, and do these coordinates support the application claim? Repairing one layer does not automatically repair the other. The Numerical Analysis branch deepens the arithmetic route.

Research reference: Jonathan Richard Shewchuk: Adaptive Precision Floating-Point Arithmetic and Fast Robust Predicates for Computational Geometry.

Continue into: Numerical Analysis.

Contents · Previous chapter · Next chapter

Translation preserves the guide’s distances, areas and orientation signs. Rotating the entire point configuration also preserves those quantities in the Euclidean plane. These facts provide useful comparisons for an implementation.

A uniform scale factor of 2 multiplies distances by 2 and areas by 4. Thus the rectangle’s area changes from 12 to 48. Orientation determinants are also multiplied by 4.

A reflection reverses orientation signs while preserving Euclidean distance and unsigned area. Changing from an upward-y mathematical frame to a downward-y screen frame can therefore reverse the visual turn interpretation if the convention is not adjusted.

More general affine transformations preserve collinearity and segment incidence but need not preserve Euclidean distances or nearest-point rankings. State which property is being tested before assuming that every geometric transformation should leave every answer unchanged.

Continue into: Iterative closest point · Projection onto a flat screen.

Contents · Previous chapter · Next chapter

For the six-point hull, check that its extreme vertices are input points, its consecutive turns are counterclockwise and every input point is on or inside it. For the clipped rectangle, check that every result vertex satisfies x ≤ 2 and that the area is 6.

For a segment-intersection construction, substitute the result into both segment descriptions and check the allowed parameter ranges. Include endpoint contact, collinear overlap, disjoint collinear segments and zero-length inputs according to the chosen contract.

Test duplicate points, all-collinear sets, reversed polygon order, points on vertices and nearly degenerate coordinates. A collection of ordinary random examples can miss exactly the cases where geometric decision logic is most fragile.

Use independent properties rather than repeating the same formula under another name. Area agreement helps check triangulation; coverage and non-overlap still need their own checks. Record the arithmetic model and distinguish a verified mathematical example from a benchmark of a particular software package.

Calculation checks for this guide gave orientation values 12, 4 and 0 for the declared triples; polygon areas 12 and 8; valid ear areas 3, 3 and 2; clipped area 6; and squared query distances 10, 2, 5, 13, 1 and 2. All four rectangle corners have squared distance 6.25 from (2,1.5), confirming the cocircular example. These checks concern the teaching coordinates.

Continue into: GJK collision distance.

Contents · Previous chapter · Next chapter

The strongest outcome is a reader who can turn a spatial question into a precise computation and then return the result to its original meaning. A hull, an intersection, a nearest candidate and a clipped region are different answers to different questions.

Before accepting a result, ask what the objects represent, which boundaries count, which metric applies and whether the numerical decisions support the algorithm’s assumptions. Those questions make a geometry calculation useful beyond a single worked exercise.

Follow the directory according to the next obstacle: orientation and hulls, polygon operations, triangulations, spatial search, map representation or numerical robustness. Return to the small coordinate examples to check the new idea.

The gold standard of Computational Geometry is an answer whose geometry, algorithm and interpretation agree. The reader can reproduce the calculation, explain the exceptional cases and identify the additional evidence required when the coordinates describe the world.

Continue into: Education parent · How X Works.

Contents · Previous chapter · Connected article directory