问题
给定一个大的立方体和一批小的立方体，对于每个立方体，都知道如图的信息（知道x,y,z坐标和长、宽、高），且任意小立方体都被包含在大立方体内、各立方体之间不重叠。问如何将小立方体从大立方体中切去，留下其他空间？
代码
package com.dam.common.entity.spiltSpace; public class Point { private int x; private int y; private int z; private int index; public Point(int x, int y, int z, int index) { this.x = x; this.y = y; this.z = z; this.index = index; } public int getX() { return x; } public void setX(int x) { this.x = x; } public int getY() { return y; } public void setY(int y) { this.y = y; } public int getZ() { return z; } public void setZ(int z) { this.z = z; } public int getIndex() { return index; } public void setIndex(int index) { this.index = index; } @Override public String toString() { return "Point{" + "x=" + x + ", y=" + y + ", z=" + z + ", index=" + index + '}'+"\n"; } public Point() { } }
package com.dam.common.entity; import java.io.Serializable; //剩余空间 public class FreeSpace implements Serializable, Comparable<FreeSpace> { private int x; private int y; private int z; private int length; private int width; private int height; //顶上的空间设置为1,右侧空间和前方空间和传入的参数一致即可 private int type; //段号 private int partCode; public FreeSpace() { } public FreeSpace(int x, int y, int z, int length, int width, int height) { this.x = x; this.y = y; this.z = z; this.length = length; this.width = width; this.height = height; } public FreeSpace(int x, int y, int z, int length, int width, int height, int type) { this.x = x; this.y = y; this.z = z; this.length = length; this.width = width; this.height = height; this.type = type; } public int getX() { return x; } public void setX(int x) { this.x = x; } public int getY() { return y; } public void setY(int y) { this.y = y; } public int getZ() { return z; } public void setZ(int z) { this.z = z; } public int getLength() { return length; } public void setLength(int length) { this.length = length; } public int getWidth() { return width; } public void setWidth(int width) { this.width = width; } public int getHeight() { return height; } public void setHeight(int height) { this.height = height; } public int getType() { return type; } public void setType(int type) { this.type = type; } public int getPartCode() { return partCode; } public void setPartCode(int partCode) { this.partCode = partCode; } @Override public String toString() { return "FreeSpace{" + "x=" + x + ", y=" + y + ", z=" + z + ", length=" + length + ", width=" + width + ", height=" + height + ", type=" + type + '}'; } @Override public int compareTo(FreeSpace o) { if (o != null) { if (this.getX() > o.getX()) { return 1; } else if (this.getX() == o.getX()) { return 0; } } return -1; } }
package com.dam.common.util.SpaceUtil; import com.dam.common.entity.FreeSpace; import com.dam.common.util.DeepCloneUtil; import com.dam.common.entity.spiltSpace.Point; import java.util.ArrayList; import java.util.Collections; import java.util.List; //import static com.dam.common.StaticValue.getFreeSpaceUtilNum; import static com.dam.common.StaticValue.getFreeSpaceUtilNum; import static com.po.calculate.util.DeepCloneUtil.deepClone; public class GetFreeSpaceUtil { private int offSet = 0; public static void main(String[] args) throws Exception { FreeSpace bigFreeSpace = new FreeSpace(0, 0, 0, 100, 100, 100); List<FreeSpace> freeSpaceList = new ArrayList<>(); List<FreeSpace> usedSpaceList = new ArrayList<>(); usedSpaceList.add(new FreeSpace(0, 50, 50, 30, 30, 30)); usedSpaceList.add(new FreeSpace(0, 90, 90, 10, 5, 5)); new GetFreeSpaceUtil().getFreeSpaceUtil(bigFreeSpace, freeSpaceList, usedSpaceList, 2); System.out.println(freeSpaceList); } /** * 传入大空间和已用小空间列表，返回未使用的空间列表 * * @param bigFreeSpace * @param freeSpaceList * @param usedSpaceList * @throws Exception */ public void getFreeSpaceUtil(FreeSpace bigFreeSpace, List<FreeSpace> freeSpaceList, List<FreeSpace> usedSpaceList, int planType) throws Exception { getFreeSpaceUtilNum++; //检验数据是否正确 boolean flag = this.inspectionData(bigFreeSpace, usedSpaceList); if (flag == false) { // throw new Exception("输入数据有误——不是所有已用空间都被包含于大空间中"); } //备份已用空间列表用于检验新生成的空间是否与已用空间检验 List<FreeSpace> useFreeSpaceListClone = (List<FreeSpace>) deepClone(usedSpaceList); //处理第一个已用空间 FreeSpace firstUsedSpace = usedSpaceList.remove(0); //获得一批剩余空间，用这些剩余空间来处理后面的usedSpaceList List<FreeSpace> freeSpaces = this.eliminateSpace(bigFreeSpace, firstUsedSpace, planType); // for (int i = 0; i < 1; i++) { // usedSpaceList.remove(usedSpaceList.size() - 1); // } //处理剩下的空间 int count = 0; while (usedSpaceList.size() > 0) { //获取当前要移除的空间 FreeSpace currentUsedSpace = usedSpaceList.remove(0); if (count < useFreeSpaceListClone.size()) count++; //获取本轮循环需要移除的剩余空间 List<FreeSpace> removeFreeSpaceList = new ArrayList<>(); //获取本轮循环需要加入的已用空间 List<FreeSpace> addFreeSpaceList = new ArrayList<>(); // System.out.println("freeSpaces:" + freeSpaces); for (int i = 0; i < freeSpaces.size(); i++) { FreeSpace freeSpace = freeSpaces.get(i); //判断有没有交集 // System.out.println("判断有无交集："); // System.out.println("空间1" + freeSpace.toString()); // System.out.println("空间2" + currentUsedSpace.toString()); int state = this.judgeSpaceRelationship(freeSpace, currentUsedSpace); // System.out.println("有无交集state：" + state); if (state == 0) { //无交集，直接切换下一个剩余空间 continue; } else if (state == 1) { //两个空间相交 if (count == 26 && i == 112 && getFreeSpaceUtilNum == 4) { int dsa = 0; } //有交集就要移除当前空间 removeFreeSpaceList.add(freeSpace); List<FreeSpace>[] spaceArray = this.splitSpace(currentUsedSpace, freeSpace); //移除交集空间之后，已用空间的分解空间 List<FreeSpace> usedList = spaceArray[0]; //移除交集空间之后，剩余空间的分解空间 List<FreeSpace> freeList = spaceArray[1]; //验证生成的空间是否与currentUsedSpace相交 // for (FreeSpace space : freeList) { // for (int j = 0; j < count; j++) { // if (this.judgeSpaceRelationship(space, useFreeSpaceListClone.get(j)) != 0) { // System.out.println("count>>" + count); // System.out.println("i>>" + i); // System.out.println("getFreeSpaceUtilNum>>" + getFreeSpaceUtilNum); // throw new Exception("space>>" + space + ",useFreeSpaceListClone.get(i)>>" + useFreeSpaceListClone.get(j)); // } // } // } //将剩余空间的分解空间添加到剩余空间列表 addFreeSpaceList.addAll(freeList); //将已用空间的分解空间添加到已用空间列表 usedSpaceList.addAll(usedList); } else if (state == 2) { //剩余空间全包含已用空间 removeFreeSpaceList.add(freeSpace); //获取移除已用空间之后得到的剩余空间列表 List<FreeSpace> freeSpaceList1 = this.eliminateSpace(freeSpace, currentUsedSpace, planType); //验证生成的空间是否与currentUsedSpace相交 // for (FreeSpace space : freeSpaceList1) { // for (int j = 0; j < count; j++) { // if (this.judgeSpaceRelationship(space, useFreeSpaceListClone.get(j)) != 0) { // System.out.println("count>>" + count); // System.out.println("i>>" + i); // System.out.println("getFreeSpaceUtilNum>>" + getFreeSpaceUtilNum); // throw new Exception("space>>" + space + ",useFreeSpaceListClone.get(i)>>" + useFreeSpaceListClone.get(j)); // } // } // } addFreeSpaceList.addAll(freeSpaceList1); //因为剩余空间包含已用空间，且各剩余空间不交错，可以直接break break; } else if (state == 3) { //已用空间全包含剩余空间 removeFreeSpaceList.add(freeSpace); //获取移除剩余空间之后，待移除的已用分解空间列表 List<FreeSpace> freeSpaceList1 = this.eliminateSpace(currentUsedSpace, freeSpace, planType); usedSpaceList.addAll(freeSpaceList1); } // System.out.println("来到这里"); } for (FreeSpace freeSpace : freeSpaces) { } //将分割得到的剩余空间添加回来，以便给下一个已用空间使用 freeSpaces.addAll(addFreeSpaceList); //减去已经使用的剩余空间 freeSpaces.removeAll(removeFreeSpaceList); } //存储最终的剩余空间 freeSpaceList.addAll((List<FreeSpace>) DeepCloneUtil.deepClone(freeSpaces)); Collections.sort(freeSpaceList); //处理长度 for (FreeSpace freeSpace : freeSpaceList) { if (freeSpace.getX() + freeSpace.getLength() > bigFreeSpace.getX() + bigFreeSpace.getLength()) { freeSpace.setLength(bigFreeSpace.getX() + bigFreeSpace.getLength() - freeSpace.getX()); } } //移除掉和已用空间有交错的空间，移除长宽高其中为零的空间 List<FreeSpace> removeSpaceList = new ArrayList<>(); for (FreeSpace freeSpace : freeSpaceList) { // for (FreeSpace space : useFreeSpaceListClone) { // if (this.judgeSpaceRelationship(freeSpace, space) != 0) { // removeSpaceList.add(freeSpace); // } // } if (freeSpace.getLength() < 1 || freeSpace.getWidth() < 1 || freeSpace.getHeight() < 1) { removeSpaceList.add(freeSpace); } } freeSpaceList.removeAll(removeSpaceList); //合并空间 this.combineSpaces(freeSpaceList); // System.out.println("最终剩余空间"); // System.out.println("剩余空间数量" + freeSpaceList.size()); // System.out.println(freeSpaceList); } /** * 合并可以合并的空间 * * @param spaces */ public void combineSpaces(List<FreeSpace> spaces) { this.combineSpacesOnLenDirection(spaces); this.combineSpacesOnWidDirection(spaces); this.combineSpacesOnHeiDirection(spaces); } /** * 长度方向上合并相同宽、高，且可拼接的空间 * * @param spaces */ public void combineSpacesOnLenDirection(List<FreeSpace> spaces) { int offset = 1; //将剩余空间按照x升序排排序 Collections.sort(spaces, (o1, o2) -> { if (o1.getX() > o2.getX()) { return 1; } else if (o1.getX() < o2.getX()) { return -1; } else { return 0; } }); int i = 0; while (i < spaces.size() - 1) { FreeSpace spaceI = spaces.get(i); List<FreeSpace> removeSpaces = new ArrayList<>(); int j = i + 1; while (j < spaces.size()) { FreeSpace spaceJ = spaces.get(j); if (Math.abs(spaceJ.getX() - spaceI.getX() - spaceI.getLength()) <= offset && Math.abs(spaceJ.getY() - spaceI.getY()) <= offset && Math.abs(spaceJ.getZ() - spaceI.getZ()) <= offset && Math.abs(spaceJ.getWidth() - spaceI.getWidth()) <= offset && Math.abs(spaceJ.getHeight() - spaceI.getHeight()) <= offset ) { spaceI.setLength(spaceI.getLength() + spaceJ.getLength()); removeSpaces.add(spaceJ); } j++; } spaces.removeAll(removeSpaces); i++; } } /** * 宽度方向上合并相同长、高，且可拼接的空间 * * @param spaces */ public void combineSpacesOnWidDirection(List<FreeSpace> spaces) { int offset = 1; //将剩余空间按照y升序排排序 Collections.sort(spaces, (o1, o2) -> { if (o1.getY() > o2.getY()) { return 1; } else if (o1.getY() < o2.getY()) { return -1; } else { return 0; } }); int i = 0; while (i < spaces.size() - 1) { FreeSpace spaceI = spaces.get(i); List<FreeSpace> removeSpaces = new ArrayList<>(); int j = i + 1; while (j < spaces.size()) { FreeSpace spaceJ = spaces.get(j); if (Math.abs(spaceJ.getY() - spaceI.getY() - spaceI.getWidth()) <= offset && Math.abs(spaceJ.getX() - spaceI.getX()) <= offset && Math.abs(spaceJ.getZ() - spaceI.getZ()) <= offset && Math.abs(spaceJ.getLength() - spaceI.getLength()) <= offset && Math.abs(spaceJ.getHeight() - spaceI.getHeight()) <= offset ) { spaceI.setWidth(spaceI.getWidth() + spaceJ.getWidth()); removeSpaces.add(spaceJ); } j++; } spaces.removeAll(removeSpaces); i++; } } /** * 高度方向上合并相同长、宽，且可拼接的空间 * * @param spaces */ public void combineSpacesOnHeiDirection(List<FreeSpace> spaces) { int offset = 1; //将剩余空间按照z升序排排序 Collections.sort(spaces, (o1, o2) -> { if (o1.getZ() > o2.getZ()) { return 1; } else if (o1.getZ() < o2.getZ()) { return -1; } else { return 0; } }); int i = 0; while (i < spaces.size() - 1) { FreeSpace spaceI = spaces.get(i); List<FreeSpace> removeSpaces = new ArrayList<>(); int j = i + 1; while (j < spaces.size()) { FreeSpace spaceJ = spaces.get(j); if (Math.abs(spaceJ.getZ() - spaceI.getZ() - spaceI.getHeight()) <= offset && Math.abs(spaceJ.getX() - spaceI.getX()) <= offset && Math.abs(spaceJ.getY() - spaceI.getY()) <= offset && Math.abs(spaceJ.getLength() - spaceI.getLength()) <= offset && Math.abs(spaceJ.getWidth() - spaceI.getWidth()) <= offset ) { spaceI.setHeight(spaceI.getHeight() + spaceJ.getHeight()); removeSpaces.add(spaceJ); } j++; } spaces.removeAll(removeSpaces); i++; } } /** * 检验数据是否正确 * 1、所有已用空间不能互相重合 * 2、所有已用空间都在最大空间内 * * @param bigFreeSpace * @param usedSpaceList * @return false:数据不合理 */ private boolean inspectionData(FreeSpace bigFreeSpace, List<FreeSpace> usedSpaceList) { for (int i = 0; i < usedSpaceList.size(); i++) { //判断是否所有usedSpace都被包含在bigFreeSpace中 if (this.judgeSpaceRelationship(bigFreeSpace, usedSpaceList.get(i)) != 2) { // System.out.println("bigFreeSpace>>" + bigFreeSpace); // System.out.println("usedSpaceList.get(i)>>" + usedSpaceList.get(i)); // System.out.println("不是所有usedSpace都被包含在bigFreeSpace中"); return false; } //判断usedSpace之间是否相互重合 // for (int j = 0; j < usedSpaceList.size(); j++) { // System.out.println("相交类型：" + this.judgeSpaceRelationship(usedSpaceList.get(i), usedSpaceList.get(j))); // if (i != j && (this.judgeSpaceRelationship(usedSpaceList.get(i), usedSpaceList.get(j)) != 0)) { // System.out.println("usedSpace之间相互重合"); // return false; // } // } } return true; } /** * 判断两个空间是否有交集，有返回1，没有返回0， * 若freeSpace1全包含freeSpace2，返回2， * 若freeSpace2全包含freeSpace1，返回3 * * @param freeSpace1 * @param freeSpace2 * @return */ public int judgeSpaceRelationship(FreeSpace freeSpace1, FreeSpace freeSpace2) { int offSet = 1; //判断freeSpace1是否全包含freeSpace2 if (freeSpace1.getX() - offSet <= freeSpace2.getX() && freeSpace1.getY() - offSet <= freeSpace2.getY() && freeSpace1.getZ() - offSet <= freeSpace2.getZ() && freeSpace1.getX() + freeSpace1.getLength() >= freeSpace2.getX() + freeSpace2.getLength() - offSet && freeSpace1.getY() + freeSpace1.getWidth() >= freeSpace2.getY() + freeSpace2.getWidth() - offSet && freeSpace1.getZ() + freeSpace1.getHeight() >= freeSpace2.getZ() + freeSpace2.getHeight() - offSet ) { return 2; } //判断freeSpace2是否全包含freeSpace1 if (freeSpace2.getX() <= freeSpace1.getX() && freeSpace2.getY() <= freeSpace1.getY() && freeSpace2.getZ() <= freeSpace1.getZ() && freeSpace2.getX() + freeSpace2.getLength() >= freeSpace1.getX() + freeSpace1.getLength() && freeSpace2.getY() + freeSpace2.getWidth() >= freeSpace1.getY() + freeSpace1.getWidth() && freeSpace2.getZ() + freeSpace2.getHeight() >= freeSpace1.getZ() + freeSpace1.getHeight() ) { return 3; } //获取两个空间的中心坐标 double x1 = freeSpace1.getX() + (freeSpace1.getLength() * 1.0) / 2; double y1 = freeSpace1.getY() + (freeSpace1.getWidth() * 1.0) / 2; double z1 = freeSpace1.getZ() + (freeSpace1.getHeight() * 1.0) / 2; double x2 = freeSpace2.getX() + (freeSpace2.getLength() * 1.0) / 2; double y2 = freeSpace2.getY() + (freeSpace2.getWidth() * 1.0) / 2; double z2 = freeSpace2.getZ() + (freeSpace2.getHeight() * 1.0) / 2; /* System.out.println("<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<"); System.out.println("freeSpace1>>" + freeSpace1); System.out.println("x1:" + x1 + "," + "y1:" + y1 + "," + "z1:" + z1); System.out.println("freeSpace2>>" + freeSpace2); System.out.println("x2:" + x2 + "," + "y2:" + y2 + "," + "z2:" + z2); System.out.println("-----------------------------------------------------------------"); System.out.println("Math.abs(x1 - x2) * 2:" + Math.abs(x1 - x2) * 2); System.out.println(" (freeSpace1.getLength() + freeSpace2.getLength()):" + (freeSpace1.getLength() + freeSpace2.getLength())); System.out.println("Math.abs(y1 - y2) * 2:" + Math.abs(y1 - y2) * 2); System.out.println("(freeSpace1.getWidth() + freeSpace2.getWidth()):" + (freeSpace1.getWidth() + freeSpace2.getWidth())); System.out.println("Math.abs(z1 - z2) * 2:" + Math.abs(z1 - z2) * 2); System.out.println("(freeSpace1.getHeight() + freeSpace2.getHeight())):" + (freeSpace1.getHeight() + freeSpace2.getHeight())); System.out.println(">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>"); */ //判断是否相交 if (Math.abs(x1 - x2) * 2 < (freeSpace1.getLength() + freeSpace2.getLength()) && Math.abs(y1 - y2) * 2 < (freeSpace1.getWidth() + freeSpace2.getWidth()) && Math.abs(z1 - z2) * 2 < (freeSpace1.getHeight() + freeSpace2.getHeight())) { return 1; } return 0; } /** * 给定两个空间，获取两个空间的共有空间 * * @param freeSpace1 * @param freeSpace2 * @return */ public FreeSpace getSameSpace(FreeSpace freeSpace1, FreeSpace freeSpace2) { //freeSpace1包含freeSpace2的角个数 List<Point> pointList1 = this.calculatePointNum(freeSpace1, freeSpace2); int size1 = pointList1.size(); //freeSpace2包含freeSpace1的角个数 List<Point> pointList2 = this.calculatePointNum(freeSpace2, freeSpace1); int size2 = pointList2.size(); // System.out.println("size1>>" + size1 + "," + "size2>>" + size2); //当两个矩形的点互不被包含时 if (size1 == 0 && size2 == 0) { int x = 0; int y = 0; int z = 0; int len = 0; int wid = 0; int hei = 0; //决定x和length // if (freeSpace1.getX() + freeSpace1.getLength() <= freeSpace2.getX() + freeSpace2.getLength()) { // x = freeSpace1.getX(); // len = freeSpace1.getLength(); // } else { // x = freeSpace2.getX(); // len = freeSpace2.getLength(); // } List<Integer> pointList = new ArrayList<>(); Collections.addAll(pointList, freeSpace1.getX(), freeSpace1.getX() + freeSpace1.getLength(), freeSpace2.getX(), freeSpace2.getX() + freeSpace2.getLength()); Collections.sort(pointList); x = pointList.get(1); len = pointList.get(2) - pointList.get(1); //决定y和width // if (freeSpace1.getY() + freeSpace1.getWidth() <= freeSpace2.getY() + freeSpace2.getWidth()) { // y = freeSpace1.getY(); // wid = freeSpace1.getWidth(); // } else { // y = freeSpace2.getY(); // wid = freeSpace2.getWidth(); // } pointList.clear(); Collections.addAll(pointList, freeSpace1.getY(), freeSpace1.getY() + freeSpace1.getWidth(), freeSpace2.getY(), freeSpace2.getY() + freeSpace2.getWidth()); Collections.sort(pointList); y = pointList.get(1); wid = pointList.get(2) - pointList.get(1); //决定z和height // if (freeSpace1.getZ() + freeSpace1.getHeight() <= freeSpace2.getZ() + freeSpace2.getHeight()) { // z = freeSpace1.getZ(); // hei = freeSpace1.getHeight(); // } else { // z = freeSpace2.getZ(); // hei = freeSpace2.getHeight(); // } pointList.clear(); Collections.addAll(pointList, freeSpace1.getZ(), freeSpace1.getZ() + freeSpace1.getHeight(), freeSpace2.getZ(), freeSpace2.getZ() + freeSpace2.getHeight()); Collections.sort(pointList); z = pointList.get(1); hei = pointList.get(2) - pointList.get(1); return new FreeSpace(x, y, z, len, wid, hei, 1); } //freeSpace1大于freeSpace2（不是体积意义上的大于） if (size1 >= size2) { //只有一个角被包含 if (size1 == 1) { return this.getSameSpaceWithOnePoint(freeSpace1, pointList1.get(0)); } else if (size1 == 2) { FreeSpace sameSpaceWithTwoPoint = this.getSameSpaceWithTwoPoint(freeSpace1, pointList1.get(0), pointList1.get(1)); return sameSpaceWithTwoPoint; } else if (size1 == 4) { return this.getSameSpaceWithFourPoint(freeSpace1, pointList1.get(0), pointList1.get(1), pointList1.get(2), pointList1.get(3)); } } else { //只有一个角被包含 if (size2 == 1) { return this.getSameSpaceWithOnePoint(freeSpace2, pointList2.get(0)); } else if (size2 == 2) { return this.getSameSpaceWithTwoPoint(freeSpace2, pointList2.get(0), pointList2.get(1)); } else if (size2 == 4) { // System.out.println("寻找共同空间"); return this.getSameSpaceWithFourPoint(freeSpace2, pointList2.get(0), pointList2.get(1), pointList2.get(2), pointList2.get(3)); } } return null; } /** * 给定一个已用空间，获取剩余空间 * * @param bigSpace * @param smallSpace * @param planType * @return */ public List<FreeSpace> eliminateSpace(FreeSpace bigSpace, FreeSpace smallSpace, int planType) { switch (planType) { case 1: return this.eliminateSpaceOne(bigSpace, smallSpace); case 2: return this.eliminateSpaceTwo(bigSpace, smallSpace); } return null; } /** * 剔除空间 * 给定一个大空间和一个小空间，将小空间从大空间中剔除，最多返回六个剩余空间 * * @param bigSpace * @param smallSpace */ 方案一 public List<FreeSpace> eliminateSpaceOne(FreeSpace bigSpace, FreeSpace smallSpace) { int acceptMinLen = 1; List<FreeSpace> freeSpaceList = new ArrayList<>(); // System.out.println("bigSpace>>" + bigSpace); // System.out.println("smallSpace>>" + smallSpace); //获取第一个空间 if (Math.abs(bigSpace.getY() - smallSpace.getY()) <= acceptMinLen) { //这个空间已经很小了，抛弃 } else { freeSpaceList.add(new FreeSpace(bigSpace.getX(), bigSpace.getY(), bigSpace.getZ(), smallSpace.getX() + smallSpace.getLength() - bigSpace.getX(), smallSpace.getY() - bigSpace.getY(), bigSpace.getHeight())); } //获取第二个空间 if (Math.abs(smallSpace.getX() - bigSpace.getX()) <= acceptMinLen) { //这个空间已经很小了，抛弃 } else { freeSpaceList.add(new FreeSpace(bigSpace.getX(), smallSpace.getY(), bigSpace.getZ(), smallSpace.getX() - bigSpace.getX(), smallSpace.getWidth(), bigSpace.getHeight())); } //获取第三个空间 if (Math.abs(smallSpace.getZ() - bigSpace.getZ()) <= acceptMinLen) { //这个空间已经很小了，抛弃 } else { freeSpaceList.add(new FreeSpace(smallSpace.getX(), smallSpace.getY(), bigSpace.getZ(), smallSpace.getLength(), smallSpace.getWidth(), smallSpace.getZ() - bigSpace.getZ())); } //获取第四个空间 if (Math.abs(bigSpace.getZ() + bigSpace.getHeight() - smallSpace.getZ() - smallSpace.getHeight()) <= acceptMinLen) { //这个空间已经很小了，抛弃 } else { freeSpaceList.add(new FreeSpace(smallSpace.getX(), smallSpace.getY(), smallSpace.getZ() + smallSpace.getHeight(), smallSpace.getLength(), smallSpace.getWidth(), bigSpace.getZ() + bigSpace.getHeight() - smallSpace.getZ() - smallSpace.getHeight())); } //获取第五个空间 if (Math.abs(bigSpace.getY() + bigSpace.getWidth() - smallSpace.getY() - smallSpace.getWidth()) <= acceptMinLen) { //这个空间已经很小了，抛弃 } else { freeSpaceList.add(new FreeSpace(bigSpace.getX(), smallSpace.getY() + smallSpace.getWidth(), bigSpace.getZ(), smallSpace.getX() + smallSpace.getLength() - bigSpace.getX(), bigSpace.getY() + bigSpace.getWidth() - smallSpace.getY() - smallSpace.getWidth(), bigSpace.getHeight())); } //获取第六个空间 if (Math.abs(bigSpace.getX() + bigSpace.getLength() - smallSpace.getX() - smallSpace.getLength()) <= acceptMinLen) { //这个空间已经很小了，抛弃 } else { freeSpaceList.add(new FreeSpace(smallSpace.getX() + smallSpace.getLength(), bigSpace.getY(), bigSpace.getZ(), bigSpace.getX() + bigSpace.getLength() - smallSpace.getX() - smallSpace.getLength(), bigSpace.getWidth(), bigSpace.getHeight())); } return freeSpaceList; } 方案二 public List<FreeSpace> eliminateSpaceTwo(FreeSpace bigSpace, FreeSpace smallSpace) { int acceptMinLen = 1; List<FreeSpace> freeSpaceList = new ArrayList<>(); // System.out.println("bigSpace>>" + bigSpace); // System.out.println("smallSpace>>" + smallSpace); //获取第一个空间 if (Math.abs(bigSpace.getY() - smallSpace.getY()) <= acceptMinLen) { //这个空间已经很小了，抛弃 } else { freeSpaceList.add(new FreeSpace(bigSpace.getX(), bigSpace.getY(), bigSpace.getZ(), smallSpace.getX() + smallSpace.getLength() - bigSpace.getX(), smallSpace.getY() - bigSpace.getY(), smallSpace.getZ() + smallSpace.getHeight() - bigSpace.getZ())); } //获取第二个空间 if (Math.abs(smallSpace.getX() - bigSpace.getX()) <= acceptMinLen) { //这个空间已经很小了，抛弃 } else { freeSpaceList.add(new FreeSpace(bigSpace.getX(), smallSpace.getY(), smallSpace.getZ(), smallSpace.getX() - bigSpace.getX(), smallSpace.getWidth(), smallSpace.getHeight())); } //获取第三个空间 if (Math.abs(smallSpace.getZ() - bigSpace.getZ()) <= acceptMinLen) { //这个空间已经很小了，抛弃 } else { freeSpaceList.add(new FreeSpace(bigSpace.getX(), smallSpace.getY(), bigSpace.getZ(), smallSpace.getX() + smallSpace.getLength() - bigSpace.getX(), smallSpace.getWidth(), smallSpace.getZ() - bigSpace.getZ())); } //获取第四个空间 if (Math.abs(bigSpace.getZ() + bigSpace.getHeight() - smallSpace.getZ() - smallSpace.getHeight()) <= acceptMinLen) { //这个空间已经很小了，抛弃 } else { freeSpaceList.add(new FreeSpace(bigSpace.getX(), bigSpace.getY(), smallSpace.getZ() + smallSpace.getHeight(), smallSpace.getX() + smallSpace.getLength() - bigSpace.getX(), bigSpace.getWidth(), bigSpace.getZ() + bigSpace.getHeight() - smallSpace.getZ() - smallSpace.getHeight())); } //获取第五个空间 if (Math.abs(bigSpace.getY() + bigSpace.getWidth() - smallSpace.getY() - smallSpace.getWidth()) <= acceptMinLen) { //这个空间已经很小了，抛弃 } else { freeSpaceList.add(new FreeSpace(bigSpace.getX(), smallSpace.getY() + smallSpace.getWidth(), bigSpace.getZ(), smallSpace.getX() + smallSpace.getLength() - bigSpace.getX(), bigSpace.getY() + bigSpace.getWidth() - smallSpace.getY() - smallSpace.getWidth(), smallSpace.getZ() + smallSpace.getHeight() - bigSpace.getZ())); } //获取第六个空间 if (Math.abs(bigSpace.getX() + bigSpace.getLength() - smallSpace.getX() - smallSpace.getLength()) <= acceptMinLen) { //这个空间已经很小了，抛弃 } else { freeSpaceList.add(new FreeSpace(smallSpace.getX() + smallSpace.getLength(), bigSpace.getY(), bigSpace.getZ(), bigSpace.getX() + bigSpace.getLength() - smallSpace.getX() - smallSpace.getLength(), bigSpace.getWidth(), bigSpace.getHeight())); } /* for (int i = 0; i < freeSpaceList.size() - 1; i++) { for (int j = i + 1; j < freeSpaceList.size(); j++) { System.out.println(this.judgeSpaceRelationship(freeSpaceList.get(i), freeSpaceList.get(j))); if (this.judgeSpaceRelationship(freeSpaceList.get(i), freeSpaceList.get(j)) != 0) { try { throw new Exception("空间重叠"); } catch (Exception e) { e.printStackTrace(); } } } }*/ return freeSpaceList; } 方案三 /* public List<FreeSpace> eliminateSpace(FreeSpace bigSpace, FreeSpace smallSpace) { int acceptMinLen = 1; List<FreeSpace> freeSpaceList = new ArrayList<>(); // System.out.println("bigSpace>>" + bigSpace); // System.out.println("smallSpace>>" + smallSpace); //获取第一个空间 if (Math.abs(bigSpace.getY() - smallSpace.getY()) <= acceptMinLen) { //这个空间已经很小了，抛弃 } else { freeSpaceList.add(new FreeSpace(bigSpace.getX(), bigSpace.getY(), bigSpace.getZ(), smallSpace.getX() + smallSpace.getLength() - bigSpace.getX(), smallSpace.getY() - bigSpace.getY(), smallSpace.getZ() + smallSpace.getHeight() - bigSpace.getZ())); } //获取第二个空间 if (Math.abs(smallSpace.getX() - bigSpace.getX()) <= acceptMinLen) { //这个空间已经很小了，抛弃 } else { freeSpaceList.add(new FreeSpace(bigSpace.getX(), smallSpace.getY(), smallSpace.getZ(), smallSpace.getX() - bigSpace.getX(), smallSpace.getWidth(), smallSpace.getHeight())); } //获取第三个空间 if (Math.abs(smallSpace.getZ() - bigSpace.getZ()) <= acceptMinLen) { //这个空间已经很小了，抛弃 } else { freeSpaceList.add(new FreeSpace(bigSpace.getX(), smallSpace.getY(), bigSpace.getZ(), smallSpace.getX() + smallSpace.getLength() - bigSpace.getX(), smallSpace.getWidth(), smallSpace.getZ() - bigSpace.getZ())); } //获取第四个空间 if (Math.abs(bigSpace.getZ() + bigSpace.getHeight() - smallSpace.getZ() - smallSpace.getHeight()) <= acceptMinLen) { //这个空间已经很小了，抛弃 } else { freeSpaceList.add(new FreeSpace(bigSpace.getX(), bigSpace.getY(), smallSpace.getZ() + smallSpace.getHeight(), smallSpace.getX() + smallSpace.getLength() - bigSpace.getX(), smallSpace.getY() + smallSpace.getWidth() - bigSpace.getY(), bigSpace.getZ() + bigSpace.getHeight() - smallSpace.getZ() - smallSpace.getHeight())); } //获取第五个空间 if (Math.abs(bigSpace.getY() + bigSpace.getWidth() - smallSpace.getY() - smallSpace.getWidth()) <= acceptMinLen) { //这个空间已经很小了，抛弃 } else { freeSpaceList.add(new FreeSpace(bigSpace.getX(), smallSpace.getY() + smallSpace.getWidth(), bigSpace.getZ(), smallSpace.getX() + smallSpace.getLength() - bigSpace.getX(), bigSpace.getY() + bigSpace.getWidth() - smallSpace.getY() - smallSpace.getWidth(), bigSpace.getHeight())); } //获取第六个空间 if (Math.abs(bigSpace.getX() + bigSpace.getLength() - smallSpace.getX() - smallSpace.getLength()) <= acceptMinLen) { //这个空间已经很小了，抛弃 } else { freeSpaceList.add(new FreeSpace(smallSpace.getX() + smallSpace.getLength(), bigSpace.getY(), bigSpace.getZ(), bigSpace.getX() + bigSpace.getLength() - smallSpace.getX() - smallSpace.getLength(), bigSpace.getWidth(), bigSpace.getHeight())); } return freeSpaceList; }*/ /** * 给定一个剩余空间，返回剩余空间的八个角坐标 * * @param space * @return */ public List<Point> getPointListWithSpace(FreeSpace space) { List<Point> pointList = new ArrayList<>(); //点1 pointList.add(new Point(space.getX(), space.getY(), space.getZ(), 1)); //点2 pointList.add(new Point(space.getX() + space.getLength(), space.getY(), space.getZ(), 2)); //点3 pointList.add(new Point(space.getX() + space.getLength(), space.getY() + space.getWidth(), space.getZ(), 3)); //点4 pointList.add(new Point(space.getX(), space.getY() + space.getWidth(), space.getZ(), 4)); //点5 pointList.add(new Point(space.getX(), space.getY(), space.getZ() + space.getHeight(), 5)); //点6 pointList.add(new Point(space.getX() + space.getLength(), space.getY(), space.getZ() + space.getHeight(), 6)); //点7 pointList.add(new Point(space.getX() + space.getLength(), space.getY() + space.getWidth(), space.getZ() + space.getHeight(), 7)); //点8 pointList.add(new Point(space.getX(), space.getY() + space.getWidth(), space.getZ() + space.getHeight(), 8)); return pointList; } /** * 给定一个点和一个空间，判断点是否被包含在空间中 * * @param space * @param point * @return */ public boolean isContainedInSpace(FreeSpace space, Point point) { if (space.getX() <= point.getX() && point.getX() <= (space.getX() + space.getLength()) && space.getY() <= point.getY() && point.getY() <= (space.getY() + space.getWidth()) && space.getZ() <= point.getZ() && point.getZ() <= (space.getZ() + space.getHeight()) ) { return true; } return false; } /** * 集合1：freeSpace1包含freeSpace2的角集合 * * @param freeSpace1 * @param freeSpace2 * @return */ public List<Point> calculatePointNum(FreeSpace freeSpace1, FreeSpace freeSpace2) { List<Point> pointList = new ArrayList<>(); List<Point> eightPointList = getPointListWithSpace(freeSpace2); // System.out.println("八个点集合："); // System.out.println(eightPointList.toString()); // // System.out.println("空间：" + freeSpace1.toString()); // System.out.println("x2:" + (freeSpace1.getX() + freeSpace1.getLength()) + ",y2:" + (freeSpace1.getY() + freeSpace1.getWidth()) + ",z2:" + (freeSpace1.getZ() + freeSpace1.getHeight())); for (Point point : eightPointList) { if (this.isContainedInSpace(freeSpace1, point) == true) { pointList.add(point); } } // System.out.println("找到的点数量" + pointList.size()); return pointList; } /** * 一个空间只有一个点被另一个空间包含时，找共同空间 * * @return */ public FreeSpace getSameSpaceWithOnePoint(FreeSpace bigSpace, Point point) { List<Point> pointListWithBigSpace = this.getPointListWithSpace(bigSpace); //1>七 if (point.getIndex() == 1) { return new FreeSpace(point.getX(), point.getY(), point.getZ(), pointListWithBigSpace.get(6).getX() - point.getX(), pointListWithBigSpace.get(6).getY() - point.getY(), pointListWithBigSpace.get(6).getZ() - point.getZ()); } //2>八 if (point.getIndex() == 2) { return new FreeSpace(pointListWithBigSpace.get(7).getX(), point.getY(), point.getZ(), point.getX() - pointListWithBigSpace.get(7).getX(), pointListWithBigSpace.get(7).getY() - point.getY(), pointListWithBigSpace.get(7).getZ() - point.getZ()); } //3>五 if (point.getIndex() == 3) { return new FreeSpace(pointListWithBigSpace.get(4).getX(), pointListWithBigSpace.get(4).getY(), point.getZ(), point.getX() - pointListWithBigSpace.get(4).getX(), point.getY() - pointListWithBigSpace.get(4).getY(), pointListWithBigSpace.get(4).getZ() - point.getZ()); } //4>六 if (point.getIndex() == 4) { return new FreeSpace(point.getX(), pointListWithBigSpace.get(5).getY(), point.getZ(), pointListWithBigSpace.get(5).getX() - point.getX(), point.getY() - pointListWithBigSpace.get(5).getY(), pointListWithBigSpace.get(5).getZ() - point.getZ()); } //5>三 if (point.getIndex() == 5) { return new FreeSpace(point.getX(), point.getY(), pointListWithBigSpace.get(2).getZ(), pointListWithBigSpace.get(2).getX() - point.getX(), pointListWithBigSpace.get(2).getY() - point.getY(), point.getZ() - pointListWithBigSpace.get(2).getZ()); } //6>四 if (point.getIndex() == 6) { // return new FreeSpace(pointListWithBigSpace.get(3).getX(), // point.getY(), // point.getZ(), // point.getX() - pointListWithBigSpace.get(3).getX(), // pointListWithBigSpace.get(3).getY() - point.getY(), // point.getZ() - pointListWithBigSpace.get(3).getZ()); return new FreeSpace(pointListWithBigSpace.get(3).getX(), point.getY(), pointListWithBigSpace.get(3).getZ(), point.getX() - pointListWithBigSpace.get(3).getX(), pointListWithBigSpace.get(3).getY() - point.getY(), point.getZ() - pointListWithBigSpace.get(3).getZ()); } //7>一 if (point.getIndex() == 7) { return new FreeSpace(pointListWithBigSpace.get(0).getX(), pointListWithBigSpace.get(0).getY(), pointListWithBigSpace.get(0).getZ(), point.getX() - pointListWithBigSpace.get(0).getX(), point.getY() - pointListWithBigSpace.get(0).getY(), point.getZ() - pointListWithBigSpace.get(0).getZ()); } //8>二 if (point.getIndex() == 8) { // return new FreeSpace(pointListWithBigSpace.get(1).getX(), // pointListWithBigSpace.get(1).getY(), // point.getZ(), // point.getX() - pointListWithBigSpace.get(1).getX(), // point.getY() - pointListWithBigSpace.get(1).getY(), // pointListWithBigSpace.get(1).getZ() - point.getZ()); return new FreeSpace(point.getX(), pointListWithBigSpace.get(1).getY(), pointListWithBigSpace.get(1).getZ(), pointListWithBigSpace.get(1).getX() - point.getX(), point.getY() - pointListWithBigSpace.get(1).getY(), pointListWithBigSpace.get(1).getZ() - point.getZ()); } return null; } /** * 一个空间有两个点被另一个空间包含时，找共同空间 * * @return */ public FreeSpace getSameSpaceWithTwoPoint(FreeSpace bigSpace, Point point1, Point point2) { List<Point> pointListWithBigSpace = this.getPointListWithSpace(bigSpace); //1、2 if (point1.getIndex() == 1 && point2.getIndex() == 2) { return new FreeSpace(point1.getX(), point1.getY(), point1.getZ(), point2.getX() - point1.getX(), pointListWithBigSpace.get(7).getY() - point1.getY(), pointListWithBigSpace.get(7).getZ() - point1.getZ()); } //3、4 if (point1.getIndex() == 3 && point2.getIndex() == 4) { return new FreeSpace(point2.getX(), pointListWithBigSpace.get(4).getY(), point2.getZ(), point1.getX() - point2.getX(), point2.getY() - pointListWithBigSpace.get(4).getY(), pointListWithBigSpace.get(4).getZ() - point2.getZ()); } //5、6 if (point1.getIndex() == 5 && point2.getIndex() == 6) { return new FreeSpace(point1.getX(), point1.getY(), pointListWithBigSpace.get(3).getZ(), point2.getX() - point1.getX(), pointListWithBigSpace.get(3).getY() - point1.getY(), point1.getZ() - pointListWithBigSpace.get(3).getZ()); } //7、8 if (point1.getIndex() == 7 && point2.getIndex() == 8) { return new FreeSpace(point2.getX(), pointListWithBigSpace.get(0).getY(), pointListWithBigSpace.get(0).getZ(), point1.getX() - point2.getX(), point2.getY() - pointListWithBigSpace.get(0).getY(), point2.getZ() - pointListWithBigSpace.get(0).getZ()); } //1、4 if (point1.getIndex() == 1 && point2.getIndex() == 4) { return new FreeSpace(point1.getX(), point1.getY(), point1.getZ(), pointListWithBigSpace.get(5).getX() - point1.getX(), point2.getY() - point1.getY(), pointListWithBigSpace.get(5).getZ() - point1.getZ()); } //5、8 if (point1.getIndex() == 5 && point2.getIndex() == 8) { return new FreeSpace(point1.getX(), point1.getY(), pointListWithBigSpace.get(1).getZ(), pointListWithBigSpace.get(1).getX() - point1.getX(), point2.getY() - point1.getY(), point1.getZ() - pointListWithBigSpace.get(1).getZ()); } //2、3 if (point1.getIndex() == 2 && point2.getIndex() == 3) { // return new FreeSpace(pointListWithBigSpace.get(1).getX(), // point1.getY(), // point1.getZ(), // point1.getX() - pointListWithBigSpace.get(4).getX(), // point2.getY() - point1.getY(), // pointListWithBigSpace.get(4).getZ() - point1.getZ()); return new FreeSpace(pointListWithBigSpace.get(4).getX(), point1.getY(), point1.getZ(), point1.getX() - pointListWithBigSpace.get(4).getX(), point2.getY() - point1.getY(), pointListWithBigSpace.get(4).getZ() - point1.getZ()); } //6、7 if (point1.getIndex() == 6 && point2.getIndex() == 7) { // return new FreeSpace(point1.getX(), // pointListWithBigSpace.get(0).getY(), // pointListWithBigSpace.get(0).getZ(), // point2.getX() - point1.getX(), // point2.getY() - pointListWithBigSpace.get(0).getY(), // point1.getZ() - pointListWithBigSpace.get(0).getZ()); return new FreeSpace(pointListWithBigSpace.get(0).getX(), point1.getY(), pointListWithBigSpace.get(0).getZ(), point2.getX() - pointListWithBigSpace.get(0).getX(), point2.getY() - point1.getY(), point1.getZ() - pointListWithBigSpace.get(0).getZ()); } //1、5 if (point1.getIndex() == 1 && point2.getIndex() == 5) { return new FreeSpace(point1.getX(), point1.getY(), point1.getZ(), pointListWithBigSpace.get(2).getX() - point1.getX(), pointListWithBigSpace.get(2).getY() - point1.getY(), point2.getZ() - point1.getZ()); } //2、6 if (point1.getIndex() == 2 && point2.getIndex() == 6) { return new FreeSpace(pointListWithBigSpace.get(3).getX(), point1.getY(), point1.getZ(), point1.getX() - pointListWithBigSpace.get(3).getX(), pointListWithBigSpace.get(3).getY() - point1.getY(), point2.getZ() - point1.getZ()); } //4、8 if (point1.getIndex() == 4 && point2.getIndex() == 8) { // return new FreeSpace(point1.getX(), // pointListWithBigSpace.get(1).getY(), // point1.getZ(), // pointListWithBigSpace.get(1).getX() - point1.getX(), // point1.getY() - pointListWithBigSpace.get(1).getY(), // point2.getZ() - point1.getZ()); return new FreeSpace(point1.getX(), pointListWithBigSpace.get(1).getY(), point1.getZ(), pointListWithBigSpace.get(1).getX() - point1.getX(), point1.getY() - pointListWithBigSpace.get(1).getY(), point2.getZ() - point1.getZ()); } //3、7 if (point1.getIndex() == 3 && point2.getIndex() == 7) { return new FreeSpace(pointListWithBigSpace.get(0).getX(), pointListWithBigSpace.get(0).getY(), point1.getZ(), point1.getX() - pointListWithBigSpace.get(0).getX(), point2.getY() - pointListWithBigSpace.get(0).getY(), point2.getZ() - point1.getZ()); } return null; } /** * 一个空间有四个点被另一个空间包含时，找共同空间 * * @return */ public FreeSpace getSameSpaceWithFourPoint(FreeSpace bigSpace, Point point1, Point point2, Point point3, Point point4) { List<Point> pointListWithBigSpace = this.getPointListWithSpace(bigSpace); //1、2、3、4 if (point1.getIndex() == 1 && point2.getIndex() == 2 && point3.getIndex() == 3 && point4.getIndex() == 4) { return new FreeSpace(point1.getX(), point1.getY(), point1.getZ(), point2.getX() - point1.getX(), point4.getY() - point1.getY(), pointListWithBigSpace.get(4).getZ() - point1.getZ()); } //5、6、7、8 if (point1.getIndex() == 5 && point2.getIndex() == 6 && point3.getIndex() == 7 && point4.getIndex() == 8) { return new FreeSpace(point1.getX(), point1.getY(), pointListWithBigSpace.get(3).getZ(), point2.getX() - point1.getX(), point4.getY() - point1.getY(), point1.getZ() - pointListWithBigSpace.get(3).getZ()); } //1、4、5、8 if (point1.getIndex() == 1 && point2.getIndex() == 4 && point3.getIndex() == 5 && point4.getIndex() == 8) { return new FreeSpace(point1.getX(), point1.getY(), point1.getZ(), pointListWithBigSpace.get(1).getX() - point1.getX(), point2.getY() - point1.getY(), point3.getZ() - point1.getZ()); } //2、3、6、7 if (point1.getIndex() == 2 && point2.getIndex() == 3 && point3.getIndex() == 6 && point4.getIndex() == 7) { return new FreeSpace(pointListWithBigSpace.get(0).getX(), point1.getY(), point1.getZ(), point1.getX() - pointListWithBigSpace.get(0).getX(), point2.getY() - point1.getY(), point3.getZ() - point1.getZ()); } //3、4、7、8 if (point1.getIndex() == 3 && point2.getIndex() == 4 && point3.getIndex() == 7 && point4.getIndex() == 8) { return new FreeSpace(point2.getX(), pointListWithBigSpace.get(0).getY(), point2.getZ(), point1.getX() - point2.getX(), point2.getY() - pointListWithBigSpace.get(0).getY(), point4.getZ() - point2.getZ()); } //1、2、5、6 if (point1.getIndex() == 1 && point2.getIndex() == 2 && point3.getIndex() == 5 && point4.getIndex() == 6) { return new FreeSpace(point1.getX(), point1.getY(), point1.getZ(), point2.getX() - point1.getX(), pointListWithBigSpace.get(3).getY() - point1.getY(), point3.getZ() - point1.getZ()); } return null; } /** * freeSpace1：已用空间 * freeSpace2：剩余空间 * * @return 数组 * * 数组元素1：已用空间的分解 * * 数组元素2：返回剩余空间 */ public List<FreeSpace>[] splitSpace(FreeSpace freeSpace1, FreeSpace freeSpace2) { List<FreeSpace>[] listArry = new List[2]; // System.out.println(">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>"); // System.out.println("freeSpace1>>" + freeSpace1 + "," + "freeSpace2>>" + freeSpace2); FreeSpace sameSpace = this.getSameSpace(freeSpace1, freeSpace2); // System.out.println("sameSpace" + sameSpace); // System.out.println("<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<"); listArry[0] = this.eliminateSpaceTwo(freeSpace1, sameSpace); listArry[1] = this.eliminateSpaceTwo(freeSpace2, sameSpace); return listArry; } }
效果演示
测试数据
package com.dam.controller; import com.dam.algorithm.algorithmPackage.freeSpaceTubePackingAlgorithm.util.GetUsedSpaceUtil; import com.dam.algorithm.common.entity.FreeSpace; import com.dam.common.Result; import io.swagger.annotations.Api; import io.swagger.annotations.ApiOperation; import org.springframework.web.bind.annotation.GetMapping; import org.springframework.web.bind.annotation.RequestMapping; import org.springframework.web.bind.annotation.RestController; import java.io.IOException; import java.util.ArrayList; import java.util.List; @RestController @RequestMapping("/splitSpace") @Api(tags = "获取装载方案") public class SplitSpaceController { @GetMapping("/usedSpace") @ApiOperation("获取装载方案集合") private Result usedSpace() throws Exception { //添加已用空间 List<FreeSpace> usedSpaceList = new ArrayList<>(); //需要修改大空间 usedSpaceList.add(new FreeSpace(0, 0, 0, 100, 100, 100)); this.addUsedSpace(usedSpaceList); return Result.ok().data("usedSpaceList", usedSpaceList); } @GetMapping("/splitSpace") @ApiOperation("获取装载方案集合") private Result splitSpace() throws Exception { System.out.println("开始计算"); long start = System.currentTimeMillis(); FreeSpace bigFreeSpace = new FreeSpace(0, 0, 0, 100, 100, 100); List<FreeSpace> freeSpaceList = new ArrayList<>(); freeSpaceList.add(bigFreeSpace); //添加已用空间 List<FreeSpace> usedSpaceList = new ArrayList<>(); this.addUsedSpace(usedSpaceList); //计算 new GetUsedSpaceUtil().getFreeSpaceUtil(bigFreeSpace, freeSpaceList, usedSpaceList); long end = System.currentTimeMillis(); System.out.println("计算时间：" + (end - start) + "ms"); return Result.ok().data("freeSpaceList", freeSpaceList); } private void addUsedSpace(List<FreeSpace> usedSpaceList) { usedSpaceList.add(new FreeSpace(0, 50, 50, 30, 30, 30)); usedSpaceList.add(new FreeSpace(0, 80, 80, 10, 20, 15)); usedSpaceList.add(new FreeSpace(36, 35, 50, 50, 30, 30)); usedSpaceList.add(new FreeSpace(0, 50, 0, 70, 50, 30)); usedSpaceList.add(new FreeSpace(0, 0, 0, 90, 20, 20)); } }
结果
大立方体和待切除的小立方体
切除小立方体之后剩余的空间
