• zh_CN 简体中文

Polygon Nesting with Lattice Algorithm

This repository implements a lattice-based algorithm for nesting irregular polygons on a rectangular sheet, optimizing the arrangement to maximize the number of polygons while minimizing the occupied space. The algorithm is inspired by the paper Heuristic approaches to large-scale periodic packing of irregular shapes on a rectangular sheet by M. Teresa Costa, A. Miguel Gomes, and José F. Oliveira.

Features

• Polygon Nesting: Efficiently nests irregular polygons on a rectangular sheet using a lattice-based approach.
• Rotation Support: Supports multiple rotation angles for polygons to explore various configurations.
• Visualization: Uses Plotly to visualize the nested polygons and the sheet.
• Non-Feasible Polygon (NFP): Computes NFP to determine valid placement vectors (v0, v1) for lattice construction.
• Customizable Parameters: Allows customization of sheet dimensions, number of parts, and rotation angles.

Installation

1. Clone the repository:

   git clone https://github.com/la667-j/NestingLattice.git

2. Install dependencies:

   pip install -r requirements.txt

3. Ensure you have Python 3.8+ and the required libraries (plotly, etc.).

Usage

The main script (main.py) demonstrates how to use the Lattice class to nest polygons. Below is an example of how to run the code:

from lattice.Lattice import Lattice
from utils.Point import Point
from lattice.Sheet import Sheet

# Define polygon points
pointsA = [Point(0, 0), Point(10, -5), Point(20, 2), Point(30, -10), Point(44, 5),
           Point(25, 20), Point(15, 20), Point(10, 10), Point(0, 10), Point(0, 0)]
angles = [i * 10 for i in range(36)]  # Rotation angles from 0 to 350 degrees
sheet = Sheet(200, 300, 600)  # Sheet dimensions（300*600） and number of parts（200）

# Initialize and run nesting
lattice = Lattice(pointsA, angles, sheet)
latticeResult = lattice.nesting()

# Visualize the result
lattice.plot_polygons(latticeResult, sheet)

Examples

Below are three example outputs of the nesting algorithm for different polygon shapes:

How It Works

1. Initialization: The Lattice class takes a list of Point objects defining a polygon, a list of rotation angles, and a Sheet object specifying the rectangular area.
2. NFP Calculation: For each rotation angle, the algorithm computes the Non-Feasible Polygon (NFP) to determine valid translation vectors (v0, v1).
3. Lattice Iteration: The algorithm iterates through possible lattice configurations, calculating valid placements within the sheet boundaries.
4. Optimization: The best configuration is selected based on the number of nested polygons and the maximum X-coordinate (minimizing waste).
5. Visualization: The final arrangement is visualized using Plotly, showing the nested polygons and the sheet.

Dependencies

• Python 3.8+
• Plotly (pip install plotly)
• Custom modules: utils.Point, utils.Geometry, lattice.Polygon, lattice.Sheet, lattice.LatticeSolution, lattice.LatticeResult, nfp.Nfp

Reference

This implementation is based on the following paper:

• M. Teresa Costa, A. Miguel Gomes, José F. Oliveira. Heuristic approaches to large-scale periodic packing of irregular shapes on a rectangular sheet. European Journal of Operational Research, 2013.