Algorithm Alley
by Lee Kamentsky


Listing One
void CMonochromeBitmap::BuildBlobList()
{
  CLineVectorIterator clviNew,clviEnd;
  AllocateLineBlock(clviNew,clviEnd);
  m_pBlob.reserve(eBlobsPerBlock);

  // Create two vectors of pointers to lines to hold the new line list
  // and the old line list. We initialize them to hold Width()/2 members.
  // This is the maximum possible number of lines.
  CLinePointerVector clpvRaster[2];
  clpvRaster[0].reserve(Width()/2);
  clpvRaster[1].reserve(Width()/2);
  int nOldLineIndex = 0;
  int nNewLineIndex = 1;
  // At the start, the old line list has no members.
  CLinePointerVectorIterator clpviOldEnd = clpvRaster[nOldLineIndex].begin();
  for (int nY = 0; nY < Height(); nY++) {
    CLinePointerVector &clpvOld = clpvRaster[nOldLineIndex];
    CLinePointerVector &clpvNew = clpvRaster[nNewLineIndex];
    nOldLineIndex = nOldLineIndex ^ 1;
    nNewLineIndex = nNewLineIndex ^ 1;
    CLinePointerVectorIterator clpviOld = clpvOld.begin();
    CLine *pLineOld;
    if (clpviOld == clpviOldEnd)
      pLineOld = NULL;
    else
      pLineOld = *clpviOld++;

    CLinePointerVectorIterator clpviNew = clpvNew.begin();
    // Get the raster to process and set up for the first byte
    const BYTE *pRaster = GetRaster(nY);
    BYTE bBit = 0x80;
    BYTE bByte = *pRaster++;
    //  Set up the X extents.
    int nX = 0;
    const int nXEnd = Width();

    while(nX < nXEnd) {
      CBlob *pBlobOld;
      // Search for the start of a line.
      while((bByte & bBit) == 0) {
        if (++nX == nXEnd) goto linedone;
        bBit = bBit >> 1;
        if (bBit == 0) {
          bBit = 0x80;
          bByte = *pRaster++;
        }
      }
      // Start a line.
      if (clviNew == clviEnd) {
        // need more memory for lines.
        AllocateLineBlock(clviNew,clviEnd);
      }
      CLine &lineNew = *clviNew++;
      lineNew.m_nXStart = nX;
      lineNew.m_pNextLineSameBlob = 0;
      lineNew.m_nY = nY;

      // Put it on the new list.
      *clpviNew++ = &lineNew;
      // Find the extent of the line.
      do {
        if (nX == nXEnd) break;
        bBit = bBit >> 1;
        if (bBit == 0) {
          bBit = 0x80;
          bByte = *pRaster++;
        }
        nX++;
      } while (bBit & bByte);
      lineNew.m_nXEnd = nX - 1;
      // Now finish all old lines wholly before our new line
      if (pLineOld) {
        while (pLineOld->m_nXEnd < lineNew.m_nXStart) {
          pBlobOld = pLineOld->m_pBlob;
          if (--(pBlobOld->m_nOpenLines) == 0) {
            AddBlob(pBlobOld);
          }
          if (clpviOld == clpviOldEnd) {
            pLineOld = NULL;
            break;
          } else {
            pLineOld = *clpviOld++;
          }
        }
      }
      // Do the first line that overlaps our new line
      if (pLineOld && pLineOld->m_nXStart <= lineNew.m_nXEnd) {
        pBlobOld = pLineOld->m_pBlob;
        lineNew.m_pBlob = pBlobOld;
        *(pBlobOld->m_ppLastLine) = &lineNew;
        pBlobOld->m_ppLastLine = &(lineNew.m_pNextLineSameBlob);
        // See if the new line ends the old line or vice-versa.
        if (pLineOld->m_nXEnd > lineNew.m_nXEnd) {
          // the old line extends past the new line.
          // the new line gives the old line's blob another open line.
          pBlobOld->m_nOpenLines++;
          continue;
        } else {
          // we close the old line and extend the blob at the
          // same time. We continue to close old lines.
          if (clpviOld == clpviOldEnd) {
            pLineOld = NULL;
          } else {
            pLineOld = *clpviOld++;
            while(pLineOld->m_nXEnd <= lineNew.m_nXEnd) {
              // End this line too. We have two cases:
              CBlob *pBlobOther;
              if ((pBlobOther = pLineOld->m_pBlob) == pBlobOld) {
                // the old line is part of the new line's blob.
                // This is just a loop.
                pBlobOld->m_nLoops++;
                pBlobOld->m_nOpenLines--;
              } else {
                // This is the merge case
                pBlobOld->Merge(pBlobOther);
                delete pBlobOther;
                pBlobOld->m_nOpenLines--;
              }
              if (clpviOld == clpviOldEnd) {
                pLineOld = NULL;
                break;
              } else {
                pLineOld = *clpviOld++;
              }
            }
            if (pLineOld && pLineOld->m_nXStart <= lineNew.m_nXEnd) {
              // This last old line overlaps and ends the new line.
              CBlob *pBlobOther = pLineOld->m_pBlob;
              if (pBlobOther == pBlobOld) {
                pBlobOld->m_nLoops++;
              } else {
                pBlobOld->Merge(pBlobOther);
                delete pBlobOther;
              }
            }
          }
        }
      } else {
        // This is the case where no line overlaps the new line.
        // Start a blob with this line.
        CBlob *pBlobNew = lineNew.m_pBlob = new CBlob;
        pBlobNew->m_nOpenLines = 1;
        pBlobNew->m_pFirstLine = &lineNew;
        pBlobNew->m_ppLastLine = &(lineNew.m_pNextLineSameBlob);
        pBlobNew->m_nLoops = 0;
      }
    }
linedone:
    if (pLineOld) {
      while (TRUE) {
        // Finish all old lines.
        CBlob *pBlobOld = pLineOld->m_pBlob;
        if (--(pBlobOld->m_nOpenLines) == 0) {
          AddBlob(pBlobOld);
        }
        if (clpviOld == clpviOldEnd) break;
        pLineOld = *clpviOld++;
      }
    }
    // Finally, record the end of the new list as the
    // end of the old list to be.
    clpviOldEnd = clpviNew;
  }
  // At the end, we've got one last raster of lines to finish.
  CLinePointerVector &clpvLast = clpvRaster[nOldLineIndex];
  for (CLinePointerVectorIterator clpvi = clpvLast.begin();
  clpvi != clpviOldEnd;) {
    // Finish all old lines.
    CBlob *pBlobOld = (*clpvi++)->m_pBlob;
    if (--(pBlobOld->m_nOpenLines) == 0) {
      AddBlob(pBlobOld);
    }
  }
  // and finally, segmentation is complete
}


1


