GeoKernel-Lite

GeoKernel-Lite is a compact C++17 2D computational geometry kernel built around one main idea: robust predicates, explicit degenerate-input handling, and visual debugging are more valuable here than a long list of half-finished algorithms.

It is a portfolio and interview project, not a CGAL, GEOS, OpenCascade, CAD, or GIS replacement. The codebase is intentionally small enough to inspect: a header-only C++ core, a JSON CLI contract, Python adapter tests, and a Streamlit visualizer that renders algorithm traces.

What is GeoKernel-Lite?

GeoKernel-Lite demonstrates how contest-style computational geometry can be shaped into an engineering project:

• Predicate policy is explicit: EPS, filtered exact, and exact modes are visible in the API.
• Degenerate cases are first-class regression tests: duplicate points, near-collinear predicates, endpoint touches, zero-length segments, collinear overlaps, invalid rings.
• Algorithms can emit JSON trace steps so failures can be inspected in the CLI or the Streamlit UI.
• Experimental features are labeled as scope-limited instead of being presented as production geometry tooling.

Why robustness matters

An EPS predicate can collapse a nonzero determinant to zero. In geometry code, that is not just a numerical detail: it can change topology. A hull may drop the wrong point, a segment pair may become a false overlap, a triangulation ear may be rejected, or a Delaunay cavity may be rebuilt incorrectly.

GeoKernel-Lite separates two ideas:

• Exact predicates: orient2d and incircle sign decisions can use filtered exact or exact classification for finite double inputs.
• Floating constructions: intersection points, distances, areas, projections, and rectangle coordinates are still constructed as double values.

That boundary is deliberate and documented. The project shows better topological decisions without claiming to be an exact-construction kernel.

Key features

• Header-only C++17 core under core/include/geokernel.
• Robust predicate layer for EPS, filtered exact, and exact orient2d / incircle.
• Segment intersection search with endpoint events, intersection events, active-order updates, and targeted handling for zero-length, vertical, same-point, endpoint-touch, and collinear-overlap cases.
• Segment arrangement builder that splits intersections and overlaps into nodes and atomic edges for debugging and polygon work.
• JSON CLI envelope with stable status, summary, result, trace, and warnings fields.
• Streamlit + Plotly visualizer for inspecting input geometry, output geometry, and trace steps.
• C++ tests, Python contract tests, deterministic case catalogs, clang-format check, and a Windows / Ubuntu / macOS GitHub Actions matrix.

Visual debugging screenshots

Convex Hull	Segment Intersection	Polygon Clipping

Half-Plane Intersection	Closest Pair	Triangulation

Algorithm status table

Algorithm	Status	Current implementation	Notes
Predicate comparison	stable	EPS / filtered exact / exact orient2d and incircle	finite double inputs
Convex hull	stable	Andrew monotone chain	O(n log n)
Convex diameter	stable	rotating calipers on cyclic hull	O(h) after hull
Minimum-area bounding rectangle	stable but simple	edge-direction scan	O(h^2), not optimized calipers
Segment intersection search	stable contract	event sweep with intersection events and targeted degenerate scans	may degrade to quadratic on dense/degenerate input
Segment arrangement	scope-limited	correctness-first pairwise split builder	useful for traces and polygon boolean MVP
Closest pair	stable	divide and conquer with duplicate detection	distances are double
Polygon clipping	stable for convex clipper	Sutherland-Hodgman	not general boolean overlay
Ear clipping triangulation	stable for simple polygons	validated ear clipping	simple polygon input
Half-plane intersection	experimental / scope	iterative clipping against finite bounding box	visualization-oriented
Polygon boolean	experimental / scope	simple-polygon intersection MVP	no union/difference/xor/holes/general overlay
Delaunay	experimental / scope	Bowyer-Watson prototype with validation	not production CDT

Experimental / Scope

The following are intentionally not described as production-ready:

• polygon_boolean: currently an intersection MVP for one simple subject polygon and one simple clip polygon without holes.
• delaunay: useful for predicate and validation discussion, but still a prototype.
• half_plane_intersection: implemented as bounded-box clipping for stable visualization.
• experimental_bentley_ottmann: retained as a stricter experimental mode; the default contract_safe mode is now the practical event-sweep path.

Quick start

Install Python dependencies:

python -m pip install -r requirements.txt

Windows with Ninja:

cmake -S . -B build -G Ninja -DCMAKE_BUILD_TYPE=Release
cmake --build build
ctest --test-dir build --output-on-failure
python -m pytest

Linux/macOS:

cmake -S . -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build
ctest --test-dir build --output-on-failure
python -m pytest

Useful CMake options:

• GEOKERNEL_BUILD_TESTS=ON
• GEOKERNEL_BUILD_BENCHMARKS=ON
• GEOKERNEL_ENABLE_SANITIZERS=ON
• GEOKERNEL_ENABLE_WARNINGS=ON

Launch the visualizer:

streamlit run visualizer/app.py

CLI JSON contract

Run the CLI:

.\build\geokernel_demo.exe --algorithm segment_intersection --input examples\segment_intersection.json --output out.json --trace --pretty

Successful responses use this envelope:

{
  "status": "ok",
  "summary": {},
  "result": {},
  "trace": [],
  "warnings": []
}

Example segment intersection input:

{
  "input": {
    "predicate_mode": "filtered_exact",
    "mode": "contract_safe",
    "segments": [
      [[0, 0], [4, 4]],
      [[0, 4], [4, 0]]
    ]
  }
}

Supported algorithm names:

• predicate_compare
• convex_hull
• rotating_calipers
• segment_intersection
• segment_arrangement
• half_plane_intersection
• polygon_clipping
• polygon_boolean
• closest_pair
• triangulation
• delaunay

Project architecture

GeoKernel-Lite/
|-- core/                  # Header-only C++ geometry kernel
|-- apps/                  # geokernel_demo JSON CLI
|-- python/                # Python runner, case loader, visualization adapter
|-- visualizer/            # Streamlit + Plotly visual debugger
|-- tests/                 # Split C++ tests, Python tests, JSON boundary cases
|-- docs/                  # Architecture, algorithms, traces, limitations
|-- examples/              # CLI-ready JSON examples
|-- benchmarks/            # Deterministic smoke benchmarks
|-- assets/                # README screenshots
`-- CMakeLists.txt

The Python and Streamlit layers call the compiled CLI instead of binding directly to C++. That keeps the core header-only and avoids ABI complexity while still exercising the real kernel in demos and tests.

Known limitations

• Exact predicate mode does not make constructed coordinates exact.
• Segment intersection is now event-driven, but it uses vector-backed active/event containers plus targeted scans for degenerates. It is traceable and tested, not a production Bentley-Ottmann overlay engine.
• Segment arrangement is correctness-first and pairwise.
• Polygon boolean only implements a scoped simple-polygon intersection path.
• Delaunay and half-plane intersection remain experimental/scope-limited.
• Benchmarks are smoke measurements, not performance claims.

See docs/known_limitations.md for the full list.

Interview talking points

• Robustness: EPS can change topology; this project compares EPS, filtered exact, and exact predicate decisions on the same inputs.
• Engineering shape: the C++ core is header-only, but the project has a CLI contract, Python tests, trace JSON, visual debugging, CI, and clang-format.
• Segment intersection: the default path now uses intersection events and active-order updates, with explicit handling for common degenerates and tests against a brute-force oracle.
• Honesty: polygon boolean, Delaunay, and half-plane intersection are documented as experimental or scope-limited instead of oversold.

For a prepared explanation, see docs/interview_guide.md.