blob: 0c47554baf899ff65a3bc2d5a056551d42820254 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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.
|
