Project 1: The Robust Predicate Engine (The Foundation)

Build a library of robust orientation and incircle predicates that never fail on edge cases.

Project Overview

Attribute Value
Difficulty Level 2: Intermediate
Time Estimate Weekend
Main Language C++
Alternative Languages C, Rust, Python (numeric focus)
Knowledge Area Numerical robustness and geometry
Tools Unit-test framework, plotting tool
Main Book “Computational Geometry: Algorithms and Applications” by de Berg et al.

What you’ll build: A small library that answers geometric questions like orientation, point-in-circle, and segment intersection with reliable results.

Why it teaches computational geometry: Every higher-level algorithm depends on these predicates. If they lie, everything breaks.

Core challenges you’ll face:

  • Handling floating-point precision issues
  • Implementing exact or adaptive arithmetic strategies
  • Designing tests that expose degenerate cases

Real World Outcome

You will have a predicate library you can trust. When you feed nearly-collinear points or tiny triangles, the outputs remain stable and deterministic.

Example Output:

$ ./predicate_tests
Orientation tests: 312 passed
Incircle tests: 180 passed
Segment intersection tests: 96 passed
Degenerate cases: 48 passed

Verification steps:

  • Run random stress tests with near-degenerate input
  • Compare results against high-precision reference values

The Core Question You’re Answering

“How can I make geometric decisions that are correct even when floating-point math is unreliable?”

This question defines the entire CAD kernel. Precision is not optional.

Concepts You Must Understand First

Stop and research these before coding:

  1. Orientation test
    • What does the sign of a 2D cross product represent?
    • Book Reference: “Computational Geometry: Algorithms and Applications” Ch. 1
  2. Floating-point error
    • Why do nearly collinear points flip sign?
    • Book Reference: “Geometric Tools for Computer Graphics” by Schneider & Eberly, Ch. 2
  3. Exact arithmetic strategies
    • What is adaptive precision and why is it necessary?
    • Book Reference: “Real-Time Collision Detection” by Christer Ericson, Ch. 3

Questions to Guide Your Design

  1. Robustness strategy
    • Will you implement adaptive precision or fixed exact arithmetic?
    • How will you detect when a fast computation is unreliable?
  2. Test coverage
    • How will you generate worst-case inputs?
    • What is your definition of “correct” for degenerates?

Thinking Exercise

Orientation by Hand

Given points A(0,0), B(1,0), and C(1,1e-12), determine whether the orientation is clockwise, counterclockwise, or collinear.

Questions while working:

  • How sensitive is the result to floating-point rounding?
  • What threshold would you consider “collinear”?

The Interview Questions They’ll Ask

Prepare to answer these:

  1. “What is the orientation predicate and why is it foundational?”
  2. “Why do geometric predicates fail with floating-point?”
  3. “What is adaptive precision?”
  4. “How do you test robustness of geometric code?”
  5. “How do degeneracies affect triangulation algorithms?”

Hints in Layers

Hint 1: Starting Point Start with a standard cross-product orientation function.

Hint 2: Next Level Introduce tolerance only after understanding its failure modes.

Hint 3: Technical Details Use higher-precision calculations as a fallback when results are near zero.

Hint 4: Tools/Debugging Create randomized tests that generate nearly collinear triples.

Books That Will Help

Topic Book Chapter
Orientation tests “Computational Geometry: Algorithms and Applications” by de Berg et al. Ch. 1
Floating-point pitfalls “Geometric Tools for Computer Graphics” by Schneider & Eberly Ch. 2
Robust geometry “Real-Time Collision Detection” by Christer Ericson Ch. 3

Implementation Hints

  • Treat tolerances as last resort, not a fix-all.
  • Separate fast path and robust fallback paths.
  • Keep predicate outputs deterministic for testing.

Learning Milestones

  1. First milestone: You can implement basic orientation and incircle tests.
  2. Second milestone: You can identify and fix failure cases.
  3. Final milestone: You can explain why robustness is non-negotiable.