# rectangular-layout

**Repository Path**: Gxuliqin_admin/rectangular-layout

## Basic Information

- **Project Name**: rectangular-layout
- **Description**: 矩形排样算法，GA库jenetics
- **Primary Language**: Java
- **License**: GPL-3.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 3
- **Created**: 2024-08-20
- **Last Updated**: 2024-08-20

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

## 功能简介  
本功能是矩形排样算法，算法用的是GA库jenetics来做遗传算法，通过排序的逻辑，循环矩形，排进空余空间，最后得出面积占用率，占用率返回算法，然后基因迭代和优化，最后尽可能的把多矩形排进去  
由于每次迭代的方向可能不一样，出现的结果会不一样，利用率也会有细微差别  
排序逻辑还有点缺陷，就是合并空余点位的时候不够完善，目前处理的逻辑是合并两次，而较少情况可能出现可以多次合并多次的空余点位，这样会导致可能出现无法最大利用面积的情况  
## 目录说明
+ config：和排序逻辑没关系，放个swagger配置文件
+ constant：常量，直接改里面常量，不用代码里面改
+ controller：接口
+ entity：用到实体  
+ result：和排序逻辑没关系，返回结果包装  
+ resultShow：打印排序结果
+ service：排序逻辑
+ sort：遗传算法用的类，还有另外两个包jenetics和engine，都是算法相关的

## 使用说明
有两种使用方式  
1.通过controller接口直接调用，返回排序结果  
2.把排序结果用javafx启用，在resultShow中，将json赋值，直接看效果图

## 遗传算法参考代码
https://www.cnblogs.com/aarond/p/GA.html  
因为是抄的，就不做过多说明了，就是在原有基础上略微改动，用排序顺序作为遗传因子，尽量算出最大的面积利用率


## 项目接口访问地址
http://localhost:8081/doc.html#  
http://localhost:8081/swagger-ui/index.html#

## 矩形排样主要业务逻辑
+ 1.取（0,0）为最初的点位，包含的长度是容器的长和宽  
+ 2.矩形排入逻辑，优先寻找x坐标最小的点位，其次是y坐标，最后是包含的长宽能够装下矩形  
+ 3.如果增加的矩形所在范围，覆盖了空余的点位，那么删除这些点位，并且新增两个点位，左下角和右上角的点位增加点位后，新增加的点位左上角位置固定，覆盖的长和宽有范围限制  
    右上角长的范围：覆盖点位剩余的长度  
	右上角宽的范围：覆盖点位的宽度  
	左下角长的范围：覆盖点位的长度  
	左下角宽的范围：覆盖点位剩余的宽度  
+ 4.修改点位信息，因为空余点位会有相互覆盖的范围，排入一个矩形会影响其他的空余点位，所以修改有交集部分的空余点位信息
![avatar](sort_png1.png)  
+ 5.合并：如果左边界线属于某个空余点位的范围，那么扩展长度和减小左上角x坐标值；上边界线如果属于某个空余点位的范围，就像下图中打叉的红色点位和蓝色点位的关系
![avatar](sort_png2.png)  
+ 6.合并可能会导致增加重复的点位出现，所以再去一次重  
+ 7.重复2~6的过程，直到无法排入新的矩形,计算面积利用率，将此利用率返回遗传算法