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.
My memory of polygon offsets is foggy. Architects flagged two Z and H-shaped floor plans where offsets produced loops that tripped Rhino 3D. Instead of straight skeletons, rolled my own that fixed invalid loops by backtracking—may not scale, but worked for us.
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 (buildable area) was messier. Didn’t find a solution that covered both convex and concave polygons. Found a paper on convex polygons but couldn’t fill in implementation details. Fell back to a brute-force grid search: 12% gain over the existing approach, but not the true optimum.
Reconciling floating point results was the hardest part.
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.