单元格法近似求解多边形最大内接矩形问题【思路讲解+java实现】

文章目录

  • 问题描述
  • 问题解决方案
    • 多边形网格化
    • 区分每个单元格是在多边形内部还是外部
    • 根据已标记单元格寻找最大内接矩形
    • 剪枝优化
    • 多角度旋转
  • 案例测试
  • 代码实现
  • 说明

问题描述

给定一个多边形的点集,希望找出多边形内部面积最大的矩形。该问题可能出现在,从一个多边形废料上面切割出一个最大的矩形,该矩形可以重复利用,解决该问题可以节约原材料,降低企业运作成本

问题解决方案

本文主要使用的方法是:将多边形离散化为多个单元格,然后判断哪些单元格处于多边形内部,最后通过遍历内部的单元格来找到面积最大的矩形

多边形网格化

已知每个多边形点集中的每个点的坐标为(y,z),通过遍历所有点,可以找出minY,maxY,minZ,maxZ,本文使用一个参数segmentNum来决定y轴方向上对多边形多离散的段数,dis=(maxY-minY)/segmentNum为步进长度,每间隔一个步进长度生成一条垂直于于y轴的扫描线,该扫描线会与多边形相交,本文将相交点的z坐标值生成为一条垂直于z轴的扫描线。最终待垂直于y轴或z轴的扫描线都生成完毕之后,会得到如下图所示的网格

在这里插入图片描述

segmentNum=5对应的网格

在这里插入图片描述

segmentNum=100对应的网格

需要注意的是,为了加快计算速度,可以使用一定的策略来筛选掉部分扫描线,如果两条扫描线之间间隔的距离非常相近,只需要使用其中一条即可,本文使用一个非常简单的策略,例如y=1.2、y=1.3,使用一个map来记录(int)(1.2)=1,因为int(1.3)也等于1,该扫描线会被舍弃

【java代码实现】

/*** 构建网络单元** @param pointList* @return*/
private Cell[][] constructCells(List<Point> pointList) {声明变量Cell[][] cells;开始构建List<Double> yList = new ArrayList<>();List<Double> zList = new ArrayList<>();Map<Integer, Boolean> yMap = new HashMap<>();Map<Integer, Boolean> zMap = new HashMap<>();for (Point point : pointList) {if (!yMap.containsKey((int) point.getY())) {yList.add(point.getY());yMap.put((int) point.getY(), true);}if (!zMap.containsKey((int) point.getZ())) {zList.add(point.getZ());zMap.put((int) point.getZ(), true);}}根据分段继续添加yList和zListdouble minY = Double.MAX_VALUE;double maxY = -Double.MAX_VALUE;double minZ = Double.MAX_VALUE;double maxZ = -Double.MAX_VALUE;for (Point point : pointList) {minY = Math.min(minY, point.getY());maxY = Math.max(maxY, point.getY());minZ = Math.min(minZ, point.getZ());maxZ = Math.max(maxZ, point.getZ());}///根据分段数来确定y的增量double deltaOfY = (maxY - minY) * 1.0 / this.segmentNum;double curY = minY + deltaOfY;while (curY < maxY) {if (yMap.containsKey(curY)) {curY += deltaOfY;continue;}boolean isAdd = false;// 对于每一根y扫描线,都拿来和多边形的每条边相交一下,来找到z扫描线for (int i = 0; i < pointList.size(); i++) {int j = (i + 1) % pointList.size();//获取边的两个点Point point1 = pointList.get(i);Point point2 = pointList.get(j);double minYOfSide = Math.min(point1.getY(), point2.getY());double maxYOfSide = Math.max(point1.getY(), point2.getY());if (minYOfSide < curY && curY < maxYOfSide) {///对边构建表达式double curZ = this.getZByYAndLineMessage(point1, point2, curY);if (curZ == Double.MAX_VALUE) {continue;}if (!zMap.containsKey((int) curZ)) {zList.add(curZ);zMap.put((int) curZ, true);}isAdd = true;}}if (isAdd == true) {yList.add(curY);yMap.put((int) curY, true);}curY += deltaOfY;}//对yList、zList升序排序Collections.sort(yList);Collections.sort(zList);cells = new Cell[zList.size() - 1][yList.size() - 1];for (int j = 0; j < zList.size() - 1; j++) {for (int i = 0; i < yList.size() - 1; i++) {Point left_up_point = new Point(0, yList.get(i), zList.get(j));Point right_down_point = new Point(0, yList.get(i + 1), zList.get(j + 1));cells[j][i] = new Cell(left_up_point, right_down_point);}}return cells;
}

区分每个单元格是在多边形内部还是外部

本文使用的区分方式是,分别判断一个单元格的四个点是否都在多边形内部,判断一个点是否在多边形的内部可以参考文章射线法——判断一个点是否在多边形内部(适用于凸多边形和凹多边形)【关键原理解释+文字伪代码+java代码实现】,只要有一个点不在多边形内部,则该单元格被标记为0,代表其不在多边形内部。如果单元格的四个点都在多边形内部,也不足以说明单元格就真的在多边形内部,下图就是一个例子
在这里插入图片描述
因此还需要判断单元格的边和多边形的边是否有相交,如果有相交,则单元格不完全在多边形内部。等所有的单元格都被判断是否完整地处于多边形内部并被标记为1之后,得到下图
在这里插入图片描述
【java实现】

