Aufteilen eines Rechtecks in kleinere Rechtecke

[kills]

Hi zusammen,

ich stehe vor folgendem Problem:

Ein Rechteck, z.b. 320x200 soll aufgeteilt werden in 100x100 große Stücke. Die Reststücke sollen ebenfalls miterrechnet werden..

Ich habe dazu schon eine Lösung, würde diese aber gerne optimieren...

Hier meine Lösung in C:

ArgPtr_ptr parquet(int blockx, int blocky)

{

  int i, j, overflowx, overflowy;

  ArgPtr_ptr first = NULL;

  ArgPtr_ptr list = NULL;


  overflowx = (MaxX + 1) % blockx;

  overflowy = (MaxY + 1) % blocky;

  ArgPtr_ptr argPtr = NULL;


  //  printf ("max%d:%d\n", MaxX, MaxY);

  //  printf ("over%d:%d\n", overflowx, overflowy);


  for (i = 0; i <= (MaxX + 1 - blockx); i+=blockx)

  {

    for (j = 0; j <= (MaxY + 1 - blocky); j+=blocky)

    {

      //  printf ("%d:%d\n", i, j);

      argPtr = createArg (i, j, blockx, blocky);

      if (list == NULL)

      {

	list = argPtr;

	first = argPtr;

      }

      else

      {

	list->next = argPtr;

	list = argPtr;

      }

      if (overflowx != 0)		/* ggf reststueck in x richtung */

      {

	argPtr = createArg (MaxX + 1 - overflowx, j, overflowx, blocky);

	if (list == NULL)

        {

	  list = argPtr;

	  first = argPtr;

	}

	else

	{

	  list->next = argPtr;

	  list = argPtr;

	}

      }

    }    

    if (overflowy != 0) 		/* ggf reststueck in y richtung */

    {

      argPtr = createArg (i, MaxY + 1 - overflowy, blockx, overflowy);

      if (list == NULL)

      {

	list = argPtr;

	first = argPtr;

      }

      else

      {

        list->next = argPtr;

        list = argPtr;

      }  

    }

    /* letztes reststueck */

    if (overflowy != 0 && overflowx != 0)

    {      

      argPtr = createArg (MaxX + 1 - overflowx,

			  MaxY + 1 - overflowy,

			  overflowx,

			  overflowy);

      if (list == NULL)

      {

	list = argPtr;

	first = argPtr;

      }

      else

      {

        list->next = argPtr;

        list = argPtr;

      }  

    }

    overflowx = 0;			/* ist nur einmal noetig!	*/

  }


  return first;

}



ArgPtr_ptr createArg (int x, int y, int width, int height)

{

  ThrArg_ptr thrArg = (ThrArg_ptr) malloc (sizeof (struct ThrArg));

  ArgPtr_ptr argPtr = (ArgPtr_ptr) malloc (sizeof (struct ArgPtr));

  thrArg->x = x;

  thrArg->y = y;

  thrArg->width = width;

  thrArg->height = height;

  argPtr->arg = thrArg;

  argPtr->next = NULL;

  return argPtr;  

}

MaxX ist dabei die Breite des Gesamtfensters

MaxY ist dabei die Höhe des Gesamtfensters

blockx ist die Breite des Ausschnitts

blocky ist die Höhe des Ausschnitts

Das ganze geht doch bestimmt eleganter? (Aber auch die Performanz sollte dabei wichtig sein!)

Viele Grüße,

Markus

Bearbeitet 7. Mai 2008 von kills

[Klotzkopp]

Alle Stücke in derselben Reihe haben denselben Y-Wert.

Alle Stücke in derselben Spalte haben denselben X-Wert.

Alle bis auf die Reststücke haben dieselben width- und height-Werte.

Das könntest du ausnutzen. Ich würde hier auch eher ein dynamisches Array als eine verkettete Liste benutzen. Immerhin ist doch vorher schon klar, wieviele Stücke es werden. Damit reduzierst du die Anzahl der Allokationen.

In C könnte das so aussehen:

ArgPtr_ptr parquet(int blockx, int blocky)

{

    int i, j;

    int rows = MaxY / blocky + 1;

    int cols = MaxX / blockx + 1;

    int pieces = rows * cols;

    int overflowx = (MaxX + 1) % blockx;

    int overflowy = (MaxY + 1) % blocky;

    int lastrowstart = cols * (rows - 1);

    ArgPtr_ptr array = calloc(pieces, sizeof(ArgPtr));


    for( i=0; i<pieces; ++i )

    {

        array[i].arg = malloc(sizeof(struct ThrArg));

        array[i].height = blocky;

        array[i].width = blockx;

    }

    for( i=0; i<rows; ++i )

    {

        int y = i * blocky;

        for( j = 0; j<cols; ++j )

        {

            array[i*cols+j].y = y;

            array[i*cols+j].x = j * blockx;

        }

    }

    if(overflowx > 0)

    {

        for( i=0; i<rows; ++i )

        {

            array[i*cols+rows].width = overflowx;

        }

    }


    if(overflowy > 0)

    {

        for( j=lastrowstart; j<pieces; ++j )

        {

            array[j].height = overflowy;

        }

    }

    return array;

}[/code]