Algoritma Nesting Pemotongan Plat di Browser: No-Fit Polygon dan Metaheuristik Jaya

Ada satu angka yang jarang muncul di laporan produksi bengkel fabrikasi: berapa persen plat yang berakhir jadi besi tua.

Angka itu diam-diam menentukan margin.

Tekanannya makin terasa ketika Kontan melaporkan bahwa impor menguasai sekitar 55% kebutuhan baja nasional sepanjang 2026 sementara utilisasi pabrik dalam negeri tertahan di kisaran 50%. Ketika harga bahan baku tidak bisa ditawar dan volume order tidak bisa dipaksa naik, satu-satunya variabel yang masih bisa dikendalikan adalah efisiensi material. Di titik itulah algoritma nesting pemotongan plat berhenti jadi urusan operator CAM, dan mulai jadi urusan kita — para developer.

Masalahnya bukan sepele.

Menyusun potongan berbentuk tidak beraturan di atas lembaran plat adalah persoalan kombinatorial yang sejak 1981 sudah dibuktikan NP-complete, sehingga tidak ada solusi eksak yang praktis untuk ukuran order nyata. Riset yang terbit di Journal of Computational Design and Engineering (Oxford Academic) menunjukkan pendekatan metaheuristik Jaya mampu memangkas area convex hull antara 20% sampai 38% pada dataset benchmark standar. Kami mengangkat tema ini karena celahnya nyata: banyak bengkel fabrikasi masih nesting manual, padahal tooling-nya bisa dibangun sendiri dan jalan penuh di browser.

Tidak butuh lisensi CAM enam digit.

Tidak butuh backend.

Cukup TypeScript, geometri komputasional, dan kesabaran menulis objective function yang tidak bohong.

TL;DR — Nesting yang bagus bukan soal algoritma paling canggih, tapi soal tiga lapisan yang jujur: geometri yang presisi (No-Fit Polygon), heuristik penempatan yang cepat (Bottom-Left-Fill), dan metaheuristik yang mengurutkan part tanpa perlu tuning parameter. Sisanya adalah constraint dunia nyata yang tidak pernah muncul di paper: kerf, grain direction, dan sisa plat yang harus dicatat.

1. Kenapa Sisa Potong Plat Adalah Masalah Software

Sebelum masuk ke geometri, kita perlu sepakat dulu bahwa ini bukan masalah estetika layout. Ini masalah uang, dan besarannya bisa dihitung. Pada industri berbasis lembaran, biaya bahan baku mendominasi struktur biaya produksi — di industri tekstil misalnya, material bisa menyerap 50–60% dari total biaya manufaktur, dan pola serupa berlaku di fabrikasi logam. Artinya, perbaikan beberapa persen di sisi utilisasi material punya leverage yang jauh lebih besar dibanding mempercepat mesin.

Yang Sebenarnya Kita Optimasi: Material Yield

Metrik utamanya sederhana: berapa persen luas plat yang benar-benar jadi part.

const yieldRatio = totalPartArea / (sheetCount * sheetArea);

Yang tidak sederhana adalah menaikkannya. Berikut ilustrasi dampaknya pada order fabrikasi bracket dengan konsumsi 1.000 lembar plat per bulan:

Angka di atas ilustratif, tapi rasionya realistis. Selisih 9 poin persentase saja sudah setara belanja engineer setahun.

Kenapa Ini Bukan Sekadar "Susun yang Rapi"

Operator berpengalaman sering menghasilkan layout yang setara software komersial — dan itu bukan mitos, riset akademik pun mengakuinya. Yang tidak bisa dilakukan manusia adalah mengulang kualitas itu 400 kali sehari, konsisten, tanpa lelah, sambil memperhitungkan sisa plat dari job kemarin.

Di sinilah software menang: bukan karena lebih pintar, tapi karena tidak pernah bosan.

Konteks ini juga yang membuat topiknya relevan buat siapa pun yang membangun sistem untuk penyedia layanan fabrikasi plat, stamping, dan konstruksi industri — karena kebutuhan mereka bukan dashboard cantik, tapi angka scrap yang turun.

2. Anatomi Masalahnya: 2D Irregular Packing

Sebelum menulis satu baris kode, kita harus tahu persis kelas masalah apa yang sedang dihadapi. Salah klasifikasi di tahap ini akan membuat kita memilih struktur data yang salah, dan itu mahal untuk diperbaiki belakangan.

Strip Packing vs Bin Packing

