Computational Geometry

Robust geometric computation, built on exact arithmetic.

Much of computational geometry comes down to a few yes-or-no questions: which side of a line a point lies on, whether a point falls inside a circle, whether two segments cross. In ordinary floating-point arithmetic these answers are almost always right. The exceptions arise in nearly degenerate configurations, such as shared vertices, nearly parallel edges and points that almost touch, where rounding error can outweigh the quantity being measured and flip the answer. Because every later step trusts that answer, a single wrong sign can leave a triangulation or a polygon operation in an inconsistent state.

Exact geometric predicates, developed by Jonathan Shewchuk and others and used in libraries such as CGAL, address this directly, and the packages here build on that work. Fast floating-point arithmetic does the work wherever an error bound shows its answer can be trusted, and exact arithmetic takes over where it cannot, so ordinary inputs stay fast and difficult ones stay correct. Published packages come with clear APIs, worked examples, and minimal dependencies.

• arithmetica: Exact geometric predicates for Rust. Orientation, in-circle and in-sphere tests in 2D and 3D that return the exact sign for every finite f64 input, built on Shewchuk’s adaptive-precision arithmetic and extended to cover the full floating-point range. It also provides exact line-intersection points and the expansion arithmetic underneath. No runtime dependencies. Available on crates.io.

Arithmetica is the foundation layer. Higher-level geometry built on these exact primitives is in development and will join this area as it reaches the same standard of correctness.