Računalne metode prikladne za rješavanje problema pakiranja pri uklapanju krojnih slika

Daniel Domović; Tomislav Rolich

Autor(i)

Daniel Domović Tekstilno-tehnološki fakultet Sveučilišta u Zagrebu, Zavod za temeljne prirodne i tehničke znanosti, Zagreb, Hrvatska https://orcid.org/0000-0003-4576-7988
Tomislav Rolich Tekstilno-tehnološki fakultet Sveučilišta u Zagrebu, Zavod za temeljne prirodne i tehničke znanosti, Zagreb, Hrvatska https://orcid.org/0000-0003-0165-9555

Ključne riječi:

problem pakiranja, genetski algoritam, detekcija preklapanja, automatsko uklapanje krojnih slika, rasterska metoda, no-fitpoligon, metoda izravne trigonometrije, D-funkcija, grafovi ograničenja

Sažetak

U ovom je radu dan sustavan pregled problematike istraživanja dvodimenzionalnog problema računalnog uklapanja krojnih slika. Spomenuti problem i njegove podvrste osobito su proučavani u području računarske znanosti gdje su zajedničkim imenom opisani kao problem pakiranja. Problem pakiranja je u tome da se skup poligona mora umetnuti u veći spremnik (također poligon) uz uvjet da se poligoni u spremniku ne preklapaju, niti izlaze izvan granica spremnika. Svrha je minimiziranje površine slobodnog prostora između poligona, odnosno smanjenje površine spremnika. S obzirom na to da se problem pakiranja u praksi javlja u različitim industrijama, u radu je dan pregled podtipova problema pakiranja i njihova taksonomija, pregled metoda za detekciju preklapanja dvaju poligona: rasterska metoda, no-fit poligon, metoda izravne trigonometrije i D-funkcija, te grafovi ograničenja. Također, opisani su i neki od postojećih algoritama za rješavanje problema pakiranja.