Dua varian ini sering tertukar, padahal objective-nya berbeda:

• 2D Strip Packing — lebar lembaran tetap, panjang dianggap tak terbatas. Tujuan: meminimalkan panjang terpakai. Cocok untuk coil.
• 2D Bin Packing — dimensi lembaran tetap. Tujuan: meminimalkan jumlah lembaran. Ini kasus mayoritas bengkel plat.

Keduanya masuk keluarga cutting and packing problems. Versi persegi panjangnya sudah terbukti NP-complete, dan versi bentuk tidak beraturan jelas tidak lebih mudah. Konsekuensi praktisnya: lupakan solusi optimal, kejar solusi bagus dalam waktu yang bisa diterima.

Kenapa Bounding Box Selalu Boros

Pendekatan naif adalah membungkus setiap part dengan bounding box, lalu menyusun kotak-kotak itu. Cepat ditulis, mudah di-debug, dan langsung terasa salah begitu part-nya berbentuk L atau punya lekukan.

Bracket berbentuk L bisa kehilangan 40% area hanya karena dibungkus persegi panjang.

Padahal dua bracket L yang diputar 180 derajat bisa saling mengunci nyaris sempurna.

Itulah kenapa kita butuh geometri yang lebih jujur.

3. No-Fit Polygon: Fondasi Geometri Algoritma Nesting Pemotongan Plat

Inilah bagian yang membuat seluruh sistem mungkin. Tanpa representasi geometri yang tepat, metaheuristik secanggih apa pun hanya akan mengaduk-aduk solusi yang sama-sama salah. No-Fit Polygon (NFP) adalah struktur yang mengubah pertanyaan "apakah dua poligon bertabrakan?" menjadi pertanyaan yang jauh lebih murah.

Cara Kerja NFP Secara Intuitif

Bayangan mentalnya begini: kunci poligon A di tempatnya, lalu geser poligon B mengelilingi A sambil terus menempel tanpa pernah tumpang tindih. Jejak yang ditinggalkan titik referensi B selama perjalanan itu adalah NFP-nya.

Konsekuensinya elegan:

• Titik referensi B di dalam NFP → dua part tumpang tindih.
• Titik referensi B di garis NFP → dua part bersentuhan sempurna.
• Titik referensi B di luar NFP → dua part terpisah.

Cek tabrakan yang tadinya butuh iterasi antar-edge berubah jadi satu tes point-in-polygon. Untuk poligon konveks, NFP bisa dihitung langsung lewat Minkowski sum. Untuk poligon konkaf — dan hampir semua part fabrikasi itu konkaf — urusannya jauh lebih berduri. NFP sendiri sebenarnya adalah kasus khusus dari phi-function, representasi yang lebih umum untuk posisi relatif dua objek.

Minkowski Sum, Clipper, dan Jebakan Floating Point

Jangan tulis operasi boolean poligon dari nol. Serius.

Pakai pustaka yang sudah teruji:

npm install polygon-clipping   # boolean ops, robust
npm install martinez-polygon-clipping

Tiga jebakan yang akan menemui Anda dalam 48 jam pertama:

1. Presisi floating point. Koordinat DXF sering punya 6+ desimal. Snap ke grid integer (misal 0,01 mm) sebelum operasi boolean, atau siap-siap dapat sliver polygon berluas 1e-13.
2. Orientasi winding. Konvensi CCW untuk outer boundary, CW untuk hole. Salah satu saja terbalik, seluruh perhitungan NFP jadi sampah.
3. Cache NFP. Menghitung NFP itu mahal. Untuk 40 part unik dengan 4 sudut rotasi, ada 25.600 pasangan. Precompute sekali, simpan di Map dengan key ${idA}-${rotA}-${idB}-${rotB}.

4. Lapisan Pencarian: Dari Bottom-Left-Fill ke Metaheuristik

NFP memberi tahu kita di mana sebuah part boleh diletakkan, bukan di mana ia sebaiknya diletakkan. Untuk itu kita butuh dua lapisan tambahan: heuristik penempatan yang cepat, dan algoritma pencarian yang menentukan urutan serta rotasi.

BLF sebagai Placement, Metaheuristik sebagai Sequencer

Bottom-Left-Fill adalah strategi klasik: dorong setiap part sejauh mungkin ke bawah, lalu sejauh mungkin ke kiri, ambil posisi valid pertama. Cepat, deterministik, dan hasilnya sangat bergantung pada urutan part yang masuk.

