Program Overview
This program is made for packing two dimensional rectangular elements at orthogonal table in sequence along X axis of table, with horizontal orientation exclusively. User interface is simple. At the top left are two fields for entering Table dimension and Pack button for starting packing process, below is table for entering Elements dimensions, and on the right is graphical representation of packed elements at table. For it to work it is necessary to have installed .NET framework 4.0.

Download links
Full solution with executable version of program and open source code with detailed comments download at links.
Problem Introduction
Solving problem of packing two dimensional rectangular elements at orthogonal table involves packing a certain number of elements at one table with fixed dimensions so that the table surface is maximally filled with elements and the time needed for that operation is as short as possible.
Considering the time necessary for solving this problem, it is classified as NP hard by mathematical nomenclature. Even though it is the 21st century and with all advances in math theory, there is no complete math solution for this problem. Here is shown development and implementation of one out of many possible algorithms as solutions for this problem, developed by using Heuristic methods and does not
represent final solution of this problem based on a comprehensive mathematical analysis.
Problem Solving Theory
Theory References
Observing process of packing elements
For purpose of observation there is a need for:
ONE TABLE { Tn(L, W), n=1 }

AND FINIT SEQUENCE OF ELEMENTS { En(l, w), nЄZ and n>0}

TABLE and ELEMENTS are characterized by it's LENGTH and WIDTH.
These two characteristics with it's values are called DIMENSIONS.
Therm 'LENGTH' do not imply greater value in the relation to therm 'WIDTH'.
Allowed range for value of dimensions:
T(L, W), {LЄR and L>0} , {WЄR and W>0}
E(l, w), {lЄR and l>0 and l<=L} , {wЄR and w>0 and w<=W}
LENGTH of element can't be greater than LENGTH of TABLE.
WIDTH of element can't be greater than WIDTH of TABLE.
Because of precision, whole packing process shall be observed within the XY orthogonal coordinate system.
When placed inside coordinate sistem, TABLE and ELEMENTS obtains third characteristic ORIENTATION – POSITION OF SIDES OF TABLE OR ELEMENT, RELATIVE TO X OR Y AXIS. Considering numerus positions that table or elements can take, there are two distinctive for which ORIENTATION gets defined value : HORIZONTAL and VERTICAL.
HORIZONTAL orientation is case when longer side of table or element is parallel to X axis.
VERTICAL orientation is case when longer edge of table or element is parallel to Y axis.
Graphical presentation of five cases of TABLE with packed ELEMENTS inside XY orthogonal coordinate system.

After these five attempts of packing elements there are several important conclusions:
- Table can be positioned anywhere inside coordinate system horizontally or vertically.
- Orientation and layout of the elements before packing are irrelevant.
- Elements can be rotated and packed horizontally or vertically.
- Packing elements at the table can be random or in sequence along the X or Y axis at free surface of table, called POSITION for packing.
- Therm 'POSITION', free surface of the table, denotes part of the table that is not already occupied with some other packed element and where can be placed any of remaining elements. There can not be overlapping of elements at surface of the table.
- Shape of the POSITON does not necessarily have to be rectangular as elements.
- Selection of the next element that is going to be packed, depends on the possibility of element to be fitted inside observed position.
- When there is more than one element that can be placed at selected position the choice is random.
- Packing elements should be compact, side by side, matching dimensions of elements and dimensions of positions so that utilization of the surface of table is maximum.
- Process of packing is finished when:
- There is no more elements to be packed, all elements are packed on the table.
- Table is completely filled, sum of areas of packed elements is equal to the area of the table.
- There is no more positions on the table for packing elements, at remaining free surface of the table is not possible to fit any of remaining elements.
Developing algorithm
Algorithm that should be developed upon above observations is too complex, so for further study of this problem it is necessary to introduce some restriction.
- Before packing process starts, table shall be placed at the origin of coordinate system with horizontal orientation.
- Before packing process starts, all elements must be horizontally oriented and sorted in descending order by size of it's area then by length then by width.
- Elements can not rotate during packing process.
- Elements must be packed in sequence along X axis of table, with horizontal orientation exclusively.
- Coordinates of the first position are always coordinates of the origin, since that at the beginning of packing process table is empty and it's whole surface is free.
- Conditions for finding new free positions according to demand for a way of packing elements.
- Position must be rectangular shaped, with determined coordinates of lower left corner, and dimension that corresponds at least to one of the remaining elements. At least one of the remaining elements should be able to fit in position.
- Coordinates of new position can only be the same as coordinates of lover right or upper left corner of previously packed element.
- If the position have different shape than rectangular it is necessary to adjust it. It is done by making new positions out of old one, which must fulfill previously two conditions. If newly created positions do not fulfill conditions they are discarded.
- Order of positions is determined by sorting values of coordinates of lover left corner of position, in ascending order, first by Y than by X axis. This way elements are packed in the way as specified.
- When there is no more free positions, packing process ends.
- Conditions for selecting next element for packing
- Selection of next element that is going to be packed depends of the next characteristic of packed element - FITTING FACTOR and it's calculated numeral value for selected position, which defines possibility of element to be fitted inside observed position. The greater value of this characteristic means that element better fits to the observed position. BEST FIT therm describes FITTING FACTOR value of element with equal length and width as observed position, a 100% filled position.
- Next element that is going to be packed, is selected upon calculated value for FITTING FACTOR for selected position.
- Initial fitting factor of all elements for the observed position is zero.
- If element with it's dimensions can fit inside position, fitting factor is increased by one.
- If element have equal length as position, fitting factor is increased by one, favoring element that fits exactly across the length of position.
- If element have equal width as position, fitting factor is increased by one, favoring element that fits exactly across the width of position.
- When fitting factor is calculated for all elements, they are sorted in descending sort order first by fitting factor value, than by value of area, then by value of length, then by value of width.
- First element in sorted sequence is selected and if it's fitting factor is greater than zero, it is placed at selected position so that the bottom left corner of the element matches the lower left corner of position.
- If value of fitting factor of first element in sorted sequence is equal zero, selected position is discarded due to lack of fitting element.
- When there is no more elements, packing process ends.
- Selection of next element that is going to be packed depends of the next characteristic of packed element - FITTING FACTOR and it's calculated numeral value for selected position, which defines possibility of element to be fitted inside observed position. The greater value of this characteristic means that element better fits to the observed position. BEST FIT therm describes FITTING FACTOR value of element with equal length and width as observed position, a 100% filled position.
- This algorithm do not need check if table is completely filled for stopping process.
Graphical presentation of packing process step by step, according to above restriction.
- Table is placed at the origin of coordinate system and elements are sorted in descending order by size of its area.

- Selecting first position and packing one element in it.
- Since that at the beginning of packing process table is empty, first free position, Position 1, is whole area of table with it's lower left corner placed at origin.
- Coordinates of Position 1 are coordinates of the origin.
- Calculated value for fitting factor for all four elements is one, so the one with the greater size of area is selected to be packed, and it is element E1.
- Selected element E1 is placed at coordinates of selected Position 1.
- Finding new positions after placing element.
- Free surface on table does not meet the requirement for new position because of it's shape and it needs to be adjusted. Accordingly to request for packing direction, along X axis of table, with horizontal orientation exclusively, Position 1 is splited into two rectangular shapes with horizontal line from the upper right corner of the last placed element to the right edge of Position 1.
- Now there are two new positions, Position 1 and Position 2, with it's coordinates that are aligned accordingly to condition for sorting positions. Previous Position 1 is erased from the list of positions.
- Coordinates of new Position 1 are coordinates of lower right corner of E1.
- Coordinates of new Position 2 are coordinates of upper left corner of E1.

- Free surface on table does not meet the requirement for new position because of it's shape and it needs to be adjusted. Accordingly to request for packing direction, along X axis of table, with horizontal orientation exclusively, Position 1 is splited into two rectangular shapes with horizontal line from the upper right corner of the last placed element to the right edge of Position 1.
- Packing new element.
- Selected position is Position 1.
- Calculated value for fitting factor for all three elements is one, so the one with the greater size of area is selected to be packed, and it is element E4.
- Selected element E4 is placed at coordinates of selected Position 1.

- Selected position is Position 1.
- Finding new positions
- Situation on the table is similar to situation after placing first element, so the steps are also similar. Divide Position 1 into two rectangular shapes with horizontal line from the upper right corner of the last placed element to the right edge of Position 1.
- There are now two new positions and one old, with it's coordinates that are aligned accordingly to condition for sorting positions.
- Position 1 with coordinates at lower right corner of E4.
- Position 2 with coordinates at upper left corner of E4.
- Position 3, former position 2, with coordinates at upper left corner of E1.

- Situation on the table is similar to situation after placing first element, so the steps are also similar. Divide Position 1 into two rectangular shapes with horizontal line from the upper right corner of the last placed element to the right edge of Position 1.
- INADEQUATE POSITION CASE !
- Position 2 is inadequate because of it's width and shall be discarded. There is no element left that can fit across width of Position 2.
- After erasing position 2, Position 1 shall be adjusted as shown below.
- Colored in white is part of discarded Position 2, and unused space of table.
- Position 3 is now Position 2.

- Position 2 is inadequate because of it's width and shall be discarded. There is no element left that can fit across width of Position 2.
- Process is continued by packing the last two elements and finding new positions.


- Process has ended because there is no more free elements. All elements are packed.
Finally packed elements on table

After analysis here is written universal algorithm




Fron GeorgePosted Nov 13, 2018, 4:38 AM
Hey man, what if you want to use numbers that are not integer. Like 1.2, or 5.7
Kapi ShivharePosted Jun 26, 2016, 12:26 PM
Nice
Gowtham RajamanickamPosted May 25, 2016, 1:16 AM
Good one..
Munesh SharmaPosted May 25, 2016, 12:28 AM
good one
Sonu ChaudharyPosted May 24, 2016, 12:47 PM
Nice Sharing..
Debasis SahaPosted May 24, 2016, 5:21 AM
Good one..
Gowtham RajamanickamPosted May 24, 2016, 1:17 AM
nice article
Munesh SharmaPosted May 22, 2016, 10:57 AM
nice
Kuppurasu NagarajPosted May 22, 2016, 5:19 AM
Nice Sharing..
Vignesh ManiPosted May 21, 2016, 9:19 AM
nice
Debasis SahaPosted May 20, 2016, 10:48 AM
Nice One..
Thiruppathi RPosted May 20, 2016, 4:51 AM
Good One...