Convex Hull-Based Laser Cutting Layout Optimization System

An interactive design and layout optimization system developed for simulating industrial laser cutting workflows. This tool enables users to custom-design 2D shapes, automatically compute their convex hulls, and arrange them using a greedy packing algorithm that minimizes material waste.

Empirical testing across 100-trial benchmarks shows that the system achieves high packing density, with fabric usage averaging 50% for triangular shapes (where the shape matches roughly half of its bounding box), 60.03% for 4-point shapes, 63.97% for 5-point shapes, and 68.14% for 6-point shapes (with optimal layouts reaching up to 90% utilization). As the number of vertices increases, the computed convex hulls more closely approximate stable, packable geometries, leading to higher efficiency and more consistent layout optimization.

---

Authors

• Authors:
  • Alkım Gönenç Efe
  • Sarp Sünbül

---

System Workflow & Algorithm Overview

graph TD
    A[User Input: Click Canvas] --> B[Store & Plot Control Points]
    B --> C[Compute Convex Hull via Quickhull]
    C --> D[Determine Dimensions & Aspect Ratio via PCA]
    D --> E{Aspect Ratio > 25?}
    E -- Yes --> F[Show Aspect Ratio Error]
    E -- No --> G[Iterate 360° Rotations]
    G --> H[Greedy Packing: Find Best Fit Spacing]
    H --> I[Overlap Checks via Shapely intersects]
    I --> J[Evaluate Fabric Utilization %]
    J --> K[Select & Display Layout with Max Fabric Usage]

Loading

Key Components

1. Interactive Shape Canvas (Tkinter GUI)
   • Provides a $50 \times 50$ px grid canvas. Users define custom parts/polygons by clicking to place control points.
2. Convex Hull Computation
   • Uses the Quickhull algorithm (via scipy.spatial.ConvexHull) to construct the smallest convex polygon enclosing the user-defined points.
3. Dimensional Analysis via PCA
   • Uses Principal Component Analysis (PCA) to calculate the covariance matrix and eigenvalues of the centered shape coordinates.
   • Aligns the shape's bounding dimensions to its principal axes rather than the axis-aligned coordinate system, finding the true width and height of the shape.
   • Automatically rejects shapes with an aspect ratio $> 25$ to maintain stability.
4. Greedy Layout Optimization
   • Evaluates the layout across all 360 degrees of rotation.
   • Performs horizontal and vertical distance calculations (find_best_fit_distance and find_best_fit_distance_scalable) using a precision-scaled step matching.
   • Detects overlaps between polygons using the Separating Axis Theorem (via shapely.geometry.Polygon.intersects).
5. Visualization
   • Displays the convex hull boundary of the designed shape.
   • Renders the fully packed $1000 \times 200$ px cutting area using matplotlib along with the final fabric usage percentage.

---

Time Complexity Analysis

Function	Description	Time Complexity
on_canvas_click	Registers mouse clicks and draws points	$\mathcal{O}(1)$
calculate_convex_hull	Converts points and computes the hull (Quickhull)	$\mathcal{O}(n \log n)$ where $n$ is the number of points
optimize_placement	Rotates the shape over $360^\circ$ and calculates distances	$\mathcal{O}(m \cdot k^2 \cdot p)$ where $m$ is the number of shifts, $k$ is the number of vertices, and $p$ is the precision factor
calculate_fabric_usage	Computes the area of the shape and total usage	$\mathcal{O}(k)$ where $k$ is the number of vertices

---

Installation & Setup

Prerequisites

• Python 3.8 or higher is required.

Dependencies

Install the required packages using pip:

pip install numpy scipy matplotlib shapely

(Note: tkinter is standard on most Python installations. If you are on Linux, you may need to install python3-tk)

---

Usage Instructions

1. Run the application:

   python "Laser Cutting Algorithm.py"

2. Draw a shape: Left-click on the white canvas window to define at least 3 control points.
3. Optimize the layout: Click the Calculate Convex Hull button.
4. Inspect the output:
   • A pop-up showing the shape's calculated Convex Hull.
   • A second pop-up displaying the Optimized Cutting Layout showing packed items on the sheet.
   • The final fabric usage statistic displayed directly in the GUI.