/*** 标记网络单元,当一个单元处于多边形内部时,将单元标记为 1,否则标记为 0** @param pointList* @param cells*/
private void markCellsLabel(List<Point> pointList, Cell[][] cells) throws Exception {long start = System.currentTimeMillis();for (int i = 0; i < cells.length; i++) {for (int j = 0; j < cells[i].length; j++) {cells[i][j].setLabel(this.getCellLabel(pointList, cells[i][j]));}}long end = System.currentTimeMillis();this.setCellsLabelTime += end - start;
}/*** 判断单元格是否被纯包含于多边形内,是:返回1;否:返回0* 单元格中有一个点不在多边形内,单元格便是不在单元格内* type=0:第一次设置label时使用; type=1:reset label时使用;** @param pointList* @param cell*/
private int getCellLabel(List<Point> pointList, Cell cell) throws Exception {// 存储单元格的四个点Point[] pointArr = new Point[4];//左上角pointArr[0] = new Point(0, cell.getLeft_up_point().getY(), cell.getLeft_up_point().getZ());//右上角pointArr[1] = new Point(0, cell.getRight_down_point().getY(), cell.getLeft_up_point().getZ());//右下角pointArr[2] = new Point(0, cell.getRight_down_point().getY(), cell.getRight_down_point().getZ());//左下角pointArr[3] = new Point(0, cell.getLeft_up_point().getY(), cell.getRight_down_point().getZ());for (Point point : pointArr) {//只要有一个点不在多边形内,单元格被标记为不在多边形内if (PolygonUtil.judgeWhetherThePointInPolygon(pointList, point) == false) {return 0;}}//就算单元格的所有点都在多边形内部,不代表单元格就在多边形内了//再判断一下网络单元的四条边是否和线段有相交,且斜率不能相同,为了避免出现较特殊矩形时,单元的四个点都在多边形内部,但是实际上不在内部的情况出现for (int i = 0; i < pointArr.length; i++) {int j = (i + 1) % pointArr.length;for (int m = 0; m < pointList.size(); m++) {int n = (m + 1) % pointList.size();if (PolygonUtil.judgeWhetherTwoLineSegmentIsIntersect(pointArr[i], pointArr[j], pointList.get(m), pointList.get(n)) == true &&(this.getKOfLine(pointArr[i], pointArr[j]) != this.getKOfLine(pointList.get(m), pointList.get(n)))) {//--if--当单元格的边和多边形有交叉,且不是平行的那种时,单元不在多边形内部return 0;}}}
//            System.out.println("单元格在多边形内部");return 1;
}

根据已标记单元格寻找最大内接矩形

本文寻找最大内接矩形的方式如下:遍历每个单元格,尝试将该单元格开始,然后向右、向下寻找单元格进行组合来找到该单元格最大的矩形。在遍历的途中,不断更新面积最大的矩形,遍历结束之后即可求得结果

当遍历到一个单元格时,从单元格开始,向右遍历每一列,找出每一列的对应的连续高度填充到heightArr中,如下图所示。同理,遍历每一行,找出每一行的连续宽度,填充到widthArr中,同时将每一行最大连续宽度的单元格所在的列索引填充到maxColumnNumArr
在这里插入图片描述
具体操作如下面的代码所示

/*
* 只需要设置一次heightArr,后面需要多少列直接拿就行
* 只需要设置一次widthArr,下一列的格子的所能找到的最大宽度直接为当前格子所能找到的最大宽度-当前格子宽度
*/
double[] widthArr = new double[cells.length - i];
// 存储每一行到达最大宽度时的列数
int[] maxColumnNumArr = new int[cells.length - i];
double[] heightArr = new double[cells[0].length - j];/// 初始化heightArr
for (int x = j; x < heightArr.length + j; x++) {// --for--循环每一列double heightOfCurColumn = 0;for (int y = i; y < cells.length; y++) {// --for--循环每一行if (cells[y][x].getLabel() == 1) {heightOfCurColumn += cells[y][x].getHeight();} else {break;}}heightArr[x - j] = heightOfCurColumn;if (Math.abs(heightOfCurColumn - 0) < this.precisionError) {// 相当于这一列开始,后面的列全是默认为0,因为所形成的矩形需要被最矮的一列限制break;}
}/// 初始化 widthArr 和 maxColumnNumArr
for (int m = i; m < widthArr.length + i; m++) {// --for--循环每一行double widthOfCurRow = 0;// 找最大宽度所到达的列数int maxColumnNum = j;int num = 0;for (int k = j; k < cells[0].length; k++) {// --for--循环每一列if (cells[m][k].getLabel() == 1) {widthOfCurRow += cells[m][k].getWidth();num++;} else {break;}}maxColumnNum += num > 0 ? num - 1 : 0;// 存储当前行宽度widthArr[m - i] = widthOfCurRow;maxColumnNumArr[m - i] = maxColumnNum;
}

当遍历到一个单元格时,还需要做如下事情来寻找当前单元格对应的最大矩形,因为文字实在太难描述,我直接贴代码了o(╥﹏╥)o

