My specific problem is that I have a vertically scrollable window into which I need to place rectangular <div> elements that are locked horizontally and have different widths and heights. Basically each <div> has a different start/end horizontally. The order in which the <div> elements gets placed is based on priority. The placement of each <div> needs to be as close to the top of the main window as possible without overlapping a previously placed <div>.

I have conceptualized this as an array of rows. Where the rows are stored as a number - which is a binary representation of whether a column for that row is empty 0 or filled 1. My current algorithm is determining the correct binary mask to use to AND with the row to determine if the current <div> can be placed in that row. Then using that mask to iterate through the rows (from top to bottom) to find the first set of rows (large enough to contain the height of the <div>) that are empty. If no row set is found, we create some new empty rows and place it there.

Ultimately, this process works. But it feels inefficient. Looking at the process to find the right row for instance... worst case is we do comparisons on every row... and as we add rows those comparisons only take longer.

I've thought of tracking the columns rather than the rows, but then I am still needing to do similar comparisons in order to determine which set of rows/columns are open.

I could track open spaces in each column... at least then we would be skipping the completely full rows in our checking.

Is anyone aware of algorithms in this space? I've looked to see if there is anything out there for a similar process. I have seen some rectangle packing algorithms for efficient space usage - think using as much of a sheet of metal while cutting out the required rectangles. That, in particular, is not helpful as my rectangles are locked in one direction and can't be rotated.

  • I would try a sweep line algorithm. For this, you need a data structure which stores the rows for which the occupied columns changes, together with the information which columns change (ordered by the row number). That will allow you to restrict the search to the "interesting" subset of rows, the rows where "something changes".
    – Doc Brown
    Dec 30, 2021 at 17:48
  • Great Scott, @DocBrown. This is heavy. I think that is close to my conception of tracking the empty cells in each column. Sweeping down the list of empty cells in columns until reaching a set that are all empty. I've got some reading to do. Thanks!
    – Jeffrey P
    Dec 30, 2021 at 20:41
  • Interesting line sweep algorithm examples page: topcoder.com/thrive/articles/Line%20Sweep%20Algorithms
    – Jeffrey P
    Dec 30, 2021 at 22:00


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.