Skip to content

Latest commit

 

History

History
74 lines (59 loc) · 3.48 KB

README_zh.md

File metadata and controls

74 lines (59 loc) · 3.48 KB

多边形配对聚类

项目概述

本项目实现了基于无适配多边形（No-Fit Polygon, NFP）概念的多边形配对聚类算法，参考了 Ahmed Elkeran 在 2013 年发表的论文《A new approach for sheet nesting problem using guided cuckoo search and pairwise clustering》。该算法通过考虑两个多边形的旋转和平移，计算其最优放置位置，以最大化聚类效率，特别关注凹形 NFP。项目使用 shapely 库进行几何运算，适用于板材排样和计算几何等应用场景。

功能

  • 计算两个多边形的无适配多边形（NFP）。
  • 支持多边形的多种旋转角度。
  • 基于凸包差和联合面积计算聚类值。
  • 使用绘图工具可视化多边形放置结果。

安装

  1. 克隆仓库： 
    git clone https://github.com/la667-j/PolygonPairwise.git
cd PolygonPairwise
git clone https://github.com/la667-j/SimpleNFP.git
  2. 安装依赖项： 
    pip install shapely
    注意：utils.Point、utils.Geometry、utils.Plot 和 nfp 模块为自定义实现。请确保这些模块在您的项目目录中可用，或根据需要实现这些模块。

使用方法

  1. 使用 Point 类定义两个多边形并创建 PwPolygon 对象。
  2. 为每个多边形指定允许的旋转角度。
  3. 运行聚类算法以获取最优放置位置。
  4. 使用 Plot 工具可视化结果。

示例代码

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 允许旋转的角度
pwPolygonB = PwPolygon(pointsB)
rotsB = [0, 45, 90, 135, 180] # B 允许旋转的角度

result = PolygonPairwise.cluster(pwPolygonA, pwPolygonB, rotsA, rotsB)
if len(result) == 0:
    print("不存在NFP为凹多边形的情况")
else:
    Plot.plot_polygons_with_shifted_pair(pwPolygonA.points, pwPolygonB.points, result[0].points, result[1].points)

截图

  1. 举例1：多边形聚类结果。
    聚类结果

  2. 举例2：多边形聚类结果。
    聚类结果

  3. 举例3：多边形聚类结果。
    聚类结果

参考文献

本实现参考以下论文：
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。

论文解释

Ahmed Elkeran 的论文提出了一种解决板材排样问题的新方法，结合了引导布谷鸟搜索（Guided Cuckoo Search）和配对聚类技术。板材排样问题是一个优化问题，目标是将多个不规则形状的多边形高效地排列在一块有限的板材上，以最小化材料浪费。论文中的配对聚类方法通过计算两个多边形的无适配多边形（NFP），并基于凹形 NFP 确定最优的相对位置和旋转角度，从而提高排列的紧凑性。本项目实现了论文中描述的配对聚类部分，重点关注凹形 NFP 的计算和基于凸包差的聚类值评估。

许可证

本项目采用 MIT 许可证，详情请见 LICENSE 文件。