Geometry engine post.

1 files changed, 37 insertions, 0 deletions

diff --git a/_log/2d-geometry-kernel.md b/_log/2d-geometry-kernel.md
new file mode 100644
index 0000000..0c47554
--- /dev/null
+++ b/_log/2d-geometry-kernel.md
@@ -0,0 +1,37 @@
+---
+title: Built a geometry kernel for building design
+date: 2022-07-31
+layout: post
+---
+
+Written in 2026, backdated to 2022.
+
+Joined the real estate firm mid-migration (C# to Java). The Java building
+design system lacked a geometry kernel; project had stalled.
+
+Small geometries (hundreds of points)—mostly 2D. No frame budget or low-latency
+requirements. Architects and structural engineers supplied the test cases.
+Numerical parity with Rhino 3D was mandatory.
+
+Implemented polygon clipping with Sutherland–Hodgman. No drama.
+
+Polygon offsets had always been problematic. Architects flagged two Z and
+H-shaped floor plans where offsets produced self-intersections that tripped
+Rhino 3D. Instead of straight skeletons, implemented a custom solver that fixed
+invalid loops by backtracking.
+
+Fortune's algorithm for Voronoi diagrams was a missed opportunity. Implemented
+the beach line with an array (O(N<sup>2</sup>)). Didn't pursue the balanced
+binary tree (O(N log N))—ran out of time.
+
+Finding the largest inscribed rectangle was messier; no solution covered both
+convex and concave polygons. Found a paper on the convex case but couldn't
+bridge the gap from theory to implementation. Fell back to a brute-force grid
+search: 12% gain over the existing approach, but not the true optimum.
+
+Rhino 3D's geometry model was numerically incompatible with Apache Commons'
+Binary Space Partitioning—intersections didn't match. Replaced BSP trees with
+point-based structures. JBLAS stabilized intersection results between systems.
+
+Migration resumed. No regressions in the building layouts.
+