• zh_CN 简体中文

Polygon Pairwise Clustering

Overview

This project implements a polygon pairwise clustering algorithm based on the No-Fit Polygon (NFP) concept, as described in the paper "A new approach for sheet nesting problem using guided cuckoo search and pairwise clustering" by Ahmed Elkeran (2013). The algorithm computes the optimal placement of two polygons by considering their rotations and translations to maximize clustering efficiency, focusing on concave NFPs. It uses the shapely library for geometric operations and is designed for applications in sheet nesting and computational geometry.

Features

• Computes No-Fit Polygons (NFPs) for two polygons.
• Supports multiple rotation angles for both polygons.
• Calculates cluster values based on convex hull differences and union areas.
• Visualizes the resulting polygon placements using a plotting utility.

Installation

1. Clone the repository:

   git clone https://github.com/la667-j/PolygonPairwise.git
   cd PolygonPairwise
   git clone https://github.com/la667-j/SimpleNFP.git

2. Install the required dependencies:

   pip install shapely

   Note: The utils.Point, utils.Geometry, utils.Plot, and nfp modules are assumed to be custom implementations. Ensure these are available in your project directory or implement them as needed.

Usage

1. Define two polygons using the Point class and create PwPolygon objects.
2. Specify allowed rotation angles for each polygon.
3. Run the clustering algorithm to obtain the optimal placement.
4. Visualize the results using the Plot utility.

Example

from Pairwise.polygon_pairwise import PolygonPairwise
from Pairwise.PwPolygon import PwPolygon
from utils.Point import Point
from utils import Plot

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)]
pointsB = [Point(0, 0), Point(10, -5), Point(20, 10), Point(15, 5), Point(0, 0)]

pwPolygonA = PwPolygon(pointsB)
rotsA = [0, 45, 90, 135, 180] # A allowed angles
pwPolygonB = PwPolygon(pointsB)
rotsB = [0, 45, 90, 135, 180] # B allowed angles

result = PolygonPairwise.cluster(pwPolygonA, pwPolygonB, rotsA, rotsB)
if len(result) == 0:
    print("No concave NFP found")
else:
    Plot.plot_polygons_with_shifted_pair(pwPolygonA.points, pwPolygonB.points, result[0].points, result[1].points)

Screenshots

1. Example1: The final placement of the polygons after clustering.
   

2. Example2: The final placement of the polygons after clustering.
   

3. Example3: The final placement of the polygons after clustering.
   

Reference

This implementation is based on the following paper:
Elkeran, A. (2013). A new approach for sheet nesting problem using guided cuckoo search and pairwise clustering. Engineering Optimization, 45(6), 739–756. DOI: 10.1080/0305215X.2012.709517.

License

This project is licensed under the MIT License - see the LICENSE file for details.