Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#include "tcenterlinevectP.h"
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//==========================================================================
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//************************
Toshihiro Shimizu 890ddd
//*    Polygonization    *
Toshihiro Shimizu 890ddd
//************************
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//===============================
Toshihiro Shimizu 890ddd
//    Raw Borders Extraction
Toshihiro Shimizu 890ddd
//===============================
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
// Raw contour class definition
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
class RawBorderPoint {
Shinya Kitaoka 120a6e
  TPoint m_position;
Shinya Kitaoka 120a6e
  int m_ambiguousTurn;  // used to remember cases of multiple turning directions
Shinya Kitaoka 120a6e
  // in a RawBorder extraction.
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
public:
Shinya Kitaoka 120a6e
  RawBorderPoint() : m_ambiguousTurn(0) {}
Shinya Kitaoka 120a6e
  RawBorderPoint(int i, int j) : m_position(i, j), m_ambiguousTurn(0) {}
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  inline TPoint pos() const { return m_position; }
Shinya Kitaoka 120a6e
  inline int x() const { return m_position.x; }
Shinya Kitaoka 120a6e
  inline int y() const { return m_position.y; }
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  enum { left = 1, right = 2 };  // Direction taken at ambiguous turning point
Shinya Kitaoka 120a6e
  inline int getAmbiguous() const { return m_ambiguousTurn; }
Shinya Kitaoka 120a6e
  inline void setAmbiguous(int direction) { m_ambiguousTurn = direction; }
Toshihiro Shimizu 890ddd
};
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka d1f6c4
class RawBorder final : public std::vector<rawborderpoint> {</rawborderpoint>
Shinya Kitaoka 120a6e
  int m_xExternal;  // x coordinate of a specific vertex in the outer
Shinya Kitaoka 120a6e
  // RawBorder which contains this inner one.
Shinya Kitaoka 120a6e
  TPointD *m_coordinateSums;
Shinya Kitaoka 120a6e
  TPointD *m_coordinateSquareSums;
Shinya Kitaoka 120a6e
  double *m_coordinateMixedSums;
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
public:
Shinya Kitaoka 120a6e
  RawBorder() {}
Shinya Kitaoka 120a6e
  ~RawBorder() {}
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  void setXExternalPixel(int a) { m_xExternal = a; }
Shinya Kitaoka 120a6e
  int xExternalPixel() { return m_xExternal; }
Shinya Kitaoka 120a6e
  TPointD *&sums() { return m_coordinateSums; }
Shinya Kitaoka 120a6e
  TPointD *&sums2() { return m_coordinateSquareSums; }
Shinya Kitaoka 120a6e
  double *&sumsMix() { return m_coordinateMixedSums; }
Toshihiro Shimizu 890ddd
};
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
// Of course we don't want RawBorders to be entirely copied whenever STL
Shinya Kitaoka 120a6e
// requires to resize a BorderFamily...
Toshihiro Shimizu 890ddd
typedef std::vector<rawborder *=""> BorderFamily;</rawborder>
Toshihiro Shimizu 890ddd
typedef std::vector<borderfamily> BorderList;</borderfamily>
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//==========================================================================
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//============================
Toshihiro Shimizu 890ddd
//    Polygonizer Locals
Toshihiro Shimizu 890ddd
//============================
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
namespace {
Shinya Kitaoka 120a6e
// Const names
Shinya Kitaoka 120a6e
enum { white = 0, black = 1 };
Shinya Kitaoka 120a6e
enum { inner = 0, outer = 1, none = 2, invalid = 3 };
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//=======================================================================================
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//-------------------------------
Toshihiro Shimizu 890ddd
//    Raster Data Functions
Toshihiro Shimizu 890ddd
//-------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
// NOTA: Il tono di un TPixelCM32 rappresenta la transizione tra colore ink e
Shinya Kitaoka 120a6e
// colore paint.
Shinya Kitaoka 120a6e
//      di solito, se il tono e' basso abbiamo un colore ink - che puo' anche
Shinya Kitaoka 120a6e
//      essere bianco,
Toshihiro Shimizu 890ddd
//      in teoria...
Shinya Kitaoka 120a6e
//      Sarebbe opportuno che il vettorizzatore riconoscesse - per colormap - il
Shinya Kitaoka 120a6e
//      colore
Toshihiro Shimizu 890ddd
//      delle strokes.
Shinya Kitaoka 120a6e
//      Approcci: a)  la Signaturemap diventa *piu'* di una bitmap e si seguono
Shinya Kitaoka 120a6e
//      le outline
Toshihiro Shimizu 890ddd
//                    dei singoli colori.
Shinya Kitaoka 120a6e
//                 => Sconnessioni tra i colori adiacenti. Bisogna introdurre la
Shinya Kitaoka 120a6e
//                 distanza tra
Shinya Kitaoka 120a6e
//                    colori per seguire l'outline (ossia, i pixel tenuti a dx
Shinya Kitaoka 120a6e
//                    della outline
Toshihiro Shimizu 890ddd
//                    devono essere simili).
Toshihiro Shimizu 890ddd
//
Shinya Kitaoka 120a6e
//                b)  Una volta vettorizzato tutto, si sceglie il colore della
Shinya Kitaoka 120a6e
//                stroke.
Shinya Kitaoka 120a6e
//                    E' possibile controllare il colore sui vertici delle
Shinya Kitaoka 120a6e
//                    sequenze semplificate
Toshihiro Shimizu 890ddd
//                    e fare una media.
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
// NOTE: Transparency makes colors fade to white. Full transparent black pixels
Shinya Kitaoka 120a6e
// are considered white.
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
template <typename t=""></typename>
Shinya Kitaoka 120a6e
class PixelEvaluator {
Shinya Kitaoka 120a6e
  TRasterPT<t> m_ras;</t>
Shinya Kitaoka 120a6e
  int m_threshold;
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
public:
Shinya Kitaoka 120a6e
  PixelEvaluator(const TRasterPT<t> &ras, int threshold)</t>
Shinya Kitaoka 120a6e
      : m_ras(ras), m_threshold(threshold) {}
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  inline unsigned char getBlackOrWhite(int x, int y);
Toshihiro Shimizu 890ddd
};
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
template <>
Shinya Kitaoka 120a6e
inline unsigned char PixelEvaluator<tpixel32>::getBlackOrWhite(int x, int y) {</tpixel32>
Shinya Kitaoka 120a6e
  // return ras->pixels(y)[x].r + 2 * ras->pixels(y)[x].g + ras->pixels(y)[x].b
Shinya Kitaoka 120a6e
  // <
Shinya Kitaoka 120a6e
  //   threshold * (ras->pixels(y)[x].m / 255.0);
Shinya Kitaoka 120a6e
  // NOTE: Green is considered twice brighter than red or blue channel.
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Using Value of HSV color model
Shinya Kitaoka 120a6e
  return std::max(m_ras->pixels(y)[x].r,
Shinya Kitaoka 120a6e
                  std::max(m_ras->pixels(y)[x].g, m_ras->pixels(y)[x].b)) <
Shinya Kitaoka 120a6e
         m_threshold * (m_ras->pixels(y)[x].m / 255.0);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Using Lightness of HSV color model
Shinya Kitaoka 120a6e
  // return (max(ras->pixels(y)[x].r, max(ras->pixels(y)[x].g,
Shinya Kitaoka 120a6e
  // ras->pixels(y)[x].b)) +
Shinya Kitaoka 120a6e
  //       min(ras->pixels(y)[x].r, min(ras->pixels(y)[x].g,
Shinya Kitaoka 120a6e
  //       ras->pixels(y)[x].b))) / 2.0 <
Shinya Kitaoka 120a6e
  //  threshold * (ras->pixels(y)[x].m / 255.0);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Using (relative) Luminance
Shinya Kitaoka 120a6e
  // return 0.2126 * ras->pixels(y)[x].r + 0.7152 * ras->pixels(y)[x].g + 0.0722
Shinya Kitaoka 120a6e
  // * ras->pixels(y)[x].b <
Shinya Kitaoka 120a6e
  //  threshold * (ras->pixels(y)[x].m / 255.0);
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
template <>
Shinya Kitaoka 120a6e
inline unsigned char PixelEvaluator<tpixelgr8>::getBlackOrWhite(int x, int y) {</tpixelgr8>
Shinya Kitaoka 120a6e
  return m_ras->pixels(y)[x].value < m_threshold;
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
template <>
Shinya Kitaoka 120a6e
inline unsigned char PixelEvaluator<tpixelcm32>::getBlackOrWhite(int x, int y) {</tpixelcm32>
Shinya Kitaoka 120a6e
  return m_ras->pixels(y)[x].getTone() < m_threshold;
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
// Signaturemap format:
Shinya Kitaoka 120a6e
//  stores a map of bytes, whose first bit represents the color (black/white) of
Shinya Kitaoka 120a6e
//  corresponding pixel, and
Toshihiro Shimizu 890ddd
//  the rest its 'signature', used as an int to store information.
Shinya Kitaoka 120a6e
// NOTE: given a TRaster32, the corresponding Signaturemap constructed is
Shinya Kitaoka 120a6e
// intended 0(white)-padded
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
class Signaturemap {
Shinya Kitaoka 120a6e
  std::unique_ptr<unsigned char[]=""> m_array;</unsigned>
Shinya Kitaoka 120a6e
  int m_rowSize;
Shinya Kitaoka 120a6e
  int m_colSize;
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
public:
Shinya Kitaoka 120a6e
  Signaturemap(const TRasterP &ras, int threshold);
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  template <typename t=""></typename>
Shinya Kitaoka 120a6e
  void readRasterData(const TRasterPT<t> &ras, int threshold);</t>
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  inline int getRowSize() const { return m_rowSize; }
Shinya Kitaoka 120a6e
  inline int getColSize() const { return m_colSize; }
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  unsigned char *pixelByte(int x, int y) {
Shinya Kitaoka 120a6e
    return &m_array[(y + 1) * m_rowSize + x + 1];
Shinya Kitaoka 120a6e
  }
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  bool getBitmapColor(int x, int y) const {
Shinya Kitaoka 120a6e
    return m_array[(y + 1) * m_rowSize + x + 1] & 1;
Shinya Kitaoka 120a6e
  }
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  inline unsigned char getSignature(int x, int y) const {
Shinya Kitaoka 120a6e
    return m_array[(y + 1) * m_rowSize + x + 1] >> 1;
Shinya Kitaoka 120a6e
  }
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  void setSignature(int x, int y, int val) {
Shinya Kitaoka 120a6e
    unsigned char *pixel = pixelByte(x, y);
Shinya Kitaoka 120a6e
    *pixel &= 1;
Shinya Kitaoka 120a6e
    *pixel |= (val << 1);  // Si puo' fare meglio??
Shinya Kitaoka 120a6e
  }
Toshihiro Shimizu 890ddd
};
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
Signaturemap::Signaturemap(const TRasterP &ras, int threshold) {
Shinya Kitaoka 120a6e
  // Extrapolate raster type
Shinya Kitaoka 120a6e
  TRaster32P rr   = (TRaster32P)ras;
Shinya Kitaoka 120a6e
  TRasterGR8P rgr = (TRasterGR8P)ras;
Shinya Kitaoka 120a6e
  TRasterCM32P rt = (TRasterCM32P)ras;
Shinya Kitaoka 120a6e
  assert(rr || rgr || rt);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Read raster data
Shinya Kitaoka 120a6e
  if (rr) {
Shinya Kitaoka 120a6e
    rr->lock();
Shinya Kitaoka 120a6e
    readRasterData(rr, threshold);
Shinya Kitaoka 120a6e
    rr->unlock();
Shinya Kitaoka 120a6e
  } else if (rgr) {
Shinya Kitaoka 120a6e
    rgr->lock();
Shinya Kitaoka 120a6e
    readRasterData(rgr, threshold);
Shinya Kitaoka 120a6e
    rgr->unlock();
Shinya Kitaoka 120a6e
  } else {
Shinya Kitaoka 120a6e
    rt->lock();
Shinya Kitaoka 120a6e
    readRasterData(rt, threshold);
Shinya Kitaoka 120a6e
    rt->unlock();
Shinya Kitaoka 120a6e
  }
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
template <typename t=""></typename>
Shinya Kitaoka 120a6e
void Signaturemap::readRasterData(const TRasterPT<t> &ras, int threshold) {</t>
Shinya Kitaoka 120a6e
  unsigned char *currByte;
Shinya Kitaoka 120a6e
  int x, y;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  PixelEvaluator<t> evaluator(ras, threshold);</t>
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  m_rowSize = ras->getLx() + 2;
Shinya Kitaoka 120a6e
  m_colSize = ras->getLy() + 2;
Shinya Kitaoka 120a6e
  m_array.reset(new unsigned char[m_rowSize * m_colSize]);
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  memset(m_array.get(), none << 1, m_rowSize);
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  currByte = m_array.get() + m_rowSize;
Shinya Kitaoka 120a6e
  for (y = 0; y < ras->getLy(); ++y) {
Shinya Kitaoka 120a6e
    *currByte = none << 1;
Shinya Kitaoka 120a6e
    currByte++;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
    for (x = 0; x < ras->getLx(); ++x, ++currByte)
Shinya Kitaoka 120a6e
      *currByte = evaluator.getBlackOrWhite(x, y) | (none << 1);
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
    *currByte = none << 1;
Shinya Kitaoka 120a6e
    currByte++;
Shinya Kitaoka 120a6e
  }
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  memset(currByte, none << 1, m_rowSize);
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
// Minority check for amiguous turning directions
Shinya Kitaoka 120a6e
inline bool getMinorityCheck(const Signaturemap &ras, int x, int y) {
Shinya Kitaoka 120a6e
  // Assumes (x,y) is ambiguous case: 2 immediate surrounding pixels are white
Shinya Kitaoka 120a6e
  // and 2 black
Shinya Kitaoka 120a6e
  return (ras.getBitmapColor(x + 1, y) + ras.getBitmapColor(x + 1, y - 1) +
Shinya Kitaoka 120a6e
          ras.getBitmapColor(x - 2, y) + ras.getBitmapColor(x - 2, y - 1) +
Shinya Kitaoka 120a6e
          ras.getBitmapColor(x - 1, y + 1) + ras.getBitmapColor(x - 1, y - 2) +
Shinya Kitaoka 120a6e
          ras.getBitmapColor(x, y + 1) + ras.getBitmapColor(x, y - 2)) > 4;
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
// Sets signature of a given border
Shinya Kitaoka 120a6e
inline void setSignature(Signaturemap &ras, const RawBorder &border, int val) {
Shinya Kitaoka 120a6e
  unsigned int j;
Shinya Kitaoka 120a6e
  int yOld;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Set border's alpha channel
Shinya Kitaoka 120a6e
  yOld = border.back().y();
Shinya Kitaoka 120a6e
  for (j = 0; j < border.size(); ++j) {
Shinya Kitaoka 120a6e
    if (border[j].y() < yOld) {
Shinya Kitaoka 120a6e
      ras.setSignature(border[j].x(), border[j].y(), val);
Shinya Kitaoka 120a6e
    } else if (border[j].y() > yOld) {
Shinya Kitaoka 120a6e
      ras.setSignature(border[j].x(), yOld, val);
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
    yOld = border[j].y();
Shinya Kitaoka 120a6e
  }
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//==========================================================================
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//-------------------------------
Toshihiro Shimizu 890ddd
//    Raw Borders Extraction
Toshihiro Shimizu 890ddd
//-------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
// RawBorderPoints correspond to lower-left pixel corners.
Shinya Kitaoka 120a6e
// EXAMPLE: (0,0) is the lower-left *corner* of the image, whereas (0,0) also
Toshihiro Shimizu 890ddd
// represents coordinates of the lower-left *pixel*.
Shinya Kitaoka 120a6e
// NOTE: 'Ambiguous turning' vertices are those of kind:
Toshihiro Shimizu 890ddd
//
Toshihiro Shimizu 890ddd
//    B|W           W|B
Toshihiro Shimizu 890ddd
//    -x-    -or-   -x-
Toshihiro Shimizu 890ddd
//    W|B           B|W
Toshihiro Shimizu 890ddd
//
Shinya Kitaoka 120a6e
// Keeping B on the right of our path-seeking direction, we may either turn
Shinya Kitaoka 120a6e
// left or right at these points.
Shinya Kitaoka 120a6e
Campbell Barton b3bd84
static RawBorder *extractPath(Signaturemap &ras, int x0, int y0, int pathType,
Campbell Barton b3bd84
                              int xOuterPixel, int despeckling) {
Shinya Kitaoka 120a6e
  RawBorder *path = new RawBorder;
Shinya Kitaoka 120a6e
  int x, y;
Shinya Kitaoka 120a6e
  short dirX, dirY;
Shinya Kitaoka 120a6e
  long int area = 0;
Shinya Kitaoka 120a6e
  bool nextLeftPixel, nextRightPixel;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  if (pathType == outer) {
Shinya Kitaoka 120a6e
    dirX = 0;
Shinya Kitaoka 120a6e
    dirY = 1;
Shinya Kitaoka 120a6e
  } else {
Shinya Kitaoka 120a6e
    dirX = 1;
Shinya Kitaoka 120a6e
    dirY = 0;
Shinya Kitaoka 120a6e
    area += y0;
Shinya Kitaoka 120a6e
    path->setXExternalPixel(xOuterPixel);
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  path->push_back(RawBorderPoint(x0, y0));
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Check here if (x0, y0) is an ambiguous-direction point
Shinya Kitaoka 120a6e
  nextLeftPixel = ras.getBitmapColor(x0 + (dirY - dirX - 1) / 2,
Shinya Kitaoka 120a6e
                                     y0 + (-dirY - dirX - 1) / 2);
Shinya Kitaoka 120a6e
  nextRightPixel = ras.getBitmapColor(x0 + (-dirX - dirY - 1) / 2,
Shinya Kitaoka 120a6e
                                      y0 + (dirX - dirY - 1) / 2);
Shinya Kitaoka 120a6e
  if ((nextRightPixel == black) && (nextLeftPixel == white))
Shinya Kitaoka 120a6e
    path->back().setAmbiguous(dirX ? RawBorderPoint::left
Shinya Kitaoka 120a6e
                                   : RawBorderPoint::right);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Begin path extraction
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  for (x = x0 + dirX, y = y0 + dirY; !(x == x0 && y == y0);
Shinya Kitaoka 120a6e
       x += dirX, y += dirY) {
Shinya Kitaoka 120a6e
    path->push_back(RawBorderPoint(x, y));
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    // Calculate next direction
Shinya Kitaoka 120a6e
    nextLeftPixel = ras.getBitmapColor(x + (dirX - dirY - 1) / 2,
Shinya Kitaoka 120a6e
                                       y + (dirY + dirX - 1) / 2);
Shinya Kitaoka 120a6e
    nextRightPixel = ras.getBitmapColor(x + (dirX + dirY - 1) / 2,
Shinya Kitaoka 120a6e
                                        y + (dirY - dirX - 1) / 2);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    if ((nextRightPixel == black) && (nextLeftPixel == black)) {
Shinya Kitaoka 120a6e
      // Left Turn
Shinya Kitaoka 120a6e
      std::swap(dirY, dirX);
Shinya Kitaoka 120a6e
      dirX = -dirX;
Shinya Kitaoka 120a6e
    } else if ((nextRightPixel == white) && (nextLeftPixel == white)) {
Shinya Kitaoka 120a6e
      // Right Turn
Shinya Kitaoka 120a6e
      std::swap(dirY, dirX);
Shinya Kitaoka 120a6e
      dirY = -dirY;
Shinya Kitaoka 120a6e
    } else if ((nextRightPixel == white) && (nextLeftPixel == black)) {
Shinya Kitaoka 120a6e
      // path->back().setAmbiguous();
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      // Do a surrounding check and connect minority color
Shinya Kitaoka 120a6e
      if (getMinorityCheck(ras, x, y) == black) {
Shinya Kitaoka 120a6e
        std::swap(dirY, dirX);
Shinya Kitaoka 120a6e
        dirY = -dirY;
Shinya Kitaoka 120a6e
        path->back().setAmbiguous(RawBorderPoint::right);
Shinya Kitaoka 120a6e
      }  // right turn
Shinya Kitaoka 120a6e
      else {
Shinya Kitaoka 120a6e
        std::swap(dirY, dirX);
Shinya Kitaoka 120a6e
        dirX = -dirX;
Shinya Kitaoka 120a6e
        path->back().setAmbiguous(RawBorderPoint::left);
Shinya Kitaoka 120a6e
      }  // left turn
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    // Also calculate border area
Shinya Kitaoka 120a6e
    area += y * dirX;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    // And sign treated pixel
Shinya Kitaoka 120a6e
    if (dirY != 0) ras.setSignature(x, y + (dirY - 1) / 2, pathType);
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // If the inner region's overall area is under a given threshold,
Shinya Kitaoka 120a6e
  // then erase it (intended as image noise).
Shinya Kitaoka 120a6e
  if (abs(area) < despeckling) {
Shinya Kitaoka 120a6e
    setSignature(ras, *path, invalid);
Shinya Kitaoka 120a6e
    delete path;
Shinya Kitaoka 120a6e
    path = 0;
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  return path;
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Campbell Barton b3bd84
static BorderList *extractBorders(const TRasterP &ras, int threshold,
Campbell Barton b3bd84
                                  int despeckling) {
Shinya Kitaoka 120a6e
  Signaturemap byteImage(ras, threshold);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  BorderList *borderHierarchy = new BorderList;
Shinya Kitaoka 120a6e
  std::vector<rawborder *=""> outerBorders;</rawborder>
Shinya Kitaoka 120a6e
  std::list<rawborder *=""> innerBorders;</rawborder>
Shinya Kitaoka 120a6e
  RawBorder *foundPath;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  int x, y;
Shinya Kitaoka 120a6e
  bool Color, oldColor;
Shinya Kitaoka 120a6e
  int xOuterPixel = 0;
Shinya Kitaoka 120a6e
  bool enteredRegionType;
Shinya Kitaoka 120a6e
  unsigned char signature;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Traverse image to extract raw borders
Shinya Kitaoka 120a6e
  for (y = 0; y < ras->getLy(); ++y) {
Shinya Kitaoka 120a6e
    oldColor          = white;
Shinya Kitaoka 120a6e
    enteredRegionType = outer;
Shinya Kitaoka 120a6e
    for (x = 0; x < ras->getLx(); ++x) {
Shinya Kitaoka 120a6e
      if (oldColor ^ (Color = byteImage.getBitmapColor(x, y))) {
Shinya Kitaoka 120a6e
        // Region type changes
Shinya Kitaoka 120a6e
        enteredRegionType = !enteredRegionType;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
        if ((signature = byteImage.getSignature(x, y)) == none) {
Shinya Kitaoka 120a6e
          // We've found a border
Shinya Kitaoka 120a6e
          if ((foundPath = extractPath(byteImage, x, y, !enteredRegionType,
Shinya Kitaoka 120a6e
                                       xOuterPixel, despeckling)))
Shinya Kitaoka 120a6e
            if (enteredRegionType == outer)
Shinya Kitaoka 120a6e
              innerBorders.push_back(foundPath);
Shinya Kitaoka 120a6e
            else
Shinya Kitaoka 120a6e
              outerBorders.push_back(foundPath);
Shinya Kitaoka 120a6e
        }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
        // If leaving a white region, remember it - in order to establish
Shinya Kitaoka 120a6e
        // border hierarchy in the future
Shinya Kitaoka 120a6e
        if (enteredRegionType == inner && signature != invalid) xOuterPixel = x;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
        // Invalid pixels got signed by a cut-out path, due to insufficient area
Shinya Kitaoka 120a6e
        if (signature == invalid)
Shinya Kitaoka 120a6e
          byteImage.setSignature(x, y, none);  // Restore them now
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
        oldColor = Color;
Shinya Kitaoka 120a6e
      }
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Now, we have all borders found, but no hierarchy between them.
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  unsigned int i;
Shinya Kitaoka 120a6e
  std::list<rawborder *="">::iterator l;</rawborder>
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Build hierarchy
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  innerBorders.push_front(0);  // Just to keep a fixed list head
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  for (i = 0; i < outerBorders.size(); ++i) {
Shinya Kitaoka 120a6e
    // Initialize a border family
Shinya Kitaoka 120a6e
    borderHierarchy->push_back(BorderFamily());
Shinya Kitaoka 120a6e
    borderHierarchy->back().push_back(outerBorders[i]);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    // Reset outerBorders[i]'s signature
Shinya Kitaoka 120a6e
    setSignature(byteImage, *outerBorders[i], none);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    // Now check inner borders for insideness - check if the outerPixel
Shinya Kitaoka 120a6e
    // remembered in path extraction has been cleared
Shinya Kitaoka 120a6e
    for (l = innerBorders.begin(), ++l; l != innerBorders.end(); ++l) {
Shinya Kitaoka 120a6e
      if (byteImage.getSignature((*l)->xExternalPixel(), (**l)[0].y()) ==
Shinya Kitaoka 120a6e
          none) {
Shinya Kitaoka 120a6e
        borderHierarchy->back().push_back(*l);
Shinya Kitaoka 120a6e
        setSignature(byteImage, **l, none);
Shinya Kitaoka 120a6e
        l = innerBorders.erase(l);
Shinya Kitaoka 120a6e
        --l;
Shinya Kitaoka 120a6e
      }
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  return borderHierarchy;
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//==================================
Toshihiro Shimizu 890ddd
//    Calculate optimal polygons
Toshihiro Shimizu 890ddd
//==================================
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
// The optimal polygon for a given original border is found like:
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
// 1) Find couples (i,k(i)), so that k(i) be the largest k:
Toshihiro Shimizu 890ddd
//        d(j,ik) <= 1;  for *all* i
Toshihiro Shimizu 890ddd
//    It can be shown that such a condition is equivalent to:
Toshihiro Shimizu 890ddd
//      exists line l : d(l,j)<=1/2, for all i<=j<=k(i).
Toshihiro Shimizu 890ddd
// 2) Clean the above couples - find couples (i,l(i)):
Toshihiro Shimizu 890ddd
//        l(i)=min{k(j)},  j=i..n.
Toshihiro Shimizu 890ddd
// 3) Calculate clipped couples (i',l'); where i'=i+1, l'=l(i)-1.
Toshihiro Shimizu 890ddd
// 4) Calculate sums for path penalties.
Toshihiro Shimizu 890ddd
// 5) Apply optimality algorithm.
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
// NOTE: Weak simpleness reads like: a set of polygons is weak-simple if no edge
Shinya Kitaoka 120a6e
//      *crosses* another edge. Superposition and collision of edges with
Shinya Kitaoka 120a6e
//      vertices
Toshihiro Shimizu 890ddd
//      are still admitted.
Toshihiro Shimizu 890ddd
//        =>  It can be shown that due to 1) and special conditions on ambiguous
Toshihiro Shimizu 890ddd
//            turnings applied in both 1) and 3), weak simpleness is insured in
Toshihiro Shimizu 890ddd
//            our polygonization.
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
// Helper functions/classes: circular-indexed vectors
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
// returns 1 whenever the triple (a,b,c) is 'circular' mod n.
Shinya Kitaoka 120a6e
// NOTE: We'll find useful taking (i,i,j) as 1 and (i,j,j) as 0.
Shinya Kitaoka 120a6e
inline bool isCircular(int a, int b, int c) {
Shinya Kitaoka 120a6e
  return a <= c ? a <= b && b < c : c > b || b >= a;
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
// Extracts a 'next corner' array - helps improving overall speed
Shinya Kitaoka 120a6e
inline std::unique_ptr<int[]> findNextCorners(RawBorder &path) {</int[]>
Shinya Kitaoka 120a6e
  std::unique_ptr<int[]> corners(new int[path.size()]);</int[]>
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // NOTE: 0 is a corner, due to the path extraction procedure.
Shinya Kitaoka 120a6e
  int currentCorner = 0;
Shinya Kitaoka 120a6e
  for (int i = path.size() - 1; i >= 0; --i) {
Shinya Kitaoka 120a6e
    if (path[currentCorner].x() != path[i].x() &&
Shinya Kitaoka 120a6e
        path[currentCorner].y() != path[i].y())
Shinya Kitaoka 120a6e
      currentCorner = i + 1;
Shinya Kitaoka 120a6e
    corners[i]      = currentCorner;
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  return corners;
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
// Calculate furthest k satisfying 1) for all fixed i.
Shinya Kitaoka 120a6e
inline std::unique_ptr<int[]> furthestKs(RawBorder &path,</int[]>
Shinya Kitaoka 120a6e
                                         std::unique_ptr<int[]> &nextCorners) {</int[]>
Shinya Kitaoka 120a6e
  int n = path.size();
Shinya Kitaoka 120a6e
  std::unique_ptr<int[]> kVector(new int[n]);</int[]>
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  enum { left, up, right, down };
Shinya Kitaoka 120a6e
  int directionsOccurred[4];
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  nextCorners = findNextCorners(path);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  int i, j, k;
Shinya Kitaoka 120a6e
  TPoint shift;
Shinya Kitaoka 120a6e
  TPoint leftConstraint, rightConstraint, violatedConstraint;
Shinya Kitaoka 120a6e
  TPoint newLeftConstraint, newRightConstraint;
Shinya Kitaoka 120a6e
  TPoint jPoint, jNextPoint, iPoint, direction;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  int directionSignature;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  for (i = 0; i < n; ++i) {
Shinya Kitaoka 120a6e
    // Initialize search
Shinya Kitaoka 120a6e
    leftConstraint = rightConstraint = TPoint();
Shinya Kitaoka 120a6e
    directionsOccurred[0] = directionsOccurred[1] = directionsOccurred[2] =
Shinya Kitaoka 120a6e
        directionsOccurred[3]                     = 0;
Shinya Kitaoka 120a6e
    j                                             = i;
Shinya Kitaoka 120a6e
    jNextPoint = iPoint = path[i].pos();
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    // Search for k(i)
Shinya Kitaoka 120a6e
    while (1) {
Shinya Kitaoka 120a6e
      // NOTE: Here using TPoint::operator= is less effective than setting
Shinya Kitaoka 120a6e
      // its x and y components directly...
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      jPoint     = jNextPoint;
Shinya Kitaoka 120a6e
      jNextPoint = path[nextCorners[j]].pos();
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      // Update directions count
Shinya Kitaoka 120a6e
      directionSignature = jNextPoint.x > jPoint.x
Shinya Kitaoka 120a6e
                               ? right
Shinya Kitaoka 120a6e
                               : jNextPoint.x < jPoint.x
Shinya Kitaoka 120a6e
                                     ? left
Shinya Kitaoka 120a6e
                                     : jNextPoint.y > jPoint.y ? up : down;
Shinya Kitaoka 120a6e
      directionsOccurred[directionSignature] = 1;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      // If all 4 axis directions occurred, quit
Shinya Kitaoka 120a6e
      if (directionsOccurred[left] && directionsOccurred[right] &&
Shinya Kitaoka 120a6e
          directionsOccurred[up] && directionsOccurred[down]) {
Shinya Kitaoka 120a6e
        k = j;
Shinya Kitaoka 120a6e
        goto foundK;
Shinya Kitaoka 120a6e
      }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      // Update displacement from i
Shinya Kitaoka 120a6e
      shift = jNextPoint - iPoint;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      // Test j against constraints
Shinya Kitaoka 120a6e
      // if(cross(shift, leftConstraint)<0 || cross(shift, rightConstraint)>0)
Shinya Kitaoka 120a6e
      if (cross(shift, leftConstraint) < 0) {
Shinya Kitaoka 120a6e
        violatedConstraint = leftConstraint;
Shinya Kitaoka 120a6e
        break;
Shinya Kitaoka 120a6e
      }
Shinya Kitaoka 120a6e
      if (cross(shift, rightConstraint) > 0) {
Shinya Kitaoka 120a6e
        violatedConstraint = rightConstraint;
Shinya Kitaoka 120a6e
        break;
Shinya Kitaoka 120a6e
      }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      // Update constraints
Shinya Kitaoka 120a6e
      if (abs(shift.x) > 1 || abs(shift.y) > 1) {
Shinya Kitaoka 120a6e
        newLeftConstraint.x =
Shinya Kitaoka 120a6e
            shift.x + (shift.y < 0 || (shift.y == 0 && shift.x < 0) ? 1 : -1);
Shinya Kitaoka 120a6e
        newLeftConstraint.y =
Shinya Kitaoka 120a6e
            shift.y + (shift.x > 0 || (shift.x == 0 && shift.y < 0) ? 1 : -1);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
        if (cross(newLeftConstraint, leftConstraint) >= 0)
Shinya Kitaoka 120a6e
          leftConstraint = newLeftConstraint;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
        newRightConstraint.x =
Shinya Kitaoka 120a6e
            shift.x + (shift.y > 0 || (shift.y == 0 && shift.x < 0) ? 1 : -1);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
        newRightConstraint.y =
Shinya Kitaoka 120a6e
            shift.y + (shift.x < 0 || (shift.x == 0 && shift.y < 0) ? 1 : -1);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
        if (cross(newRightConstraint, rightConstraint) <= 0)
Shinya Kitaoka 120a6e
          rightConstraint = newRightConstraint;
Shinya Kitaoka 120a6e
      }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      // Imposing strict constraint for ambiguous turnings, to ensure polygons'
Shinya Kitaoka 120a6e
      // weak simpleness.
Shinya Kitaoka 120a6e
      // Has to be defined *outside* abs checks.
Shinya Kitaoka 120a6e
      if (path[nextCorners[j]].getAmbiguous()) {
Shinya Kitaoka 120a6e
        if (path[nextCorners[j]].getAmbiguous() == RawBorderPoint::left)
Shinya Kitaoka 120a6e
          rightConstraint = shift;
Shinya Kitaoka 120a6e
        else
Shinya Kitaoka 120a6e
          leftConstraint = shift;
Shinya Kitaoka 120a6e
      }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      j = nextCorners[j];
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    // At this point, constraints are violated by the next corner.
Shinya Kitaoka 120a6e
    // Then, search for the last k between j and corners[j] not violating them.
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    direction = convert(normalize(convert(jNextPoint - jPoint)));
Shinya Kitaoka 120a6e
    k         = (j +
Shinya Kitaoka 120a6e
         cross(jPoint - iPoint, violatedConstraint) /
Shinya Kitaoka 120a6e
             cross(violatedConstraint, direction)) %
Shinya Kitaoka 120a6e
        n;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  foundK:
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    kVector[i] = k;
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  return kVector;
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
// Now find the effective intervals inside which we can define possible
Toshihiro Shimizu 890ddd
// arcs approximating the given raw border:
Toshihiro Shimizu 890ddd
//    for every a in [i,res[i]], the arc connecting border[i] and
Toshihiro Shimizu 890ddd
//    border[a] will be a possible one.
Shinya Kitaoka 120a6e
inline std::unique_ptr<int[]> calculateForwardArcs(RawBorder &border,</int[]>
Shinya Kitaoka 120a6e
                                                   bool ambiguitiesCheck) {
Shinya Kitaoka 120a6e
  int const n = (int)border.size();
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  std::unique_ptr<int[]> nextCorners;</int[]>
Shinya Kitaoka 120a6e
  std::unique_ptr<int[]> k = furthestKs(border, nextCorners);</int[]>
Shinya Kitaoka 120a6e
  std::unique_ptr<int[]> K(new int[n]);</int[]>
Shinya Kitaoka 120a6e
  std::unique_ptr<int[]> res(new int[n]);</int[]>
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // find K[i]= min {k[j]}, j=i..n-1.
Shinya Kitaoka 120a6e
  for (int i = 0; i < n; ++i) {
Shinya Kitaoka 120a6e
    int j;
Shinya Kitaoka 120a6e
    for (j = i, K[i] = k[i]; isCircular(i, j, K[i]); j = (j + 1) % n)
Shinya Kitaoka 120a6e
      if (isCircular(j, k[j], K[i])) K[i] = k[j];
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Finally, we perform the following clean-up operations:
Shinya Kitaoka 120a6e
  //  first, extremities of [i,K[i]] are clipped away, to obtain a
Shinya Kitaoka 120a6e
  //    smoother optimal polygon (and deal with cases like the unitary
Shinya Kitaoka 120a6e
  //    square);
Shinya Kitaoka 120a6e
  //  second, arcs of the kind [i,j] with j
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  for (int i = n - 1, j = 0; j < n; i = j, ++j) {
Shinya Kitaoka 120a6e
    res[j] = K[i] < j ? (K[i] == 0 ? n - 1 : n) : K[i] - 1;
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Amibiguities check for vertex and edge superpositions. Prevent problems in
Shinya Kitaoka 120a6e
  // the forecoming
Shinya Kitaoka 120a6e
  // straight-skeleton thinning process.
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  if (ambiguitiesCheck) {
Shinya Kitaoka 120a6e
    for (int i = 1; nextCorners[i] > 0; i = nextCorners[i]) {
Shinya Kitaoka 120a6e
      if (border[i].getAmbiguous() == RawBorderPoint::right) {
Shinya Kitaoka 120a6e
        // Check vertices from i (excluded) to res[res[i]]; if in it there
Shinya Kitaoka 120a6e
        // exists vertex k so that pos(k)==pos(i)...
Shinya Kitaoka 120a6e
        // This prevents the existence of 0 degree angles in the optimal
Shinya Kitaoka 120a6e
        // polygon.
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
        int rrPlus1 = (res[res[i] % n] + 1) % n;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
        for (int j = nextCorners[i];
Shinya Kitaoka 120a6e
             isCircular(i, j, rrPlus1) &&
Shinya Kitaoka 120a6e
             j != i;  // remember that isCircular(a,a,b) == 1 ...
Shinya Kitaoka 120a6e
             j = nextCorners[j]) {
Shinya Kitaoka 120a6e
          if (border[j].getAmbiguous() &&
Shinya Kitaoka 120a6e
              (border[j].pos() == border[i].pos())) {
Shinya Kitaoka 120a6e
            res[res[i] % n] = j - 1;
Shinya Kitaoka 120a6e
            assert((res[i] % n) != j - 1);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
            // Further, ensure res is increasing
Shinya Kitaoka 120a6e
            for (int k = res[i] % n; res[k] >= j - 1 && k >= 0; --k) {
Shinya Kitaoka 120a6e
              res[k] = j - 1;
Shinya Kitaoka 120a6e
              assert(k != j - 1);
Shinya Kitaoka 120a6e
            }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
            break;
Shinya Kitaoka 120a6e
          }
Shinya Kitaoka 120a6e
        }
Shinya Kitaoka 120a6e
      }
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  return res;
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
// Let sum[i] and sum2[i] be respectively the sums of vertex coordinates
Shinya Kitaoka 120a6e
// from 0 to i, and the sums of their squares; sumsMix contain sums of
Shinya Kitaoka 120a6e
// xy terms.
Shinya Kitaoka 120a6e
inline void calculateSums(RawBorder &path) {
Shinya Kitaoka 120a6e
  unsigned int i, n = path.size();
Shinya Kitaoka 120a6e
  TPointD currentRelativePos;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  path.sums()    = new TPointD[n + 1];
Shinya Kitaoka 120a6e
  path.sums2()   = new TPointD[n + 1];
Shinya Kitaoka 120a6e
  path.sumsMix() = new double[n + 1];
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  path.sums()[0].x = path.sums()[0].y = path.sums2()[0].x = path.sums2()[0].y =
Shinya Kitaoka 120a6e
      0;
Shinya Kitaoka 120a6e
  for (i = 1; i < path.size(); ++i) {
Shinya Kitaoka 120a6e
    currentRelativePos = convert(path[i].pos() - path[0].pos());
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    path.sums()[i] = path.sums()[i - 1] + currentRelativePos;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    path.sums2()[i].x =
Shinya Kitaoka 120a6e
        path.sums2()[i - 1].x + currentRelativePos.x * currentRelativePos.x;
Shinya Kitaoka 120a6e
    path.sums2()[i].y =
Shinya Kitaoka 120a6e
        path.sums2()[i - 1].y + currentRelativePos.y * currentRelativePos.y;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    path.sumsMix()[i] =
Shinya Kitaoka 120a6e
        path.sumsMix()[i - 1] + currentRelativePos.x * currentRelativePos.y;
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // path[n] is virtually intended as path[0], but we prefer to introduce
Shinya Kitaoka 120a6e
  // it in the optimality algorithm's count
Shinya Kitaoka 120a6e
  path.sums()[n].x = path.sums()[n].y = path.sums2()[n].x = path.sums2()[n].y =
Shinya Kitaoka 120a6e
      0;
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
// Let a,b the index-extremities of an arc of this path.
Shinya Kitaoka 120a6e
// Then return its penalty.
Shinya Kitaoka 120a6e
inline double penalty(RawBorder &path, int a, int b) {
Shinya Kitaoka 120a6e
  int n = b - a + 1;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  TPointD v =
Shinya Kitaoka 120a6e
      convert(rotate90(path[b == path.size() ? 0 : b].pos() - path[a].pos()));
Shinya Kitaoka 120a6e
  TPointD sum   = path.sums()[b] - path.sums()[a];
Shinya Kitaoka 120a6e
  TPointD sum2  = path.sums2()[b] - path.sums2()[a];
Shinya Kitaoka 120a6e
  double sumMix = path.sumsMix()[b] - path.sumsMix()[a];
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  double F1 = sum2.x - 2 * sum.x * path[a].x() + n * path[a].x() * path[a].x();
Shinya Kitaoka 120a6e
  double F2 = sum2.y - 2 * sum.y * path[a].y() + n * path[a].y() * path[a].y();
Shinya Kitaoka 120a6e
  double F3 = sumMix - sum.x * path[a].y() - sum.y * path[a].x() +
Shinya Kitaoka 120a6e
              n * path[a].x() * path[a].y();
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  return sqrt((v.y * v.y * F1 + v.x * v.x * F2 - 2 * v.x * v.y * F3) / n);
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
// NOTA: Il seguente algoritmo di riduzione assicura la semplicita' (debole) dei
Shinya Kitaoka 120a6e
// poligoni prodotti.
Toshihiro Shimizu 890ddd
//
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
inline void reduceBorder(RawBorder &border, Contour &res,
Shinya Kitaoka 120a6e
                         bool ambiguitiesCheck) {
Shinya Kitaoka 120a6e
  int n = border.size();
Shinya Kitaoka 120a6e
  int minPenaltyNext;
Shinya Kitaoka 120a6e
  std::unique_ptr<int[]> minPenaltyNextArray(new int[n]);</int[]>
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Calculate preliminary infos
Shinya Kitaoka 120a6e
  std::unique_ptr<int[]> longestArcFrom =</int[]>
Shinya Kitaoka 120a6e
      calculateForwardArcs(border, ambiguitiesCheck);
Shinya Kitaoka 120a6e
  calculateSums(border);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  std::unique_ptr<double[]> penaltyToEnd(new double[n + 1]);</double[]>
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // EXPLANATION:
Shinya Kitaoka 120a6e
  // The fastest way to extract the optimal reduced border is based on the
Shinya Kitaoka 120a6e
  // weakly monotonic property of longestArc[].
Shinya Kitaoka 120a6e
  // The minimal number of its vertices 'm' is easily found by
Shinya Kitaoka 120a6e
  // traversing the path with the longest step allowed. Let b[] be that
Shinya Kitaoka 120a6e
  // succession; then, given res[i], it has to be reached by a vertex in
Shinya Kitaoka 120a6e
  // the interval: {a[i-1], .. , b[i-1]}, where longestArc[a[i-1]]=a[i],
Shinya Kitaoka 120a6e
  // longestArc[a[i-1]-1]
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Calculate m
Shinya Kitaoka 120a6e
  int m = 0;
Shinya Kitaoka 120a6e
  for (int i = 0; i < n; i = longestArcFrom[i]) ++m;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Calculate b[]
Shinya Kitaoka 120a6e
  std::unique_ptr<int[]> b(new int[m + 1]);</int[]>
Shinya Kitaoka 120a6e
  b[m] = n;
Shinya Kitaoka 120a6e
  for (int i = 0, j = 0; j < m; i = longestArcFrom[i], ++j) b[j] = i;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // NOTE: a[] need not be completely found - we just remember the
Shinya Kitaoka 120a6e
  // a=a[j+1] currently needed.
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Now, build the optimal polygon
Shinya Kitaoka 120a6e
  for (int j = m - 1, a = n; j >= 0; --j) {
Shinya Kitaoka 120a6e
    int k;
Shinya Kitaoka 120a6e
    for (k = b[j]; k >= 0 && longestArcFrom[k] >= a; --k) {
Shinya Kitaoka 120a6e
      penaltyToEnd[k] = infinity;
Shinya Kitaoka 120a6e
      for (int i = a; i <= longestArcFrom[k]; ++i) {
Shinya Kitaoka 120a6e
        double newPenalty = penaltyToEnd[i] + penalty(border, k, i);
Shinya Kitaoka 120a6e
        if (newPenalty < penaltyToEnd[k]) penaltyToEnd[k] = newPenalty;
Shinya Kitaoka 120a6e
        minPenaltyNext                                    = i;
Shinya Kitaoka 120a6e
      }
Shinya Kitaoka 120a6e
      minPenaltyNextArray[k] = minPenaltyNext;
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
    a = k + 1;
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Finally, read off the optimal polygon
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  res.resize(m);
Shinya Kitaoka 120a6e
  for (int i = 0, j = 0; i < n; i = minPenaltyNextArray[i], ++j) {
Shinya Kitaoka 120a6e
    res[j] = ContourNode(border[i].x(), border[i].y());
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    // Ambiguities are still remembered in the output polygon.
Shinya Kitaoka 120a6e
    if (border[i].getAmbiguous() == RawBorderPoint::left)
Shinya Kitaoka 120a6e
      res[j].setAttribute(ContourNode::AMBIGUOUS_LEFT);
Shinya Kitaoka 120a6e
    if (border[i].getAmbiguous() == RawBorderPoint::right)
Shinya Kitaoka 120a6e
      res[j].setAttribute(ContourNode::AMBIGUOUS_RIGHT);
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  delete[] border.sums();
Shinya Kitaoka 120a6e
  delete[] border.sums2();
Shinya Kitaoka 120a6e
  delete[] border.sumsMix();
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
// Reduction caller and list copier.
Shinya Kitaoka 120a6e
inline void reduceBorders(BorderList &borders, Contours &result,
Shinya Kitaoka 120a6e
                          bool ambiguitiesCheck) {
Shinya Kitaoka 120a6e
  unsigned int i, j;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Initialize output container
Shinya Kitaoka 120a6e
  result.resize(borders.size());
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Copy results
Shinya Kitaoka 120a6e
  for (i = 0; i < borders.size(); ++i) {
Shinya Kitaoka 120a6e
    result[i].resize(borders[i].size());
Shinya Kitaoka 120a6e
    for (j = 0; j < borders[i].size(); ++j) {
Shinya Kitaoka 120a6e
      reduceBorder(*borders[i][j], result[i][j], ambiguitiesCheck);
Shinya Kitaoka 120a6e
      delete borders[i][j];
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
  }
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//===========================
Toshihiro Shimizu 890ddd
//    Polygonization Main
Toshihiro Shimizu 890ddd
//===========================
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
// Extracts a polygonal, minimal yet faithful representation of image contours
Shinya Kitaoka 120a6e
// Contours* polygonize(const TRasterP &ras){
Shinya Kitaoka 120a6e
void polygonize(const TRasterP &ras, Contours &polygons,
Shinya Kitaoka 120a6e
                VectorizerCoreGlobals &g) {
Shinya Kitaoka 120a6e
  BorderList *borders;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  borders = extractBorders(ras, g.currConfig->m_threshold,
Shinya Kitaoka 120a6e
                           g.currConfig->m_despeckling);
Shinya Kitaoka 120a6e
  reduceBorders(*borders, polygons, g.currConfig->m_maxThickness > 0.0);
Toshihiro Shimizu 890ddd
}