Nah, urutan itulah yang dicari metaheuristik.

Beberapa opsi yang paling sering dipakai di literatur:

Jaya menarik justru karena kesederhanaannya. Ia tidak punya parameter kontrol spesifik — cukup tentukan ukuran populasi dan jumlah iterasi. Prinsipnya satu kalimat: dekati solusi terbaik, jauhi solusi terburuk.

// inti update Jaya, per variabel, per anggota populasi
const r1 = Math.random();
const r2 = Math.random();
xNew = x + r1 * (xBest - x) - r2 * (xWorst - x);

Riset JCDE juga menemukan korelasi kuat antara jumlah part dan ukuran populasi optimal — jadikan jumlah part sebagai estimasi awal populasi Anda. Aturan praktis yang lumayan akurat.

Objective Function yang Tidak Menghukum Terlalu Keras

Ini bagian yang paling sering salah, dan paling menentukan.

Godaannya adalah memberi nilai tak hingga pada setiap layout yang tumpang tindih. Jangan. Solusi yang tumpang tindih tipis sering kali adalah tetangga dari solusi terbaik, dan membuangnya berarti memutus jalan menuju optimum.

Pendekatan yang dipakai di paper JCDE jauh lebih halus: ketika terjadi tabrakan, nilai objective diambil dari solusi terbaik saat ini ditambah penalti proporsional terhadap jumlah tabrakan.

function evaluate(layout: Layout, bestF: number): number {
  let f = convexHullArea(layout);
  const collisions = countCollisions(layout);

  if (collisions > 0) {
    f = bestF + (Math.abs(f - bestF) + 0.01) * collisions;
  }
  if (exceedsSheetBounds(layout)) {
    f = f * 2;
  }
  return f;
}

Satu catatan jujur soal keterbatasannya: convex hull tidak bisa membedakan pemanfaatan lubang atau area konkaf. Dua layout dengan hull identik bisa punya utilisasi nyata yang berbeda jauh. Untuk produksi, ganti metriknya dengan luas bounding rectangle aktual atau langsung hitung sheet utilization.

5. Arsitektur di Browser: Web Worker, WASM, dan Alasan Tidak Perlu Backend

Pertanyaan yang selalu muncul: kenapa tidak dijalankan di server saja? Jawabannya bukan ideologis, tapi praktis — file DXF milik klien itu sensitif, latensi upload-download memperlambat iterasi, dan biaya compute untuk ribuan iterasi metaheuristik tidak murah kalau dibebankan ke server. Menjalankan algoritma nesting pemotongan plat sepenuhnya di sisi klien menyelesaikan ketiganya sekaligus.

Pembagian Beban

Main Thread
 ├── UI, form, kontrol parameter
 └── Rendering hasil (Canvas 2D / SVG)

Web Worker #1
 └── Parsing DXF → normalisasi poligon → simplifikasi

Web Worker #2..N
 └── Precompute NFP (paralel per pasangan part)

Web Worker (dedicated)
 └── Loop metaheuristik + BLF
      └── postMessage progres tiap N iterasi

Poin-poin arsitektural yang penting:

• Jangan pernah jalankan loop optimasi di main thread. UI akan beku dan pengguna akan menutup tab sebelum iterasi ke-200.
• Kirim progres secara berkala, bukan setiap iterasi. postMessage punya biaya serialisasi.
• Untuk operasi boolean poligon yang berat, kompilasi Clipper ke WebAssembly memberi percepatan 3–8× dibanding implementasi JS murni.
• Gunakan Transferable (ArrayBuffer) untuk mengirim koordinat antar-worker, bukan array objek.

Rendering dan UX

Canvas 2D cukup sampai sekitar 500 part. Di atas itu, pertimbangkan WebGL atau render hanya bounding box saat animasi berlangsung, lalu render detail penuh ketika iterasi berhenti.

Satu detail UX yang sering dilupakan: tampilkan grafik konvergensi.

Operator perlu tahu kapan harus berhenti menunggu.

6. Constraint Dunia Nyata yang Diabaikan Hampir Semua Paper

Di sinilah jarak antara riset dan produksi terasa paling lebar. Algoritma yang menang di dataset Albano atau Jakobs bisa menghasilkan layout yang secara fisik tidak bisa dipotong. Constraint berikut wajib masuk sebelum sistem Anda dipakai orang sungguhan.

Kerf, Grain Direction, dan Lead-In