/// 找到最小的n
// 从widthArr和nArr来看
int minN = Integer.MAX_VALUE;
for (int index = 0; index < maxColumnNumArr.length; index++) {if (maxColumnNumArr[index] > 0) {minN = Math.min(minN, maxColumnNumArr[index]);} else {break;}
}
if (minN == Integer.MAX_VALUE) {// 将minN赋值为j-1,这样下面就无需循环寻找结果了minN = j - 1;
}
// 从heightArr来看
int minNOfHeightArr = j;
for (int k = 1; k < heightArr.length; k++) {if (heightArr[k] <= heightArr[k - 1]) {minNOfHeightArr++;} else {break;}
}
minN = Math.min(minN, minNOfHeightArr);/// 【寻找最大面积的矩形】
int columnNum = 0;
int recordJ = j;
if (j <= minN) {while (j <= minN) {if (cells[i][j].getLabel() == 1 && cells[i][j].getMaxArea() > bestArea) {for (int m = i; m < widthArr.length + i; m++) {// --for--循环每一行double widthOfCurRow = widthArr[m - i];// 找最大宽度所到达的列数int maxColumnNum = maxColumnNumArr[m - i];if ((m - i - 1) >= 0 && maxColumnNum == maxColumnNumArr[m - i - 1]) {// --if-- 最大列数和上一个的最大列数一样,可以直接跳过此轮循环,直接进入下一轮continue;}if (Math.abs(widthOfCurRow - 0) < this.precisionError) {break;} else {// 当前行对应的最大宽度double maxWid = widthOfCurRow;// 寻找当前宽度对应的最小高度double maxHei = Integer.MAX_VALUE;boolean isAssign = false;for (int k = columnNum; k < maxColumnNum - recordJ + 1; k++) {maxHei = Math.min(maxHei, heightArr[k]);isAssign = true;}// 更新最优解if (maxWid * maxHei > bestArea && isAssign == true) {bestArea = maxWid * maxHei;bestRectangle = new LoadProductDto(maxWid, maxHei, cells[i][j].getLeft_up_point().getY(), cells[i][j].getLeft_up_point().getZ());}}}}// 更新widthArrfor (int m = i; m < widthArr.length + i; m++) {if (widthArr[m - i] > 0) {// 每一行的width减去当前列的宽度widthArr[m - i] -= cells[m][j].getWidth();} else {break;}}j++;columnNum++;break;}// 上面的j++已经超出minN了,重新回到minN,因为循环的时候,j会++,如果不回到minN,会漏掉一列j = minN;
}

代码中注释为【寻找最大面积的矩形】的代码片段主要在做如下的事情,可以结合下面的一系列图片来理解

在这里插入图片描述
【从第一列开始寻找矩形】
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
【从第二列开始寻找矩形】
在这里插入图片描述
---- 依次类推 ----
在这里插入图片描述
【上面的过程结束之后,下一个遍历的单元格如下图,原因是y已经变成了minN+1
在这里插入图片描述

你们可能会困惑,为啥需要这段代码来限制minN

// 从heightArr来看
int minNOfHeightArr = j;
for (int k = 1; k < heightArr.length; k++) {if (heightArr[k] <= heightArr[k - 1]) {minNOfHeightArr++;} else {break;}
}
minN = Math.min(minN, minNOfHeightArr);

假如不限制的话,遍历情况如图所示
在这里插入图片描述
再直接点说,会找不到如下面类型的结果
在这里插入图片描述

剪枝优化

当从网格的左上角遍历到网格的右下角时,能找到的矩形实际上已经非常小了,如果能提前预知一个单元格所能找到的最大矩形面积已经小于当前所找到的最大矩形面积的话,则该单元格无需进行遍历,直接跳过即可

本文使用递推的方法来设置一个单元格所能找到的理想最优矩形面积,代码如下:

/**
* 填充单元格的理想最大面积
*
* @param cells
*/
private void fillCellsMaxArea(Cell[][] cells) { 填补每个单元格所能找到的理想最大面积(递推)/// 初始化网络单元的最后一行和最后一列// 初始化最后一行for (int i = 0; i < cells[cells.length - 1].length; i++) {//对每一列的最后一个单元进行处理Cell cell = cells[cells.length - 1][i];cell.setMaxArea(cell.getWidth() * cell.getHeight() * cell.getLabel());}// 初始化最后一列for (int i = 0; i < cells.length; i++) {//对每一行的最后一个单元进行处理Cell cell = cells[i][cells[0].length - 1];cell.setMaxArea(cell.getWidth() * cell.getHeight() * cell.getLabel());}/// 填充其他单元格的理想最大面积for (int i = cells.length - 2; i >= 0; i--) {for (int j = cells[0].length - 2; j >= 0; j--) {Cell cell = cells[i][j];//先填充自己的面积cell.setMaxArea(cell.getWidth() * cell.getHeight() * cell.getLabel());//再添加自己下面的单元格maxArea和右侧的单元格的maxAreaif (i + 1 < cells.length) {cell.setMaxArea(cell.getMaxArea() + cells[i + 1][j].getMaxArea());}if (j + 1 < cells[0].length) {cell.setMaxArea(cell.getMaxArea() + cells[i][j + 1].getMaxArea());}}}
}

当满足单元格的标记为1,且理想最大矩形面积超过当前已经找到的最大矩形面积,才会去根据该单元格去执行上面的【根据已标记单元格寻找最大内接矩形】步骤

// 对每个被标记为1的单元格,将其向右、向下遍历,计算形成的最大矩形
for (int i = 0; i < cells.length; i++) {for (int j = 0; j < cells[0].length; j++) {if (cells[i][j].getLabel() == 1 && cells[i][j].getMaxArea() > bestArea) {// 根据已标记单元格寻找最大内接矩形}}
}

多角度旋转

上面的方法结束之后,只能求得一个角度下的最大内接矩形,会导致下图的情况发生

在这里插入图片描述
本文通过每旋转5°,求解一个最大内接矩形,最终选择最大的那个矩形作为最终结果,当然,如果想要找到更好的结果,可以不断缩小旋转角度,当然,计算时间也会上涨很多
在这里插入图片描述

案例测试

在这里插入图片描述在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

代码实现

package com.ruoyi.algorithm.get_maximumArea_rectangles_in_a_simple_polygon.version.v1;import com.ruoyi.algorithm.common.entity.Cell;
import com.ruoyi.algorithm.common.entity.GetMaxRectangleInSimplePolygonResult;
import com.ruoyi.algorithm.common.entity.LoadProductDto;
import com.ruoyi.algorithm.common.entity.Point;import java.util.*;/*** 获取多边形内的最大内接矩形*/
public class GetMaximumAreaRectangleInASimplePolygonApi {/*** 对边进行分段处理,增加更多的点*/private int segmentNum = 100;/*** 是否打印标记矩阵*/private boolean isPrintLabelMatrix = false;/*** paintType=0:画未补充点的线;paintType=1:画补充点后的线*/private int paintType = 0;/*** 旋转度数*/private int rotateDegreeDelta = 5;/*** 精度误差*/private double precisionError = 0.0001;/*** 标记单元格时间*/private long setCellsLabelTime = 0;/*** 根据已有解重置单元格标记的时间*/private long resetCellsLabelTime = 0;/*** 给定单元格,寻找解的时间*/private long searchSolutionTime = 0;/*** 且多边形的最大内接矩形** @param pointList         顺时针或逆时针将点集传进来* @param bestRectangleList 可能有多个相等的内接矩形,都存储下来*/public GetMaxRectangleInSimplePolygonResult solve(List<Point> pointList, List<LoadProductDto> bestRectangleList) throws Exception {System.out.println();long start = System.currentTimeMillis();声明变量List<Point> solution = new ArrayList<>();GetMaxRectangleInSimplePolygonResult getMaxRectangleInSimplePolygonResult = new GetMaxRectangleInSimplePolygonResult();存储到结果的数据List<Double> yList = new ArrayList<>();List<Double> zList = new ArrayList<>();double minY = Double.MAX_VALUE;double maxY = -Double.MAX_VALUE;double minZ = Double.MAX_VALUE;double maxZ = -Double.MAX_VALUE;Cell[][] cells = null;for (Point point : pointList) {minY = Math.min(minY, point.getY());maxY = Math.max(maxY, point.getY());minZ = Math.min(minZ, point.getZ());maxZ = Math.max(maxZ, point.getZ());}找最大矩形///声明变量//记录最大矩形的面积double bestArea = 0;//记录最佳旋转角度int bestRotateDegree = 0;LoadProductDto bestRectangle = null;List<Point> bestSolution = new ArrayList<>();//记录当前所遍历到的角度int rotateDegree = 0;int endRotateDegree = 360;while (rotateDegree <= endRotateDegree) {
//            System.out.println("当前角度:"+rotateDegree);//每旋转rotateDegreeDelta,求一次结果,取中间的最优解LoadProductDto curRectangle = this.solveWithAppointRotateDegree(Point.cloneList(pointList), rotateDegree, solution);if (curRectangle == null) {rotateDegree += this.rotateDegreeDelta;continue;}//更新结果double curArea = curRectangle.getWidth() * curRectangle.getHeight();if ((bestRectangle == null) || (curArea > bestArea)) {System.out.println("找到矩形1-------------------------");//找curRectangle的4个角点List<Point> curSolution = new ArrayList<>();Point leftUpPoint = new Point(0, curRectangle.getY(), curRectangle.getZ());Point rightUpPoint = new Point(0, curRectangle.getY() + curRectangle.getWidth(), curRectangle.getZ());Point rightDownPoint = new Point(0, curRectangle.getY() + curRectangle.getWidth(), curRectangle.getZ() + curRectangle.getHeight());Point leftDownPoint = new Point(0, curRectangle.getY(), curRectangle.getZ() + curRectangle.getHeight());Collections.addAll(curSolution, leftDownPoint, rightDownPoint, rightUpPoint, leftUpPoint);//对结果进行反旋转for (Point point : curSolution) {double[] arr = this.rotate(point.getY(), point.getZ(), 0, 0, -rotateDegree);point.setY(arr[0]);point.setZ(arr[1]);}//替换结果bestArea = curArea;bestRectangle = curRectangle;bestSolution.clear();bestSolution.addAll(curSolution);bestRotateDegree = rotateDegree;bestRectangle.setBestRotateDegree(bestRotateDegree);}rotateDegree += this.rotateDegreeDelta;}if (bestRectangle != null) {//找到解,对解进行存储solution = Point.cloneList(bestSolution);System.out.println("找到矩形2-------------------------");System.out.println("最优旋转角度:" + bestRotateDegree);System.out.println("bestSolution:" + bestSolution);bestRectangleList.add(bestRectangle);///存储最优解,需要将网格那些也保存下来if (this.paintType == 1) {minY = Double.MAX_VALUE;maxY = -Double.MAX_VALUE;minZ = Double.MAX_VALUE;maxZ = -Double.MAX_VALUE;// 将零件点旋转一下for (Point point : pointList) {double[] arr = this.rotate(point.getY(), point.getZ(), 0, 0, bestRotateDegree);point.setY(arr[0]);point.setZ(arr[1]);minY = Math.min(minY, point.getY());maxY = Math.max(maxY, point.getY());minZ = Math.min(minZ, point.getZ());maxZ = Math.max(maxZ, point.getZ());}// 将结旋转一下for (Point point : solution) {double[] arr = this.rotate(point.getY(), point.getZ(), 0, 0, bestRotateDegree);point.setY(arr[0]);point.setZ(arr[1]);}//构建网络单元cells = this.constructCells(pointList);//标记单元格,所有被全包含于多边形的单元格被标记为1this.markCellsLabel(pointList, cells);}}getMaxRectangleInSimplePolygonResult.setSolution(solution);getMaxRectangleInSimplePolygonResult.setPointList(pointList);getMaxRectangleInSimplePolygonResult.setBestRectangleList(bestRectangleList);getMaxRectangleInSimplePolygonResult.setYList(yList);getMaxRectangleInSimplePolygonResult.setZList(zList);getMaxRectangleInSimplePolygonResult.setWidth(maxY - minY);getMaxRectangleInSimplePolygonResult.setHeight(maxZ - minZ);getMaxRectangleInSimplePolygonResult.setMinY(minY);getMaxRectangleInSimplePolygonResult.setMinZ(minZ);getMaxRectangleInSimplePolygonResult.setCells(cells);long end = System.currentTimeMillis();double calculateTime = (end - start) * 1.0 / 1000;getMaxRectangleInSimplePolygonResult.setCalculateTime(calculateTime);System.out.println("结果输出--------------------------------------------------");System.out.println("计算时间:" + calculateTime + "s");System.out.println("标记网络单元总标记时间:" + this.setCellsLabelTime * 1.0 / 1000 + "s");System.out.println("重置网络单元总标记时间:" + this.resetCellsLabelTime * 1.0 / 1000 + "s");System.out.println("给定网络搜索解时间:" + this.searchSolutionTime * 1.0 / 1000 + "s");return getMaxRectangleInSimplePolygonResult;}/*** 指定旋转角度,求当前旋转角度的最大矩形** @param pointList* @param rotateDegree* @return*/private LoadProductDto solveWithAppointRotateDegree(List<Point> pointList, int rotateDegree, List<Point> solution) throws Exception { 数据处理// 将点旋转一下for (Point point : pointList) {double[] arr = this.rotate(point.getY(), point.getZ(), 0, 0, rotateDegree);point.setY(arr[0]);point.setZ(arr[1]);} 声明变量double bestArea = 0;LoadProductDto bestRectangle = null;// 构建单元格Cell[][] cells = this.constructCells(pointList);// 标记单元格,所有被全包含于多边形的单元格被标记为1this.markCellsLabel(pointList, cells);if (this.isPrintLabelMatrix == true) {System.out.println("输出真实标记矩阵,在多边形内的单元被标记为1");for (int i = 0; i < cells.length; i++) {for (int j = 0; j < cells[i].length; j++) {System.out.printf(String.valueOf(cells[i][j].getLabel()) + "\t");}System.out.println();}}// 填充单元格的最大面积(搜索到右下角的单元格时,如果知道所能找到的矩形一定不可能大于已经搜索到的矩形时,直接停止该单元格的搜索)this.fillCellsMaxArea(cells);// 对每个被标记为1的单元格,将其向右、向下遍历,计算形成的最大矩形for (int i = 0; i < cells.length; i++) {for (int j = 0; j < cells[0].length; j++) {if (cells[i][j].getLabel() == 1 && cells[i][j].getMaxArea() > bestArea) {/** 只需要设置一次heightArr,后面需要多少列直接拿就行* 只需要设置一次widthArr,下一列的格子的所能找到的最大宽度直接为当前格子所能找到的最大宽度-当前格子宽度*/long searchSolutionTimeStart = System.currentTimeMillis();double[] widthArr = new double[cells.length - i];// 存储每一行到达最大宽度时的列数int[] maxColumnNumArr = new int[cells.length - i];double[] heightArr = new double[cells[0].length - j];/// 初始化heightArrfor (int x = j; x < heightArr.length + j; x++) {// --for--循环每一列double heightOfCurColumn = 0;for (int y = i; y < cells.length; y++) {// --for--循环每一行if (cells[y][x].getLabel() == 1) {heightOfCurColumn += cells[y][x].getHeight();} else {break;}}heightArr[x - j] = heightOfCurColumn;if (Math.abs(heightOfCurColumn - 0) < this.precisionError) {// 相当于这一列开始,后面的列全是默认为0,因为所形成的矩形需要被最矮的一列限制break;}}/// 初始化 widthArr 和 maxColumnNumArrfor (int m = i; m < widthArr.length + i; m++) {// --for--循环每一行double widthOfCurRow = 0;// 找最大宽度所到达的列数int maxColumnNum = j;int num = 0;for (int k = j; k < cells[0].length; k++) {// --for--循环每一列if (cells[m][k].getLabel() == 1) {widthOfCurRow += cells[m][k].getWidth();num++;} else {break;}}maxColumnNum += num > 0 ? num - 1 : 0;// 存储当前行宽度widthArr[m - i] = widthOfCurRow;maxColumnNumArr[m - i] = maxColumnNum;}/// 找到最小的n// 从widthArr和nArr来看int minN = Integer.MAX_VALUE;for (int index = 0; index < maxColumnNumArr.length; index++) {if (maxColumnNumArr[index] > 0) {minN = Math.min(minN, maxColumnNumArr[index]);} else {break;}}if (minN == Integer.MAX_VALUE) {// 将minN赋值为j-1,这样下面就无需循环寻找结果了minN = j - 1;}// 从heightArr来看int minNOfHeightArr = j;for (int k = 1; k < heightArr.length; k++) {if (heightArr[k] <= heightArr[k - 1]) {minNOfHeightArr++;} else {break;}}minN = Math.min(minN, minNOfHeightArr);/// 寻找最大面积的矩形int columnNum = 0;int recordJ = j;if (j <= minN) {while (j <= minN) {if (cells[i][j].getLabel() == 1 && cells[i][j].getMaxArea() > bestArea) {for (int m = i; m < widthArr.length + i; m++) {// --for--循环每一行double widthOfCurRow = widthArr[m - i];// 找最大宽度所到达的列数int maxColumnNum = maxColumnNumArr[m - i];if ((m - i - 1) >= 0 && maxColumnNum == maxColumnNumArr[m - i - 1]) {// --if-- 最大列数和上一个的最大列数一样,可以直接跳过此轮循环,直接进入下一轮continue;}if (Math.abs(widthOfCurRow - 0) < this.precisionError) {break;} else {// 当前行对应的最大宽度double maxWid = widthOfCurRow;// 寻找当前宽度对应的最小高度double maxHei = Integer.MAX_VALUE;boolean isAssign = false;for (int k = columnNum; k < maxColumnNum - recordJ + 1; k++) {maxHei = Math.min(maxHei, heightArr[k]);isAssign = true;}// 更新最优解if (maxWid * maxHei > bestArea && isAssign == true) {bestArea = maxWid * maxHei;bestRectangle = new LoadProductDto(maxWid, maxHei, cells[i][j].getLeft_up_point().getY(), cells[i][j].getLeft_up_point().getZ());}}}}// 更新widthArrfor (int m = i; m < widthArr.length + i; m++) {if (widthArr[m - i] > 0) {// 每一行的width减去当前列的宽度widthArr[m - i] -= cells[m][j].getWidth();} else {break;}}j++;columnNum++;break;}// 上面的j++已经超出minN了,重新回到minN,因为循环的时候,j会++,如果不回到minN,会漏掉一列j = minN;}long searchSolutionTimeEnd = System.currentTimeMillis();this.searchSolutionTime += searchSolutionTimeEnd - searchSolutionTimeStart;}}}return bestRectangle;}/*** 构建网络单元** @param pointList* @return*/private Cell[][] constructCells(List<Point> pointList) {声明变量Cell[][] cells;开始构建List<Double> yList = new ArrayList<>();List<Double> zList = new ArrayList<>();Map<Integer, Boolean> yMap = new HashMap<>();Map<Integer, Boolean> zMap = new HashMap<>();for (Point point : pointList) {if (!yMap.containsKey((int) point.getY())) {yList.add(point.getY());yMap.put((int) point.getY(), true);}if (!zMap.containsKey((int) point.getZ())) {zList.add(point.getZ());zMap.put((int) point.getZ(), true);}}根据分段继续添加yList和zListdouble minY = Double.MAX_VALUE;double maxY = -Double.MAX_VALUE;double minZ = Double.MAX_VALUE;double maxZ = -Double.MAX_VALUE;for (Point point : pointList) {minY = Math.min(minY, point.getY());maxY = Math.max(maxY, point.getY());minZ = Math.min(minZ, point.getZ());maxZ = Math.max(maxZ, point.getZ());}///根据分段数来确定y的增量double deltaOfY = (maxY - minY) * 1.0 / this.segmentNum;double curY = minY + deltaOfY;while (curY < maxY) {if (yMap.containsKey(curY)) {curY += deltaOfY;continue;}boolean isAdd = false;// 对于每一根y扫描线,都拿来和多边形的每条边相交一下,来找到z扫描线for (int i = 0; i < pointList.size(); i++) {int j = (i + 1) % pointList.size();//获取边的两个点Point point1 = pointList.get(i);Point point2 = pointList.get(j);double minYOfSide = Math.min(point1.getY(), point2.getY());double maxYOfSide = Math.max(point1.getY(), point2.getY());if (minYOfSide < curY && curY < maxYOfSide) {///对边构建表达式double curZ = this.getZByYAndLineMessage(point1, point2, curY);if (curZ == Double.MAX_VALUE) {continue;}if (!zMap.containsKey((int) curZ)) {zList.add(curZ);zMap.put((int) curZ, true);}isAdd = true;}}if (isAdd == true) {yList.add(curY);yMap.put((int) curY, true);}curY += deltaOfY;}//对yList、zList升序排序Collections.sort(yList);Collections.sort(zList);cells = new Cell[zList.size() - 1][yList.size() - 1];for (int j = 0; j < zList.size() - 1; j++) {for (int i = 0; i < yList.size() - 1; i++) {Point left_up_point = new Point(0, yList.get(i), zList.get(j));Point right_down_point = new Point(0, yList.get(i + 1), zList.get(j + 1));cells[j][i] = new Cell(left_up_point, right_down_point);}}return cells;}/*** 标记网络单元,当一个单元处于多边形内部时,将单元标记为1,否则标记为0** @param pointList* @param cells*/private void markCellsLabel(List<Point> pointList, Cell[][] cells) throws Exception {long start = System.currentTimeMillis();for (int i = 0; i < cells.length; i++) {for (int j = 0; j < cells[i].length; j++) {cells[i][j].setLabel(this.getCellLabel(pointList, cells[i][j]));}}long end = System.currentTimeMillis();this.setCellsLabelTime += end - start;}/*** 判断单元格是否被纯包含于多边形内,是:返回1;否:返回0* 单元格中有一个点不在多边形内,单元格便是不在单元格内* type=0:第一次设置label时使用; type=1:reset label时使用;** @param pointList* @param cell*/private int getCellLabel(List<Point> pointList, Cell cell) throws Exception {// 存储单元格的四个点Point[] pointArr = new Point[4];//左上角pointArr[0] = new Point(0, cell.getLeft_up_point().getY(), cell.getLeft_up_point().getZ());//右上角pointArr[1] = new Point(0, cell.getRight_down_point().getY(), cell.getLeft_up_point().getZ());//右下角pointArr[2] = new Point(0, cell.getRight_down_point().getY(), cell.getRight_down_point().getZ());//左下角pointArr[3] = new Point(0, cell.getLeft_up_point().getY(), cell.getRight_down_point().getZ());for (Point point : pointArr) {//只要有一个点不在多边形内,单元格被标记为不在多边形内if (PolygonUtil.judgeWhetherThePointInPolygon(pointList, point) == false) {return 0;}}//就算单元格的所有点都在多边形内部,不代表单元格就在多边形内了//再判断一下网络单元的四条边是否和线段有相交,且斜率不能相同,为了避免出现较特殊矩形时,单元的四个点都在多边形内部,但是实际上不在内部的情况出现for (int i = 0; i < pointArr.length; i++) {int j = (i + 1) % pointArr.length;for (int m = 0; m < pointList.size(); m++) {int n = (m + 1) % pointList.size();if (PolygonUtil.judgeWhetherTwoLineSegmentIsIntersect(pointArr[i], pointArr[j], pointList.get(m), pointList.get(n)) == true &&(this.getKOfLine(pointArr[i], pointArr[j]) != this.getKOfLine(pointList.get(m), pointList.get(n)))) {//--if--当单元格的边和多边形有交叉,且不是平行的那种时,单元不在多边形内部return 0;}}}
//            System.out.println("单元格在多边形内部");return 1;}/*** 填充单元格的理想最大面积** @param cells*/private void fillCellsMaxArea(Cell[][] cells) { 填补每个单元格所能找到的理想最大面积(递推)/// 初始化网络单元的最后一行和最后一列// 初始化最后一行for (int i = 0; i < cells[cells.length - 1].length; i++) {//对每一列的最后一个单元进行处理Cell cell = cells[cells.length - 1][i];cell.setMaxArea(cell.getWidth() * cell.getHeight() * cell.getLabel());}// 初始化最后一列for (int i = 0; i < cells.length; i++) {//对每一行的最后一个单元进行处理Cell cell = cells[i][cells[0].length - 1];cell.setMaxArea(cell.getWidth() * cell.getHeight() * cell.getLabel());}/// 填充其他单元格的理想最大面积for (int i = cells.length - 2; i >= 0; i--) {for (int j = cells[0].length - 2; j >= 0; j--) {Cell cell = cells[i][j];//先填充自己的面积cell.setMaxArea(cell.getWidth() * cell.getHeight() * cell.getLabel());//再添加自己下面的单元格maxArea和右侧的单元格的maxAreaif (i + 1 < cells.length) {cell.setMaxArea(cell.getMaxArea() + cells[i + 1][j].getMaxArea());}if (j + 1 < cells[0].length) {cell.setMaxArea(cell.getMaxArea() + cells[i][j + 1].getMaxArea());}}}}/*** 求一条直线的斜率** @param p1* @param p2* @return*/private double getKOfLine(Point p1, Point p2) {return MathUtil.getKOfLine(p1.getY(), p1.getZ(), p2.getY(), p2.getZ());}/*** 平面上一点x1,y1,绕平面上另一点x2,y2顺时针旋转rotateDegree角度,求旋转后的x1,y1对应的坐标x,y** @param x1* @param y1* @param x2* @param y2* @param rotateDegree* @return arr[0]:x;arr[1]:y*/private double[] rotate(double x1, double y1, double x2, double y2, int rotateDegree) {double[] arr = new double[2];//根据角度求弧度double radian = (rotateDegree * 1.0 / 180) * Math.PI;//旋转arr[0] = (x1 - x2) * Math.cos(radian) - (y1 - y2) * Math.sin(radian) + x2;arr[1] = (y1 - y2) * Math.cos(radian) + (x1 - x2) * Math.sin(radian) + y2;return arr;}/*** 传入一条线段,然后根据已知的y来求线段上的z** @param p1* @param p2* @param y* @return*/private double getZByYAndLineMessage(Point p1, Point p2, double y) {double k = this.getKOfLine(p1, p2);if (Math.abs(k - Double.MAX_VALUE) < this.precisionError) {return Double.MAX_VALUE;} else if (Math.abs(k - 0) < this.precisionError) {return p1.getZ();} else {//截距double b = p2.getZ() - k * p2.getY();return k * y + b;}}public GetMaximumAreaRectangleInASimplePolygonApi() {}
}

代码中使用的一些工具类麻烦查看文章射线法——判断一个点是否在多边形内部(适用于凸多边形和凹多边形)【关键原理解释+文字伪代码+java代码实现】

说明

本文的算法算是比较粗暴的求解算法,加上本人代码能力不够强,编码时间短,部分地方的处理还有待提高,可能导致部分数据计算时间较长,假如读者们有什么更好的建议也希望可以不吝赐教。如果你们觉得有帮助,也希望可以点个赞

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/133895.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

聊聊Spring事务同步器TransactionSynchronization

在一些业务场景中可能我们需要去对某一个spring事务的生命周期进行监控&#xff0c;比如在这个事务提交&#xff0c;回滚&#xff0c;被挂起的时候&#xff0c;我们想要去执行一些自定义的操作&#xff0c;这怎么去做呢&#xff1f;其实spring作为一个高扩展性的框架&#xff0…

关系型三大范式与BCNF有什么用呢

学的时候就知道是一堆公式。 实际中在设计表的时候可能会用到。 前提是关系型数据库&#xff0c;比如mysql。 &#xff08;实际中oracle比mysql更好用。但是他收费啊。&#xff09; 第一范式&#xff1a;每个属性都是原子的&#xff08;需要做到每个属性都是不可分割的。&…

02 java ---- Android 基础app开发

目录 相对布局 显示一个美女 显示两个美女 安卓APP启动过程 安卓布局控件 常用布局之相对布局 常用布局之相对布局 padding和margin 按键美化 常用布局之线性布局 安卓按键响应的几种方式 直接设置按键的onClick绑定的函数 自定义类实现按键监听事件的接口 匿名内…

[NLP] LLM---<训练中文LLama2(一)>训练一个中文LLama2的步骤

一 数据集 【Awesome-Chinese-LLM中文数据集】 【awesome-instruction-dataset】【awesome-instruction-datasets】【LLaMA-Efficient-Tuning-数据集】Wiki中文百科&#xff08;25w词条&#xff09;wikipedia-cn-20230720-filteredBaiduBaiKe&#xff08;563w词条&#xff09; …

4.后端·新建子模块与开发(传统模式)

文章目录 学习资料新建子模块与各层查询entity的列表entitymapper层service层controller层 测试 学习资料 https://www.bilibili.com/video/BV13g411Y7GS?p8&spm_id_frompageDriver&vd_sourceed09a620bf87401694f763818a31c91e b站的学习视频 新建子模块与各层 在r…

Linux Ubuntu20.04深度学习环境快速配置命令记录

一、驱动安装 1、更新系统包 sudo apt-get updatesudo apt-get upgrade 2、安装显卡驱动 使用apt方式安装驱动&#xff0c;多数情况不容易成功&#xff0c; 使用一下方法更佳&#xff1a; 1.查看合适显卡的驱动版本 ubuntu-drivers devices NVIDIA GeForce 驱动程序 - …

POJ 3684 Physics Experiment 弹性碰撞

一、题目大意 我们有N个半径为R厘米的球&#xff0c;固定在距离地面高度为H的管道上&#xff0c;刚开始释放第一个&#xff0c;之后每过一秒释放一个&#xff0c;释放下面的球不会影响到上面的球的高度&#xff0c;忽略一切阻力&#xff0c;认为球之间的碰撞为弹性碰撞&#x…

【电子元件】常用电子元器件的识别之电容器

目录 前言1. 电容器的简介2.电容器的识别1. 铝电解电容器2.钽电解电容器3.固态电解电容器4.瓷介电容器5. 贴片陶瓷电容器6. 聚丙烯电容7. 金属化聚丙烯薄膜电容器8. 独石电容器9. 涤纶电容器10. 超小型金属化聚酯薄膜电容器11. 可变电容器11.1 空气可变电容器11.2 薄膜介质可变…

JMeter基础 —— 使用Badboy录制JMeter脚本!

1、使用Badboy录制JMeter脚本 打开Badboy工具开始进行脚本录制&#xff1a; &#xff08;1&#xff09;当我们打开Badboy工具时&#xff0c;默认就进入录制状态。 如下图&#xff1a; 当然我们也可以点击录制按钮进行切换。 &#xff08;2&#xff09;在地址栏中输入被测地…

国庆中秋特辑(一)浪漫祝福方式 用循环神经网络(RNN)或长短时记忆网络(LSTM)生成祝福诗词

目录 一、使用深度学习中的循环神经网络&#xff08;RNN&#xff09;或长短时记忆网络&#xff08;LSTM&#xff09;生成诗词二、优化&#xff1a;使用双向 LSTM 或 GRU 单元来更好地捕捉上下文信息三、优化&#xff1a;使用生成对抗网络&#xff08;GAN&#xff09;或其他技术…

深度学习-卷积神经网络-纹理表示卷积神经网络-卷积神经网络-[北邮鲁鹏]

这里写目录标题 参考文章全连接神经网络全连接神经网络的瓶颈全连接神经网络应用场景 卷积神经网络卷积层(CONV)卷积核卷积操作卷积层设计卷积步长(stride)边界填充特征响应图组尺寸计算 激活层池化层(POOL)池化操作定义池化操作作用池化层超参数常见池化操作 全连接层(FC)样本…

重建与发展:数字资产借贷行业朝着可持续发展迈进!

纵观历史&#xff0c;贷款和货币一样古老&#xff0c;无论哪种形式的货币都需要有其借贷市场。现在&#xff0c;比特币以其分散和透明的性质&#xff0c;在加密领域占据龙头地位。 就像之前的货币一样&#xff0c;比特币要真正蓬勃发展&#xff0c;也需要一个强大的借贷市场。然…

如何在Windows 10/11中重置网络,以及重置后的注意事项有哪些

本文介绍如何在Windows 10和Windows 11中重置网络设置。 如何重置Windows 10网络设置 在Windows10中使用网络重置实用程序相当简单。 一、进入“开始”菜单>“设置”,然后选择“网络和Internet”。 二、在左侧导航窗格中,选择“状态”以确保你正在查看网络状态窗口。然…

嵌入式入门教学——模电基础概念

目录 1、模拟信号和模拟电路 2、研究领域 3、常用术语 3.1、共价键 3.2、电场 3.3、温度的电压当量 3.4、动态信号 3.5、直流电流和交流电流 3.6、内阻 3.7、信号频率 3.8、电容 3.9、电感 3.10、相位 3.11、信号失真 3.12、电导 3.13、跨导 3.14、电位 3.15…

数据结构——图(图的存储及基本操作)

文章目录 前言一、邻接矩阵法&#xff08;顺序存储&#xff09;1.无向图存储邻接矩阵算法2.有向图存储邻接矩阵算法 二、邻接表法(图的链式存储结构)总结 前言 邻接矩阵法(图的顺序存储结构) 1.1 无向图邻接矩阵算法 1.2 有向图邻接矩阵算法邻接表法(图的一种链式存储结构) 一…

Unity WebView 中文输入支持

WebView 中文输入支持 &#x1f96a;效果展示&#x1f371;原理 &#x1f96a;效果展示 &#x1f4a1;使用版本为4.4&#xff1b; &#x1f4a1;测试环境&#xff1a;unity editor 2022.3.15f1c1、Windows&#xff1b; &#x1f371;原理 提取页面激活的输入框&#xff0c;…

github上创建分支并合并到master

github上创建分支并合并到master 目录概述需求&#xff1a; 设计思路实现思路分析1.创建分支2.commit changes3.create pull request按钮4.网页解析器5.数据处理器 参考资料和推荐阅读 Survive by day and develop by night. talk for import biz , show your perfect code,ful…

多线程|多进程|高并发网络编程

一.多进程并发服务器 多进程并发服务器是一种经典的服务器架构&#xff0c;它通过创建多个子进程来处理客户端连接&#xff0c;从而实现并发处理多个客户端请求的能力。 概念&#xff1a; 服务器启动时&#xff0c;创建主进程&#xff0c;并绑定监听端口。当有客户端连接请求…

LLM 04-大模型的数据

LLM 03-大模型的数据 到目前为止&#xff0c;我们已经讨论了大型语言模型的行为&#xff08;能力和损害&#xff09;。现在&#xff0c;我们要剥开洋葱的第一层&#xff0c;开始讨论这些模型是如何构建的。任何机器学习方法的起点都是训练数据&#xff0c;因此这就是我们开始的…

【深度学习】 Python 和 NumPy 系列教程(十三):Matplotlib详解:1、2d绘图(上):折线图、散点图、柱状图、直方图、饼图

目录 一、前言 二、实验环境 三、Matplotlib详解 0、绘图风格 1、2d绘图类型 0. 设置中文字体 1. 折线图&#xff08;Line Plot&#xff09; 2. 散点图&#xff08;Scatter Plot&#xff09; 3. 柱状图&#xff08;Bar Plot&#xff09; 4. 直方图&#xff08;Histogr…