#include "toonz/tcenterlinevectorizer.h"

#include "tsystem.h"

#include "tstopwatch.h"

#include "tpalette.h"

//#include "timage_io.h"

//#include "tstrokeutil.h"

//#include "tspecialstyleid.h"

#include "trastercm.h"

#include "ttoonzimage.h"

//#include "dpiscale.h"

#include "tregion.h"

#include "tstroke.h"

#include "trasterimage.h"

#define SEARCH_WINDOW 3

#define JUNCTION_THICKNESS_RATIO 0.7

#define JOIN_LIMIT 0.8

#define THICKNESS_LIMIT 0.2

#define THICKNESS_LIMIT_2 0.04

#undef DEBUG

//---------------------------------------------------------

struct ControlPoint {

  TStroke *m_stroke;

  int m_index;

  ControlPoint(TStroke *stroke, int index) : m_stroke(stroke), m_index(index) {}

  TPointD getPoint() const { return m_stroke->getControlPoint(m_index); }

  void setPoint(const TPointD &p) {

    TThickPoint point = m_stroke->getControlPoint(m_index);

    point.x           = p.x;

    point.y           = p.y;

    m_stroke->setControlPoint(m_index, point);

  }

};

void renormalizeImage(TVectorImage *vi) {

  int i, j;

  int n = vi->getStrokeCount();

  std::vector<controlpoint> points;</controlpoint>

  points.reserve(n * 2);

  for (i = 0; i < n; i++) {

    TStroke *stroke = vi->getStroke(i);

    int m           = stroke->getControlPointCount();

    if (m > 0) {

      if (m == 1)

        points.push_back(ControlPoint(stroke, 0));

      else {

        points.push_back(ControlPoint(stroke, 0));

        points.push_back(ControlPoint(stroke, m - 1));

      }

    }

  }

  int count = points.size();

  for (i = 0; i < count; i++) {

    ControlPoint &pi = points[i];

    TPointD posi     = pi.getPoint();

    TPointD center   = posi;

    std::vector<int> neighbours;</int>

    neighbours.push_back(i);

    for (j = i + 1; j < count; j++) {

      TPointD posj = points[j].getPoint();

      double d     = tdistance(posj, posi);

      if (d < 0.01) {

        /*if(d>0)

{

int yy = 123;

}*/

        neighbours.push_back(j);

        center += posj;

      }

    }

    int m = neighbours.size();

    if (m == 1) continue;

    center = center * (1.0 / m);

    for (j = 0; j < m; j++) points[neighbours[j]].setPoint(center);

  }

}

//---------------------------------------------------------

class Node;

class DataPixel {

public:

  TPoint m_pos;

  int m_value;

  bool m_ink;

  // int m_index;

  Node *m_node;

  DataPixel() : m_value(0), m_ink(false), /*m_index(0), */ m_node(0) {}

};

//---------------------------------------------------------

#ifdef WIN32

template class DV_EXPORT_API TSmartPointerT<trastert<datapixel>>;</trastert<datapixel>

#endif

typedef TRasterPT<datapixel> DataRasterP;</datapixel>

//---------------------------------------------------------

class Junction;

class Node {

public:

  Node *m_other;

  DataPixel *m_pixel;

  Node *m_prev, *m_next;

  Junction *m_junction;

#ifdef DEBUG

  bool m_flag;

#endif

  bool m_visited;

  Node()

      : m_pixel(0)

      , m_prev(0)

      , m_next(0)

      , m_junction(0)

      ,

#ifdef DEBUG

      m_flag(false)

      ,

#endif

      m_visited(false) {

  }

};

//---------------------------------------------------------

class ProtoStroke;

class Junction {

public:

  TThickPoint m_center;

  std::deque<node *=""> m_nodes;</node>

  int m_junctionOrder;

  std::vector<protostroke *=""> m_protoStrokes;</protostroke>

  bool m_locked;

  Junction()

      : m_center()

      , m_nodes()

      , m_junctionOrder(0)

      , m_protoStrokes()

      , m_locked(false) {}

  bool isConvex();

};

//---------------------------------------------------------

class ProtoStroke {

public:

  TPointD m_startDirection, m_endDirection;

  Junction *m_startJunction, *m_endJunction;

  std::deque<tthickpoint> m_points;</tthickpoint>

  ProtoStroke()

      : m_points()

      , m_startDirection()

      , m_endDirection()

      , m_startJunction(0)

      , m_endJunction(0) {}

  ProtoStroke(std::deque<tthickpoint>::iterator it_b,</tthickpoint>

              std::deque<tthickpoint>::iterator it_e)</tthickpoint>

      : m_points(it_b, it_e)

      , m_startDirection()

      , m_endDirection()

      , m_startJunction(0)

      , m_endJunction(0) {}

};

class ProtoRegion {

public:

  TPointD m_center;

  bool m_isConvex;

  std::vector<tthickpoint> m_points;</tthickpoint>

  ProtoRegion(bool isConvex) : m_points(), m_isConvex(isConvex), m_center() {}

};

class JunctionMerge {

public:

  Junction *m_junction;

  Node *m_startNode, *m_endNode;

  bool m_isNext;

  JunctionMerge(Junction *junction)

      : m_junction(junction), m_startNode(0), m_endNode(0), m_isNext(true) {}

  JunctionMerge(Junction *junction, Node *startNode, Node *endNode, bool isNext)

      : m_junction(junction)

      , m_startNode(startNode)

      , m_endNode(endNode)

      , m_isNext(isNext) {}

  bool operator==(const JunctionMerge &op2) {

    return (m_junction == op2.m_junction);

  }

};

class JunctionLink {

public:

  Junction *m_first;

  Junction *m_second;

  int m_order;

  JunctionLink(Junction *first, Junction *second)

      : m_first(first), m_second(second), m_order(0) {}

  bool operator==(const JunctionLink &op2) const {

    return (m_first == op2.m_first && m_second == op2.m_second) ||

           (m_first == op2.m_second && m_second == op2.m_first);

  }

};

class CenterLineVectorizer {

  TPalette *m_palette;

public:

  //	int m_delta[8];

  //	int m_radius;

  TRasterP m_src;

  VectorizerConfiguration m_configuration;

#ifdef DEBUG

  TRaster32P m_output;

#endif

  DataRasterP m_dataRaster;

  vector<pair<int, datarasterp="">> m_dataRasterArray;</pair<int,>

  TVectorImageP m_vimage;

#ifdef DEBUG

  TVectorImageP m_rimage;

#endif

#ifdef DEBUG

  vector<vector<tthickpoint>> m_outlines;</vector<tthickpoint>

  vector<tpointd> m_unvisitedNodes;</tpointd>

  vector<vector<node *="">> m_junctionPolygons;</vector<node>

#endif

  vector<node *=""> m_nodes;</node>

  vector<junction *=""> m_junctions;</junction>

  vector<junctionlink> m_links;</junctionlink>

  list<protostroke> m_protoStrokes;</protostroke>

  list<protoregion> m_protoRegions;</protoregion>

  // list< std::vector<tthickpoint> > m_protoHoles;</tthickpoint>

  Node *findOtherSide(Node *node);

  bool testOtherSide(Node *na1, Node *nb1, double &startDist2);

  TPointD computeCenter(Node *na, Node *nb, double &r);

  bool isHole(Node *startNode);

  void traceLine(DataPixel *pix);  // , vector<tthickpoint> &points);</tthickpoint>

  TPoint computeGradient(DataPixel *pix) {

    assert(m_dataRaster);

    const int wrap = m_dataRaster->getWrap();

    TPoint g(0, 0);

    int n, s, w, e, nw, sw, ne, se;

    w  = pix[-1].m_value;

    nw = pix[-1 + wrap].m_value;

    sw = pix[-1 - wrap].m_value;

    e  = pix[+1].m_value;

    ne = pix[+1 + wrap].m_value;

    se = pix[+1 - wrap].m_value;

    n = pix[+wrap].m_value;

    s = pix[-wrap].m_value;

    g.y = -sw + ne - se + nw + 2 * (n - s);

    g.x = -sw + ne + se - nw + 2 * (e - w);

    return g;

  }

  CenterLineVectorizer(const VectorizerConfiguration &configuration,

                       TPalette *palette)

      : m_configuration(configuration), m_palette(palette) {}

  ~CenterLineVectorizer();

  void clearNodes();

  void createNodes();

