All geek questions in one place

Algorithm for determining (x, y) coordinates for rectangles, so that the area of ​​the surrounding rectangle is minimal?

I hope my title makes sense, but here is what I'm trying to do:

I have rectangles n, each with a width of W n and a height of H n , which I need to arrange so on the two-dimensional (x, y) plane of the rectangle into which they all fit into the smallest area. I should also be able to establish that (x, y) matches what the rectangle is.

I would prefer something in psuedo code, but can work with many languages.

Thanks for the help.

+3
source share
4 answers

, , , (, ). googling " () "... , .

+2

NP- . . , . .

+1

. , , ( ). Drools Planner (open source java) . (. ) Drools Planner ( ). , , drools-planner - .

, , . .

+1

Your problem is known as the problem with two-dimensional packaging. Even the 1D problem is NP-hard. See here for a good article on some approaches along with sample C # code.

Also see the following questions:

0
source

Source: https://habr.com/ru/post/1782124/

More articles:


All Articles