When Geometry Algorithms Disagree: Precision Boundaries in Komp-Geom

Table of Contents

Two line segments either intersect or they do not. At least, that is the question I thought I was asking.

The same near-endpoint crossing appears in both panels. A pairwise test reports it, while a sweep-line algorithm omits the pair. This is a conceptual illustration.

In Komp-Geom, my Kotlin Multiplatform geometry library, a pairwise segment test can report a contact that a Bentley–Ottmann sweep over the same finite input misses. It happens near a precision boundary, where coordinates have been perturbed by tiny amounts. I first noticed the problem in a sweep, but I do not think of it as a sweep-line problem anymore. A sweep merely makes the consequences visible: if two numerical decisions disagree, an entire chain of later decisions can go wrong.

The question I want to answer is broader. What does it mean for a geometry library to make consistent decisions about its input, and what should it promise when a result lies near a precision boundary?

A precision boundary is a decision boundary #

A Double stores a finite-precision number, and arithmetic on doubles rounds intermediate results. An epsilon is something else: a policy that says when an application will treat two values as close enough. An epsilon does not measure the rounding error of every expression. It can also deliberately blur the distinction between different input coordinates.

Komp-Geom’s EpsilonDoubleEquivalence considers finite values a and b approximately equal when

|a − b| ≤ ε · max(1, |a|, |b|)

The default geometric epsilon is 10⁻¹⁰. Near zero this has an absolute component, while at larger magnitudes the threshold scales with the operands. Operations can receive a different DoubleEquivalence. This is useful when a local comparison should respect a caller’s notion of closeness.

But closeness is not identity. With ε = 10⁻⁸, take a = 0, b = 0.75 × 10⁻⁸, and c = 1.5 × 10⁻⁸. The first two are close, as are the last two, but the first and last are not. Approximate equality is not transitive. It must not be the identity or comparator for an ordered collection. Apache Commons Geometry also distinguishes approximate eq() from strict equals() and hashing. Its precision context is useful for local tolerance-aware operations, but keeping eq() out of object identity does not, by itself, guarantee that every algorithm’s predicates and constructed coordinates agree near a boundary.

More importantly, comparing numbers is not the same as deciding geometry. An orientation test asks on which side of a directed line a point lies. An incidence test asks whether a point belongs to an edge. An intersection test asks whether two edges meet. A construction calculates a new point. If those operations disagree, the output can change its connectivity, not just its last decimal digit.

This reaches far beyond a sweep #

Consider a convex hull algorithm examining three nearly collinear points. If its orientation test changes sign, it can keep a point that should be discarded or remove a point that should be a hull vertex. A polygon algorithm deciding whether a point is inside, on the boundary, or outside must give its boundary cases compatible answers. In a triangulation, an incorrect orientation or incircle sign can change the combinatorial structure. A polygon overlay or arrangement must agree on whether two edges meet at one vertex before it can assemble faces. These are examples of the same general dependency, not claims that all these algorithms currently fail in Komp-Geom.

Orientation can change a convex hull, incidence can change a polygon arrangement, and event ordering can change a segment sweep. All three depend on a coherent precision contract.

I saw this in a different form while working on my Minkowski-sum thesis. When nearly identical computed coordinates became separate vertices in a DCEL, edges could fail to connect and faces could fail to close. The resulting error was topological. Rounding coordinates more aggressively helped that implementation in some cases, but it was a recovery strategy, not a general definition of geometric correctness.

Not every numerical operation needs exact topology. An approximate distance for display may be enough. The stronger requirements arise when that number decides which objects exist or connect.

Why the sweep exposed the gap #

A pairwise test classifies a contact with the configured tolerance and computes its point using Double arithmetic. The sweep must then place that point in an event queue. Komp-Geom shears coordinates for event ordering and checks incidence back in the original coordinate system. Its status tree now uses a stable, position-based order rather than an epsilon-dependent comparator. But event coordinates and segment heights are still calculated with rounded doubles, while incidence checks remain tolerance-aware.

The differential test exposes a disagreement along that path. A constructed event might no longer satisfy a later check that the pairwise test passed. The diagram shows one possible mechanism, not a proven diagnosis of the observed case.

Schematic of a near-endpoint crossing: pairwise classification accepts a contact, but a displaced constructed event may fail a later incidence check. The displacement is exaggerated to illustrate the concept.

The choices define different kinds of geometry #

There is no single “more precise” switch to flip. The first two ideas address different parts of a calculation and can work together. The third deliberately changes the geometry to a chosen resolution.

Filtered robust predicates: make reliable decisions #

A predicate answers a small question, such as “Is this point to the left or right of that line?” Three points that are almost in a straight line make the answer difficult because rounding might change which side the third point appears to be on. A filtered predicate first tries the fast calculation. If the possible rounding error is too small to change the answer, it accepts it. Otherwise, it calculates more carefully before deciding.

Shewchuk’s adaptive predicates use this approach for questions including orientation. They determine the correct answer for the floating-point numbers provided as input. They cannot tell us whether those numbers perfectly describe a measured object in the real world, and they do not by themselves calculate an exact intersection point. Unlike an epsilon comparison, the filter does not simply call a small result zero.

A filtered predicate accepts a sign when its error bound cannot cross zero. Otherwise, it refines the calculation before deciding. This bound is not an application epsilon.

Predicates and constructions: decide, then locate #

Knowing that two segments cross is one thing. Calculating where they cross is another. The first is a decision, or predicate. The second is a construction: it creates a new coordinate. CGAL’s robustness guidance treats these as separate responsibilities, and its kernel design asks which operations an algorithm needs.

Even if the input endpoints are Double values, their intersection may fall between the numbers a Double can represent. An approximate Vec2 is often fine for drawing a dot on a screen. It is not necessarily safe as the identity of a shared vertex or as a key for ordering later events. If an algorithm will make more decisions about that point, it must retain a representation or a way of comparing it that stays consistent with the earlier decision.

A robust predicate decides whether segments intersect. An internally consistent construction can guide later decisions, while an approximate reported point is useful for output but not automatically an exact key.

Fixed-grid geometry: choose a resolution #

Suppose a map records locations on a one-metre grid. Two distinct points might both be moved to the same grid position. They now are one point in the reduced geometry. A narrow gap can close, and a short line can collapse. This is not a rounding error to be hidden. It is a deliberate rule about which details the map keeps.

Proper snap rounding also needs rules for the lines and shapes connected to those points. JTS’s precision reducer documents a mode that preserves valid reduced topology while warning that nearby polygons may merge. A grid is useful when an application has a meaningful resolution, but it is not a drop-in replacement for saying two values are approximately equal.

Two separate points map to one grid vertex after snapping. Unlike an approximate comparison, snapping intentionally changes the geometry.

The choice for Komp-Geom #

For Komp-Geom, I would first evaluate exact-input topology for finite Double coordinates, using filtered predicates for common cases and more precise computation when a result is uncertain. This would change the API’s geometric semantics, not just its numerical accuracy: a near-miss currently accepted as a contact because of tolerance would no longer count as an intersection. An intersection returned as Vec2 could still be approximate, but that rounded point must not silently determine event order or vertex identity.

I would start with segment intersection and the sweep as a test of the whole contract, then apply the same predicate and construction rules to other topology-sensitive algorithms. I would keep EpsilonDoubleEquivalence for local approximate comparisons and consider fixed-grid geometry as a separate model.

The sweep revealed the gap, but the goal is broader: every decision that changes geometric topology must follow a coherent model.