I’m working on a tool that will allow an end user to reposition rectangles on a design surface. It’s ultimate use is for the layout of industrial equipment, but it shares a lot of principles with Tetris or those puzzles where you slide squares. Here’s an image that shows a layout and how it might change as a user interacts with it.
In A, the user decides to move the blue rectangle up. In B, the blue rectangle has moved up and the red rectangle has dropped beneath it. In C, the user drags the red rectangle down. In D it is still moving down, but the purple rectangle has popped up above it (since the red rectangle intruded on its space). In E, the red rectangle has stopped moving and the green rectangle has also popped up above red rectangle.
The way I think about it is that there is always gravity pulling the rectangles down. As a rectangle is moved up and down, it may change its position in the stack, but the rectangles above and below will always be pulled down until they hit something that prevents them from moving any further.
There are a couple constraints:
The rectangles are always one or two units wide. I added some spacing to make the diagram easier to read, but the width of the blue, green, and purple rectangles will always be 1 and the red and gray rectangle will be 2.
The height of the rectangles vary and are not measured in whole units. A rectangle might be 1.4356 units high and another might be 0.78 units high.
The design is for a layout surface that is two units wide. However, I’m trying to come up with a solution that can be generalized for 1 to n units wide. Not a hard requirement, but a nice to have.
Rectangles that are more narrow than the layout area can be dragged into other columns. For example, the green rectangle could be dragged above the purple rectangle.
Here are my questions:
Is anyone aware of any algorithms or pieces of software that implement something similar? It’s a bit similar to the knapsack or stock cutting problem, but it adds the element of it being an editable layout. Any prior art on this sort of tool would be useful.
What data structure would you use to represent the rectangles positioned on the layout surface? The layout will be fed into a backend process, so a pure visual representation isn’t enough. If there is no better way, then I guess some sort of spatial representation could be used, but I’m thinking something more abstract (a graph, maybe?) might make more sense. I guess the representation in the layout tool could be different than what is fed into the backend, provided there was some easy way to convert between the two representations.
Any pointers on approaching this soft of algorithm functionally?
Thanks in advance!