  void clearJunctions();

  void makeOutputRaster();

  void makeDataRaster(const TRasterP &src);

  DataPixel *findUnvisitedInkPixel();

  bool linkNextProtoStroke(ProtoStroke *const dstProtoStroke,

                           Junction *const currJunction, const int k);

  void joinProtoStrokes(ProtoStroke *const dstProtoStroke);

  void resolveUnvisitedNode(Node *node);

  Junction *mergeJunctions(const std::list<junctionmerge> &junctions);</junctionmerge>

  void joinJunctions();

  void createJunctionPolygon(Junction *junction);

  void handleLinks();

  void handleJunctions();

  void createStrokes();

  void createRegions();

  void vectorize();

  void init();

  //	void click(const TPoint &p);

  Node *createNode(DataPixel *pix);

  void link(DataPixel *pix, DataPixel *from, DataPixel *to);

  /*#ifdef DEBUG

  inline TPixel32 &getOutPix(DataPixel*pix) {return

m_output->pixels()[pix->m_index]; }

  void outputNodes(Node *node);

  void outputInks();

#endif*/

private:

  // not implemented

  CenterLineVectorizer(const CenterLineVectorizer &);

  CenterLineVectorizer &operator=(const CenterLineVectorizer &);

};

//=========================================================

class CompareJunctionNodes {

  TPointD m_center;

public:

  CompareJunctionNodes(TPointD center) : m_center(center) {}

  bool operator()(const Node *n1, const Node *n2) {

    TPointD p1 = convert(n1->m_pixel->m_pos) - m_center;

    TPointD p2 = convert(n2->m_pixel->m_pos) - m_center;

    double alpha1, alpha2;

    if (p1.x > 0)

      alpha1 = -p1.y / sqrt(norm2(p1));

    else if (p1.x < 0)

      alpha1 = 2 + p1.y / sqrt(norm2(p1));

    else  //(p1.x = 0)

    {

      if (p1.y > 0)

        alpha1 = -1;

      else if (p1.y < 0)

        alpha1 = 1;

      else

        assert(true);

    }

    if (p2.x > 0)

      alpha2 = -p2.y / sqrt(norm2(p2));

    else if (p2.x < 0)

      alpha2 = 2 + p2.y / sqrt(norm2(p2));

    else  //(p2.x = 0)

    {

      if (p2.y > 0)

        alpha2 = -1;

      else if (p2.y < 0)

        alpha2 = 1;

      else

        assert(true);

    }

    if (alpha2 - alpha1 > 0)

      return true;

    else if (alpha2 - alpha1 < 0)

      return false;

    else

      return false;  // n1->m_pixel->m_pos == n2->m_pixel->m_pos!!

  }

};

//---------------------------------------------------------

//---------------------------------------------------------

inline bool collinear(const TPointD &a, const TPointD &b, const TPointD &c) {

  double area = (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);

  return area == 0;

}

//---------------------------------------------------------

inline bool right(const TPointD &a, const TPointD &b, const TPointD &c) {

  double area = (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);

  return area < 0;

}

//---------------------------------------------------------

enum RectIntersectionResult { parallel, coincident, intersected };

RectIntersectionResult rectsIntersect(const TPointD &a1, const TPointD &a2,

                                      const TPointD &b1, const TPointD &b2,

                                      TPointD &intersection) {

  double ma, mb, ca, cb;

  if (a2.x == a1.x && b2.x == b1.x) {

    if (collinear(a1, a2, b1) && collinear(a1, a2, b2))

      return coincident;

    else

      return parallel;

  } else if (a1.x == a2.x) {

    mb             = (b2.y - b1.y) / (b2.x - b1.x);

    cb             = b1.y - mb * b1.x;

    intersection.x = a1.x;

    intersection.y = mb * intersection.x + cb;

    return intersected;

  } else if (b1.x == b2.x) {

    ma             = (a2.y - a1.y) / (a2.x - a1.x);

    ca             = a1.y - ma * a1.x;

    intersection.x = b1.x;

    intersection.y = ma * intersection.x + ca;

    return intersected;

  } else {

    ma = (a2.y - a1.y) / (a2.x - a1.x);

    mb = (b2.y - b1.y) / (b2.x - b1.x);

    if (ma == mb) {

      if (collinear(a1, a2, b1) && collinear(a1, a2, b2))

        return coincident;

      else

        return parallel;

    }

    ca = a1.y - ma * a1.x;

    cb = b1.y - mb * b1.x;

    intersection.x = (ca - cb) / (mb - ma);

    intersection.y = ma * intersection.x + ca;

    return intersected;

  }

}

