Suppose I have a set of squares. I get them in iterative way – one after another.
I would like to place the squares in some structure according to set of rules:
When a new square arrives all squares which arrived before it are already placed. The new square arrives with dependency flag to one of squares, which was treated. The dependency flag can be L or R.
If the dependency is L and a new square i depends on j it can be placed:
If the dependency is R and a new square i depends on j it can be placed: Note: In general we have to use placement options the preferable placement is 1 if it is impossible 2 or 3 (2/3 have the same priorety) 4,5 are used only if it is impossible to use one of 1,2,3.
If j is totally surrounded by another squares i is placed "after" surrounding squares based on dependency flag.
The placement goal is to generate as compact a "mesh" as possible.
For example if squares arrive in the format: new_square, dependent_on_square, dependency_flag
And we have
1, NULL, NULL
2, 1, R
3, 2, R
4, 2, L
5, 4, L
6, 5, L
7, 6, L
8, 7, L
9, 8, L
It is possible to create two arrangement 1) compact 2) not compact
Definition for compact layout(placement):
If we will pad the acquired layout with empty squares ,in such a way that we will get rectangular the number of empty squares will be minimumal in obtained layout.
Note : The rectangular obtained as a result of padding shoud be as small as possible.
I mean that if the width if layout before padding is w the generated rectangular will be by width w.(The same regarding the height) .
Demonstartion in the above examples
Could someone propose an algorithm to do such kind of placement?