diff options
Diffstat (limited to '_log/2d-geometry-kernel.md')
| -rw-r--r-- | _log/2d-geometry-kernel.md | 39 |
1 files changed, 18 insertions, 21 deletions
diff --git a/_log/2d-geometry-kernel.md b/_log/2d-geometry-kernel.md index fbdf842..5275ad8 100644 --- a/_log/2d-geometry-kernel.md +++ b/_log/2d-geometry-kernel.md @@ -1,37 +1,34 @@ --- -title: 2D geometry kernel for building design +title: Geometry kernel for building design date: 2022-07-31 layout: post --- Written in 2026, backdated to 2022. -Joined real estate firm mid-migration (C# to Java). Java version lacked a -geometry kernel; project stalled. +Joined real estate firm mid-migration from C# to Java. Lacking a geometry +kernel, the project had stalled. -Geometries were small, mostly 2D—no frame budget or low-latency constraints. -Architects supplied test cases and tolerances; numerical parity with Rhino was -mandatory. +Building geometries are small—mostly 2D. No frame budgets or low-latency +constraints. Numerical parity with Rhino was mandatory. Architects and +structural engineers supplied test cases and tolerances. Implemented polygon clipping with Sutherland–Hodgman. No drama. -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. +Fortune's algorithm was a missed opportunity. Implemented the beach line using +a linear list instead of the balanced binary tree. Planned to return to this. +Never had the chance. -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. +Z and H-shaped floor plan offsets produced self-intersections that even Rhino +mishandled. Couldn't implement straight skeletons under time pressure. Wrote a +custom solver that fixed invalid loops by backtracking instead. -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. +Problem of finding the largest inscribed rectangle surprised me. No single +algorithm covered both convex and concave shapes. Brute-force grid search +yielded 12% more buildable area—but not the true optimum. -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. +Java BSP library produced results numerically incompatible with Rhino's. +Replaced BSP trees with vector-based primitives and JBLAS. -Migration resumed. No regressions in the building layouts. +Migration resumed. |