I’m trying to implement a very crude form of the css grid layout. It’s layout algorithm is as documented.
“sparse” packing (default behavior)
Set the column-start line of its placement to the earliest (smallest positive index) line index that ensures this item’s grid area will not overlap any occupied grid cells and that is past any grid items previously placed in this row by this step.
Is there an efficient data structure to calculate the next available position of a grid rectangle given a list of existing grid rectangles?
I’ve thought about using a 2D Interval Tree but can’t find any good references on extending from 1D to 2D.
I have also seen an r-tree which answers whether a rectangle will intersect with a given list of rectangles, but don’t know whether that answers “find the next available space for this rectangle” efficiently.
If someone finds the implementation for css-grid in firefox or chrome, I would also take that as an answer.
Similar question: efficiently calculate locations for rectangles in a unit grid
A first idea is that you’d want to maintain something like a quadtree or k-d tree of free space.