What’s in a room?
To a human being, this tends to be a simple question. We can look at a table in front of us and quickly determine whether it is enclosed in a surrounding set of walls, but our ability to do this and record the result is limited to a few iterations per second. When Social Tables set out to build a layout automation API, we knew we would need to answer that question programmatically at a significantly higher frequency. Diagrams where tables are half-in, half-out of a wall are generally a hard sell to event planners who would rather not break out the power tools. To avoid this kind of clipping, we needed to be able to ascertain whether a given table is fully enclosed within a given room a few hundred thousand times a second across a wide variety of venues.
Fortunately, collision and enclosure checking is mostly a solved problem. For almost half a century, video game and simulation engines have been resolving collisions between things very very quickly. Such systems generally use a two-phase system; a broad phase provides loosely accurate, cheap to compute collision candidates and a narrow phase generates the pixel or polygon perfect collisions. Broad-phase systems are typically implemented using spatial partitioning trees or hashes, whereas narrow-phase systems will use either fine-grained bounding boxes, pixel masks, or convex polygon intersection. Our data is vector-based and relatively low in detail by modern standards, so we chose to use a simple CPU-based convex polygon checking approach. In order to do so, we needed a way to transform room data from thousands of venues into the right kind of polygons.
Floor plans can be complex beasts. Although the word “room” may inspire imagery of an entity with four flat walls (and perhaps a door), in the wild they can range from L-shaped conference rooms to massive, circular stadium atriums. This puts the generalized concept of a room firmly into the domain of complex polygons — that is, collections of edge-connected vertices that are not guaranteed to be fully contiguous, and generally not convex. To map our geometry onto the industry-standard convex solution, we employed a simple but effective subtract-and-divide approach.
Let’s say we have a concave room R. What we want is to be able to say for certain that a given convex polygon P is fully enclosed in R. We can do this by taking the convex hull of R, which we will refer to as C(R), and the difference between R and C(R), which will be a set of inward projections. If these projections are decomposed into convex polygons, we end up with a group of convex collision-checkable entities which can be checked individually to ascertain whether P is contained in R. In fewer words:
R = C(R) - (C(R) - R), where R ⊂ C(R) ∴
P ⊂ R ⟺ P ⊂ C(R) ∧ P ⊄ (C(R) - R)
Ignoring cases where polygons have inner rings, this makes our problem much easier — we simply have to use boolean operations to compute the subtraction, and then decompose the resulting inner projections! Even more excitingly, the tools to do this are already available as open-source NPM packages!
- monotone-convex-hull-2d provides C(R) quite nicely.
- polybooljs quickly handles boolean operations over complex 2D polygons.
- poly-decomp.js does a great job at deconstructing simple concave polygons into their convex components.
- earcut (written by MapBox, also based in DC) triangulates anything that poly-decomp can’t handle, making a great fallback for when polybool spits something out that self-intersects.
- sat-js is a solid separating axis theorem implementation, and provides the convex intersection/containment calculations wonderfully.
Let’s see an implementation in action:
Of course, decomposing the simple polygons was only the first step. We then implemented an enclosed room tree to handle interior rooms (polygons with holes), and exposed the decomposed polygons for each level at the broad phase, limiting the number of narrow-phase polygon-polygon checks significantly. Simple-quadtree made doing this fairly trivial, providing a simple interface for fetching candidate geometry based on the bounding box of each intersection candidate. Each deconstruction is then cached as a single redis line (most rooms are on the order of a few kilobytes) to avoid having to re-do work on subsequent requests.
With these off-the-shelf modules and a creative pre-compute phase, we were able to crank out an enclosure-resolution system fast enough to run less optimal table placement algorithms within an acceptable HTTP request window on standard (non-GPU-enabled) compute hardware.
If you’re contemplating building a game or similar engine that needs to constrain entities to user-generated environment geometry, I highly recommend this technique.
