diff options
Diffstat (limited to '_log/2d-geometry-kernel.md')
| -rw-r--r-- | _log/2d-geometry-kernel.md | 35 |
1 files changed, 17 insertions, 18 deletions
diff --git a/_log/2d-geometry-kernel.md b/_log/2d-geometry-kernel.md index 60d76af..385df18 100644 --- a/_log/2d-geometry-kernel.md +++ b/_log/2d-geometry-kernel.md @@ -6,33 +6,32 @@ 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. +Joined real estate firm mid-migration (C# to Java). Java version lacked a +geometry kernel; project 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 was mandatory. +Geometries were small, mostly 2D—no frame budget or low-latency constraints. +Architects supplied test cases and tolerances; numerical parity with Rhino 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. 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. +Polygon offsets had always been problematic. Two Z and H-shaped floor plans +produced self-intersections that tripped Rhino. Straight skeletons had too many +edge cases we didn't need—hard to get right under time pressure. Implemented a +custom solver that fixed invalid loops by backtracking. + +Finding the largest inscribed rectangle was messy. No single algorithm covered +both convex and concave shapes. Found a paper on the convex case, but couldn't +translate the math to code. Fell back to a brute-force grid search: 12% gain, +but not the true optimum. -Rhino uses points, vectors, planes, and linear algebra (via BLAS). Java system -used Binary Space Partitioning. The two were numerically incompatible. Replaced -BSP trees with vector-based structures. JBLAS aligned the linear algebra with -Rhino's. +Rhino's BLAS-based linear algebra and Java's Binary Space Partitioning were +numerically incompatible. Replaced BSP trees with vector-based structures. +JBLAS reconciled most floating-point issues. Migration resumed. No regressions in the building layouts. |