Pagina 1 van 1

Oppervlakte bereken met vaste breedte maat

Geplaatst: 04 okt 2017, 10:52
door ChrisH
Dag,

Ik moet de optimale lengte berekenen bij een vaste breedte van een oppervlakte. (zo min mogelijk aantal in de lengte).
De oppervlakte moet zo klein mogelijk blijven bij een vaste breedte maat.

Er zijn X aantal rechthoeken of vierkanten die in de oppervlakte komen.
Alle maten van de rechthoeken of vierkanten zijn gekend.

voorbeeld 1:
vaste breedte voor de oppervlakte is 500m.
Er zijn 2 rechthoeken (400x200 en 150x150)
Dit wil zeggen dat er een lengte van 350m nodig is om een oppervlakte te verkrijgen waar beide rechthoeken inpassen.

voorbeeld 2:
vaste breedte voor de oppervlakte is 500m.
er zijn 3 rechthoeken/vierkanten (400x200 en 150x150 en 300x100)
Ook in dit voorbeeld is er 350m lengte nodig om de 3 rechthoeken/vierkanten in de oppervlakte te krijgen.


Hoe kan ik de optimale lengte berekenen?
Gekende variabelen: vaste breedte van de oppervlakte + alle maten van de figuren die in de oppervlakte horen te komen (dit zijn enkel rechthoeken/vierkanten).

Gts,
Chris

Re: Oppervlakte bereken met vaste breedte maat

Geplaatst: 04 okt 2017, 22:17
door arie
Dit is een variant van het Strip Packing Problem.
Hiervoor bestaan in zijn algemeenheid geen eenvoudige oplossingen.

Zie bijvoorbeeld voor:
>> een probleemdefinitie:
https://users.cs.cf.ac.uk/C.L.Mumford/h ... round.html
>> een aantal zoek-algoritmes:
http://cgi.csc.liv.ac.uk/~epa/surveyhtml.html
>> een uitgebreider overzicht:
http://www.scielo.br/pdf/pope/v36n2/167 ... -00197.pdf

Heb je wellicht een specifiek probleem, met een gegeven aantal rechthoeken en hun afmetingen?
Sta je rotaties toe, en zo ja, alleen 90 graden of alle mogelijke draaihoeken?

Re: Oppervlakte bereken met vaste breedte maat

Geplaatst: 05 okt 2017, 10:05
door ChrisH
Dag Arie,

Dit lijkt inderdaad op het Strip packing problem.
We hebben een stuk stof met een vaste breedte.
De lengte van de stof is oneindig en de dikte van de stof is irrelevant.

We proberen de lengte van de stof te berekenen om zo weinig mogelijk afval te hebben.
De rechthoeken/vierkanten mogen gedraaid worden, enkel 90 graden rotaties.

Ik probeer dit in onze software te programmeren zodat iedere berekening de meest efficiente manier is.

Gts,
Chris