Arrange 2D areas on a given surface in the most effective way

This topic is 788 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

Hi,

i am wondering how i could arrange 2D areas with given width and height in the most effective way (no overlapping) on a surface (also with a given width and height)? I have literally no clue where and how i should start. I visualized my intentions with a small image.

Edited by IsItSharp

Share on other sites

Thanks a lot for the hint. I googled a bit and came up with this code:

def arrange():
global index
if(index == len(rList)):
return 0
rect = rList[index]
for i in range(0,len(freeNodesList)):
node = freeNodesList[i]
if(node.width >= rect.width and node.height >= rect.height): #rectangle fits inside the node
freeNodesList.pop(i) #remove current node because it's going to be filled
rect.sX = node.sX
rect.sY = node.sY

node.rectangle = rect
node.width = rect.width
node.height = rect.height

child1 = Node(wW-(node.sX+node.width),node.height,node.sX+node.width,node.sY)
freeNodesList.append(child1)
if(wH-(node.sY+node.height) > 0): #there is still space left to the top
child2 = Node(wW,wH-(node.sY+node.height),0,node.sY+node.height)
freeNodesList.append(child2)
index += 1
break;
else: #current node doesn't fit
continue


But it is not working as expected. The problem is, that i generate two new nodes after every rectangle and that those nodes don't consider the already placed rectangles. I made a short gif which should show that problem:

So basically i have to check for every node if there is already a rectangle which shrinks the originally intended space. The next problem would be to combine two free nodes if there is a rectangle which can only be placed if those two nodes are combined.

I would really appreciate it if someone could explain to me how i can solve those problems.

Best regards

1. 1
2. 2
3. 3
Rutin
12
4. 4
5. 5

• 26
• 10
• 9
• 9
• 11
• Forum Statistics

• Total Topics
633695
• Total Posts
3013382
×