//---------------------------------------------------------

//---------------------------------------------------------

bool Junction::isConvex() {

  int nonConvexAngles = 0;

  assert(m_nodes.size() > 2);

  std::deque<node *="">::iterator it   = m_nodes.begin();</node>

  std::deque<node *="">::iterator it_e = m_nodes.end() - 2;</node>

  for (; it != it_e; ++it) {

    if (right(convert((*(it))->m_pixel->m_pos),

              convert((*(it + 1))->m_pixel->m_pos),

              convert((*(it + 2))->m_pixel->m_pos)))

      nonConvexAngles++;

    if (nonConvexAngles > 1) return false;

  }

  if (right(convert((*(it))->m_pixel->m_pos),

            convert((*(it + 1))->m_pixel->m_pos),

            convert((*(m_nodes.begin()))->m_pixel->m_pos)))

    nonConvexAngles++;

  if (nonConvexAngles > 1) return false;

  return true;

}

//---------------------------------------------------------

//---------------------------------------------------------

CenterLineVectorizer::~CenterLineVectorizer() {

  clearNodes();

  clearJunctions();

#ifdef DEBUG

  m_outlines.clear();

  m_unvisitedNodes.clear();

  m_junctionPolygons.clear();

#endif

  m_links.clear();

  m_protoStrokes.clear();

  m_protoRegions.clear();

  // m_protoHoles.clear();

}

//---------------------------------------------------------

void CenterLineVectorizer::clearNodes() {

  for (int i = 0; i < (int)m_nodes.size(); i++) delete m_nodes[i];

  m_nodes.clear();

}

//---------------------------------------------------------

void CenterLineVectorizer::clearJunctions() {

  for (int i = 0; i < (int)m_junctions.size(); i++) delete m_junctions[i];

  m_junctions.clear();

}

//---------------------------------------------------------

void CenterLineVectorizer::link(DataPixel *pix, DataPixel *srcPix,

                                DataPixel *dstPix) {

  Node *srcNode = 0, *dstNode = 0, *node = 0;

  Node *tmp;

  for (tmp = pix->m_node; tmp; tmp = tmp->m_other) {

    if (tmp->m_pixel == 0) continue;

    if (tmp->m_prev && tmp->m_prev->m_pixel == srcPix) {

      assert(srcNode == 0);

      if (node) {

        assert(node->m_next->m_pixel == dstPix);

        assert(node->m_prev == 0);

        node->m_prev        = tmp->m_prev;

        tmp->m_prev->m_next = node;

        tmp->m_next = tmp->m_prev = 0;

        tmp->m_pixel              = 0;

        return;

      }

      assert(tmp->m_next == 0);

      srcNode = tmp->m_prev;

      node    = tmp;

    }

    if (tmp->m_next && tmp->m_next->m_pixel == dstPix) {

      assert(dstNode == 0);

      if (node) {

        assert(node->m_prev->m_pixel == srcPix);

        assert(node->m_next == 0);

        node->m_next        = tmp->m_next;

        tmp->m_next->m_prev = node;

        tmp->m_next = tmp->m_prev = 0;

        tmp->m_pixel              = 0;

        return;

      }

      assert(tmp->m_prev == 0);

      dstNode = tmp->m_next;

      node    = tmp;

    }

  }

  if (!node) node       = createNode(pix);

  if (!srcNode) srcNode = createNode(srcPix);

  if (!dstNode) dstNode = createNode(dstPix);

  if (!node->m_next) {

    node->m_next = dstNode;

    assert(dstNode->m_prev == 0);

    dstNode->m_prev = node;

  }

  if (!node->m_prev) {

    node->m_prev = srcNode;

    assert(srcNode->m_next == 0);

    srcNode->m_next = node;

  }

  assert(node->m_next == dstNode);

  assert(node->m_prev == srcNode);

  assert(dstNode->m_prev == node);

  assert(srcNode->m_next == node);

}

