blobs.cpp

C++&datastructure书籍源码,以前外教提供现在与大家共享

#include <iostream>
#include <iomanip>
using namespace std;
#include "tmatrix.h"
#include "randgen.h"
#include "prompt.h"
#include "charbitmap.h"

// find blobs in a two-dimensional grid/bitmap

class Blobs
{
  public:
    
    Blobs();
    int FindBlobs(const CharBitMap& cbm, int minSize);
    void Display(ostream& out) const;
    
  private:
    
    tmatrix<int> myGrid;
    int          myBlobCount;
    
    int BlobFill(int row, int col,int lookFor, int fillWith);
    void Initialize(const CharBitMap& cbm);
    
    static int PIXEL_OFF, PIXEL_ON;
};

int Blobs::PIXEL_OFF = 0;
int Blobs::PIXEL_ON = -1;

Blobs::Blobs()
  : myBlobCount(0)
{
  // grid is empty
}

void Blobs::Display(ostream& out) const
// post: display the blobs    
{
    int j,k;
    int rows = myGrid.numrows();
    int cols = myGrid.numcols();
    for(j=0; j < rows; j++)
    {   for(k=0; k < cols; k++)
        {   char ch = '.';
            if (myGrid[j][k] > PIXEL_OFF)
            {   ch = char ('0' + myGrid[j][k]);
            }
            out << ch;;
        }
        out << endl;
    }
}

int Blobs::FindBlobs(const CharBitMap& cbm, int minSize)
// post: return # blobs whose size > minSize    
{
    int j,k;
    myGrid.resize(cbm.Rows(), cbm.Cols());  
    Initialize(cbm); 
    int rows = myGrid.numrows();
    int cols = myGrid.numcols();
    for(j=0; j < rows; j++)
     {   for(k=0; k < cols; k++)
         {   if (myGrid[j][k] == PIXEL_ON)
             {   if (BlobFill(j,k,PIXEL_ON,myBlobCount+1) > minSize)
                 {   myBlobCount++;
                 }
                 else
                 {   BlobFill(j,k,myBlobCount+1,PIXEL_OFF); // erase it
                 }
             }
         }
     }
     return myBlobCount;
}

void Blobs::Initialize(const CharBitMap& cbm)
// post: myGrid initialized from cbm    
{
    int j,k;
    int rows = myGrid.numrows();
    int cols = myGrid.numcols();
    for(j=0; j < rows; j++)
    {   for(k=0; k < cols; k++)
        {   if (cbm.GetPixel(j,k) == CharBitMap::black)
            {   myGrid[j][k] = PIXEL_ON;
            }
            else
            {   myGrid[j][k] = PIXEL_OFF;
            }
         }
     }
     myBlobCount = 0;   // no blobs yet
}

int Blobs::BlobFill(int row, int col, int lookFor, int fillWith)
// spec: look for blob with pixel-value 'lookFor', color in this
//       blob using 'fillWith' value and return size of blob
// post: returns size of blob at (row,col) and ``colors''
//       blob so that it won't be counted again
{
    static int rowoffset[] = { -1,+1,0,0 }; // north,south,east,west
    static int coloffset[] = { 0,0,+1,-1 };
    const int  NBR_COUNT = 4;

    if (0 <= row && row < myGrid.numrows() &&
        0 <= col && col < myGrid.numcols())
    {
        if (myGrid[row][col] != lookFor)  // not part of this blob
        {   return 0;
        }
	
        // we found a blob element, color it and its neighbors
        myGrid[row][col] = fillWith;
        int k,r,c;
        int size = 1;  // count this pixel, add connected counts
        for(k=0; k < NBR_COUNT; k++)
        {   r = row + rowoffset[k];
            c = col + coloffset[k];
            size += BlobFill(r,c,lookFor,fillWith);
        }
        return size;
    }
    return 0;   // not on grid, not part of blob
}

int main()
{
    int rows, cols;
    cout << "enter row col size ";
    cin >> rows >> cols;
    CharBitMap bmap(rows,cols);
    int k;
    RandGen gen;
    Blobs blobber;
    int pixelCount = PromptRange("# pixels on: ",1,rows*cols);
    for(k=0; k < pixelCount; k++)
    {    bmap.SetPixel(gen.RandInt(0,rows-1),gen.RandInt(0,cols-1),
                       CharBitMap::black);
    }
    bmap.Display(cout);
    int bsize;
    int blobCount;
    do
    {   bsize = PromptRange("blob size (0 to exit) ",0,50);
        if (bsize != 0)
        {   blobCount = blobber.FindBlobs(bmap,bsize);  
            blobber.Display(cout);
            cout << endl << "# blobs = " << blobCount << endl;
        }
    } while (bsize > 0);
    return 0;
}