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:

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.

Graphical presentation of packing process step by step, according to above restriction.

Finally packed elements on table



After analysis here is written universal algorithm

Program code

Implementation of algorithm shown above in programming language C# 4.0, .Net framework 4.0 as independent class with it's public method that requires three arguments and returns one:

public DataGridView Pack_Elements(int Table_length, int Table_width, DataGridView Elements)

DataGridView with it's values that is going to be passed as argument to method, has to be the same structure as DataGridView ELEMENT_LIST declared inside class.

Values that are going to be passed to method, must be arranged and sorted accordingly to packing process demands,
length of table and elements must be greater than width, so that elements are packed with horizontal orientation.

If there is need for different orientation values should be arranged accordingly.

After finishing packing process, method returns DataGridView TABLE_LIST as argument to caller method, that contains coordinates of positions and dimensions of packed elements, that can be used for graphical presentation of packed elements at orthogonal table. Program code below is just an example made for learning. For a more detailed analysis it is better to download full project with open source code.

Code
  1. using System;
  2. using System.ComponentModel;
  3. using System.Windows.Forms;
  4. namespace Packing_two_dimensional_rectangular_elements_at_orthogonal_table
  5. {
  6. public class Pack_Elements_Along_X_Horizontally
  7. {
  8. //
  9. // Tables
  10. //
  11. DataGridView ELEMENT_LIST;
  12. DataGridView POSITION_LIST;
  13. DataGridView TABLE_LIST;
  14. //
  15. // Variables
  16. //
  17. int Tl, Tw; // table length and width
  18. int n, k, p, i; // counters
  19. int x, l, w, a, f; // element index, length, width, area and fitting factor
  20. int Lmin, Wmin; // smalest element length and width
  21. int X11, Y11, L11, W11, A11; // new position I coordinates, length, width and area
  22. int X12, Y12, L12, W12, A12; // new position II coordinates, length, width and area
  23. int p_X; // old position X
  24. int p_Y; // old position Y
  25. int Pl; // old position length
  26. int Pw; // old position width
  27. bool P_ok; // new position 'is adequate' state flag
  28. const string format = "0000000000"; // number format
  29. //
  30. //
  31. //
  32. void Initialize_Tables()
  33. {
  34. //
  35. // Create table ELEMENT_LIST
  36. //
  37. ELEMENT_LIST = new DataGridView();
  38. //
  39. // Add columns
  40. //
  41. // DataGridView.Columns.Add("Column Name", "Column Header Text");
  42. //
  43. ELEMENT_LIST.Columns.Add("E_Index", "Element index");
  44. ELEMENT_LIST.Columns.Add("E_Length", "Element length");
  45. ELEMENT_LIST.Columns.Add("E_Width", "Element width");
  46. ELEMENT_LIST.Columns.Add("E_Area", "Element area");
  47. ELEMENT_LIST.Columns.Add("E_Fitting", "Element fiting faktor");
  48. //
  49. // Add SortCompare event handler
  50. //
  51. ELEMENT_LIST.SortCompare +=
  52. new System.Windows.Forms.DataGridViewSortCompareEventHandler(E_SortCompare);
  53. //
  54. //
  55. //
  56. //
  57. // Create table POSITION LIST
  58. //
  59. POSITION_LIST = new DataGridView();
  60. //
  61. // Add columns
  62. //
  63. // DataGridView.Columns.Add("Column Name", "Column Header Text");
  64. //
  65. POSITION_LIST.Columns.Add("P_X", "Position X");
  66. POSITION_LIST.Columns.Add("P_Y", "Position Y");
  67. POSITION_LIST.Columns.Add("P_Length", "Position length");
  68. POSITION_LIST.Columns.Add("P_Width", "Position width");
  69. //
  70. // Add SortCompare event handler
  71. //
  72. POSITION_LIST.SortCompare +=
  73. new System.Windows.Forms.DataGridViewSortCompareEventHandler(P_SortCompare);
  74. //
  75. //
  76. //
  77. //
  78. // Create table TABLE LIST
  79. //
  80. TABLE_LIST = new DataGridView();
  81. //
  82. // Add columns
  83. //
  84. // DataGridView.Columns.Add("Column Name", "Column Header Text");
  85. //
  86. TABLE_LIST.Columns.Add("E_I", "Element index");
  87. TABLE_LIST.Columns.Add("E_X", "Element X");
  88. TABLE_LIST.Columns.Add("E_Y", "Element Y");
  89. TABLE_LIST.Columns.Add("E_Length", "Element length");
  90. TABLE_LIST.Columns.Add("E_Width", "Element width");
  91. //
  92. //
  93. //
  94. }
  95. void Initialize_Variables()
  96. {
  97. Tl = 0;
  98. Tw = 0;
  99. n = 0;
  100. k = 0;
  101. p = 0;
  102. i = 0;
  103. x = 0;
  104. l = 0;
  105. w = 0;
  106. a = 0;
  107. f = 0;
  108. Lmin = 0;
  109. Wmin = 0;
  110. X11 = 0;
  111. Y11 = 0;
  112. L11 = 0;
  113. W11 = 0;
  114. A11 = 0;
  115. X12 = 0;
  116. Y12 = 0;
  117. L12 = 0;
  118. W12 = 0;
  119. A12 = 0;
  120. p_X = 0;
  121. p_Y = 0;
  122. Pl = 0;
  123. Pw = 0;
  124. P_ok = false;
  125. }
  126. void E_SortCompare(object sender, DataGridViewSortCompareEventArgs e)
  127. {
  128. //
  129. // SortCompare event handler
  130. //
  131. //
  132. // Sort table by selected column then by forth then by second
  133. // then by third then by first column in the selected Sort Direction
  134. //
  135. // Compare values inside cells in selected column
  136. e.SortResult = System.String.CompareOrdinal(
  137. e.CellValue1.ToString(), e.CellValue2.ToString());
  138. // If values are equal
  139. // Compare values inside cells in forth column
  140. if (e.SortResult == 0)
  141. {
  142. e.SortResult = System.String.CompareOrdinal(
  143. ELEMENT_LIST.Rows[e.RowIndex1].Cells[3].Value.ToString(),
  144. ELEMENT_LIST.Rows[e.RowIndex2].Cells[3].Value.ToString());
  145. // If values are equal
  146. // Compare values inside cells in second column
  147. if (e.SortResult == 0)
  148. {
  149. e.SortResult = System.String.CompareOrdinal(
  150. ELEMENT_LIST.Rows[e.RowIndex1].Cells[1].Value.ToString(),
  151. ELEMENT_LIST.Rows[e.RowIndex2].Cells[1].Value.ToString());
  152. // If values are equal
  153. // Compare values inside cells in third column
  154. if (e.SortResult == 0)
  155. {
  156. e.SortResult = System.String.CompareOrdinal(
  157. ELEMENT_LIST.Rows[e.RowIndex1].Cells[2].Value.ToString(),
  158. ELEMENT_LIST.Rows[e.RowIndex2].Cells[2].Value.ToString());
  159. // If values are equal
  160. // Compare values inside cells in first column
  161. // in oposite sort direction than selected
  162. if (e.SortResult == 0)
  163. {
  164. e.SortResult = System.String.CompareOrdinal(
  165. ELEMENT_LIST.Rows[e.RowIndex2].Cells[0].Value.ToString(),
  166. ELEMENT_LIST.Rows[e.RowIndex1].Cells[0].Value.ToString());
  167. }
  168. }
  169. }
  170. }
  171. e.Handled = true;
  172. }
  173. void P_SortCompare(object sender, DataGridViewSortCompareEventArgs e)
  174. {
  175. //
  176. // SortCompare event handler
  177. //
  178. // Sort table by selected column then by first column
  179. // in the selected Sort Direction
  180. //
  181. // Compare values inside cells in selected column
  182. e.SortResult = System.String.CompareOrdinal(
  183. e.CellValue1.ToString(), e.CellValue2.ToString());
  184. // If values are equal
  185. // Compare values inside cells in first column
  186. if (e.SortResult == 0)
  187. {
  188. e.SortResult = System.String.CompareOrdinal(
  189. POSITION_LIST.Rows[e.RowIndex1].Cells[0].Value.ToString(),
  190. POSITION_LIST.Rows[e.RowIndex2].Cells[0].Value.ToString());
  191. }
  192. e.Handled = true;
  193. }
  194. public DataGridView Pack_Elements(int Table_length, int Table_width, DataGridView Elements)
  195. {
  196. //
  197. // Packing elements in sequence along X axis of table,
  198. // with horizontal orientation exclusively.
  199. //
  200. // Algorithm has optimisation for adjusting area
  201. // of positions along X axes
  202. //
  203. //
  204. // This method needs three arguments and returns one argument.
  205. // Table_length, Table_width and DataGridView Elements.
  206. //
  207. // Structure of DataGridView that is going to be passed as argument,
  208. // from caller method, must be the same as structure of
  209. // DataGridView ELEMENT_LIST.
  210. //
  211. // Method returns DataGridView TABLE_LIST with data
  212. // of packed elements: index, x, y, length and width.
  213. //
  214. //
  215. //
  216. //
  217. Initialize_Tables();
  218. //
  219. //
  220. //
  221. Initialize_Variables();
  222. //
  223. // Set table length and width
  224. //
  225. Tl = Table_length;
  226. Tw = Table_width;
  227. //
  228. // Copy element dimensions from DataGridView Elements
  229. // to ELEMENT_LIST table and format it's values
  230. //
  231. // Set elements counter to zero
  232. n = 0;
  233. // Set table row counter to zero
  234. i = 0;
  235. // Fill ELEMENT_LIST
  236. for (i = 0; i < Elements.RowCount; i++)
  237. {
  238. if (Elements[1, i].Value != null)
  239. {
  240. ELEMENT_LIST.Rows.Add();
  241. ELEMENT_LIST[0, i].Value = (int.Parse(Elements[0, i].Value.ToString())).ToString(format);
  242. ELEMENT_LIST[1, i].Value = (int.Parse(Elements[1, i].Value.ToString())).ToString(format);
  243. ELEMENT_LIST[2, i].Value = (int.Parse(Elements[2, i].Value.ToString())).ToString(format);
  244. ELEMENT_LIST[3, i].Value = (int.Parse(Elements[3, i].Value.ToString())).ToString(format);
  245. ELEMENT_LIST[4, i].Value = (int.Parse(Elements[4, i].Value.ToString())).ToString(format);
  246. // Increase elements counter by one
  247. n++;
  248. }
  249. }
  250. //
  251. // Sort elements in descending sort order
  252. // first by area then by length then by width of elements
  253. //
  254. ELEMENT_LIST.Sort(ELEMENT_LIST.Columns[3], ListSortDirection.Descending);
  255. // Set position coordinates to origin
  256. p_X = 0;
  257. p_Y = 0;
  258. //
  259. // Enter coordinates and dimensions
  260. // of first position in table 'POSITION_LIST'
  261. //
  262. POSITION_LIST.Rows.Add(p_X.ToString(format), // X coordinate
  263. p_Y.ToString(format), // Y coordinate
  264. Tl.ToString(format), // table lenght
  265. Tw.ToString(format)); // table width
  266. // Set position counter to one
  267. k = 1;
  268. // Set counter of packed elements to zero
  269. p = 0;
  270. //
  271. // Pack elements while there is free positions and
  272. // elements for packing
  273. //
  274. while (k > 0 && n > 0)
  275. {
  276. // Sort positions in ascending sort order first by Y, and then by X axes
  277. POSITION_LIST.Sort(POSITION_LIST.Columns[1], ListSortDirection.Ascending);
  278. // Get length and width of first position in 'POSITION_LIST'
  279. Pl = int.Parse(POSITION_LIST[2, 0].Value.ToString());
  280. Pw = int.Parse(POSITION_LIST[3, 0].Value.ToString());
  281. // Calculate fitting factor for each element for the first position
  282. for (i = 0; i < n; i++)
  283. {
  284. // Element length
  285. l = int.Parse(ELEMENT_LIST[1, i].Value.ToString());
  286. // Element width
  287. w = int.Parse(ELEMENT_LIST[2, i].Value.ToString());
  288. // Set fitting factor initial value
  289. f = 0;
  290. // Does element fits inside position
  291. if (Pl < l || Pw < w)
  292. {
  293. // If not
  294. f = 0;
  295. }
  296. else
  297. {
  298. // If yes
  299. f++;
  300. //
  301. if (Pl == l)
  302. {
  303. // If element fits exactly across lenght of position
  304. f++;
  305. }
  306. //
  307. if (Pw == w)
  308. {
  309. // If element fits exactly across width of position
  310. f++;
  311. }
  312. }
  313. // Enter fitting factor value inside ELEMENT_LIST table
  314. ELEMENT_LIST[4, i].Value = f.ToString(format);
  315. }
  316. //
  317. // Sort elements in descending sort order first by fitting factor value,
  318. // then by area then by length then by width of elements
  319. //
  320. ELEMENT_LIST.Sort(ELEMENT_LIST.Columns[4], ListSortDirection.Descending);
  321. //
  322. // Get fitting factor value for the first element
  323. //
  324. f = int.Parse(ELEMENT_LIST[4, 0].Value.ToString());
  325. //
  326. // If fitting factor is greater than zero
  327. // element can be packed inside selected position
  328. //
  329. if (f > 0)
  330. {
  331. //
  332. // Get coordinates of selected position
  333. //
  334. p_X = int.Parse(POSITION_LIST[0, 0].Value.ToString());
  335. p_Y = int.Parse(POSITION_LIST[1, 0].Value.ToString());
  336. // Get index, length and width of packed element
  337. x = int.Parse(ELEMENT_LIST[0, 0].Value.ToString());
  338. l = int.Parse(ELEMENT_LIST[1, 0].Value.ToString());
  339. w = int.Parse(ELEMENT_LIST[2, 0].Value.ToString());
  340. //
  341. // Enter coordinates of position,
  342. // element dimensions and index,
  343. // at TABLE LIST
  344. //
  345. TABLE_LIST.Rows.Add();
  346. TABLE_LIST[0, p].Value = x.ToString(); // index
  347. TABLE_LIST[1, p].Value = p_X.ToString(); // position x
  348. TABLE_LIST[2, p].Value = p_Y.ToString(); // position y
  349. TABLE_LIST[3, p].Value = l.ToString(); // element length
  350. TABLE_LIST[4, p].Value = w.ToString(); // element width
  351. // Increase packed elements counter by one
  352. p++;
  353. // Erase packed element from list of elements
  354. ELEMENT_LIST.Rows.RemoveAt(0);
  355. // Decrease elements counter by one
  356. n--;
  357. //
  358. // If there is free elements left
  359. // seek for new positions
  360. //
  361. if (n > 0)
  362. {
  363. //
  364. // Sort elements in descending sort order,
  365. // first by area then by length then by width of elements
  366. //
  367. // This step is necessary for faster searching
  368. // for element that can fit inside new positions
  369. //
  370. // And the elements are sorted accordingly to demand of
  371. // second restriction in algorithm development
  372. // for the next step in packing process
  373. //
  374. ELEMENT_LIST.Sort(ELEMENT_LIST.Columns[3], ListSortDirection.Descending);
  375. // Set new position 'is adequate' state flag
  376. P_ok = true;
  377. //
  378. // New position II with coordinates
  379. // at upper left corner of previous
  380. // packed element
  381. //
  382. if (Pw > w)
  383. {
  384. //
  385. // Initialize local variables
  386. //
  387. X12 = 0;
  388. Y12 = 0;
  389. L12 = 0;
  390. W12 = 0;
  391. A12 = 0;
  392. // Set new position 'is adequate' state flag
  393. P_ok = false;
  394. //
  395. // Coordinates of new position II
  396. //
  397. X12 = p_X;
  398. Y12 = p_Y + w;
  399. //
  400. // Length, width and area of new position II
  401. //
  402. L12 = Tl - X12;
  403. W12 = Pw - w;
  404. A12 = L12 * W12;
  405. //
  406. // Find is there element left that can fit inside position
  407. //
  408. // Set ELEMENT_LIST table counter value
  409. i = n - 1;
  410. //
  411. // Get area of the last element in table
  412. //
  413. a = int.Parse(ELEMENT_LIST[3, i].Value.ToString());
  414. while (a <= A12 && i > -1)
  415. {
  416. //
  417. // Get next element area
  418. //
  419. a = int.Parse(ELEMENT_LIST[3, i].Value.ToString());
  420. //
  421. // Get element length and width value
  422. //
  423. Lmin = int.Parse(ELEMENT_LIST[1, i].Value.ToString());
  424. Wmin = int.Parse(ELEMENT_LIST[2, i].Value.ToString());
  425. //
  426. // If element can fit
  427. // at observed position,
  428. // set new position II at list of positions
  429. //
  430. if (L12 >= Lmin && W12 >= Wmin)
  431. {
  432. POSITION_LIST.Rows.Add(X12.ToString(format),
  433. Y12.ToString(format),
  434. L12.ToString(format),
  435. W12.ToString(format));
  436. // Increase positions counter by one
  437. k++;
  438. // Set new position 'is adequate' state flag
  439. P_ok = true;
  440. // Set counter value to loop exit value
  441. i = -1;
  442. }
  443. // Decrease elements counter by one
  444. i--;
  445. }
  446. }
  447. //
  448. // New position I with coordinates
  449. // at lower right corner of previous
  450. // packed element
  451. //
  452. if (Pl > l)
  453. {
  454. //
  455. // Initialize local variables
  456. //
  457. X11 = 0;
  458. Y11 = 0;
  459. L11 = 0;
  460. W11 = 0;
  461. A11 = 0;
  462. //
  463. // Coordinates of new position I
  464. //
  465. X11 = p_X + l;
  466. Y11 = p_Y;
  467. //
  468. // Length, width and area of new position I
  469. //
  470. L11 = Tl - X11;
  471. W11 = w;
  472. A11 = L11 * W11;
  473. //
  474. // If position two is inadeqate,
  475. // adjust width of position one
  476. //
  477. if (!P_ok)
  478. {
  479. W11 = W11 + W12;
  480. A11 = L11 * W11
  481. }
  482. //
  483. // Find is there element left that can fit inside position
  484. //
  485. // Set element counter value
  486. i = n - 1;
  487. //
  488. // Get area of the last element in table
  489. //
  490. a = int.Parse(ELEMENT_LIST[3, i].Value.ToString());
  491. while (a <= A11 && i > -1)
  492. {
  493. //
  494. // Get next element area
  495. //
  496. a = int.Parse(ELEMENT_LIST[3, i].Value.ToString());
  497. //
  498. // Get element length and width value
  499. //
  500. Lmin = int.Parse(ELEMENT_LIST[1, i].Value.ToString());
  501. Wmin = int.Parse(ELEMENT_LIST[2, i].Value.ToString());
  502. //
  503. // If there is element that can fit
  504. // at position,
  505. // set new position I at list of positions
  506. //
  507. if (L11 >= Lmin && W11 >= Wmin)
  508. {
  509. POSITION_LIST.Rows.Add(X11.ToString(format),
  510. Y11.ToString(format),
  511. L11.ToString(format),
  512. W11.ToString(format));
  513. // Increase positions counter by one
  514. k++;
  515. // Set counter value to loop exit value
  516. i = -1;
  517. }
  518. // Decrease elements counter by one
  519. i--;
  520. }
  521. }
  522. }
  523. }
  524. //
  525. // Is there free elements left for packing
  526. //
  527. if (n > 0)
  528. {
  529. //
  530. // Erase first position from list
  531. //
  532. POSITION_LIST.Rows.RemoveAt(0);
  533. // Decrease positions counter by one
  534. k--;
  535. }
  536. }
  537. //
  538. // End of packing process
  539. //
  540. return TABLE_LIST;
  541. }
  542. }
  543. }
Conclusion

This article shows that by using common algorithm development and programming knowledge, we can find a solution for very complex mathematical problem without need of knowing complex math theory for describing such problem.

Algorithm and program code developed inside this article solves only one type of packing problem, packing two dimensional rectangular elements at orthogonal table in sequence along X axis of table, with horizontal orientation exclusively and can be easily changed to solve the same problem with different element orientation, or withthe possibility that elements can rotate during packing process or to change axes along with elements that will be packed.

It can also be a good starting point for any deeper mathematical analysis of such problem.