//---------------------------------------------------------

inline int colorDistance2(const TPixel32 &c0, const TPixel32 &c1) {

  return ((c0.r - c1.r) * (c0.r - c1.r) + (c0.g - c1.g) * (c0.g - c1.g) +

          (c0.b - c1.b) * (c0.b - c1.b));

}

//---------------------------------------------------------

#define MAX_TOLERANCE 20

#include "tcolorstyles.h"

void CenterLineVectorizer::makeDataRaster(const TRasterP &src) {

  m_vimage = new TVectorImage();

  if (!src) return;

  m_src = src;

  clearNodes();

  clearJunctions();

  int ii, x, y = 0;

  TRaster32P srcRGBM = (TRaster32P)m_src;

  TRasterCM32P srcCM = (TRasterCM32P)m_src;

  TRasterGR8P srcGR  = (TRasterGR8P)m_src;

  DataRasterP dataRaster(m_src->getSize().lx + 2, m_src->getSize().ly + 2);

  int ly              = dataRaster->getLy();

  int lx              = dataRaster->getLx();

  int wrap            = dataRaster->getWrap();

  DataPixel *dataPix0 = dataRaster->pixels(0);

  DataPixel *dataPix1 = dataRaster->pixels(0) + m_src->getLx() + 1;

  for (y = 0; y < ly; y++, dataPix0 += wrap, dataPix1 += wrap) {

    dataPix0->m_pos.x = 0;

    dataPix1->m_pos.x = lx - 1;

    dataPix0->m_pos.y = dataPix1->m_pos.y = y;

    dataPix0->m_value = dataPix1->m_value = 0;

    dataPix0->m_ink = dataPix1->m_ink = false;

    dataPix0->m_node = dataPix1->m_node = 0;

  }

  dataPix0 = dataRaster->pixels(0);

  dataPix1 = dataRaster->pixels(ly - 1);

  for (x = 0; x < lx; x++, dataPix0++, dataPix1++) {

    dataPix0->m_pos.x = dataPix1->m_pos.x = x;

    dataPix0->m_pos.y                     = 0;

    dataPix1->m_pos.y                     = ly - 1;

    dataPix0->m_value = dataPix1->m_value = 0;

    dataPix0->m_ink = dataPix1->m_ink = false;

    dataPix0->m_node = dataPix1->m_node = 0;

  }

  if (srcRGBM) {

    assert(m_palette);

    int inkId = m_palette->addStyle(m_configuration.m_inkColor);

    m_dataRasterArray.push_back(pair<int, datarasterp="">(inkId, dataRaster));</int,>

    int maxDistance2 =

        m_configuration.m_threshold * m_configuration.m_threshold;

    for (y = 0; y < m_src->getLy(); y++) {

      TPixel32 *inPix    = srcRGBM->pixels(y);

      TPixel32 *inEndPix = inPix + srcRGBM->getLx();

      DataPixel *dataPix = dataRaster->pixels(y + 1) + 1;

      x                  = 0;

      while (inPix < inEndPix) {

        *dataPix      = DataPixel();

        int distance2 = colorDistance2(m_configuration.m_inkColor, *inPix);

        // int value = (inPix->r + 2*inPix->g + inPix->b)>>2;

        if (y == 0 || y == m_src->getLy() - 1 || x == 0 ||

            x == m_src->getLx() - 1) {

          dataPix->m_value = 255;

          dataPix->m_ink   = false;

        } else {

          dataPix->m_value = (inPix->r + 2 * inPix->g + inPix->b) >> 2;

          dataPix->m_ink   = (distance2 < maxDistance2);

        }

        dataPix->m_pos.x = x++;

        dataPix->m_pos.y = y;

        dataPix->m_node  = 0;

        // dataPix->m_index = index++;

        inPix++;

        dataPix++;

      }

    }

  } else if (srcGR) {

    assert(m_palette);

    int inkId = m_palette->addStyle(m_configuration.m_inkColor);

    m_dataRasterArray.push_back(pair<int, datarasterp="">(inkId, dataRaster));</int,>

    int threshold = m_configuration.m_threshold;

    for (y = 0; y < m_src->getLy(); y++) {

      TPixelGR8 *inPix    = srcGR->pixels(y);

      TPixelGR8 *inEndPix = inPix + srcGR->getLx();

      DataPixel *dataPix  = dataRaster->pixels(y + 1) + 1;

      x                   = 0;

      while (inPix < inEndPix) {

        *dataPix = DataPixel();

        // int distance2 = colorDistance2(m_configuration.m_inkColor, *inPix);

        // int value = (inPix->r + 2*inPix->g + inPix->b)>>2;

        if (y == 0 || y == m_src->getLy() - 1 || x == 0 ||

            x == m_src->getLx() - 1) {

          dataPix->m_value = 255;

          dataPix->m_ink   = false;

        } else {

          dataPix->m_value = inPix->value;

          dataPix->m_ink   = (inPix->value < threshold);

        }

        dataPix->m_pos.x = x++;

        dataPix->m_pos.y = y;

        dataPix->m_node  = 0;

        // dataPix->m_index = index++;

        inPix++;

        dataPix++;

      }

    }

  }

  else if (srcCM) {

    int currInk, nextInk = 0;

    do {

      int threshold =

          m_configuration.m_threshold;  // tolerance: 1->MAX thresh: 1-255

      currInk = nextInk;

      nextInk = 0;

      m_dataRasterArray.push_back(pair<int, datarasterp="">(currInk, dataRaster));</int,>

      // inizializza la parte centrale

      for (y = 0; y < srcCM->getLy(); y++) {

        TPixelCM32 *inPix    = srcCM->pixels(y);

        TPixelCM32 *inEndPix = inPix + m_src->getLx();

        DataPixel *dataPix   = dataRaster->pixels(y + 1) + 1;

        x                    = 0;

        while (inPix < inEndPix) {

          *dataPix  = DataPixel();

          int value = inPix->getTone();

          if (value < 255 && !m_configuration.m_ignoreInkColors) {

            int ink = inPix->getInk();

            if (currInk == 0) {

              currInk                        = ink;

              m_dataRasterArray.back().first = ink;

            } else if (ink != currInk) {

              value = 255;

              if (nextInk == 0) {

                for (ii = 0; ii < (int)m_dataRasterArray.size() - 1; ii++)

                  if (m_dataRasterArray[ii].first == ink) break;

                if (ii == (int)m_dataRasterArray.size() - 1) nextInk = ink;

              }

            }

          }

          // TPixel col = m_palette->getStyle(inPix->getInk())->getMainColor();

          dataPix->m_pos.x = x++;

          dataPix->m_pos.y = y;

          dataPix->m_value = value;

          dataPix->m_ink   = (value < threshold);

          dataPix->m_node  = 0;

          // dataPix->m_index = index++;

          inPix++;

          dataPix++;

        }

      }

    } while (nextInk != 0);

    if (m_configuration.m_ignoreInkColors) {

      assert(m_dataRasterArray.size() == 1);

      m_dataRasterArray.back().first = 1;

    }

  } else

    assert(false);

}

