From fb15536326a8d5b3187981b0036df65f4bb60996 Mon Sep 17 00:00:00 2001 From: Sadeep Madurange Date: Fri, 1 May 2026 20:40:08 +0800 Subject: Geometry engine post. --- _log/2d-geometry-kernel.md | 37 +++++++++++++++++++++++++++++++++++++ _log/site-search.md | 4 ++-- 2 files changed, 39 insertions(+), 2 deletions(-) create mode 100644 _log/2d-geometry-kernel.md 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(N2)). 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. + diff --git a/_log/site-search.md b/_log/site-search.md index d4d7180..7b916fe 100644 --- a/_log/site-search.md +++ b/_log/site-search.md @@ -96,8 +96,8 @@ Resource exhaustion and XSS attacks are inherent. Limited concurrent searches using lock-file semaphores, and capped the query length (64 B) and the result set (20). Mitigated XSS by HTML-escaping all output using HTML::Escape. -At my current pace of twelve articles a year, this should work for the next 833 -years. Penciled in the next release for Anno Domini 2859. +At six articles a year, this should work for the next 1600 years. Penciled in +the next release for Anno Domini 3626. Commit: