Computational Geometry
Computational geometry turns positions and shapes into decisions: whether segments intersect, which points form a boundary, or which objects might overlap a query region. The difficult cases often sit exactly where the picture looks obvious—touching endpoints, overlapping edges, repeated points, and almost-collinear coordinates.
Start with the coordinate system and the meaning of a boundary. Then choose predicates and constructions that preserve that meaning under the representation you actually use. A fast spatial index cannot repair a wrong orientation decision or an undefined policy for touching shapes.
TL;DR
- Define coordinate system, units, dimensionality, and boundary inclusion.
- Distinguish predicates that decide topology from constructions that compute new coordinates.
- Handle repeated, collinear, and zero-size inputs deliberately.
- Use exact or appropriate robust predicates for the input representation.
- Treat a spatial index as candidate selection followed by the required exact test.
Quick Example
This complete Python example tests closed 2D segment intersection using integer coordinates. Endpoint touching and collinear overlap count as intersection, including a zero-length segment lying on another segment.
The explicit cases passed, including a large-integer near-collinear determinant of -1. Additional order/symmetry checks passed for all 6,561 quadruples from a 3×3 integer grid. This is not an adaptive floating-point predicate, coordinate projection, intersection-coordinate construction, or GIS/library integration test.
Core Concepts
Orientation
In 2D, the sign of an orientation determinant identifies the turn made by three points. The example returns that determinant rather than prematurely reducing it to a floating-point angle.
Numerical robustness
Shewchuk explains how roundoff near zero can reverse orientation or incircle decisions and describes adaptive precision techniques that preserve the needed sign. An arbitrary epsilon is not automatically a replacement for such a predicate. Robust geometric predicates
Representation scope
Python integers make the demonstration’s arithmetic exact for its integer inputs. That fact does not make rounded measurements exact or prevent overflow in a fixed-width implementation copied into another language. State the actual representation at the algorithm boundary.
Specify boundary behavior before implementing it
This table is a declared contract, not the only valid geometry API. A layout engine, CAD operation, and geographic boundary query can need different interpretations. Choose one that fits the task and preserve it through all stages.
The example first checks whether each segment’s endpoints lie on opposite sides of the other line. It separately handles zero orientation through a bounding-box test. That second step matters: collinearity alone does not imply the finite segments overlap.
Keep the boolean intersection decision separate from returning an intersection point. Integer segment endpoints can produce a fractional crossing coordinate. A construction may need rational arithmetic, a supported exact-construction kernel, or a documented rounding policy even when the predicate was exact.
Review invalid-input handling before exposing the example as a general API. It assumes pairs of integer coordinates. Nonfinite floating-point values, wrong dimensions, malformed records, and mixed coordinate systems need validation at the appropriate boundary.
Build convex hulls and spatial queries on the same semantics
A convex hull encloses a point set with a convex boundary. For a monotone-chain implementation, sort and deduplicate points, build lower and upper chains, and use orientation to decide which turns to retain. Define whether intermediate collinear boundary points remain in the output.
Empty, single-point, two-point, and all-collinear inputs need explicit return conventions. A caller expecting a polygon cannot blindly apply polygon operations to every hull result. Keep dimensional collapse visible in the interface.
Test hull properties as well as example coordinates: every input point should be inside or on the declared hull, boundary turns should follow the chosen orientation convention, and reordering input should preserve the same geometric result under a canonical output policy. These are proposed checks; no hull implementation was executed for this article.
For spatial search, use a bounding box or another index to narrow candidate objects, then run the exact predicate required by the task. Bounding-box overlap can contain false positives for the actual shapes. Candidate selection and geometric acceptance are different stages.
Choose an index from data dimension, update pattern, query shape, and distribution. A method that works well for a static low-dimensional point set may behave differently for frequently changing extended objects. Measure candidate counts and full query work, not only index lookup time.
Preserve numerical meaning across the pipeline
An exact predicate operates on the supplied coordinates. If an earlier conversion rounded two distinct positions together, later exact arithmetic cannot recover the lost distinction. Record measurement resolution, projection, normalization, and any snapping policy.
Avoid a universal tiny tolerance copied between units or scales. A threshold that is meaningful in meters can be absurd in degrees or microscopic model units. If the domain requires tolerance, define what equivalence means and check whether the resulting decisions remain consistent across related predicates.
Inconsistent decisions can break topology. For example, different stages might disagree about whether an endpoint lies on an edge. Use a coherent kernel or reviewed predicate policy rather than mixing unrelated approximations throughout the algorithm.
Build a regression set around degeneracy: duplicates, endpoint touches, reversed order, overlapping collinear segments, very large coordinates, and near-zero determinants. Compare against a trusted exact reference on bounded cases where practical.
Before using the method for a consequential decision, validate the real input model and chosen library with the responsible domain owner. The local integer tests demonstrate a specific contract, not every geometry operation or coordinate system.
Best Practices
Declare the geometry contract
Put units, coordinate system, boundary inclusion, and degenerate-result conventions beside the public interface.
Separate decisions and constructions
Choose numeric methods for both the topology test and any new coordinates. Verify conversions between them.
Test adversarial cases
Preserve small degenerate and near-boundary fixtures. Exercise symmetry and input-order changes without mistaking them for a complete proof.
Common Mistakes
Bad: A determinant close to zero can always be rounded to zero.
Correct: Choose a robust predicate or a domain-specific tolerance policy that preserves required consistency.
Bad: Bounding boxes overlap, so the shapes intersect.
Correct: Run the relevant shape predicate on the candidate set.
Bad: Integer predicates make every output coordinate an integer.
Correct: Use an appropriate representation for constructed intersections and other derived coordinates.
FAQ
Does the example support floating-point measurements?
It is intended for Python integer coordinates. Real measured or floating-point data needs an appropriate numerical policy.
Is endpoint touching an intersection?
In this example, yes. Other APIs may differ, so make the policy explicit.
Was a convex hull or spatial index tested?
No. Those sections explain design and proposed verification; the executed code covers segment predicates only.
Related Topics
- Algorithms & Data Structures — Algorithm models and representation tradeoffs.
- Data Structures — Indexes and candidate selection.
- Probability and Linear Algebra for Computing — Coordinate and transformation foundations.