Как оптимизировать 2D (панельную) резку [закрыто] ⇐ JAVA

[Anonymous]

Мы работаем над программой 2D-резки панелей, и я застрял на расчете оставшихся площадей после добавления на доску примера 4 элементов
Например: у меня есть доска 2,44x1,22 м2 img alt="введите описание изображения здесь" src="https://i.sstatic.net/jgQxk1Fd.png" />
Я хочу добавить

элемент 1: 2,1x0,3
элемент 2: 2,0x0,8
элемент 3: 0,3x0,9
элемент 4: 0,2x0,9

как вы можете видеть на изображении p>
поэтому я писал код много раз, но лучший из них показан ниже:

Код: Выделить всё

import UIKit

//(height, width)

let baseBoard = (Decimal(2.44), Decimal(1.22), UIColor.white)
var usedBoard: [UIColor] = []
var unUsedBoardsPartsIndex = -1
var unUsedBoardsParts: [(Int, Int, (Decimal, Decimal), (Decimal, Decimal), UIColor)] = [] // (index, boardNumber, (height, width) from board's bottom, (height, width) from board's side)
var usedElemantPartsOnBoard: [(Int, String)] = [] // (boardNumber, elemantName)

let bedBack = ("bedBack", Decimal(1.5), Decimal(1.0), UIColor.white) // (height, width)
let bedFront = ("bedFront", Decimal(0.6), Decimal(1.0), UIColor.white)
let bedSide1 = ("bedSide1", Decimal(2.2), Decimal(0.5), UIColor.blue)
let bedSide2 = ("bedSide2", Decimal(2.2), Decimal(0.5), UIColor.blue)

let comdinaSide1 = ("comdinaSide1", Decimal(0.6), Decimal(0.5), UIColor.blue)
let comdinaSide2 = ("comdinaSide2", Decimal(0.6), Decimal(0.5), UIColor.systemPink)
let comdinaUp = ("comdinaUp", Decimal(0.6), Decimal(0.6), UIColor.white)
let comdinaDrawer1 = ("comdinaDrawer1", Decimal(0.2), Decimal(0.5), UIColor.white)
let comdinaDrawer2 = ("comdinaDrawer2", Decimal(0.2), Decimal(0.5), UIColor.white)

let wardrobeSide1 = ("wardrobeSide1", Decimal(2.2), Decimal(1.0), UIColor.white)
let wardrobeSide2 = ("wardrobeSide2", Decimal(2.2), Decimal(1.0), UIColor.white)
let wardrobeUp = ("wardrobeUp", Decimal(2.4), Decimal(1.1), UIColor.white)
let wardrobeDown = ("wardrobeDown", Decimal(2.4), Decimal(1.1), UIColor.white)
let wardrobeDoor1 = ("wardrobeDoor1", Decimal(2.1), Decimal(0.7), UIColor.white)
let wardrobeDoor2 = ("wardrobeDoor2", Decimal(2.1), Decimal(0.7), UIColor.white)
let wardrobeDoor3 = ("wardrobeDoor3", Decimal(2.1), Decimal(0.7), UIColor.white)

let allElemants = [bedBack, bedFront, bedSide1, bedSide2, comdinaSide1, comdinaSide2, comdinaUp, comdinaDrawer1, comdinaDrawer2, wardrobeSide1, wardrobeSide2, wardrobeUp, wardrobeDown, wardrobeDoor1, wardrobeDoor2, wardrobeDoor3]
var currentElemants = [bedBack, bedFront, bedSide1, bedSide2, comdinaSide1, comdinaSide2, comdinaUp, comdinaDrawer1, comdinaDrawer2, wardrobeSide1, wardrobeSide2, wardrobeUp, wardrobeDown, wardrobeDoor1, wardrobeDoor2, wardrobeDoor3]

enum Orientation {
case BottomVirticaly
case BottomHorizontally
case SideVirticaly
case SideHorizontally
}

calculate()

func calculate() {
var largestElemant = findLargestElemant()

if !unUsedBoardsParts.isEmpty {
lookForExistsBoardParts(largestElemant: largestElemant)

} else {
useNewBoard(largestElemant: largestElemant)
}

checkIfNoElemantLeft()
}

func findLargestElemant() -> (String, Decimal, Decimal, UIColor) {
var largestElemantIndex = 0
var largestElemant = currentElemants[0]

for i in 0...currentElemants.count - 1 {
if currentElemants[i].1 * currentElemants[i].2 > largestElemant.1 * largestElemant.2 {
largestElemantIndex = i
largestElemant = currentElemants[i]
}
}

currentElemants.remove(at: largestElemantIndex)

return largestElemant
}

