Correctness
Computational Geometry is notoriously difficult to get right. From 1972 to 1989, 7 out of 16 published convex hull algorithms were wrong.[1]
Why trust RGeometry? Our design provides strong guarantees and predictable behavior.
Fixed precision vs arbitrary precision
While research often assumes infinite precision, RGeometry supports both arbitrary and fixed-precision modes. We avoid precision loss through exact geometric primitives—for example, comparing distances without computing them.
All algorithms are tested with 8bit, 16bit, 32bit, and 64bit integers, plus 32bit and 64bit floating-point.
Property testing
RGeometry uses comprehensive property testing to ensure correctness. We generate diverse test data including convex polygons, monotone polygons, star-shaped polygons, and two-opt polygons across multiple precision levels.
All documented API properties are verified through automated testing. Additionally, efficient algorithms are validated against slower but provably correct reference implementations.
Simulation of Simplicity
RGeometry has first-class support for Simulation of Simplicity (SoS)[2], which eliminates geometric edge cases by perturbing degenerate configurations. This makes algorithms easier to verify and implement correctly.
Floating-point
Fixed-precision floating-point arithmetic is notoriously difficult to get right but widely used in practice. The value space is enormous, making edge cases nearly impossible to discover through random sampling alone. RGeometry addresses this by testing algorithms in 8-bit integer space, where the smaller value space makes edge cases much easier to trigger and verify.