void CenterLineVectorizer::init() {

  int y;

  /*m_links.clear();

  m_protoStrokes.clear();

  m_protoRegions.clear();

  clearNodes();

  clearJunctions();*/

  DataRasterP dataRaster = m_dataRaster;

  const int wrap         = dataRaster->getWrap();

  const int delta[]      = {-wrap - 1, -wrap, -wrap + 1, 1,

                       wrap + 1,  wrap,  wrap - 1,  -1};

  for (y = 1; y < dataRaster->getLy() - 1; y++) {

    DataPixel *pix    = dataRaster->pixels(y);

    DataPixel *endPix = pix + dataRaster->getLx() - 1;

    pix++;

    for (pix++; pix < endPix; ++pix) {

      if ((pix->m_ink == false) || (pix[-wrap].m_ink && pix[wrap].m_ink &&

                                    pix[-1].m_ink && pix[1].m_ink))

        continue;

      int i;

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

        if (pix[delta[i]].m_ink && pix[delta[(i + 1) & 0x7]].m_ink == false)

          break;

      int start = i;

      if (i == 8) continue;  // punto isolato

      for (;;) {

        int j = (i + 1) & 0x7;

        assert(i < 8 && pix[delta[i]].m_ink);

        assert(j < 8 && pix[delta[j]].m_ink == false);

        do

          j = (j + 1) & 0x7;

        while (pix[delta[j]].m_ink == false);

        assert(j < 8 && pix[delta[j]].m_ink);

        if (((i + 2) & 0x7) != j || (i & 1) == 0) {

          // il bianco comprende anche un fianco

          link(pix, pix + delta[i], pix + delta[j]);

        }

        i = j;

        assert(i < 8);

        while (pix[delta[(i + 1) & 0x7]].m_ink) i = (i + 1) & 0x7;

        assert(i < 8 && pix[delta[i]].m_ink);

        assert(pix[delta[(i + 1) & 0x7]].m_ink == false);

        if (i == start) break;

      }

    }

  }

}

/*

#ifdef DEBUG

    int i;

    for(i = 0;i<(int)m_nodes.size();i++)

        {

                Node *node = m_nodes[i];

                if(node->m_pixel==0) continue;

                assert(node->m_prev);

                assert(node->m_next);

                assert(node->m_prev->m_next == node);

                assert(node->m_next->m_prev == node);

        }

    for(i = 0;i<m_dataraster->getLx()*m_dataRaster->getLy(); i++)</m_dataraster->

        {

                DataPixel *pix = m_dataRaster->pixels()+i;

                for(Node *node = pix->m_node; node; node=node->m_other)

                {

                        if(node->m_pixel==0) continue;

                        assert(node->m_pixel == pix);

                        assert(node->m_prev);

                        assert(node->m_next);

                        assert(node->m_prev->m_next == node);

                        assert(node->m_next->m_prev == node);

                }

        }

#endif

*/

//---------------------------------------------------------

TPointD CenterLineVectorizer::computeCenter(Node *na, Node *nb, double &r) {

  TPointD pa = convert(na->m_pixel->m_pos);

  TPointD pb = convert(nb->m_pixel->m_pos);

  r          = THICKNESS_LIMIT;

  if (pa == pb) return pa;

  TPointD center((pa + pb) * 0.5);

  r = norm(pa - pb) * 0.5;

  return center;

  /*	double vsum = 0.0;

  TPointD d = pa-pb;

  if(fabs(d.x)>fabs(d.y))

{

          if(pa.x>pb.x) std::swap(pa,pb);

          for(int x = pa.x; x<=pb.x; x++)

          {

                  int y = pa.y + (pb.y-pa.y)*(x-pa.x)/(pb.x-pa.x);

                  int v = 255-m_dataRaster->pixels(y)[x].m_value;

                  center += v * TPointD(x,y);

                  vsum += v;

  }

}

  else

{

          if(pa.y>pb.y) std::swap(pa,pb);

          for(int y = pa.y; y<=pb.y; y++)

          {

                  int x = pa.x + (pb.x-pa.x)*(y-pa.y)/(pb.y-pa.y);

                  int v = 255-m_dataRaster->pixels(y)[x].m_value;

                  center += v * TPointD(x,y);

                  vsum += v;

          }

}

  assert(vsum>0);

  r = 0.5*vsum/255.0;

  return center * (1/vsum);

*/

}

//---------------------------------------------------------

double computeDistance2(Node *na, Node *nb) {

  assert(na->m_pixel);

  assert(nb->m_pixel);

  TPointD d = convert(na->m_pixel->m_pos - nb->m_pixel->m_pos);

  return d * d;

}

//---------------------------------------------------------

Node *CenterLineVectorizer::findOtherSide(Node *node) {

  DataPixel *pix = node->m_pixel;

  TPoint dir = -computeGradient(pix);

  if (dir == TPoint(0, 0)) return 0;

  TPoint d1(tsign(dir.x), 0), d2(0, tsign(dir.y));

  int num = abs(dir.y), den = abs(dir.x);

  if (num > den) {

    std::swap(d1, d2);

    std::swap(num, den);

  }

  TPoint pos = pix->m_pos;

  int i;

  for (i = 0;; i++) {

    TPoint q(pos.x + d1.x * i + d2.x * num * i / den,

             pos.y + d1.y * i + d2.y * num * i / den);

    // if (!m_dataRaster->getBounds().contains(q)) break;

    DataPixel *nextPix = m_dataRaster->pixels(q.y) + q.x;

    if (nextPix->m_ink == false) break;

    pix = nextPix;

  }