func lookForExistsBoardParts(largestElemant: (String, Decimal, Decimal, UIColor)) {
var partFits = false

for i in 0...unUsedBoardsParts.count - 1 {
if unUsedBoardsParts[i].4 == largestElemant.3 {

let checkIfBottomVirticalyFits = largestElemant.1 < unUsedBoardsParts[i].2.0 && largestElemant.2 < unUsedBoardsParts[i].2.1
let checkIfBottomHorizontallyFits = largestElemant.2 < unUsedBoardsParts[i].2.0 && largestElemant.1 < unUsedBoardsParts[i].2.1

let checkIfSideVirticalyFits = largestElemant.1 < unUsedBoardsParts[i].3.0 && largestElemant.2 < unUsedBoardsParts[i].3.1
let checkIfSideHorizontallyFits = largestElemant.2 < unUsedBoardsParts[i].3.0 && largestElemant.1 <  unUsedBoardsParts[i].3.1

if checkIfBottomVirticalyFits {
partFits = true
useUsedBoardPart(largestElemant: largestElemant, boardPart: unUsedBoardsParts[i], orientation: .BottomVirticaly)
break

} else if checkIfBottomHorizontallyFits {
partFits = true
useUsedBoardPart(largestElemant: largestElemant, boardPart: unUsedBoardsParts[i], orientation: .BottomHorizontally)
break

} else if checkIfSideVirticalyFits {
partFits = true
useUsedBoardPart(largestElemant: largestElemant, boardPart: unUsedBoardsParts[i], orientation: .SideVirticaly)
break

} else if checkIfSideHorizontallyFits {
partFits = true
useUsedBoardPart(largestElemant: largestElemant, boardPart: unUsedBoardsParts[i], orientation: .SideHorizontally)
break
}
}
}

if !partFits {
useNewBoard(largestElemant: largestElemant)
}
}

func useUsedBoardPart(largestElemant: (String, Decimal, Decimal, UIColor), boardPart: (Int, Int, (Decimal, Decimal), (Decimal, Decimal), UIColor), orientation: Orientation) {
let boardPartIndex = unUsedBoardsParts.firstIndex { (index, boardNumber, bottom, side, color) in
index == boardPart.0
}

guard boardPartIndex != nil else { return }

if orientation == .BottomVirticaly {
let heightLeft = boardPart.2.0 - largestElemant.1

usedElemantPartsOnBoard.append((boardPart.1, largestElemant.0))
unUsedBoardsParts[boardPartIndex ?? 0] = (boardPart.0, boardPart.1, (heightLeft, boardPart.2.1), boardPart.3, largestElemant.3)

} else if orientation == .BottomHorizontally {
let heightLeft = boardPart.2.1 - largestElemant.1

usedElemantPartsOnBoard.append((boardPart.1, largestElemant.0))
unUsedBoardsParts[boardPartIndex ?? 0] = (boardPart.0, boardPart.1, (heightLeft, boardPart.2.1), boardPart.3, largestElemant.3)

} else if orientation == .SideVirticaly {
let heightLeft = boardPart.3.0 - largestElemant.1

usedElemantPartsOnBoard.append((boardPart.1, largestElemant.0))
unUsedBoardsParts[boardPartIndex ?? 0] = (boardPart.0, boardPart.1, boardPart.2, (heightLeft, boardPart.3.1), largestElemant.3)

} else if orientation == .SideHorizontally {
let heightLeft = boardPart.3.1 - largestElemant.1

usedElemantPartsOnBoard.append((boardPart.1, largestElemant.0))
unUsedBoardsParts[boardPartIndex ?? 0] = (boardPart.0, boardPart.1, boardPart.2, (heightLeft, boardPart.3.1), largestElemant.3)
}
}

func useNewBoard(largestElemant: (String, Decimal, Decimal, UIColor)) {
usedBoard.append(largestElemant.3)

let heightLeft = baseBoard.0 - largestElemant.1
let widthLeft = baseBoard.1 - largestElemant.2

usedElemantPartsOnBoard.append((usedBoard.endIndex, largestElemant.0))

unUsedBoardsPartsIndex += 1
unUsedBoardsParts.append((unUsedBoardsPartsIndex, usedBoard.endIndex, (heightLeft, baseBoard.1), (baseBoard.0, widthLeft), largestElemant.3))
}

func checkIfNoElemantLeft() {
if currentElemants.isEmpty {
print("Done: used boards: \(usedBoard.count)")
print("Done: used elemant parts on Board: \(usedElemantPartsOnBoard)")
print("Done: un used boards parts: \(unUsedBoardsParts)")

} else {
calculate()
}
}

Я знаю, что использование ориентации перечисления создаст пробелы после добавления нескольких элементов
но это лучшее, что я могу сделать.
Основная идея кода — вычислить минимальное количество панелей, используемых для определенного количества элементов.
спасибо за помощь.

Подробнее здесь: https://stackoverflow.com/questions/786 ... timization