Decoupling Geometry from Optimization in 2D Irregular Cutting and Packing Problems: An Open-Source Collision Detection Engine

References

• Agafonkin V (2016) Polylabel: A fast algorithm for finding the pole of inaccessibility of a polygon. https://github.com/mapbox/polylabel.Google Scholar
• Antonio F IV (1992) Faster line segment intersection. Kirk D, ed. Graphics Gems III (IBM Version) (Morgan Kaufmann, San Francisco), 199–202.Crossref, Google Scholar
• Baldacci R, Boschetti MA, Ganovelli M, Maniezzo V (2014) Algorithms for nesting with defects. Discrete Appl. Math. 163:17–33.Crossref, Google Scholar
• Bennell JA, Oliveira JF (2008) The geometry of nesting problems: A tutorial. Eur. J. Oper. Res. 184(2):397–415.Crossref, Google Scholar
• Bentley JL, Ottmann T (1979) Algorithms for reporting and counting geometric intersections. IEEE Trans. Comput. C-28(9):643–647.Crossref, Google Scholar
• Douglas DH, Peucker TK (1973) Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. Cartographica 10(2):112–122.Crossref, Google Scholar
• Ericson C (2004) Real-Time Collision Detection (CRC Press, Boca Raton, FL).Crossref, Google Scholar
• Finkel RA, Bentley JL (1974) Quad trees a data structure for retrieval on composite keys. Acta Inform. 4:1–9.Crossref, Google Scholar
• Fisher PF, Zhou S, Jones CB (2005) Shape-aware line generalisation with weighted effective area. Developments Spatial Data Handling: 11th Internat. Sympos. Spatial Data Handling (Springer, Berlin, Heidelberg), 369–380.Google Scholar
• Gardeyn J (2025) jagua-rs: A fast and fearless collision detection engine for 2D nesting problems. https://doi.org/10.1287/ijoc.2024.1025.cd, https://github.com/INFORMSJoC/2024.1025.Google Scholar
• Gardeyn J, Vanden Berghe G, Wauters T (2025) An open-source heuristic to reboot 2d nesting research. Preprint, submitted September 5, https://arxiv.org/abs/2509.13329.Google Scholar
• Haralick RM, Elliott GL (1980) Increasing tree search efficiency for constraint satisfaction problems. Artificial Intelligence 14(3):263–313.Crossref, Google Scholar
• Heisler B, Aparicio J (2014) Criterion.rs: Statistics-driven benchmarking library for Rust. https://github.com/bheisler/criterion.rs.Google Scholar
• Heistermann J, Lengauer T (1995) The nesting problem in the leather manufacturing industry. Ann. Oper. Res. 57(1):147–173.Crossref, Google Scholar
• Ma H, Liu CC (2007) Fast nesting of 2-D sheet parts with arbitrary shapes using a greedy method and semi-discrete representations. IEEE Trans. Automation Sci. Engrg. 4(2):273–282.Crossref, Google Scholar
• Mészáros T (2018) Libnest2d. https://github.com/tamasmeszaros/libnest2d.Google Scholar
• Oliveira JF, Gomes AM, Ferreira JS (2000) TOPOS–A new constructive algorithm for nesting problems. OR-Spektrum 22:263–284.Crossref, Google Scholar
• Preparata F, Shamos M (1985) Computational Geometry: An Introduction, Texts and Monographs in Computer Science (Springer, New York).Crossref, Google Scholar
• Rocha P, Rodrigues R, Toledo FM, Gomes AM (2013) Circle covering using medial axis. IFAC Proc. Volumes 46(7):402–407.Crossref, Google Scholar
• Segenreich SA, Braga LMPF (1986) Optimal nesting of general plane figures: A Monte Carlo heuristical approach. Comput. Graphics 10(3):229–237.Crossref, Google Scholar
• Shimrat M (1962) Algorithm 112: Position of point relative to polygon. Comm. ACM 5(8):434.Crossref, Google Scholar
• Shusterman E, Feder M (1994) Image compression via improved quadtree decomposition algorithms. IEEE Trans. Image Processing 3(2):207–215.Crossref, Google Scholar
• Visvalingam M, Whyatt JD (1993) Line generalisation by repeated elimination of points. Cartography J. 30(1):46–51.Crossref, Google Scholar
• Wang Z, Müller JC (1998) Line generalization based on analysis of shape characteristics. Cartography Geographic Inform. Systems 25(1):3–15.Crossref, Google Scholar