• Kerf — plasma cutting memakan material selebar 1,5–4 mm tergantung ketebalan dan arus. Offset ini harus masuk ke perhitungan NFP, bukan ditambahkan belakangan.
• Grain direction — untuk part struktural, arah serat pelat membatasi rotasi yang diizinkan. Sering kali hanya 0° dan 180° yang boleh, bukan bebas 360°.
• Lead-in / lead-out — torch butuh ruang untuk memulai dan mengakhiri potongan. Part yang menempel sempurna secara geometris bisa gagal dipotong karena tidak ada ruang lead-in.
• Common-line cutting — dua part yang berbagi satu garis potong menghemat material sekaligus waktu. Ini bonus besar, tapi menuntut toleransi ketat.

Dokumentasikan Aturannya, Bukan Cuma Kodenya

Semua constraint di atas adalah tribal knowledge. Ia hidup di kepala kepala workshop, bukan di repositori.

Dan begitu orang itu pindah kerja, sistem Anda kehilangan konteks kenapa MIN_LEAD_IN = 8 bukan 5.

Ben Halpern, pendiri DEV, menulis argumen yang pas untuk situasi ini dalam The Myth of the Post-Documentation Era — bahwa kode menjelaskan logika, tapi hanya dokumentasi yang menjelaskan maksud. Untuk nesting engine, maksud itu justru yang paling mahal kalau hilang.

Tulis alasan di balik setiap konstanta. Validasi angkanya langsung ke workshop — cara paling cepat adalah duduk bersama tim yang menangani bending, shearing, plasma cutting, dan pengelasan setiap hari, karena mereka yang tahu kenapa toleransi 2 mm masuk akal di plat 6 mm tapi tidak di plat 20 mm.

7. HowTo: Membangun MVP Nesting Engine dalam Tujuh Langkah

Bagian ini adalah jalur tercepat dari nol ke prototipe yang bisa didemokan. Targetnya bukan produk komersial, melainkan bukti bahwa algoritma nesting pemotongan plat bisa berjalan di browser dengan hasil yang lebih baik daripada susun manual. Alokasikan sekitar dua minggu kerja.

Langkah demi Langkah

1. Parsing input. Baca DXF, ekstrak entity LWPOLYLINE dan POLYLINE, konversi jadi array koordinat. Abaikan layer dimensi dan teks.
2. Normalisasi geometri. Tutup poligon terbuka, perbaiki winding order, jalankan simplifikasi Douglas-Peucker dengan toleransi 0,05 mm untuk memangkas jumlah verteks.
3. Terapkan offset kerf. Buffer setiap poligon sebesar setengah lebar kerf ditambah safety margin.
4. Precompute NFP. Hitung untuk setiap pasangan part pada setiap sudut rotasi yang diizinkan. Simpan di cache. Jalankan di Web Worker terpisah.
5. Implementasi BLF. Tulis fungsi penempatan yang menerima urutan part dan mengembalikan layout beserta metrik utilisasi.
6. Pasang metaheuristik. Mulai dengan Jaya karena tanpa parameter. Set populasi setara jumlah part, iterasi 5.000, dengan early stopping ketika tidak ada perbaikan selama 500 iterasi.
7. Ekspor hasil. Keluarkan DXF layout final plus laporan JSON berisi utilisasi, jumlah lembar, dan daftar sisa plat yang layak disimpan.

Schema HowTo (JSON-LD)

Tempel di halaman dokumentasi proyek Anda agar langkah-langkahnya layak muncul sebagai rich result:

{
  "@context": "https://schema.org",
  "@type": "HowTo",
  "name": "Membangun Nesting Engine 2D di Browser",
  "description": "Panduan membangun algoritma nesting pemotongan plat berbasis No-Fit Polygon dan metaheuristik yang berjalan penuh di sisi klien.",
  "totalTime": "P14D",
  "tool": [
    { "@type": "HowToTool", "name": "TypeScript" },
    { "@type": "HowToTool", "name": "polygon-clipping" },
    { "@type": "HowToTool", "name": "Web Workers API" }
  ],
  "step": [
    { "@type": "HowToStep", "position": 1, "name": "Parsing input DXF", "text": "Ekstrak entity LWPOLYLINE dan POLYLINE menjadi array koordinat." },
    { "@type": "HowToStep", "position": 2, "name": "Normalisasi geometri", "text": "Perbaiki winding order dan sederhanakan verteks dengan toleransi 0,05 mm." },
    { "@type": "HowToStep", "position": 3, "name": "Terapkan offset kerf", "text": "Buffer poligon sebesar setengah lebar kerf ditambah safety margin." },
    { "@type": "HowToStep", "position": 4, "name": "Precompute No-Fit Polygon", "text": "Hitung NFP tiap pasangan part per sudut rotasi, simpan dalam cache." },
    { "@type": "HowToStep", "position": 5, "name": "Implementasi Bottom-Left-Fill", "text": "Tempatkan part sesuai urutan masukan dan kembalikan metrik utilisasi." },
    { "@type": "HowToStep", "position": 6, "name": "Pasang metaheuristik", "text": "Gunakan algoritma Jaya dengan populasi setara jumlah part dan early stopping." },
    { "@type": "HowToStep", "position": 7, "name": "Ekspor hasil", "text": "Hasilkan DXF layout final beserta laporan utilisasi dan daftar sisa plat." }
  ]
}

8. Pertanyaan yang Sering Muncul

Beberapa pertanyaan ini berulang setiap kali topik nesting dibahas di forum developer maupun di ruang meeting produksi. Jawabannya saya ringkas sependek mungkin.

Apakah algoritma nesting pemotongan plat harus pakai machine learning?

Tidak. Untuk mayoritas kasus, metaheuristik klasik seperti Jaya, GA, atau SA sudah memberi hasil yang sangat kompetitif dengan biaya komputasi jauh lebih rendah dan tanpa kebutuhan data latih. ML baru masuk akal ketika Anda punya ribuan layout historis dan ingin memprediksi urutan awal yang bagus.

Berapa lama waktu komputasi yang wajar?

Untuk 50–80 part di satu lembaran, target 10–30 detik di browser modern sudah realistis. Di atas 200 part, pertimbangkan strategi clustering: kelompokkan part serupa lebih dulu, nesting per klaster, baru gabungkan.

Kenapa hasil saya lebih buruk daripada operator manual?

Hampir selalu karena tiga hal: rotasi yang diizinkan terlalu sedikit, objective function memakai bounding box alih-alih geometri asli, atau iterasi berhenti terlalu cepat. Periksa ketiganya secara berurutan.

Apakah pendekatan ini bisa dipakai untuk laser dan waterjet?

Bisa, dan justru lebih mudah. Kerf laser dan waterjet lebih kecil dan lebih konsisten dibanding plasma, sehingga toleransi jarak antar-part bisa lebih rapat.

Library open source apa yang layak dilirik dulu?

polygon-clipping untuk operasi boolean, dxf-parser untuk input, dan svgnest sebagai referensi implementasi NFP + GA yang bisa dibaca kodenya. Jangan pakai mentah-mentah — baca, pahami, lalu tulis versi Anda dengan constraint yang sesuai.

Efisiensi Itu Dibangun di Layar, Bukan Ditemukan di Mesin

Menutup artikel ini, ada satu hal yang layak digarisbawahi: nesting engine yang baik bukan yang paling rumit, melainkan yang paling jujur terhadap constraint di lantai produksi. Anda bisa menghabiskan tiga bulan menyempurnakan implementasi phi-function, lalu kalah oleh kompetitor yang cuma pakai BLF sederhana tapi sudah memasukkan grain direction dan manajemen sisa plat sejak minggu pertama.

Urutannya penting. Benar dulu, baru cepat.

Donald Knuth merangkumnya dalam kalimat yang sudah jadi doktrin di kalangan programmer:

"Premature optimization is the root of all evil."

Knuth adalah profesor emeritus Stanford dan penulis The Art of Computer Programming, karya rujukan utama untuk analisis algoritma — termasuk kelas masalah kombinatorial yang jadi fondasi nesting. Peringatannya sangat relevan di sini: godaan terbesar saat membangun nesting engine adalah mengejar algoritma tercanggih sebelum sempat mengukur utilisasi baseline. Ukur dulu berapa persen yield yang dihasilkan operator Anda hari ini. Baru setelah angka itu ada di layar, Anda tahu optimasi mana yang benar-benar layak dikejar.

Sisa plat yang menumpuk di sudut workshop itu bukan takdir industri.

Itu bug yang belum diperbaiki.

Kalau Anda pernah membangun atau memaksa nesting engine masuk ke lini produksi nyata, saya penasaran dengan constraint paling aneh yang pernah Anda temui. Tulis di komentar.