Abstract
Cutting and packing problems arise in many fields of applications and theory. When dealing with irregular objects, an important subproblem is the identification of the optimal clustering of two objects. Within this paper we consider a container (rectangle, circle, convex polygon) of variable sizes and two irregular objects bounded by circular arcs and/or line segments, that can be continuously translated and rotated. In addition minimal allowable distances between objects and between each object and the frontier of a container, may be imposed. The objects should be arranged within a container such that a given objective will reach its minimal value. We consider a polynomial function as the objective, which depends on the variable parameters associated with the objects and the container. The paper presents a universal mathematical model and a solution strategy which are based on the concept of phi-functions and provide new benchmark instances of finding the containing region that has either minimal area, perimeter or homothetic coefficient of a given container, as well as finding the convex polygonal hull (or its approximation) of a pair of objects.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Adamowicz, M., Albano, A.: Nesting two-dimensional shapes in rectanglular modules. Comput. Aided Des. 8(1), 27–33 (1976)
Avnaim, F., Boissonnat, J.D.: Polygon placement under translation and rotation. Informatique Theorique et Applications 23(1), 5–28 (1989)
Avnaim, F., Boissonnat, J.D.: Simultaneous containment of several polygons. In: Symposium on Computational Geometry, pp. 242–247 (1987)
Bennell, J.A., Oliveira, J.F.: The geometry of nesting problems: a tutorial. Eur. J. Oper. Res. 184, 397–415 (2008)
Bennell, J.A., Oliveira, J.F.: A tutorial in irregular shape packing problem. J. Oper. Res. Soc. 60, s93–s105 (2009)
Bennell, J., Scheithauer, G., Stoyan, Y., Romanova, T.: Tools of mathematical modeling of arbitrary object packing problems. Ann. OR 179, 343–368 (2008)
Blazewicz, J., Drozdowski, M., Soniewicki, B., Walkowiak, R.: Two-dimensional cutting problem—basic complexity results and algorithms for irregular shapes. Found. Cont. Eng. 14(4), 60–137 (1989)
Burke, E.K., Hellier, R., Kendall, G., Whitwell, G.: Irregular packing using the line and arc no-fit polygon. Oper. Res. 58(4), 948–970 (2010)
Chazelle, B., Edelsbrunner, H., Guibas, L.J.: The complexity of cutting complexes. Discret. Comput. Geom. 4(2), 139–181 (1989)
Chernov, N., Stoyan, Yu., Romanova, T.: Mathematical model and efficient algorithms for object packing problem. Comput. Geom. Theory Appl. 43, 535–553 (2010)
Chernov, N., Stoyan, Yu., Romanova, T., Pankratov, A.: Phi-functions for 2D objects formed by line segments and circular arcs. Adv. Oper. Res. (2012). doi:10.1155/2012/346358
Chlebik, M., Chlebikova, J.: Hardness of approximation for orthogonal rectangle packing and covering problems. J. Discret. Algorithms 7, 291–305 (2009)
Dori, D., Ben-Bassat, M.: Circumscribing a convex polygon by a polygon of fewer sides with minimal area additions. Comput. Vis. Graph. Image Process. 24, 131–159 (1983)
Dowsland, K.A., Dowsland, W.B.: Solution approaches to irregular nesting problems. Eur. J. Oper. Res. 84, 506–521 (1995)
Grinde, R.B., Cavalier, T.M.: Containment of a single polygon using mathematical programming. Eur. J. Oper. Res. 92, 368–386 (1996)
Grinde, R.B., Cavalier, T.M.: A new algorithm for the two-polygon containment problem. Comput. Oper. Res. 24, 231–251 (1997)
Grinde, R.B., Cavalier, T.M.: A new algorithm for the minimum-area convex enclosing problem. Eur. J. Oper. Res. 84, 522–538 (1995)
Han, W., Bennell, J.A., Song, X., Zhao, X.: Construction heuristics for two-dimensional irregular shape bin packing with guillotine constraints. Eur. J. Oper. Res. (2013). doi:10.1016/j.ejor.2013.04.048
Kallrath, J.: Cutting circles and polygons from area-minimizing rectangles. J. Glob. Optim. 43, 299–328 (2009)
Li, Z., Milenkovic, V.: The complexity of the compaction problem. In: 5th Canadian Conference on Computational Geometry, Univ. Waterloo (1993)
Martin, R.R., Stephenson, P.C.: Putting objects into boxes. Comput. Aided Des. 20(9), 506–514 (1988)
Milenkovic, V.: Multiple translational containment. Part II: Exact algorithms. Algorithmica 19(9), 183–218 (1997)
Milenkovic, V.: Rotational polygon containment and minimum enclosure using only robust 2D constructions. Comput. Geom. 13(1), 3–19 (1999)
Milenkovic, V.: Rotational polygon overlap minimization and compaction. Comput. Geom. 10(4), 305–318 (1998)
Milenkovic, V., Daniels, K.: Translational polygon containment and minimal enclosure using mathematical programming. Int. Trans. Oper. Res. 6(5), 525–554 (1999)
Milenkovic, V., Sacks, E.: Two approximate Minkowski sum algorithms. Int. J. Comput. Geom. Appl. 20, 485–509 (2010)
Wachter, A., Biegler, L.T.: On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Math. Program. 106(1), 25–57 (2006)
Wascher, G., Hauner, H., Schuma, H.: An improved typology of cutting and packing problems. Eur. J. Oper. Res. 183, 1109–1130 (2007)
Acknowledgments
T. Romanova, Yu. Stoyan and A. Pankratov acknowledge the support of the Science and Technology Center in Ukraine and the National Academy of Sciences of Ukraine, Grant 5710.
Author information
Authors and Affiliations
Corresponding author
Appendices
Appendix 1: Primitive and basic objects
See Fig. 13.
a 3 types of primitive objects, b 4 types of basic objects
Appendix 2: Description of irregular objects in an analytical form
We define phi-object \(T\), given in Fig. 14, as follows: \(T=T_1 \cup T_2 \), where \(T_1 \) is a circle of radius \(r_1 \), \(T_{2}=T_{21}\cap T_{22}\cap T_{23}\), where \(T_{21}\) and \(T_{23}\) are half-planes, \(T_{22}\) is the complement to the interior of a circle of radius \(r_2\) with center point \((x_{22} ,y_{22} )\). Primitive objects \(T_1, T_{21}, T_{22}, T_{23}\) are defined as follows: \(T_1 =\{t\in R^{2}:f_1 (t)\le 0\}\), \(f_1 (t)=f_{11} (t)=x_t^2 +y_t^2 -r_1^2 \), \(T_{21} =\{t\in R^{2}:f_{21} (t)\le 0\}\), \(f_{21} (t)={\upalpha }'x_t +{\upbeta }'y_t +{\upgamma }'\), \(T_{22} =\{t\in R^{2}:f_{22} (t)\le 0\}\), \(f_{22} (t)=-(x_t -x_{22} )^{2}-(y_t -y_{22} )^{2}+r_2^2 \), \(T_{23} =\{t\in R^{2}:f_{23} (t)\le 0\}\), \(f_{23} (t)={{\upalpha }^{{\prime }{\prime }}}x_t +{{\upbeta ^{{\prime }{\prime }} }}y_t +{{\gamma ^{{\prime }{\prime }} }}\).
Now we may conclude, that \(T_2 =\{t\in R^{2}:f_2 (t)\le 0\}\), where \(f_2 (t)=\max \{f_{21} (t),f_{22} (t),f_{23} (t)\}\). Thus, \(T=\{t\in R^{2}:f(t)\le 0\}\), where \(f(t)=\min \{f_1 (t),f_2 (t)\}\). Note, that \(\mathrm{int}T=\{t\in R^{2}:f(t)<0\}\), \(frT=\{t\in R^{2}:f(t)=0\}\).
Definition of object \(T\)
Appendix 3: Definition of circular segment \(D\) for deriving phi-functions
Given \(A=P\cap C\) and \(B=K\) convex polygon, where \(P\) is a half-plane and \(C\) is a circle. We arrange \(A\) and \(B\) as it is shown in Fig. 15a. One can see that \(P\cap K\ne \emptyset \) (resulting in \(\Phi ^{PK}<0)\) and \(C\cap K\ne \emptyset \) (resulting in \(\Phi ^{CK}<0)\), while \(A\cap K=\emptyset \) (meaning that \(\Phi ^{AB}\) should be positive). Therefore, \(\Phi ^{AB}\ne \max \{\Phi ^{RK},\Phi ^{C^{{*}}K}\}\). If we take \(A=T\cap C\), where \(T\) is a triangle with two tangent sides to circle \(C\) (see Fig. 15b), then we have \(\Phi ^{AB}=\max \{\Phi ^{TK},\Phi ^{CK}\}\).
Definition of circular segment \(D\) for deriving phi-functions: a \(D\) is an intersection of circle \(C\) and half-plane \(P\), b \(D\) is an intersection of circle \(C\) and triangle \(T\)
Appendix 4: Phi-tree diagram
See Fig. 16.
Diagram of phi-tree for \(\Phi _{D_1 D_2 } \ge 0\)
Appendix 5: Input and output data for examples
Example_1
INPUT DATA
OBJECT A EX_1
\(l_A =(2, -1, 0, 0, 2, 0, -2, 0, 0)\)
OBJECT B EX_1
\(l_B =(0, 0, 0, 3, 2, 0, 0, 2, 0)\)
Example_1 OUTPUT DATA
Example 1.1. \(u^{*}=(a^{*},b^{*},x_1^*,y_1^*,x_2^*,y_2^*)=(4.0,\;3.6667,2.0,\;1.0,0.0\), \(1.6667)\).
Example 1.2. \(u^{*}=(a^{*},b^{*},x_1^*,y_1^*,\uptheta _1^*,x_2^*,y_2^*,\uptheta _2^*)\) = (3.5355, 2.8284, 2.1213, 1.4142, 2.3562, 0.0791, 0.7591, 6.3087)
Example 1.3. Rotation step is \(30^{\circ }\),
\(u^{*}=(a^{*},b^{*},x_1^*,y_1^*,\uptheta _1^*,x_2^*,y_2^*,\uptheta _2^*)\) = (4.0, 3.0, 2.0, 1.0, 0.0, 2.0, 3.0, 1.5708)
Example_2 INPUT DATA
OBJECT A EX_2
\(l_A \) = (\(-\)1.605, \(-\)2.125, \(-\)2.693, 0.829, \(-\)3.278, 1.892, \(-\)0.804, 0, 2.039, 1.369, 0, \(-\)0.2372, 2.0661, 0)
OBJECT B EX_2
\(l_B \) = (2.022, \(-\)1.281, 1.843, 1.1539, 0.3449, 0.708, 2.133, 12.743, 7.836, \(-\)8.429, \(-\)2.934, \(-\)1.619, \(-\)3.632, \(-\)0.276, \(-\)4.0936).
Example_2 OUTPUT DATA
Example 2.1 \(u^{*}=(a^{*},b^{*},x_1^*,y_1^*,\uptheta _1^*,x_2^*,y_2^*,\uptheta _2^*)\) = (6.0977, 3.8089, 4.1637, 2.9426, 1.2554, 2.8937, 1.2500, \(-\)2.3398)
Example 2.2
\(u^{*}=(r^{*},x_1^*,y_1^*,\uptheta _1^*,x_2^*,y_2^*,\uptheta _2^*)\) = (3.2599, \(-\)0.2514, 1.4905, \(-\)5.4582, \(-\)0.1020, \(-\)0.7134, \(-\)9.01344)
Example 2.3
\(u^{*}=(a^{*},b^{*},x_1^*,y_1^*,\uptheta _1^*,x_2^*,y_2^*,\uptheta _2^*)\) = (4.4249, 6.2566, 0.8663, 4.3227, 5.9678, 3.1659, 2.8858, 2.3858)
Example 2.4 m = 11, \(u^{*}=(x_1^*,y_1^*,\uptheta _1^*,t_1^*,\ldots ,x_{11}^*,y_{11}^*,\uptheta _{11}^*,t_{11}^*,x_A^*,y_A^*,\uptheta _A^*,x_B^*,y_B^*,\uptheta _B^*)\) = (3.7724, 0.0000, 2.3683, 0.8404, 3.1711, \(-\)0.5870, 2.8165, 0.8404, 2.3747, \(-\)0.8554, \(-\)3.0185, 0.8404, 1.5408, \(-\)0.7522, \(-\)2.5702, 0.8404, 0.8339, \(-\)0.2977, \(-\)2.1220, 1.1793, 0.2163, 0.70686, \(-\)1.6199, 4.4084, 0.0000, 5.1099, \(-\)0.0673, 3.5617, 3.5537, 5.3494, 0.5327, 0.0000, 3.5537, 5.3494, 1.3184, 1.3214, 3.8837, 4.0698, 1.5251, 2.6428, 4.0045, 1.4298, 1.7318, 1.4485, 0.9580, 3.2641, 5.9187, 2.7233, 2.1026, 2.3254)
Example 2.5
Pentagon \(K\) is given by a vector of coordinates of its vertices: (7.0190, 1.4637, 1.8053, 7.2809, \(-\)5.3382, 4.1200, \(-\)4.5396, \(-\)3.6507, 3.0977, \(-\)5.2924) m = 5, \(u^{*}=(\upalpha ^*,x_A^*,y_A^*,\uptheta _A^*,x_B^*,y_B^*,\uptheta _B^*)=(\hbox {0.5259}\), 1.6035, 1.1955, 8.1947, \(-\)0.3486, \(-\)0.0779, 10.8685)
Example_3 INPUT DATA
OBJECT A EX_3
\(l_A \) = (4.326, 6.395, \(-\)1.433, 2.914, 6.639, 1.56, 6.169, \(-\)2.405, 3.738, 7.189, 1.333, 7.212, 1.507, \(-\)0.143, 6.908, \(-\)0.553, 8.358, 3.78, 3.226, 8.266, 2.139, 4.645, \(-\)1.335, 1.574, 3.436, 0.749, 2.385, \(-\)41.479, 26.033, 35.267, \(-\)4.337, 7.015, 0.69, \(-\)4.999, 6.826, \(-\)4.974, 6.137, \(-\)11.293, \(-\)10.967, \(-\)3.435, \(-\)1.594, 2.865, \(-\)2.1027, \(-\)3.484, 1.944, \(-\)1.523, 1.186, \(-\)3.278, \(-\)1.925, 4.439, \(-\)4.36, 2.245, 18.437, \(-\)17.211, \(-\)10.975, \(-\)8.242, 5.133, \(-\)19.365, \(-\)19.496, \(-\)10.626, \(-\)3.431, 0.187, \(-\)0.727, \(-\)4.157, 0.218, \(-\)4.551, \(-\)0.393, \(-\)6.038, \(-\)1.879, 5.022, \(-\)6.914, 1.689, 1.485, \(-\)8.213, 0.971, \(-\)9.274, 2.01, \(-\)1.738, \(-\)8.923, 0.308, \(-\)8.055, \(-\)1.197, 7.273, \(-\)2.074, 2.942)
OBJECT B EX_3
\(l_B \) = (2.493, 6.764, 1.771, 2.143, 5.028, 0.38, 5.191, \(-\)4.788, 1.364, 0.506, 4.149, 4.399, \(-\)1.876, 2.274, 4.368, 1.795, 2.554, 10.681, \(-\)0.594, \(-\)7.857, \(-\)1.702, 2.767, 8.905, 2.509, 10.614, 4.229, 1.877, \(-\)0.496, 4.671, 1.651, 4.781, 1.167, \(-\)16.555, 1.111, 17.31, \(-\)1.293, 0.931, 0.944, \(-\)1.623, 0.047, \(-\)1.214, \(-\)0.804, \(-\)10.767, 1.31, \(-\)11.271, 3.834, \(-\)0.804, \(-\)1.324, 3.524, \(-\)2.091, 3.361, \(-\)3.405, \(-\)40.094, 8.293, 36.385, \(-\)2.239, \(-\)2.301, 0.723, \(-\)2.193, \(-\)3.023, \(-\)2.003, \(-\)3.72, \(-\)4.687, \(-\)1.968, \(-\)8.407, 1.231, \(-\)4.981, \(-\)2.155, \(-\)0.867, \(-\)5.474, 0.837, \(-\)6.794, \(-\)1.946, \(-\)0.701, \(-\)5.602, \(-\)2.239, \(-\)6.794, 1.103, \(-\)3.112, \(-\)7.469, \(-\)3.423, \(-\)8.528, 7.762, 0.541, \(-\)1.854, 2.0200, \(-\)9.4743, 8.4740, \(-\)0.1576, \(-\)1.2849).
Example 3 OUTPUT DATA
Example 3.1 \(u^{*}=(r^{*},x_1^*,y_1^*,\uptheta _1^*,x_2^*,y_2^*,\uptheta _2^*)\) = (8.5826, 2.6036, 4.1595, \(-\)1.9849, 1.1292, \(-\)0.5965, \(-\)4.4319)
Example 3.2 \(u^{*}=(r^{*},x_1^*,y_1^*,\uptheta _1^*,x_2^*,y_2^*,\uptheta _2^*)\) = (5.6452, 4.7846, \(-\)1.3617, \(-\)1.1846, \(-\)3.5867, \(-\)3.6332)
Example 3.3
m = 24, \(u^{*}=(x_1^*,y_1^*,\uptheta _1^*,t_1^*,\ldots ,x_{24}^*,y_{24}^*,\uptheta _{24}^*,t_{24}^*,x_A^*,y_A^*,\uptheta _A^*,x_B^*,y_B^*,\uptheta _B^*)\) = (\(-\)5.3369, \(-\)8.5664, \(-\)2.6532, 2.4302, \(-\)7.4829, \(-\)7.4261, \(-\)2.3683, 2.4302, \(-\)9.2220, \(-\)5.7287, \(-\)2.0835, 2.4302, \(-\)10.4141, \(-\)3.6120, \(-\)1.7987, 2.4302, \(-\)10.9631, \(-\)1.2436, \(-\)1.5138, 2.4302, \(-\)10.8247, 1.1826, \(-\)1.2290, 2.4302, \(-\)10.0101, 3.4722, \(-\)0.9441, 1.2151, \(-\)9.2975, 4.4564, \(-\)0.8760, 0.9460, \(-\)8.6918, 5.1831, \(-\)0.6335, 1.8920, \(-\)7.1669, 6.3030, \(-\)0.3909, 1.8920, \(-\)5.4177, 7.0239, \(-\)0.2271, 1.3731, \(-\)4.0798, 7.3330, 0.0182, 4.0874, 0.00688, 7.2587, 0.3034, 2.2215, 2.1269, 6.5950, 0.6065, 2.2215, 3.9522, 5.3288, 0.9096, 2.2215, 5.3164, 3.5755, 1.2127, 2.2215, 6.0950, 1.4949, 1.5158, 2.22150, 6.2171, \(-\)0.7232, 1.8189, 2.2215, 5.6716, \(-\)2.8767, 2.1220, 2.2215, 4.5081, \(-\)4.7695, 2.3619, 4.8634, 1.0496, \(-\)8.1884, 2.6565, 0.5084, 0.5998, \(-\)8.4255, 2.7755, 1.2151, \(-\)0.5346, \(-\)8.8605, 3.0603, 2.4302, \(-\)2.9569, \(-\)9.0577, \(-\)2.9380, 2.4302, 2.1774, 1.4609, 4.9044, \(-\)1.7436, \(-\)1.6084, 2.4573)
Example_4 INPUT DATA
OBJECT A EX_4
\(l_A \) = (0.916, \(-\)3.2835, \(-\)2.1141, \(-\)1.1925, \(-\)3.4331, \(-\)3.1599, \(-\)4.2069, 1.5176, \(-\)4.5722, \(-\)4.7624, \(-\)6.0118, \(-\)5.243, \(-\)1.9194, \(-\)7.8323, \(-\)5.8509, \(-\)9.7247, \(-\)5.5302, 6.5362, \(-\)16.1691, \(-\)4.4383, \(-\)10.9427, \(-\)0.5133, 0.531, \(-\)11.3672, \(-\)0.8321, \(-\)11.8691, \(-\)0.6587, 6.4935, \(-\)5.7318, \(-\)2.7797, \(-\)11.614, \(-\)5.5302, \(-\)10.3158, \(-\)20.9587, \(-\)9.8998, \(-\)10.6432, \(-\)9.9873, 1.0287, \(-\)9.8552, \(-\)10.6486, \(-\)9.5622, \(-\)11.6347, 12.1386, \(-\)19.1497, \(-\)4.1899, \(-\)7.9948, \(-\)8.9767, \(-\)0.8426, \(-\)7.1675, \(-\)9.1368, \(-\)6.3926, \(-\)8.8058, 1.509, \(-\)5.0049, \(-\)8.213, \(-\)3.5952, \(-\)8.7513, \(-\)2.7401, \(-\)1.0353, \(-\)9.7286, \(-\)0.3511, \(-\)7.0753, \(-\)2.5557, 0.6609, \(-\)9.4221, 2.6318, \(-\)7.7951, 3.383, 5.924, \(-\)7.0167, 5.1053, \(-\)3.7343, \(-\)2.0191, 5.7366, \(-\)1.8164, 4.5707, \(-\)0.1679, 5.8141, \(-\)0.784, 2.0974, 4.2101, 5.0745, 2.1588, 2.3558, 3.9691, 2.1899, 6.1215, \(-\)0.8636, 2.1236, 6.9825, 1.721, 7.7466, 1.7119, 0.9229, 9.2611, 0.7867, 10.9676, \(-\)1.2333, 0.6886, 12.1970, 1.1388, 13.3452, 2.0740, 1.8957, 15.2761, 3.2381, 16.8571, 2.0329, 1.9223, 15.3074, \(-\)0.0714, 15.7046, \(-\)0.8439, \(-\)0.8991, 15.8695, \(-\)1.5973, 15.3956, 1.5839, \(-\)2.9079, 14.5062, \(-\)3.3626, 12.9889, \(-\)1.2291, \(-\)3.7155, 11.8116, \(-\)2.5921, 11.3130, \(-\)1.0093, \(-\)3.5146, 11.7225, \(-\)4.2379, 11.0185, 0.9691, \(-\)4.9323, 10.3426, \(-\)4.8298, 9.3789, \(-\)1.7325, \(-\)4.6465, 7.6562, \(-\)4.5749, 5.9252, 2.3942, \(-\)4.4760, 3.5330, \(-\)4.0691, 1.1736, \(-\)3.8135, \(-\)3.4210, \(-\)2.5844, \(-\)0.6502, 0.0357, \(-\)5.8961, \(-\)4.9343, \(-\)4.0153)
OBJECT B EX_4
\(l_B \) = (\(-\)3.9051, 15.6754, 3.6105, \(-\)6.3238, 12.9949, \(-\)5.4522, 9.4912, \(-\)1.7667, \(-\)4.4782, 8.0172, \(-\)5.7334, 6.7739, \(-\)7.4716, \(-\)6.5223, 14.2038, \(-\)8.5183, 7.0037, \(-\)5.0616, \(-\)13.3461, 5.4831, \(-\)8.3588, 4.6188, 6.9000, \(-\)2.9414, 0.3454, \(-\)9.7608, \(-\)0.7063, 4.6404, \(-\)11.0770, 3.7435, \(-\)6.4367, 3.7287, 1.0321, \(-\)5.8343, 4.5668, \(-\)4.8427, 4.8531, \(-\)1.5625, \(-\)3.2958, 4.6331, \(-\)1.7954, 4.1972, 0.9511, \(-\)1.0711, 3.5808, \(-\)0.7171, 2.6980, \(-\)8.0493, 2.2783, \(-\)4.7732, 9.5968, \(-\)8.1244, \(-\)4.6532, 5.3660, \(-\)6.1871, 1.0175, \(-\)7.8433, 1.0906, \(-\)0.0017, \(-\)8.2314, \(-\)1.0922, \(-\)8.2181, \(-\)3.8299, \(-\)4.9218, \(-\)8.1712, \(-\)3.1081, \(-\)11.5444, \(-\)3.3853, \(-\)4.7112, \(-\)8.5628, \(-\)8.0775, \(-\)8.9208, 1.1200, \(-\)9.1913, \(-\)9.0393, \(-\)10.2810, \(-\)8.7803, \(-\)1.2462, \(-\)11.4934, \(-\)8.4921, \(-\)11.2655, \(-\)9.7173, 1.8333, \(-\)10.9302, \(-\)11.5197, \(-\)10.6091, \(-\)13.3247, \(-\)4.1852, \(-\)9.8762, \(-\)17.4452, \(-\)5.9678, \(-\)15.9483, 2.5006, \(-\)3.6327, \(-\)15.0539, \(-\)1.7485, \(-\)16.6979, \(-\)71.089, 51.8177, \(-\)63.4345, 1.6738, \(-\)13.0436, \(-\)2.7890, 3.6411, \(-\)15.0206, 5.9870, \(-\)13.5121, 1.6693, 7.3910, \(-\)12.6092, 9.0343, \(-\)12.9031, \(-\)12.2743, 21.1169, \(-\)15.0634, 13.7224, \(-\)5.2665, 3.2491, 11.7650, \(-\)2.6732, 13.2536, 0.2149, \(-\)4.2809, 15.2149, 4.0201, 11.5659, 6.2586, 1.4523, 10.3279, 7.0180, 10.1594, 8.4605, \(-\)7.0745, 9.3387, 15.4872, 4.3461, 10.4751, 0.7968, 3.7838, 9.9105, 3.1741, 9.3975, \(-\)1.5498, 1.9882, 8.3997, 1.4863, 9.866, 2.0727, 0.8151, 11.8271, 2.8459, 11.4121, \(-\)1.7315, 4.5423, 11.0654, 5.2837, 12.6302, 0.8337, 5.6407, 13.3836, 6.4089, 13.7077, 4.1508, 2.5845, 12.0942, 1.6738, 16.1439, \(-\)20.4365, \(-\)2.8097, 36.0825)
Example 4 OUTPUT DATA
Example 4.1 \(u^{*}=(r^{*},x_1^*,y_1^*,\uptheta _1^*,x_2^*,y_2^*,\uptheta _2^*)\) = (17.7674, \(-\)1.2785, 5.0441, \(-\)2.7258, \(-\)0.2362, \(-\)2.6272, 1.8515)
Example 4.2 \(u^{*}=(a^{*},b^{*},x_1^*,y_1^*,\uptheta _1^*,x_2^*,y_2^*,\uptheta _2^*)\) = (32.8975, 34.0964, 22.0452, 19.8732, 4.7927, 15.1417, 16.3673, 3.0874)
Example 4.3 \(u^{*}=(x_1^*,y_1^*,\theta _1^*,t_1^*,\ldots ,x_m^*,y_m^*,\theta _m^*,t_m^*,u_A^*,u_B^*)\), \(m\,=\,22\), where \((x_1^*,y_1^*,\theta _1^*,t_1^*,\ldots ,x_m^*,y_m^*,\theta _m^*,t_m^*)\) = (32.1154, \(-\)1.3741, 2.4936, 9.2842, 24.7132, \(-\)6.9780, 2.6752, 0.2644, 24.4770, \(-\)7.0969, 2.8567, 10.1271, 14.7581, \(-\)9.9431, 3.0798, 0.7279, 14.0316, \(-\)9.9880, \(-\)2.9803, 0.7279, 13.3131, \(-\)9.8711, \(-\)2.7572, 0.7279, 12.6384, \(-\)9.5981, \(-\)2.5341, 11.4076, 3.2719, \(-\)3.0864, \(-\)2.17501, 0.6059, 2.9277, \(-\)2.5878, \(-\)1.8159, 12.0635, 0.0000, 9.1151, \(-\)1.4215, 0.9994, 0.14867, 10.1034, \(-\)1.0270, 14.4742, 7.6372, 22.4899, \(-\)0.6472, 1.3006, 8.6747, 23.2741, \(-\)0.2674, 1.3006, 9.9291, 23.6177, 0.1125, 16.8834, 26.7059, 21.7236, 0.5216, 0.4268, 27.0760, 21.5110, 0.9306, 11.0851, 33.6978, 12.6210, 1.0337, 0.8197, 34.1172, 11.9168, 1.3810, 1.1366, 34.3316, 10.8006, 1.6580, 9.9226, 33.4677, 0.9157, 1.8892, 0.9642, 33.1660, 0.0000, 2.1204, 0.9641, 32.6624, \(-\)0.82219, 2.3517, 0.7771), \((u_A^*,u_B^*)\) = (14.6660, 12.1616, 3.334, 17.4147, 4.9045, 1.6176).
Example 5 INPUT DATA
OBJECT A EX_5
\(l_A \) = (\(-\)7.2662, 1.5935, 0, \(-\)5.9413, \(-\)6.8803, 0, \(-\)3.2915, \(-\)8.7340, 0, 2.3109, \(-\)10.6633, 0, 6.7020, \(-\)10.6633, 0)
OBJECT B EX_5
\(l_B \) = (\(-\)1.443, \(-\)4.819, 0. 2.67, \(-\)1.107, 0. 2.089, 7, 4.41, \(-\)4.991, \(-\)2.885, 3.884, 0.83, 0.55, 0, \(-\)1.443, 2.605, \(-\)5.001, \(-\)4.7927, \(-\)1.107, 8, 0.11, \(-\)0.12, \(-\)5.0, \(-\)2.885, 3.884, \(-\)2.879, \(-\)1.116, 0. 0.21, \(-\)1.116, \(-\)5.0, \(-\)4.7927, \(-\)1.109)
Example 5 OUTPUT DATA
m = 10, \(u^{*}=(x_1^*,y_1^*,\theta _1^*,t_1^*,\ldots ,x_m^*,y_m^*,\theta _m^*,t_m^*,u_A^*,u_B^*)\) = (10.0238, \(-\)2.2864, 3.0242, 3.2338, 6.8123, \(-\)2.6651, \(-\)2.4537, 8.5767, 0.186, 2.7804, \(-\)1.5931, 8.3482, 0, 11.1266, \(-\)0.9437, 9.1846, 5.3899, 18.5634, \(-\)0.2207, 15.5024, 20.5161, 21.9577, 1.463, 7.9482, 21.3712, 14.0556, 1.8004, 11.4346, 18.7688, 2.9211, 2.4138, 0.0001, 18.7688, 2.921, 2.4138, 4.391, 15.4903, 0, 2.7454, 5.925, 6.6713, 6.4244, 5.5554, 6.6713, 6.4244, 5.5554)
Example 6 INPUT DATA
OBJECT A EX_6
\(l_A \) = (\(-\)1.4427, \(-\)4.8186, 0, 2.6700, \(-\)1.1068, 0, 2.089, 4.4005, \(-\)1, 0.830000, 0.5500, 0, \(-\)1.4427, 2.6050, 0, \(-\)0.1100, \(-\)0.1100, \(-\)1, \(-\)2.8787, \(-\)1.1163, \(-\)1, 0.2100, \(-\)1.1163, 0, \(-\)1.4427, \(-\)4.8186, \(-\)1)
OBJECT B EX_6
\(l_B \) = (\(-\)1.4427, \(-\)4.8186, 0, 2.6700, \(-\)1.1068, 0, 2.0887, 4.4005, \(-\)1, 0.8300, 0.5500, 0, \(-\)1.4427, 2.6050, 0, \(-\)0.1100, \(-\)0.1100, \(-\)1, \(-\)2.8787, \(-\)1.1163, \(-\)1, 0.2100, \(-\)1.1163, 0, \(-\)1.4427, \(-\)4.8186, \(-\)1)
Example 6 OUTPUT DATA
m = 6, \(u^{*}=(x_1^*,y_1^*,\theta _1^*,t_1^*,\ldots ,x_m^*,y_m^*,\theta _m^*,t_m^*,u_A^*,u_B^*)\) = (0.0889, 5.3038, \(-\)1.5932, 3.9616, 0, 9.2643, 0.3428, 5.5377, 5.2157, 7.4031, 1.2794, 5.5372, 6.8065, 2.099, 1.5484, 3.9615, 6.896, \(-\)1.8612, \(-\)2.7988, 5.5379, 1.6797, 0, \(-\)1.8622, 5.5372, 3.0618, 5.4759, 5.1604, 3.8337, 1.9273, 2.019)
Example 7
INPUT DATA
\(\rho =0.2\) is allowable distance between polygons \(A\) and \(B \) (see input data of example 1).
OUTPUT DATA
m = 16, \(u^{*}=(x_1^*,y_1^*,\theta _1^*,t_1^*,\ldots ,x_m^*,y_m^*,\theta _m^*,t_m^*,u_A^*,u_B^*)\) = (5.3365, \(-\)0.1823, 2.5860, 2.9023, 2.8708, \(-\)1.7132, 2.7833, 0.2494, 2.6372, \(-\)1.8006, 3.0773, 0.0592, 2.5782, \(-\)1.8045, 3.3713, 2.0522, 0.5799, \(-\)1.3371, \(-\)2.6874, 0.045, 0.5394, \(-\)1.3173, \(-\)2.463, 0.0451, 0.5043, \(-\)1.289, \(-\)2.2386, 0.0451, 0.4764, \(-\)1.2536, \(-\)2.0142, 0.045, 0.4571, \(-\)1.2129, \(-\)1.7898, 0.045, 0.4473, \(-\)1.169, \(-\)1.5655, 0.0451, 0.4475, \(-\)1.1239, \(-\)1.341, 3.1296, 1.1603, 1.9235, \(-\)0.3583, 0.3955, 1.5307, 2.0621, 0.4747, 4.2656, 5.3246, 0.1123, 1.0025, 0.1081, 5.3827, 0.0212, 1.5303, 0.1081, 5.3871, \(-\)0.0868, 2.0581, 0.1081, 3.2376, 0.4146, 3.3713, 2.5949, \(-\)1.6030, 17.5085)
Example 8 INPUT DATA
OBJECT A EX_8 and OBJECT B EX_8
\(l_A = l_B \) = (2.0, 7.0, 0, \(-\)4.0, \(-\)3.0, 0, 0, \(-\)5.0, \(-\)2.5, 1.5, \(-\)3.0, 3.0, \(-\)5.0, 0, 11.0, 0, \(-\)8.0623, 10.0, 8.0)
Example 8 OUTPUT DATA
Example 8.1 m = 6, \(u^{*}=(x_1^*,y_1^*,\theta _1^*,t_1^*,\ldots ,x_m^*,y_m^*,\theta _m^*,t_m^*,u_A^*,u_B^*)\) = (20.2289, \(-\)2.57832, 1.4978, 4.4721, 20.5550, \(-\)7.0386, 3.1454, 11.6619, 8.8932, \(-\)6.9943, \(-\)2.4381, 11.6619, 0.0000, 0.5497, \(-\)0.7467, 11.4018, 8.3684, 8.2938, 0.6766, 13.2450, 18.6952, 0.0000, 1.0342, 3.0000, 15.9317, \(-\)5.1345, 4.1758, 6.5824, \(-\)2.5603, 4.8755)
Example 8.2 m = 8, \(u^{*}=(x_1^*,y_1^*,\theta _1^*,t_1^*,\ldots ,x_m^*,y_m^*,\theta _m^*,t_m^*,u_A^*,u_B^*)\) = (0, 4.4189, \(-\)0.3471, 10.6193, 9.9858, 8.0318, 0.3941, 9.4340, 18.696, 4.4093, 0.9527, 3, 20.435, 1.9643, 1.4164, 4.4721, 21.123, \(-\)2.4546, 2.794, 10.6193, 11.1372, \(-\)6.0674, \(-\)2.7475, 9.434, 2.4264, \(-\)2.445, \(-\)2.1889, 3, 0.688, 0, \(-\)1.7252, 4.4721, 16.3601, \(-\)0.9331, 4.0943, 4.7629, 2.8974, 0.9527)
Example 9 INPUT DATA
Polygonal container \(K\) is given by a vector of coordinates of its vertices: \(K\): (0, 0, 19, 0, 30, 12, 18, 30)
OBJECT A EX_9
\(l_A \) = (30.5, 16, 0, 11.5, 16, 0, 0.5, 4, 0, 18.5, \(-\)4, 0)
OBJECT B EX_9
\(l_B \) = (10, 29.3333, 0, 22, 11.3333, 0, 28, 21.3333, 0)
OUTPUT DATA
\(u^*=(\alpha ^{*},u_A^*,u_B^*)\) = (1.0, 30.5, 16.0, \(-\)3.141593, 40.0, 41.333334, \(-\)9.4247779602)
Rights and permissions
About this article
Cite this article
Bennell, J., Scheithauer, G., Stoyan, Y. et al. Optimal clustering of a pair of irregular objects. J Glob Optim 61, 497–524 (2015). https://doi.org/10.1007/s10898-014-0192-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-014-0192-0