Re: Algorithm for 1d/2d fit (cut plan)

Giganews Newsgroups
Subject: Re: Algorithm for 1d/2d fit (cut plan)
Posted by:  Paul Nicholls (paul_nichol…@hotmail.com)
Date: Fri, 27 Jun 2008

"Juan J Velazquez Garcia" <velazqu…@usg.com.br> wrote in message
news:4863f90d$…@newsgroups.borland.com...
> Hello,
>
> Where can I find algorithms to create a 1d/2d cut plan.
> For example give a set of materials and a set of pieces create the
> "best" cut to save material.
>
> Thanks in advance,
> Juan
>
> --

I have a 2d rectangle packing routine that may help you.  It allows you to
define a 2d rectangle of some size (and location), and tries to fit smaller
rectangles into the larger one using 1 of 5 different packing modes.

Just create an instance of the TPartition class, passing in the top left and
bottom right xy coordinates of the main box rectangle and packing mode.
Then you just call the Insert method with the size of each rectangle you
want to try and fit into the larger main box.  This method will return true
and a TRect structure holding the left, right, top and bottom coordinates if
the rectangle fitted into the larger box.

Unit Partitions;
{
Thanks goes to Nitrogen for the original version he wrote for his Font
Studio program http://www.nitrogen.za.org/projectinfo.asp?id=12).

I have replaced the corner constants with an enumerated type for specifying
how to pack the rectangles, added a new option for packing rectangles as
horizontal strips, made the Insert method return true or false and the rect
as a var parameter, altered variable names, and altered the code formatting
(easier to read in my opinion, no offense intended to Nitrogen).
}

Interface

Type
{..............................................................................}
    TPackingMode = (
        ePackingMode_BestFitFromNWCorner,
        ePackingMode_BestFitFromNECorner,
        ePackingMode_BestFitFromSECorner,
        ePackingMode_BestFitFromSWCorner,
        ePackingMode_HorizontalStrips
    );
    TRect = Record
        Left,Right,Top,Bottom: Integer;
    End;
{..............................................................................}

{..............................................................................}
    TPartition = Class
    Private
        FStripsRect                  : TRect;
        FRowHeight                  : Integer;
        FX,FY,FX2,FY2,FWidth,FHeight : Integer;
        FPackingMode                : TPackingMode;
        FUsed                        : Boolean;
        FA,FB                        : TPartition;
    Public
        Constructor Create(Const ax,ay,ax2,ay2 : Integer;
                          Const APackingMode  : TPackingMode);
        Destructor  Destroy; Override;

        Function Insert(Const AWidth,AHeight : Integer;
                        Var  ARect          : TRect): Boolean;
    End;
{..............................................................................}

Implementation

{..............................................................................}

{..............................................................................}
//  APackingMode is to specify how to pack the rectangles.
//  When APackingMode is
//  ePackingMode_BestFitFromNWCorner, ePackingMode_BestFitFromNECorner,
//  ePackingMode_BestFitFromSWCorner or ePackingMode_BestFitFromSECorner,
//  the rectangles will be packed using best fit partitioning starting from
that corner.
//
//  When APackingMode is ePackingMode_HorizontalStrips, the rectangles will
be packed
//  in a single row till it can't fit anymore on the row.  When this happens
it
//  will got to the next row moving down by the largest rectangle height in
//  the row just completed.
Constructor TPartition.Create(Const ax,ay,ax2,ay2 : Integer;
                              Const APackingMode  : TPackingMode);
Begin
    Inherited Create;
    FStripsRect.Left := ax;
    FStripsRect.Top  := ay;
    FRowHeight      := 0;
    FX              := ax;
    FY              := ay;
    FX2              := ax2;
    FY2              := aY2;
    FWidth          := FX2 - FX;
    FHeight          := FY2 - FY;
    FPackingMode    := APackingMode;
    FA              := Nil;
    FB              := Nil;
    FUsed            := False;
End;
{..............................................................................}

{..............................................................................}
Destructor TPartition.Destroy;
Begin
    FA.Free;
    FB.Free;
    Inherited Destroy;
End;
{..............................................................................}

{..............................................................................}
//  Inserts a rectangle into the package, returns a Rect if result is true
//  If the rectangle could not fit, the result is False
Function TPartition.Insert(Const AWidth,AHeight : Integer;
                          Var  ARect          : TRect) : Boolean;
Var
    R : TRect;
Begin
    Result := False;
    If FPackingMode = ePackingMode_HorizontalStrips Then
    Begin
        FStripsRect.Right  := FStripsRect.Left + AWidth;
        FStripsRect.Bottom := FStripsRect.Top  + AHeight;
        If (FStripsRect.Right <= FX2) And (FStripsRect.Bottom <= FY2) Then
        Begin
            Result := True;
            ARect  := FStripsRect;
            If AHeight > FRowHeight Then FRowHeight := AHeight;
        End;
        Inc(FStripsRect.Left,AWidth);
        FStripsRect.Right  := FStripsRect.Left + AWidth;
        If FStripsRect.Right > FX2 Then
        // hit right side of partition so reset x and go to next row
        Begin
            FStripsRect.Left  := FX;
            FStripsRect.Right := FStripsRect.Left + AWidth;
            Inc(FStripsRect.Top,FRowHeight);
            FStripsRect.Bottom := FStripsRect.Top  + AHeight;
            FRowHeight        := 0;
        End;
        Exit;
    End;
    If FUsed Then
    Begin
        If Assigned(FA) Then
            Result := FA.Insert(AWidth, AHeight,R);
        If (Not Result) And Assigned(FB) Then
            Result := FB.Insert(AWidth, AHeight,R);
        If Result Then
            ARect := R;
    End
    Else
    Begin
        If (AWidth <= FWidth) and (AHeight <= FHeight) Then
        Begin
            FUsed  := True;
            Result := True;
            Case FPackingMode of
                ePackingMode_BestFitFromNWCorner: Begin
                    ARect.Left  := FX;
                    ARect.Top    := FY;
                    ARect.Right  := FX + AWidth;
                    ARect.Bottom := FY + AHeight;

                    If (FWidth-AWidth) >= (FHeight-AHeight) Then
                    Begin
                        FA := TPartition.Create(FX,(FY+Aheight),(FX+AWidth),
FY2, FPackingMode);
                        FB := TPartition.Create((FX+AWidth),FY, FX2, FY2,
FPackingMode);
                    End
                    Else
                    Begin
                        FA := TPartition.Create((FX+AWidth),FY,FX2,
(FY+AHeight), FPackingMode);
                        FB := TPartition.Create(FX,(FY+AHeight), FX2, FY2,
FPackingMode);
                    End;
                End;
                ePackingMode_BestFitFromNECorner: Begin
                    ARect.Left  := FX2 - AWidth;
                    ARect.Top    := FY;
                    ARect.Right  := FX2;
                    ARect.Bottom := FY  + AHeight;

                    If (FWidth-AWidth) >= (FHeight-AHeight) Then
                    Begin
                        FA := TPartition.Create(FX2-AWidth,(FY+Aheight),FX2,
FY2, FPackingMode);
                        FB := TPartition.Create(FX,FY, FX2-AWidth, FY2,
FPackingMode);
                    End
                    Else
                    Begin
                        FA := TPartition.Create(FX,FY,FX2-AWidth,
(FY+AHeight), FPackingMode);
                        FB := TPartition.Create(FX,(FY+AHeight), FX2, FY2,
FPackingMode);
                    End;
                End;
                ePackingMode_BestFitFromSWCorner: Begin
                    ARect.Left  := FX;
                    ARect.Top    := FY2 - AHeight;
                    ARect.Right  := FX  + AWidth;
                    ARect.Bottom := FY2;

                    If (FWidth-AWidth) >= (FHeight-AHeight) Then
                    Begin
                        FA := TPartition.Create(FX,FY,(FX+AWidth),
FY2-AHeight, FPackingMode);
                        FB := TPartition.Create((FX+AWidth),FY, FX2, FY2,
FPackingMode);
                    End
                    Else
                    Begin
                        FA := TPartition.Create((FX+AWidth),FY2-AHeight,FX2,
FY2, FPackingMode);
                        FB := TPartition.Create(FX,FY, FX2, FY2-AHeight,
FPackingMode);
                    End;
                End;
                ePackingMode_BestFitFromSECorner: Begin
                    ARect.Left  := FX2 - AWidth;
                    ARect.Top    := FY2 - AHeight;
                    ARect.Right  := FX2;
                    ARect.Bottom := FY2;

                    If (FWidth-AWidth) >= (FHeight-AHeight) Then
                    Begin
                        FA := TPartition.Create(FX2-AWidth,FY,FX2,
FY2-AHeight, FPackingMode);
                        FB := TPartition.Create(FX,FY, FX2-AWidth, FY2,
FPackingMode);
                    End
                    Else
                    Begin
                        FA := TPartition.Create(FX,FY2-AHeight,FX2-AWidth,
FY2, FPackingMode);
                        FB := TPartition.Create(FX,FY, FX2, FY2-AHeight,
FPackingMode);
                    End;
                End;
            End;
        End;
    End;
End;
{..............................................................................}

{..............................................................................}
End.

cheers,
Paul

Replies

None

In response to

Algorithm for 1d/2d fit (cut plan) posted by Juan J Velazquez Garcia on 26 Jun 2008