• Advertisement
Sign in to follow this  

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

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement

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

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement