I25 Answer — Non-overlapping Circles

#include <stdlib.h>
#include <stdio.h>

typedef struct
{
  int nrows;
  int ncols;
  unsigned char *pixels;
} image;


unsigned char *newImage( image *img, int nrows, int ncols )
{
  img->nrows = nrows;
  img->ncols = ncols;
  img->pixels = (unsigned char *)malloc( nrows * ncols );

  return img->pixels;
}

void freeImage( image *img )
{
  img->nrows = 0;
  img->ncols = 0;
  free( img->pixels );
}

void setPixel( image img, int row, int col, unsigned char val )
{
  img.pixels[ img.ncols*row + col ] = val;
}

unsigned char getPixel( image img, int row, int col )
{
  return img.pixels[ img.ncols*row + col ] ;
}

void writeImage( image img, char *filename )
{
  FILE *file;

  /* open the image file for writing */
  if ( (file = fopen( filename, "wb") ) == NULL )
  {
    printf("file %s could not be created\n", filename );
    exit( EXIT_FAILURE );
  }

  /* write out the PGM Header information */
  fprintf( file, "P5\n");
  fprintf( file, "# Created by writeImage\n");
  fprintf( file,  "%d %d %d\n", img.ncols, img.nrows, 255 );

  /* write the pixel data */
  fwrite(img.pixels, 1, img.nrows*img.ncols, file );

  /* close the file */
  fclose( file );
}

/* Make all pixels of an image the same value */
void clearImage( image img, const unsigned char val)
{
  int r, c;

  for ( r = 0; r<img.nrows; r++ )
    for ( c = 0; c<img.ncols; c++ )
      setPixel( img, r, c, val );
}

/* Draw a circle in the image */
void drawCircle( image img, int row, int col,
                 int radius, unsigned char value )
{
  int r, c;
  int boxLeft, boxRight, boxTop, boxBottom;

  /* find the bounding box for the circle */
  boxLeft = col-radius;
  if ( boxLeft < 0 ) boxLeft = 0;
  boxTop = row-radius;
  if ( boxTop < 0  ) boxTop  = 0;

  boxRight = col+radius;
  if ( boxRight >= img.ncols  ) boxRight  = img.ncols-1 ;
  boxBottom = row+radius;
  if ( boxBottom >= img.nrows ) boxBottom = img.nrows-1 ;

  /* scan thru the pixels in the bounding box, setting */
  /* those inside the circle to the forground color    */
  for ( r = boxTop; r<boxBottom; r++ )
    for ( c = boxLeft; c<boxRight; c++ )
      if ( (r-row)*(r-row)+(c-col)*(c-col) <= radius*radius )
        setPixel( img, r, c, value );
}

int main ( int argc, char* argv[] )
{
  image img ;
  
  /* image size, background and foreground gray levels */
  int nrows, ncols, bgvalue, fgvalue;
  
  /* circle radius, how many to draw, how many there are */
  int radius, howmany, circCount;
  
  /* number of attempts made, and maximum attempts allowed */
  int tries, maxtries;

  /* where circles have been drawn, up to MAXCIRC circles */
  const int MAXCIRC = 100;
  int crow[MAXCIRC];
  int ccol[MAXCIRC];

  /* proposed row and column for a circle */
  int r, c;
  
  /* distance squared of (r,c) from (oldr,oldc) of an */
  /* existing circle, and if this results in an overlap */
  int  circ, distSq, oldr, oldc, overlap ;

  /* initialize circle locations arrays */
  circCount = 0;
  for ( circ=0; circ<MAXCIRC; circ++ )
    crow[circ] = ccol[circ] = 0;

  /* remind user of parameters */
  if ( argc != 8)
  {
    printf("sepCircles fileName nrows ncols bkground");
    printf(" fground radius howmany\n");
    system( "pause" );
    return EXIT_SUCCESS;
  }

  /* collect parameters from command line */
  nrows   = atoi( argv[2] );
  ncols   = atoi( argv[3] );
  bgvalue = atoi( argv[4] );
  fgvalue = atoi( argv[5] );
  radius  = atoi( argv[6] );
  howmany = atoi( argv[7] );
  
  /* user might specify more circles than can be drawn w/o */
  /* overlap, so set a limit on the number of attempts to  */
  /* draw "howmany" circles */
  maxtries= 3*howmany;

  newImage( &img, nrows, ncols );

  clearImage( img, bgvalue );
  srand( time(NULL) );

  /* keep going until all circles have been drawn or too many */
  /* attempts to find a new location have occured */
  for ( tries=0, circCount=0; circCount<howmany && tries<maxtries;  tries++ )
  {
    overlap = 0;
    r = rand()%nrows;  /* pick a random spot for the new circle */
    c = rand()%ncols;
    
    /* look thru the old circles for one that would overlap */
    for ( circ=0; circ<circCount && !overlap; circ++ )
    {
      /* calculate distance from proposed (r,c) and an old */
      /* center (oldr, oldc) */
      oldr = crow[circ];
      oldc = ccol[circ];
      distSq = (r-oldr)*(r-oldr)+(c-oldc)*(c-oldc);
      
      /* if distance**2 is less than diameter**2, then overlap */
      if ( distSq <= 4*radius*radius ) overlap = 1;
    }
    
    /* if the proposed circle at (r,c) does not overlap another */
    if ( !overlap )
    {
      drawCircle( img, r, c, radius, fgvalue );
      
      /* remember the location of this new circle */
      crow[circCount] = r;
      ccol[circCount] = c;
      circCount++ ;
    }
  }

  /* write the image to disk and free memory */
  writePGMimage( img, argv[1]);
  freeImage( &img );
  system( "pause" );
}

Comments: